top = 100
snakes = {16: 6, 48: 26, 49: 11, 56: 53, 62: 19,
64: 60, 87: 24, 93: 73, 95: 75, 98: 78}
ladders = {2: 38, 4: 14, 9: 31, 21: 42,
28: 84, 36: 44, 51: 67, 71: 91, 80: 100}
jump = {**snakes, **ladders}
steps = 0
paths = dict()
reached_top = False
all_short_paths = list()
reached_bottom = False
while not reached_top:
steps += 1
if steps == 1:
paths[1] = [[0,1,2,3,4,5,6]]
for index,val in enumerate(paths[1][0]):
if val in jump.keys():
paths[1][0][index] = jump[val]
else:
paths[steps] = list()
for lists in paths[steps - 1]:
for val in lists[1:]:
paths[steps].append([val, val+1, val+2, val+3, val+4, val+5, val+6])
for index1,lists in enumerate(paths[steps]):
for index2,val in enumerate(lists):
if val in jump.keys():
paths[steps][index1][index2] = jump[val]
val = jump[val]
if val == top:
reached_top = True
if paths[steps][index1][0]:
all_short_paths.append([100,paths[steps][index1][0]])
all_short_paths = [list(x) for x in set(tuple(x) for x in all_short_paths)]
steps_down = 1
while not reached_bottom:
new_all_short_paths = list()
for lists1 in all_short_paths:
for lists2 in paths[steps - steps_down]:
if lists1[-1] in lists2:
new_all_short_paths.append(lists1 + [lists2[0]])
all_short_paths = [list(x) for x in set(tuple(x) for x in new_all_short_paths)]
steps_down += 1
if steps - steps_down == 1:
reached_bottom = True
print(f"Shortest steps to win is {steps}.\nNo: of Shortest paths are,\n {len(all_short_paths)}")
print(all_short_paths)
