Solution to the puzzle (https://www.youtube.com/watch?v=N3JL3z4e2Qs)

laddersnake.py

# License: no license / public domain

# puzzle: https://www.youtube.com/watch?v=N3JL3z4e2Qs

import heapq

# graph g, start s, end t
def dijkstra(g, s, t):
    prev = [-1 for _ in range(101)]
    dist = [float("inf") for _ in range(101)]
    dist[s] = 0

    pq = [(dist[x], x) for x in range(1, 101)]
    m = dict(map(lambda x: (x[1], x), pq)) # node number to tuple mapping
    while len(pq) > 0:
        du, u = heapq.heappop(pq)
        for v in g[u]:
            dv = du + 1
            if dv < dist[v]:
                old_dv = dist[v]
                dist[v] = dv
                prev[v] = u
                # decrease key, this implementation is not very efficient, but works
                pq.remove((old_dv, v))
                heapq.heapify(pq)
                heapq.heappush(pq, (dist[v], v))
    return dist, prev

# generate basic graph
def gen_graph():
    g = [[] for _ in range(101)] # don't use 0
    for i in range(1, 101):
        g[i] = [x for x in range(i + 1, i + 7) if x <= 100]
    return g

# generate constraints, replace src with dst
def add_graph_constraints(constraints, g):
    s2d = dict(constraints)
    for i in range(1, 101):
        for x in s2d:
            if x in g[i]:
                g[i].remove(x)
                g[i].append(s2d[x])
    return g

def print_path(prev, t):
    res = []
    res.append(t)
    while prev[t] > 0:
        res.append(prev[t])
        t = prev[t]
    print(res)

if __name__ == "__main__":
    constraints1 = [(4, 75), (5, 15), (19, 41), (28, 50), (35, 96), (44, 82), (53, 94), (59, 95), (70, 91), # ladders
                    (98, 12), (88, 67), (81, 62), (76, 41), (52, 23), (47, 30), (31, 8)] # snakes
    # constraint2 is without those ladders/snakes used in first run
    constraints2 = [(4, 75), (28, 50), (44, 82), (53, 94), (59, 95), (70, 91), # ladders
                    (98, 12), (88, 67), (81, 62), (76, 41), (52, 23), (31, 8)] # snakes
    g = gen_graph()
    # comment below line for second solution
    g = add_graph_constraints(constraints1, g)

    g = add_graph_constraints(constraints2, g)
    dist, prev = dijkstra(g, 1, 100)
    print(dist[100])
    print_path(prev, 100)

    # output (reverse path)
    # 1st: [100, 96, 30, 41, 15, 1]
    # 2nd: [100, 94, 47, 41, 75, 1]