A python exercise to find the best route in a field of jetstreams: First line contains only 1 integer, which is the constant energy it takes to fly 1 mile WITHOUT jet streams. Every subsequent line contains 3 space-separated integers: the start mile marker of the jet stream, the end mile marker of the jet stream, and lastly an integer denoting t…

jetstreams.py

import sys
import os

# make sure we were called with the proper args
if len(sys.argv) < 2 :
    print "Error: please call this script with a filename, e.g."
    print "jetstreams.py <somefilename.txt>"
    exit(1)

# make sure the file name called with exists
filename = sys.argv[1]
if os.path.exists(filename) == False :
    print "Error: filename " + filename + " does not exist."
    sys.exit(1)

# turn lines into lists of integers
def splitSpaces (line):
    return map(int, line.rstrip("\n").split(' '))

# get streams from text file
lines = [splitSpaces(line) for line in open(filename)]

# the first line is the cost per mile
cpm = lines.pop(0)[0]

# all the other lines contain lists of [start, end, cost]
lines.sort(key=lambda l: l[0])

# the end of the course is the highest number in the stream ends
end = max(lines, key=lambda l:l[1])[1]

# store the fastest route for checking inside the loop
bestRoute = {}

# recursive function to follow all possible streams
def getRoutes (streams, currentInfo = { 'cost' : 0, 'pos' : 0 }, currentStreams = []) :
    # define a method to recurse with to prevent scope leak
    def addStream (i,stream,streams,currentInfo, currentStreams) :
        # create streams object
        newStreams = currentStreams[:]
        # add this stream's tuple to our list of streams taken
        newStreams.append((stream[0],stream[1]))
        # recurse
        getRoutes(streams[i+1:], {
            # add the cost of getting to this stream from the last one, plus the cost of the stream
            'cost' : currentInfo['cost'] + ( ( stream[0] - currentInfo['pos'] ) * 50 ) + stream[2],
            # set our position to the end of this stream
            'pos' : stream[1]
        }, newStreams)
    # loop through possible next streams
    for i, stream in enumerate(streams) :
        if stream[0] >= currentInfo['pos'] :
            # this stream is beyond our current position
            addStream(i,stream,streams,currentInfo, currentStreams)
        else :
            # this jetstream is behind us. Add as a possible way to complete the course.
            # use the global bestRoute
            global bestRoute
            # calculate the cost when completed
            cost = currentInfo['cost'] + (end - currentInfo['pos']) * 50
            if bestRoute.get('cost') == None or cost < bestRoute['cost'] :
                bestRoute = {
                    'cost' : cost,
                    # set the streams to show how we got here
                    'streams' : currentStreams
                }

# start recursion
getRoutes(lines)

# show best route
print "Found the best route."
print "Cost : " + str(bestRoute['cost'])
print "Jetstreams : " + str(bestRoute['streams'])