-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsol_18.aes
238 lines (211 loc) · 25.8 KB
/
sol_18.aes
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
@compiler >= 4.2.0
include "List.aes"
include "Pair.aes"
contract Day18 =
type node = int
record edge = { to : node, dist : int, keys : bits, doors : bits }
type graph = map(node, list(edge))
type state = graph
type set('a) = map('a, unit)
entrypoint init() = {}
stateful entrypoint setup_1() =
put(build_graph(input_1()))
entrypoint solve_1() =
let start = { here = [0], dist = 0, path = [], todo = List.foldl(Bits.set, Bits.none, [1..26]) }
shortest_path({}, heap_insert(start, heap_empty()))
stateful entrypoint setup_2() =
put(build_graph(input_2()))
entrypoint solve_2() =
let start = { here = [0, -1, -2, -3], dist = 0, path = [], todo = List.foldl(Bits.set, Bits.none, [1..26]) }
shortest_path({}, heap_insert(start, heap_empty()))
record hole('a) = { pre : list('a), elem : 'a, suf : list('a) }
function holes(xs : list('a)) : list(hole('a)) =
holes_([], xs)
function holes_(acc, xs) =
switch(xs)
[] => []
x :: xs => { pre = List.reverse(acc), elem = x, suf = xs } :: holes_(x :: acc, xs)
record heap_entry = { here : list(node), dist : int, path : list(int), todo : bits }
record heap = { cursor : int, entries : map(int, list(heap_entry)) }
function heap_empty() = { cursor = 0, entries = {} }
function heap_insert(e : heap_entry, h : heap) =
let i = e.dist
h{ entries[i = []] @ es = e :: es }
function heap_next(h : heap) : option(heap_entry * heap) =
if (h.entries == {}) None
else
let c = h.cursor
switch (Map.lookup(c, h.entries))
None => heap_next(h{ cursor = c + 1 })
Some([]) => heap_next(h{ cursor = c + 1, entries @ es = Map.delete(c, es) })
Some(e :: es) => Some((e, h{ entries[c] = es }))
function shortest_path(seen : set(list(node) * bits), heap : heap) =
let Some((e, heap)) = heap_next(heap)
let here = e.here
let hash = (e.here, e.todo)
if (Map.member(hash, seen))
shortest_path(seen, heap)
elif (e.todo == Bits.none)
(List.reverse(e.path), e.dist)
else
let seen' = seen{ [hash] = () }
let next = [ {here = hole.pre ++ [edge.to] ++ hole.suf,
dist = e.dist + edge.dist, path = edge.to :: e.path,
todo = Bits.clear(e.todo, edge.to) }
| hole <- holes(here),
edge <- state[hole.elem],
if (Bits.test(e.todo, edge.to)), // We still need this key
if (Bits.none == Bits.intersection(edge.keys, e.todo)), // Don't go through keys we still need
if (Bits.none == Bits.intersection(edge.doors, e.todo)) // Can't go through doors we haven't unlocked
]
shortest_path(seen', List.foldr(heap_insert, heap, next))
datatype block = Start | Path | Key(int) | Door(int)
type pos = int * int
type maze = map(pos, block)
function build_graph(maze : maze) : graph =
let starts = [ p | (p, s) <- Map.to_list(maze), if(s == Start) ]
let starts = Map.from_list(List.map(Pair.swap, List.enumerate(starts)))
let mk_node((pos, block)) =
switch(Map.lookup(pos, starts))
Some(n) => [-n]
None => block_to_node(block)
Map.from_list(
[ (node, all_paths(maze, Pair.fst(pb)))
| pb <- Map.to_list(maze),
node <- mk_node(pb) ])
function neighbours((x, y) : pos) : list(pos) =
[(x, y - 1), (x + 1, y), (x, y + 1), (x - 1, y)]
function all_paths(maze : maze, p : pos) : list(edge) =
all_paths_(maze, [{pos = p, dist = 0, keys = Bits.none, doors = Bits.none}], {}, {})
record ann_p = {pos : pos, dist : int, keys : bits, doors : bits}
function block_to_node(b : block) : list(node) =
switch(b)
Start => [0]
Key(i) => [i]
_ => []
function ann_p_to_edge(maze, ap) =
[ {to = i, dist = ap.dist, keys = Bits.clear(ap.keys, i), doors = ap.doors}
| i <- block_to_node(maze[ap.pos]), if(ap.dist > 0)]
function all_paths_(maze, q : list(ann_p), acc : map(pos, edge), seen : set(pos)) : list(edge) =
switch (q)
[] => [ e | (_, e) <- Map.to_list(acc) ]
_ =>
let acc' = List.foldr((pe, acc) => acc{[Pair.fst(pe)] = Pair.snd(pe)},
acc, [ (ap.pos, e) | ap <- q, e <- ann_p_to_edge(maze, ap), if(e.to != 0) ])
let seen' = List.foldr((ap, seen) => seen{[ap.pos] = ()}, seen, q)
let set_door(x, b) =
switch(x)
Door(i) => Bits.set(b, i)
_ => b
let set_key(x, b) =
switch(x)
Key(i) => Bits.set(b, i)
_ => b
let q' = [ {pos = p', dist = ap.dist + 1, keys = set_key(item, ap.keys),
doors = set_door(item, ap.doors)}
| ap <- q,
p' <- neighbours(ap.pos),
if (!Map.member(p', seen')),
if (Map.member(p', maze)),
let item = maze[p']]
all_paths_(maze, q', acc', seen')
function input_1() =
make_maze(
[[35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35],
[35,46,46,46,46,46,46,46,46,46,35,113,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,35],
[35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35],
[35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,103,35,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,46,46,35,46,79,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35],
[35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,70,35,35,35,46,35,46,35,46,35,46,35,84,35,35,35],
[35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,35],
[35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35],
[35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,35,121,46,46,35,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,46,46,46,46,35],
[35,46,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35],
[35,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,35,46,46,46,46,46,46,46,35,46,35],
[35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35],
[35,46,35,46,46,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35],
[35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,69,35],
[35,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35],
[35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35],
[35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,46,46,35,46,46,46,35],
[35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35],
[35,101,35,46,46,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,67,46,35,46,46,46,35],
[35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35],
[35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35,46,35],
[35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35],
[35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,35,46,46,46,46,46,35,46,46,46,46,46,35,46,35],
[35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35],
[35,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35],
[35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35],
[35,46,35,46,35,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,35],
[35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,90,35],
[35,46,46,46,35,46,46,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,35,46,46,107,35,46,35,46,35,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35],
[35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35],
[35,46,46,46,78,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,46,98,35,46,35],
[35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35],
[35,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,46,46,35],
[35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35],
[35,46,35,46,46,46,86,46,35,46,35,46,72,46,35,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,35],
[35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35],
[35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,35],
[35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,46,35],
[35,46,35,46,35,46,46,46,35,46,46,97,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,46,46,35,46,46,104,46,46,35,46,35,46,35],
[35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,65,35],
[35,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,88,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,35],
[35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,46,64,46,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35],
[35,46,68,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35],
[35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,73,35,46,35,46,35,46,35,46,35],
[35,105,35,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,120,46,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,35],
[35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35],
[35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,46,46,35,46,35,46,35,46,35,46,35,46,35,118,46,46,46,46,35,46,35,46,46,46,35,46,46,46,35,100,46,46,35,46,46,46,35],
[35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,35,35,35,35,46,35],
[35,46,35,46,46,46,46,46,35,46,35,46,46,46,46,117,35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,46,46,35],
[35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,35,35],
[35,46,83,46,35,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,115,46,46,35],
[35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,46,35],
[35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,110,46,46,35,46,80,46,46,46,35,46,35,46,35,46,46,46,46,46,46,46,35],
[35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35],
[35,46,46,46,35,46,35,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35],
[35,35,35,35,35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,85,35],
[35,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,46,46,35,46,35,46,35],
[35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,46,35],
[35,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,35,46,46,119,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,75,46,35,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,35],
[35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35],
[35,46,46,46,35,46,46,112,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35],
[35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,82,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35],
[35,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,35],
[35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,77,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,87,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35],
[35,46,35,46,35,46,35,46,46,46,46,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,46,109,35,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,35,106,46,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,35],
[35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35],
[35,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,46,46,46,46,35,46,35,46,46,46,35,46,81,46,35,46,35],
[35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35],
[35,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,71,46,46,46,35,46,35,46,35,46,46,46,35,46,35],
[35,35,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,35,35,35,35,46,35,74,35,35,35,35,35,76,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,46,35,46,35,46,35],
[35,46,46,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,89,46,35],
[35,66,35,35,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,35,35],
[35,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,108,46,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,46,46,35,46,46,46,35],
[35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,46,35,35,35],
[35,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,35,46,35,46,46,46,35,102,46,46,35],
[35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,35,35,46,35,35,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,46,35],
[35,46,35,46,46,46,46,46,35,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,35,114,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,35,46,46,46,46,46,35,46,35,46,46,46,35,46,35,46,46,46,35,46,46,111,35,46,35,46,46,46,46,46,35,46,35,46,46,46,46,46,35],
[35,46,35,35,35,35,35,46,35,46,35,35,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,35,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,35,35,46,35,35,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,46,35,46,35],
[35,46,46,46,35,46,35,46,35,46,46,46,46,46,35,122,46,46,35,46,46,46,35,46,35,46,46,46,46,46,35,46,46,46,46,46,35,46,35,46,35,99,46,46,46,46,35,46,35,46,35,46,46,46,35,46,46,46,46,46,35,46,46,46,35,46,46,46,35,46,46,46,46,116,35,46,35,46,35,46,35],
[35,35,35,46,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,46,35,46,35,35,35,46,35,46,35,46,35,46,35,35,35,35,35,46,35,46,35,35,35,35,35,35,35,46,35,35,35,35,35,35,35,46,35,46,35],
[35,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,35,46,46,46,46,46,46,46,35,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,46,35,46,35],
[35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35]])
entrypoint input_2() =
let maze = input_1(){ [(40, 40)] = Start,
[(42, 40)] = Start,
[(40, 42)] = Start,
[(42, 42)] = Start }
List.foldr(Map.delete, maze, [(41, 40), (40, 41), (41, 41), (42, 41), (41, 42)])
function make_maze(ls : list(list(int))) =
let parse(c) =
switch(c)
35 => [] // Wall
46 => [Path]
64 => [Start]
_ => [if(c > 96) Key(c - 96) else Door(c - 64)]
Map.from_list([ ((Pair.fst(xc) + 1, Pair.fst(yl) + 1), block)
| yl <- List.enumerate(ls),
xc <- List.enumerate(Pair.snd(yl)),
block <- parse(Pair.snd(xc)) ])