So I have four “train lines” represented as lists:

line1 = ["a", "b", "f", "d", "e"] line2 = ["c", "e", "j", "g", "i"] line3 = ["c", "j", "k", "l", "m"] line4 = ["h", "b", "e", "a", "n"]

Essentially, each letter serves as a “station”. If a station appears on multiple lines, you can transfer from one line to another, similar to many underground city transit systems. For example, the shortest path from “a” to “h” would be [“a”, “b”, “h”] because you can go from “a” to “b” in line1, transfer to line4, and then move from “b” to “h”.

I wish to find a simple way to find the shortest path given an origin and destination point. My current solution is to convert the lines into a graph by finding the neighboring stations of a station and pairing them with that station.

stations = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n"] allLines = [line1, line2, line3, line4] nodeGraph = {} def getList(letter): neighbors = [] for i in allLines: if letter in i: pos = i.index(letter) if pos == 0: neighbors.append(i[pos+1]) elif pos == len(i) - 1: neighbors.append(i[pos-1]) elif pos > 0 and pos < len(i) - 1: neighbors.append(i[pos-1]) neighbors.append(i[pos+1]) return neighbors for station in stations: nodeGraph[station] = getList(station)

I then found a shortest path function on this website that outputs the shortest path from a graph input.

def SP(graph, start, end, path=[]): path = path + [start] if start == end: return path shortest = None for node in graph[start]: if node not in path: newpath = SP(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest

I want to avoid the step of creating a graph altogether and derive the shortest path just from the four lists. Can someone help me out?

I implemented a heuristic and brutal-force algorithm to solve the problem with pure Python functions.

from itertools import combinations, permutations stations = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n" ] line1 = ["a", "b", "f", "d", "e"] line2 = ["c", "e", "j", "g", "i"] line3 = ["c", "j", "k", "l", "m"] line4 = ["h", "b", "e", "a", "n"] lines = [line1, line2, line3, line4] def validate_step(x, y, lines): """ check if we can change fron x to y in a single line """ for i, line in enumerate(lines): if (x in line) and (y in line): if abs(line.index(x) - line.index(y)) == 1: return True, (i, (line.index(x), line.index(y))) else: return False, None def find_shortest(x, y, lines, max_step=12): # check if x and y are in the same line valid = validate_step(x, y, lines) if valid[0]: return 0, [valid[1]] # iterating over all the possibilities possible_inter = [s for s in stations if s not in (x, y)] for im_step in range(1, max_step): # intermediate step inter_steps = combinations(possible_inter, im_step) for i_step in inter_steps: for steps in permutations(i_step): solution = [] is_path_valid = True full_path = [x] + list(steps) + [y] for p1, p2 in zip(full_path[:-1], full_path[1:]): valid = validate_step(p1, p2, lines) is_path_valid *= valid[0] solution.append(valid[1]) if is_path_valid: return im_step, solution print("Did not find a solution") return None, None x = "d" y = "n" result = find_shortest(x, y, lines) print(f"with {result[0]} changes, the path from '{x}' to '{y}' is find") for step in result[1]: s1 = lines[step[0]][step[1][0]] s2 = lines[step[0]][step[1][1]] print(f"- Taking line {step[0]+1}, go from '{s1}' to '{s2}'")

The graph algorithms should certainly be favoured once the complexity of the problem increased….

P.S. My results are identical to the results from @Alain T.

## Recent Comments