1import json
2from collections import deque
3
4LEVELS = [
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
87WALL = '#'
88GOAL_CHARS = set('.*+')
89BOX_CHARS = set('$*')
90PLAYER_CHARS = set('@+')
91
92DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
93
94
95def parse(rows):
96 height = len(rows)
97 width = max(len(r) for r in rows)
98 walls = set()
99 goals = set()
100 boxes = set()
101 player = None
102 for r, row in enumerate(rows):
103 for c in range(width):
104 ch = row[c] if c < len(row) else ' '
105 if ch == WALL:
106 walls.add((r, c))
107 if ch in GOAL_CHARS:
108 goals.add((r, c))
109 if ch in BOX_CHARS:
110 boxes.add((r, c))
111 if ch in PLAYER_CHARS:
112 player = (r, c)
113 return walls, goals, frozenset(boxes), player
114
115
116def solve(rows, max_states=2_000_000):
117 walls, goals, boxes0, player0 = parse(rows)
118 start = (player0, boxes0)
119 seen = {start}
120 q = deque([(start, 0)])
121 while q:
122 (player, boxes), d = q.popleft()
123 if boxes == goals:
124 return d, len(seen)
125 if len(seen) > max_states:
126 return None, len(seen)
127 for dr, dc in DIRS:
128 nr, nc = player[0] + dr, player[1] + dc
129 if (nr, nc) in walls:
130 continue
131 nboxes = boxes
132 if (nr, nc) in boxes:
133 br, bc = nr + dr, nc + dc
134 if (br, bc) in walls or (br, bc) in boxes:
135 continue
136 nboxes = frozenset((boxes - {(nr, nc)}) | {(br, bc)})
137 state = ((nr, nc), nboxes)
138 if state not in seen:
139 seen.add(state)
140 q.append((state, d + 1))
141 return None, len(seen)
142
143
144for i, rows in enumerate(LEVELS, 1):
145 dist, states = solve(rows)
146 if dist is None:
147 print(f"Level {i}: UNSOLVED (explored {states} states)")
148 else:
149 print(f"Level {i}: solvable in {dist} moves (explored {states} states)")
150
Discussion
No comments yet. Start the discussion. Recorded by @patrick-toulme.