Functional solution for short path algorithm in Python

Question

I am reading Learn You Some Erlang for Great Good! and found out interesting puzzle. I decided to implement it in Python in a most functional way.

Please see my code:

def open_file():
    file_source = open('resource/path.txt', 'r') # contains 50\n 10\n 30\n 5\n 90\n 20\n 40\n 2\n 25\n 10\n 8\n 0\n
    return file_source


def get_path_tuple(file_source, pathList=[]):
    try:
        node = int(next(file_source)), int(next(file_source)), int(next(file_source))
        pathList.append(node)
        get_path_tuple(file_source, pathList)
    except StopIteration:
        pass
    return pathList


def short_step(pathList, n, stepList):
    try:
        stepA = pathList[n][0] + pathList[n][1]
        stepB = pathList[n][1] + pathList[n][2]
        stepList.append(min([stepA, stepB]))
        short_step(pathList, n+1, stepList)
    except IndexError:
        pass
    return stepList


pathList = get_path_tuple(open_file(), [])
pathList.reverse()
print(short_step(pathList, 0, []))

But I hit into problem, I don't know how to keep state of current location. Result is: [8, 27, 95, 40]. Could you please help to fix my code.

Answer 1

In this specific case, and using your data structure, it seems that you should be able to run two scenarios in parallel:

• Cost of A
• Cost of B

You can maintain a current cost, and the data you collect provides a "cost to switch" in the third element.

So you need to ask: which is cheaper? Staying on the starting path, or switching over to the other path?

path_list = [
        (50, 10, 30),
        (5, 90, 20),
        (40, 2, 25),
        (10, 8, 0),
]

A = 0
B = 1
Switch = 2

def cheapest_path(path_list, path=None, history=None):
    if history is not None:
        # Terminate when path_list is empty
        if not path_list:
            return history

        # Determine cost to stay this path, vs. cost to switch
        step = path_list[0]
        path_list = path_list[1:]

        stay_on_path = cheapest_path(path_list, path, history + [step[path]])
        switch_path = cheapest_path(path_list, B if path == A else A, history + [step[path], step[Switch]])

        return switch_path if sum(switch_path) < sum(stay_on_path) else stay_on_path
    else:

        pathA = cheapest_path(path_list, A, [])
        pathB = cheapest_path(path_list, B, [])
        return pathA if sum(pathA) < sum(pathB) else pathB

print(", ".join(map(str, cheapest_path(path_list))))