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
|
#!/usr/bin/env python
import operator
from collections import deque
maze = [
["*", "8", "-", "1"],
["4", "*", "11", "*"],
["+", "4", "-", "18"],
["22", "-", "9", "*"],
]
def result(path):
res, op = int(path[0]), None
path = path[1:]
operators = {"+": operator.add, "*": operator.mul, "-": operator.sub}
for i in path:
if i in operators:
op = operators[i]
else:
res = op(res, int(i))
return res
def solved(state):
x, y, p, _, _ = state
return x == 3 and y == 0 and result(p) == 30
def hash(state):
x, y, p, _, _ = state
return ",".join(map(str, (x, y, result(p))))
if __name__ == "__main__":
state = (0, 3, ["22"], 0, "")
seen = {}
dfs_s = deque([state])
sols = []
while dfs_s:
curr = dfs_s.popleft()
x, y, p, s, d = curr
print("%s steps \t%s " % (s, " ".join(p)))
if solved(curr):
sols.append(curr)
break
if hash(curr) in seen and seen[hash(curr)] < s:
continue
elif x == 3 and y == 0:
continue
seen[hash(curr)] = s
if x == 0 and y == 3 and s != 0:
continue
if x > 0:
dfs_s.append((x - 1, y, p + [maze[y][x - 1]], s + 1, d + "W"))
if x < 3:
dfs_s.append((x + 1, y, p + [maze[y][x + 1]], s + 1, d + "E"))
if y > 0:
dfs_s.append((x, y - 1, p + [maze[y - 1][x]], s + 1, d + "N"))
if y < 3:
dfs_s.append((x, y + 1, p + [maze[y + 1][x]], s + 1, d + "S"))
print("solutions")
print(sols)
|