def f(inp): def g(i, j, oi, oj, l): crossing = False deadend = False while not (crossing or deadend): steps = [] for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]: if inp[i+di][j+dj]=='.': steps.append((i+di, j+dj)) if len(steps)>2: crossing = True continue elif len(steps)==1: deadend = True continue else: if (oi, oj)!=steps[0]: oi, oj = i, j i, j = steps[0] else: oi, oj = i, j i, j = steps[1] l += 1 if deadend and (i, j)==end: paths.append(l) print(l) elif deadend: pass elif crossing and (i, j) not in visited: visited.add((i, j)) for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]: if inp[i+di][j+dj]=='.': g(i+di, j+dj, i, j, l+1) visited.remove((i, j)) visited = set() paths = [] inp = [x.replace('>', '.').replace('v', '.') for x in inp] inp = ['#'*len(inp[0])] + inp + ['#'*len(inp[0])] si = 1 sj = inp[1].index('.') end = (len(inp)-2, inp[-2].index('.')) g(si+1, sj, si, sj, 1) return sorted(paths, reverse=True) inp = ''' #.##################### #.......#########...### #######.#########.#.### ###.....#.>.>.###.#.### ###v#####.#v#.###.#.### ###.>...#.#.#.....#...# ###v###.#.#.#########.# ###...#.#.#.......#...# #####.#.#.#######.#.### #.....#.#.#.......#...# #.#####.#.#.#########v# #.#...#...#...###...>.# #.#.#v#######v###.###v# #...#.>.#...>.>.#.###.# #####v#.#.###v#.#.###.# #.....#...#...#.#.#...# #.#########.###.#.#.### #...###...#...#...#.### ###.###.#.###v#####v### #...#...#.#.>.>.#.>.### #.###.###.#.###.#.#v### #.....###...###...#...# #####################.# '''.strip().split('\n') #assert f(inp)==[94, 90, 86, 82, 82, 74] #assert max(f(inp))==154 inp = open('input.txt').read().strip().split('\n') print(max(f(inp)))