adventOfCode2016/advent_of_code_24.py at master · 4gn3s/adventOfCode2016 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import sys
from collections import deque
from itertools import permutations

test_input = """###########
#0.1.....2#
#.#######.#
#4.......3#
###########"""

my_input = """#####################################################################################################################################################################################
#...........#...#.....#.....#.....#....7#.................#.............#.....#.#.#...#.#.#.......#.......#.........#.....#.....#...#.....#.#.#.....#.......#.#.....#.....#.#.......#
#.#####.###.#####.###.#.#.#.#.#.#.#.###.###.#.#.#######.###.#.#####.#.#.#.#.###.#.#.#.#.#.#.#####.#.#.###.#.###.#.#.#.###.#.#.###.#.#.#####.#.#.#.#.#####.###.#.#.###.#.#.#.#.#.###.#
#.......#...#...#.#.....#.#.#...#...#...#.....#...#.......#.......#.......#.#.....#.#.....#.........#...#...#.#...#.#.#.....#.....#.......#.#...#.#.......#...#.#...#.#...#.#.#.....#
#.#.#.###.#.#.#.###.###.#.#.###.#.###.#.#.#.###.#.#.#.#.#.#######.#.#####.#.#.###.#.#.###.#.#.#####.#.#.#####.#.#.#.#.#.#.#.#.#.#####.#.#.###.#.#.#.###.###.#.#.#.#.#.#.#.#.#.#.#.#.#
#...........#.#.....#.....#...#...#.#.....#.#.#.........#.....#...#...#...#...#...#.#.....#.#.....#...#.........#...#.........#.#.#...............#.....#.#...#.#...#.#.......#.#...#
#.#####.###.#.###########.#.#.#.#.#.#.#.###.#.#######.#.#.#.#.#.###.#.#.#.#.#.#.#.###.#.#.#.#########.###.#.#####.#.#############.#.#.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.#####.#.###.#
#...#.#.....#....4#.......#...#.......#.......#...#.......#...#.#...#...#...#.....#.#.#...#.....#...#...#...#...#...#.............#...#...#...#...#.#...#.#...#...#.#...#..0#.....#.#
#.#.#.###.#.#.#.#.###.###.#.###.#####.#.###.#.#.#.#.#####.#.#.###.###.#.###.###.###.###.#.#.#.#.###.#.#.#.#.#.#####.#.#.#####.#.#.###.#.#.#.###.#.#.#.#.###.#.#.#####.#.#.###.#.#.###
#.#...#...........#...#.....#.#...#.#.#.#.#.......#...........#.....#.....#.#.#.#.......#.#...#.....#.#.......#.....#...#.......#.#.....#.#.#.....#.#.#.#.#.#.#.........#.#...#.#.#.#
#.#.#.#.#########.###.#.#.###.#.###.#####.###.#.#.#.###.#.#.###.###.###.#.###.#########.#.###.#.#.#.#.#.#.#.#.#########.#.#####.#.#####.#.#.###.#.#.#.#.#.#####.###.#.#.#.###.#.#.#.#
#.#.....#.....#.......#.#...#.....#...........#.#.#.....#...#.#.........#.#.#.#.........#.#.......#.......#...#...#...#...#.#...........#.#.....#.#.......#...........#...#...#.....#
#.#####.#.#.#.#####.#.#.#.#.#.#.#.#.#.#.#.#.###.###.###.#####.###.###.#.###.#.#.#.###.#######.###.#.#.#.#####.#.#####.#.###.#.#####.#.#.#.#########.#.###.#.#.#.#.#.#.###.#####.###.#
#.#...#.........#.....#...#.......#...#.#...#.......#...#...#.#.......#.......#...#.....#...........#...#.#.....#.................#.#...#.#.........#.#...#.#.#.#.......#.#.....#...#
#.#.#.#.#.###.#.#.###.#.#.#.#####.#.###.#.###.###.###.#######.#.###.###.#.###.#.#.###.#.#.#####.###.#.#.#.#.###.#.###.#######.#.#.#.#.#.#.#.#.#.#######.#.#.#.#.###.#.#.#.###.#.#.###
#.....#.#...#.....#...#.#.#.....#.#.#...#.#.#...........#.....#.#...#.................#.#.#...#.........#.......#.#...#.......#.#.#.....#...#...........#.#...#.........#...........#
###.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.###.###.#.###.#.#.#.#.###.#.#######.#.#####.###.#.#.#.#.#.#.#####.#.#.#.###.#.#.#######.#.#.#.#####.#.###.#.###.###.#.#.###.#####
#.#.#.#.#...#.....#...#...#...#...#.#...#.#.#.......#...#.#...............#...#.....#.....#.....#.....#.#.#.......#...#.#.....#.....#.........#...#...#.#.......#...#.....#.....#...#
#.#.#.#.###.###.#.#.#.#########.#.#.#########.#.#.###.#.#.#.###.#####.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.#.#####.###.#.#.#.###.#.#.#.#.#.#.###.#.#.#.###.#.###.#####.###.#.#.#.#.#
#.....#.....#.....#.......#...........#...#...#.#.....#.#.......#.......#.#.#.........#.............#...#.#.#.....#.....#...#...#.......#...#.......#...#...#...#....1#.....#...#.#.#
###.#.#.#######.#.#.#.###.#.#.###.###.#.###.#.#.#.#.#.#.###.###.###.#.#.#.#.#.#.#.#.#####.#####.###.#.###.#.#.#.#.###.###.#.#####.###.#.#.###.###.#######.#.###.###.#.###.#.#.#.###.#
#...#...#5......#.#...#.......#...#.........#.....#...........#...#.#.......#.#...........#...#.......#.....#.#.......#...#.....#.......#...#.#.................#.....#...#...#.....#
#.###.#.#.#.#####.#####.#####.###.#.#########.###.###.#.#.#####.#.#.###.#.###.###.#.#.#.#.#.###.#.#######.#.#.#.#.#.###.#.#.###.#.#####.###.#.#.#.###.#.#.###.#.###.#########.#####.#
#.#.#...#...#.....#.....#.#.....#.#.....#.........#...#...#.....#.#.#.......#.......#.......#...#.........#...#...#.....#.#.#...#.........#.#.#.#.#.....#.#.....#.........#.....#...#
###.###.###.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#####.#.#.#.#.###.#.#####.#.###.#.#.###.#.#.#.#.#.###.#.#.###.#.#########.#.#####.###.#.###.#####.#.#.#.#.#.#.###.#.#.#.#.#.###.#.#.#.#.#.#
#.#.#.#.......#...#.#...#.....#.#.................#.#.........#.....#...#...#.#.....#.....#.....#...#...#.....#...#...#...#.#.#...#...#...#...#...#...#.#...#.......................#
#.###.#############.#.#######.#.###.###########.#.#.###.###.#.#.###.###.#.###.###.#.#.###.#.#.###.#.#.#.###.#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.###.###.#.#.#.#.#.#.#.#.#.#
#.....#.#.......#...............#.....#...........#...#.#.#...#...#...#.#.#...#.......#...#...#.....#.....#.#.#...............#.#...#.....#.....#.#.#.#.......#...#.#...#...#.....#.#
#.#.###.#.###.#.#.#######.#.###.#.###.#.#.#.#.#####.#.#.#.#.#.#.#.###.#######.#.#.###.###.#.#.#.#######.#.###.#.#.###########.###.#########.#.#####.#.#.#.#.#.#.#.#.#.#####.###.#.###
#...#...#.#...............#.#.......#.#...#.#.......#.#...#.#.....#.....#.#.......#.........#.#.#...#.#...................#...#...#.............#.......#.......#.#...#...#.....#.#.#
#.#.#####.#.#######.#.###.#.#####.#.#.#.#.###.#.#.#.###.#.#.#####.###.###.#.#.#.#.#.#####.#.###.#.#.#.#.###.#.#####.#######.#.###.#.#.#.#.#####.#.#####.###.#######.#.#.#.#.###.#.#.#
#.........#.#...#.#.......#...#...#...........#.....#.....#.......#.....#.....#.#.#...#.#...#.....#.....#.....#...#.#.........#.....#.....#.#.#.....#...#...#.......#.#.#.....#...#.#
###.#######.#.#.#.#.###.#.###.#.###.###.#.###.#.#.#.#.#.#.###.#.###.#.#.#.###.###.#.#.#.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#.#####.#####.###.#.#.#.#####.###.###.#.#.#####.#.#####.#.###
#...#.......#.......#...#...#.........#.....#...#...#...#.#...#.........#...#.....#...#.#.#.#.#...#.....#.#.....#.....#.#.........#.....#.#.#.....#...#...#.......#.#3....#...#.....#
#.###.###.#####.###.###.###.#.###.#.###.###.#.###.###.#.#.#######.#.#.#.#.###.#.#.#.###.###.#.#.###.#.#.#.#####.###.###.###.#.###.#.#.###.#.#.#####.###.#.#.###.#.#.###.#.#.#.###.#.#
#.#...#.....#.#...#...#.#...........#...#.#...#.#.#.....#.#.......#.#.....#...#...#.....#...#.......#.........#...#.#...#.#.#.#.....#.....#.......#.........#.....#.....#.#...#.#...#
#.#.#.#####.#.###########.###.#.#####.###.###.#.###.###.#.#.#####.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.###.#.#.#.#.#####################.###.###.###.#.#.#.#.#.#
#.#...#.#...#.....#...#...#.....#.......#.......#.....#.#...#.....#...#.....#...#.......#...#.#...#.#...#.#...........#...#.#...#.#.......#.........#.#.......#...........#...#...#.#
###.###.#.#.#.#.#.#.#####.#.#.#.###.#.#######.#.###.#.#####.#.###.###.#.#.###.#.#.#.###.#.#######.#.#.#.###.###.#.#######.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#.#.###.###.#.#.###
#.#...#.......#.#...#.#.........#.........#...#.#...#.........#.#...#...#.........#...#.....#.......#...#.....#.....#...........#..2#.....#.#.....#...#.#.....#.......#...#...#...#.#
#.#.#.#.#.#.#.#.###.#.###.#.###.#.#.###.#.#.#.#.#.#.###.#.#####.#.###.###.#.###.#.#.#.#####.#.#.###.#.###.###.###.#.#####.#.#####.#####.#.#.#.#.#.###.#.#.#####.#.#.#.#.###.#.#.###.#
#.#..6#.........#...#.#.......#.#.......#.........#...#.....#.#...#...#.#.#.....#.....#.#.........................#.......#...#.#.........#.#...#...........#...#.....#.....#...#...#
#####################################################################################################################################################################################"""

def get_visit_orders(to_visit):
    if not to_visit:
        return [[]]
    results = [[to_visit[0]]]
    for a in to_visit[1:]:
        tmp = []
        for t in results:
            for i in range(len(t) + 1):
                x = t[:]
                x.insert(i, a)
                tmp.append(x)
        results = tmp
    return results

# print(get_visit_orders([1,2]))
# print(get_visit_orders([1,2,3]))

def is_valid(maze, r, c):
    if r < 0 or c < 0 or len(maze) <= r or len(maze[0]) <= c:
        return False
    if maze[r][c] == "#":
        return False
    return True

def get_maze(input_string):
    m = input_string.split("\n")
    maze = [list(n) for n in m]
    to_visit = []
    for r, row in enumerate(maze):
        for c, col in enumerate(row):
            if maze[r][c].isdigit():
                to_visit.append((int(maze[r][c]), (r, c)))
    return maze, to_visit

def find_shortest_path(maze, to_visit, cycle=False):
    cache = {}
    paths = [tsp(cache, maze, to_visit_order, cycle) for to_visit_order in permutations(to_visit) if to_visit_order[0][0] == 0]
    return min(paths)

def tsp(cache, maze, path_order, cycle):
    path_len = 0
    for i, p in enumerate(path_order[:-1]):
        start = p[1]
        end = path_order[i+1][1]
        if (start, end) not in cache:
            cache[(start, end)] = find_path_len(maze, start, end)
            cache[(end, start)] = cache[(start, end)]
        path_len += cache[(start, end)]
    if cycle:
        if (end, path_order[0][1]) not in cache:
            cache[(end, path_order[0][1])] = find_path_len(maze, end, path_order[0][1])
        path_len += cache[(end, path_order[0][1])]
    return path_len

def find_path_len(maze, start, end):
    visited = set([start])
    queue = deque([start])
    distances = {start: 0}
    while queue:
        current = queue.pop()
        if current == end:
            return distances[current]
        (x, y) = current
        for n in [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]:
            if n not in visited and is_valid(maze, *n):
                queue.appendleft(n)
                visited.add(n)
                if n in distances:
                    distances[n] = min(distances[n], distances[current] + 1)
                else:
                    distances[n] = distances[current] + 1
    return sys.maxint

test_maze, test_maze_to_visit = get_maze(test_input)
assert find_shortest_path(test_maze, test_maze_to_visit) == 14

maze, maze_to_visit = get_maze(my_input)
print find_shortest_path(maze, maze_to_visit)

maze, maze_to_visit = get_maze(my_input)
print find_shortest_path(maze, maze_to_visit, True)