from itertools import combinations
from collections import defaultdict
data = open("Day 20 input.txt", "r").read().strip().split("\n")
grid = {}
for y, line in enumerate(data):
for x, char in enumerate(line):
grid[(x,y)] = char
if char == "S": start = (x,y)
if char == "E": end = (x,y)
dirs = [[1,0],[0,1],[-1,0],[0,-1]]
path = []
queue = [(end, 0, None)]
visited = set()
while len(queue):
pos, dist, prev = queue.pop()
if pos in visited: continue
visited.add(pos)
path.append((pos, dist, prev))
for dx, dy in dirs:
newpos = (pos[0]+dx,pos[1]+dy)
if grid[newpos] != "#":
queue.append((newpos, dist+1, pos))
cheats = 0
savings = defaultdict(int)
for i, j in combinations(path, 2):
dist = abs(i[0][0]-j[0][0])+abs(i[0][1]-j[0][1])
if dist <= 20 and abs(i[1]-j[1])-dist >= 100:
savings[abs(i[1]-j[1])-dist] += 1
cheats += 1
#for i in sorted(savings.keys()): print savings[i], "cheats saving", i
print cheats
>spend a long time working on a robust approach
>can't get it to work
>try super lazy approach
>works on the first try
go figure
