GCJ 2008: Train Timetable

July 19th, 2008 § 0 comments

This one was the title of the second problem of Google Code Jam Qualification Round 2008.

This time my code is a bit messy, but I won’t adjust it for you :^D It’s the disadvantage of coding fast, at least for me. I often wrote something not necessary, someone call it gold planting, it’s just what I did in the maze problem with the draw method…

You can download my solution for the Train Timetable problem I wrote.

Here is the commend code.

1
2
from __future__ import with_statement
from copy import copy

Don’t ask me why I imported copy, I think I did it while testing… maybe. I don’t remember it’s not useful
The first 3 are classes but I did not spent so much time projecting their structure. Tempo just means time in italian, I didn’t want to override the python name (I know that’s the name of a lib, it’s only an excuse, I’m italian, let me name things in italian sometime :^P)

tempo is not so useful in that form… anyway converts the format ‘hh:mm’ to an int representing minutes

4
5
6
7
8
class tempo(object):
    def __init__(self, s):
        a = s.split(':')
        x = [int(i) for i in a]
        self.m = x[0]*60 + x[1]

Trip represents a trip, with starting and ending time.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Trip(object):
    def __init__(self,start,end):
        self.start = tempo(start)
        self.end = tempo(end)
        self.duration = self.end.m - self.start.m
        self.busy = False
    def __cmp__(self,x):
        return cmp(self.start.m,x.start.m)
    def use(self):
        self.busy = True
    def isfree(self):
        return self.busy == False
 
    is_free = property(isfree)

There is no need to put the duration attribute, but it did, thinking on it now it’s pretty useless… The interesting part is the flag busy, or is_free (just a joke with python property function…). A Trip is free if you did not use it yet. I added __cmp__ method because I’ll need to “sort” them, if trip X starts earlier than trip Y well…

X<y == True

It will be useful to understand what’s the first Trip to use…

A Train is identified by the time of the last thing it did (self.Time) and it has done something or not (self.init)

28
29
30
31
32
33
34
35
36
37
38
39
40
class Train(object):
    def __init__(self,Time):
        self.Time = tempo(Time)
        self.init = False
    def TripTrough(self, trip, turnaround):
        'Returns True if the train can trip (and it does)'
        if (trip.is_free and self.Time.m+turnaround <= trip.start.m) or self.init ==False:
            self.init = True
            self.Time = trip.end
            trip.use()
            return True
        else:
            return False

The TripTrough method is very important (yes I know, it’s Through not Trough… my english sucks, sorry for that :^D )… Anyway… How does it work? It’s simple. It wants a trip and the turnaround time. the flag init it’s useful because if the trip starts at 0:03 and you have a turnaround of 5 you have to don’t care about the turnaround, you have no need to turn around… my check can’t work without an init flag… I don’t know if it’s clear..

Now something magical happens, I’m doing it bad I think, I’m playing with the “all name are references” of python… I changed the trip flag as the train used it, I could do it out of that method but maybe I was tired, bored, drunk, whatever… and I did it in this way :^D. I updated the time of the train too, obviously.

Table has the algorithm! Let me explain…

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Table(object):
    def __init__(self,A,B,T): # trip lists... and turnaround
        self.A = A
        self.B = B
        self.T = T # turnaraund
    def solver(self, starting,ending,train):
        starting.sort()
        s = starting
        for i in s:
            if train.TripTrough(i,self.T):
                return self.solver(ending,starting,train)
        # else...
        return train
 
 
    def solve(self):
        tfa = []
        tfb = []
 
        check = True
        while check:
            freeA = [i for i in self.A if i.is_free]
            freeB = [i for i in self.B if i.is_free]
            #print freeA, freeB
            if len(freeB) > 0 and len(freeA)>0:
                mins = min(freeA),min(freeB)
            elif len(freeB) == len(freeA) == 0:
                break
            if len(freeA)>0 and (len(freeB) == 0 or mins[0]<mins[1]): #start from A
                tfa.append(self.solver(freeA,freeB,Train('00:00')))
            else:
                tfb.append(self.solver(freeB,freeA,Train('00:00')))
        return len(tfa),len(tfb)
  • A is the list of trips starting from station A going to B
  • B is the list of trips starting from station B going to A
  • T is the turnaround time of the case
  • solver it’s a recursive method.
    It takes 3 parameters:

    1. starting it’s the list of the trips starting from a station
    2. ending it’s the list of the trips starting from the other station
    3. train is the train that’s traveling forward and backward

    Well… I sort the trip list, in this way come first the one that will start first, then I begin to look for the first one that the train can travel through. If it can I can look (recursively part) for a return trip, just inverting starting with ending calling once again the solver method.

  • solve is the method you need to call to get the final result.
    • tfa is the list of trains starting from the A station
    • tfb is the list of trains starting from the B one
    • The part
      65
      66
      
              check = True
              while check:

      it’s just useless… I could use while True… I won’t change check

    • freeA is the list of the trip starting in A that are not busy
    • freeB it’s the same as the above one but in B, obviously
    • if there is something in freeA and freeB I’d like to know what’s the trip starting earlier in freeA and the one in freeB
    • else if there is nothing in freeA and nothing in freeB there is no need to continue
    • if there is something in freeA and there is nothing in freeB or just the earliest trip in freeA starts before the earliest one in freeB I can set up a new train and make it travel starting from the earliest trip in freeA until it stops…
    • else I can set up a new train and make it travel starting from the earliest trip in freeB until it stops…
    • I added these trains to tfa and tfb
    • I return the number of items of tfa and tfb, as the problem asks..

You can download the solution here with the file processing too.

The algorithm it’s correct but the implementation sucks, I think I can code a better one with less line of code, I’ve just to spend some time on it… It was a time challenge and I was not thinking so much of optimization… I don’t know If I’ll post a revisited one… For now it’s all folks!

return ‘Bye’

Tagged , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>