Google Code Jam - Train Timetable

from Google Code Jam - july 2008....

Problem

A train line has two stations on it, A and B. Trains can take trips from A to B or from B to A multiple times during a day. When a train arrives at B from A (or arrives at A from B), it needs a certain amount of time before it is ready to take the return journey - this is the turnaround time. For example, if a train arrives at 12:00 and the turnaround time is 0 minutes, it can leave immediately, at 12:00.

A train timetable specifies departure and arrival time of all trips between A and B. The train company needs to know how many trains have to start the day at A and B in order to make the timetable work: whenever a train is supposed to leave A or B, there must actually be one there ready to go. There are passing sections on the track, so trains don't necessarily arrive in the same order that they leave. Trains may not travel on trips that do not appear on the schedule.

Input

The first line of input gives the number of cases, N. N test cases follow.

Each case contains a number of lines. The first line is the turnaround time, T, in minutes. The next line has two numbers on it, NA and NB. NA is the number of trips from A to B, and NB is the number of trips from B to A. Then there are NA lines giving the details of the trips from A to B.

Each line contains two fields, giving the HH:MM departure and arrival time for that trip. The departure time for each trip will be earlier than the arrival time. All arrivals and departures occur on the same day. The trips may appear in any order - they are not necessarily sorted by time. The hour and minute values are both two digits, zero-padded, and are on a 24-hour clock (00:00 through 23:59).

After these NA lines, there are NB lines giving the departure and arrival times for the trips from B to A.

Output

For each test case, output one line containing "Case #x: " followed by the number of trains that must start at A and the number of trains that must start at B.

Limits

1 ≤ N ≤ 100

Small dataset

0 ≤ NA, NB ≤ 20

0 ≤ T ≤ 5

Large dataset

0 ≤ NA, NB ≤ 100

0 ≤ T ≤ 60

Sample

Input	Output
2 5 3 2 09:00 12:00 10:00 13:00 11:00 12:30 12:02 15:00 09:00 10:30 2 2 0 09:00 09:01 12:00 12:02	Case #1: 2 2 Case #2: 2 0

SOLUTION

/**
sample file

2
5
3 2
09:00 12:00
10:00 13:00
11:00 12:30
12:02 15:00
09:00 10:30
2
2 0
09:00 09:01
12:00 12:02

*/
package codejam;

import java.io.File;
import java.io.FileInputStream;
import java.util.PriorityQueue;

/**
* @author Ricardo A. Harari - ricardo.harari@gmail.com
*
*/
public class TrainTimable {

PriorityQueue schedules = new PriorityQueue();

int turnaround = -1; // minutes

int n = 0;

private static final String FILE_NAME = "/tmp/sample.txt";

/**
* pass the full location of the sample file as argument
* if you dont pass anything it will search at /tmp/sample.txt
*
* @param args
*/
public static void main(String[] args) {
String fname = args.length == 0 ? FILE_NAME : args[0];
try {
TrainTimable o = new TrainTimable();
o.start(fname);
} catch (Exception e) {
System.out.println("Oppps.");
System.out.println("An exception has been throw:" + e.getMessage());
e.printStackTrace();
}
}

private void start(String fileName) throws Exception {
File f = new File(fileName); // sample file

int na = 0;
int nb = 0;

if (!f.exists() || !f.isFile()) throw new Exception("Sorry, " + fileName + " is not a valid file.");
FileInputStream fi = new FileInputStream(f);
int cint;
String tmp = new String();
int caseNum = 0;
int step = 0;
while ((cint = fi.read()) > -1) {
char c = (char) cint;
if (c == '\r' || c == '\n') {
tmp = tmp.trim();
if (tmp.length() > 0) {
if (step == 0) {
try {
n = Integer.parseInt(tmp);
step++;
} catch (NumberFormatException nfe) {
// do nothing. the 1st line should not be in correct format
}
} else if (step == 1) {
turnaround = Integer.parseInt(tmp);
caseNum++;
na = 0;
nb = 0;
schedules.clear();
step++;
} else if (step == 2) {
int pos = tmp.lastIndexOf(' ');
if (pos > -1) {
na = Integer.parseInt(tmp.substring(0, pos).trim());
nb = Integer.parseInt(tmp.substring(pos).trim());
}
step++;
} else if (na > 0) {
addToSchedule(tmp, true);
na--;
} else if (nb > 0) {
addToSchedule(tmp, false);
nb--;
}
if (step == 3 && na == 0 && nb == 0) {
process(caseNum);
turnaround = 0;
step = 1;
}
tmp = "";
}
} else {
tmp += c;
}
}
if (step == 3) {
process(caseNum);
}
fi.close();
}

/**
* @param caseNum
*/
private void process(int caseNum) {
int trainA = 0;
int trainB = 0;
int availableTrainA = 0;
int availableTrainB = 0;

while (schedules.size() > 0) {
Schedule sched = schedules.poll();
if (!sched.arrive) {
boolean isFromA = sched.source.equals("A");
if (isFromA) {
if (availableTrainA > 0) {
availableTrainA--;
} else {
trainA++;
}
} else {
if (availableTrainB > 0) {
availableTrainB--;
} else {
trainB++;
}
}
} else {
boolean isToB = sched.source.equals("B");
if (isToB) {
availableTrainB++;
} else {
availableTrainA++;
}
}
}
print(caseNum, trainA, trainB);
}

private long hourToLong(String time) {
int hour = Integer.parseInt(time.substring(0, 2));
int minute = Integer.parseInt(time.substring(3));
return hour*60 + minute;
}

/**
* @param tmp
* @param b
*/
private void addToSchedule(String tmp, boolean fromA) {
int pos = tmp.lastIndexOf(' ');
if (pos > -1) {
long start = hourToLong(tmp.substring(0, pos).trim());
long end = hourToLong(tmp.substring(pos).trim()) + turnaround;
schedules.add(new Schedule(start * 100000 + end, fromA ? "A" : "B", false));
schedules.add(new Schedule(end * 100000, fromA ? "B" : "A", true));
}
}

/**
* @param caso
* @param i
*/
private void print(int caso, int na, int nb) {
System.out.println("Case #" + caso + ": " + na + " " + nb);
}

/**
*
* @author Ricardo Alberto Harari - ricardo.harari@gmail.com
*
*/
class Schedule implements Comparable {

public Schedule(long _nextSchedule, String _source, boolean _arrive) {
nextSchedule = _nextSchedule;
source = _source;
arrive = _arrive;
}
long nextSchedule;
String source;
boolean arrive = false;

/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(Schedule o) {
if (nextSchedule - o.nextSchedule < 0) return -1;
if (nextSchedule - o.nextSchedule > 0) return 1;
return 0;
}
}

}

Google Code Jam - Saving the Universe

from Google Code Jam - july/2008....
http://code.google.com/codejam

Problem

The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don't try it, or tell anyone. All right, maybe not. We are just kidding.

The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!

To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.

Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.

Input

The first line of the input file contains the number of cases, N. N test cases follow.

Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.

The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.

Output

For each input case, you should output:

Case #X: Y

where X is the number of the test case and Y is the number of search engine switches. Do not count the initial choice of a search engine as a switch.

Limits

0 < N ≤ 20

Small dataset

2 ≤ S ≤ 10

0 ≤ Q ≤ 100

Large dataset

2 ≤ S ≤ 100

0 ≤ Q ≤ 1000

Sample

Input	Output
2 5 Yeehaw NSM Dont Ask B9 Googol 10 Yeehaw Yeehaw Googol B9 Googol NSM B9 NSM Dont Ask Googol 5 Yeehaw NSM Dont Ask B9 Googol 7 Googol Dont Ask NSM NSM Yeehaw Yeehaw Googol	Case #1: 1 Case #2: 0

In the first case, one possible solution is to start by using Dont Ask, and switch to NSM after query number 8.
For the second case, you can use B9, and not need to make any switches.

SOLUTION

/**
*
*/
package codejam;

import java.io.File;
import java.io.FileInputStream;
import java.util.ArrayList;

/**
* @author Ricardo Alberto Harari - ricardo.harari@gmail.com
*
*/
public class SavingUniverse {

private static final String FILE_NAME = "/tmp/sample.txt";


/**
* pass the full location of the sample file as argument
* if you dont pass anything it will search at /tmp/sample.txt
*
* @param args
*/
public static void main(String[] args) {
String fname = args.length == 0 ? FILE_NAME : args[0];
try {
SavingUniverse o = new SavingUniverse();
o.start(fname);
} catch (Exception e) {
System.out.println("Oppps.");
System.out.println("An exception has been throw:" + e.getMessage());
e.printStackTrace();
}
}

private int n = 0; // # of cases
ArrayList listEngines = null; // search engines nodes
ArrayList listQueries = null;

private void start(String fileName) throws Exception {
File f = new File(fileName); // sample file
int s = 0; // # of search engines
int q = 0; // # of queries

if (!f.exists() || !f.isFile()) throw new Exception("Sorry, " + fileName + " is not a valid file.");
FileInputStream fi = new FileInputStream(f);
int cint;
String tmp = new String();
int caseNum = 0;
while ((cint = fi.read()) > -1) {
char c = (char) cint;
if (c == '\r' || c == '\n') {
if (tmp.length() > 0) {
if (n == 0) {
try {
n = Integer.parseInt(tmp);
} catch (NumberFormatException nfe) {
// do nothing. the 1st line should not be in correct format
}
} else if (q >0) {
addQuery(tmp);
q--;
if (q == 0) {
process(caseNum);
s = 0;
}
} else if (s == 0) {
s = Integer.parseInt(tmp);
if (listEngines == null){
listEngines = new ArrayList();
listQueries = new ArrayList();
} else {
listEngines.clear();
listQueries.clear();
}
caseNum++;
} else if (s > 0) {
listEngines.add(new SEngineNode(tmp));
s--;
if (s == 0) s = -1;
} else if (s == -1) {
q = Integer.parseInt(tmp);
if (q == 0) { // no queries huh?
print(caseNum, 0);
s = 0;
}
}
tmp = "";
}
} else if (c != ' ') {
tmp += c;
}
}
if (n != 0 && q > 0) {
addQuery(tmp.toString());
q--;
if (q == 0) {
process(caseNum);
}
}
}

/**
*
*/
private void process(int caso) {
// check if the 1st node has value of 0
int counter = 0;
for (int i = 0; i <>
QueryNode qrynode = listQueries.get(i);
SEngineNode engine = qrynode.node;
ArrayList farNodeList = cloneEngines(engine);
int j = i + 1;
for (j = i; j <>
QueryNode qrynodenxt = listQueries.get(j);
removeEngine(farNodeList, qrynodenxt);
if (farNodeList.size() == 0) break;
}
if (farNodeList.size() == 0) {
counter++;
i = j - 1;
} else {
break;
}
}
print(caso, counter);
}

/**
* @param farNodeList
* @param qrynodenxt
*/
private void removeEngine(ArrayList farNodeList, QueryNode qrynodenxt) {
String s = qrynodenxt.query;
for (SEngineNode n : farNodeList) {
if (s.indexOf(n.engineName) > -1) {
farNodeList.remove(n);
break;
}
}
}

/**
* @return
*/
private ArrayList cloneEngines(SEngineNode exceptNode) {
ArrayList ret = new ArrayList();
for (SEngineNode node : listEngines) {
if (!node.engineName.equals(exceptNode.engineName)) ret.add(node);
}
return ret;
}

/**
* @param caso
* @param i
*/
private void print(int caso, int i) {
System.out.println("Case #" + caso + ": " + i);
}

/**
* @param string
*/
private void addQuery(String s) {
s = s.toUpperCase();
for (SEngineNode node : listEngines) {
if (s.indexOf(node.engineName) > -1) {
node.qtd++;
listQueries.add(new QueryNode(s, node));
break;
}
}
}

class QueryNode {
public QueryNode(String _query, SEngineNode _engine) {
query = _query;
node = _engine;
}
String query;
SEngineNode node;
}

class SEngineNode {
public SEngineNode(String _engineName) {
engineName = _engineName.toUpperCase().trim();
}
int qtd; // qtd that match this search engine
String engineName;
}

}