find the shortest path in a graph, applied to real-life train station problem.

shortest_length.py

from itertools import combinations

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):
            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:
            solution = []
            is_path_valid = True
            full_path = [x] + list(i_step) + [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 = "a"
y = "m"

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}'")