Functional Solution for Short Path Algorithm in Python

Question

I read Find out that you have Erlang for Great Good! and discovered an interesting riddle. I decided to implement it in Python in the most functional way.

Check out 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 got into a problem, I do not know how to save the state of the current location. Result: [8, 27, 95, 40] . Could you help me fix my code.

Answer 1

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

• Cost A
• Cost B

You can maintain the current value, and the data you collect provides the “cost of switching” in the third element.

So, you need to ask: what is cheaper? Staying on the starting line or switching to another way?

 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)))) 

Answer 2

In fact, I think that, as in all problems with finding a path, you need to calculate the total length of the path from the beginning to each point. Then you need to compute both lists, the path to A and the list of paths to B.

I don’t know if the recursive algorithm is part of the exercise, but I used a simple loop.

 pathList = [[50,10,30],[5,90,20],[40,2,25],[10,8,999999]] def all_steps(pathList): stepListA,stepListB = [],[] for n in range(0,len(pathList)): #Step to A if pathList[n][0]<=pathList[n][1] + pathList[n][2]:#A to A new_stepListA = list(stepListA) new_stepListA.append(pathList[n][0]) else: #B to A new_stepListA = list(stepListB) new_stepListA.extend([pathList[n][1],pathList[n][2]]) #Step to B if pathList[n][1]<=pathList[n][2] + pathList[n][2]:#B to B new_stepListB = list(stepListB) new_stepListB.append(pathList[n][1]) else: #A to B new_stepListB = list(stepListA) new_stepListB.extend([pathList[n][0],pathList[n][2]]) stepListA = list(new_stepListA) stepListB = list(new_stepListB) if sum(stepListA)<=sum(stepListB): print "finish on A" return stepListA else: print "finish on B" return stepListB print all_steps(pathList)