vault.py
1.75 KB
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
#!/usr/bin/env python
MAX_DEPTH = 1
solution = None
class Node:
num = 0
op = None
value = 0
rooms = []
def __init__(self,n,o,v,r):
self.num = n
self.op = o
self.value = v
self.rooms = r
def apply_op(a,op,b):
if(op == "+"):
return a+b
elif(op == "-"):
return a-b
elif(op == "*"):
return a*b
def explore(map,room,path,current_op,value):
global MAX_DEPTH
global solution
path.append(room.num)
if(len(path) >= MAX_DEPTH):
return
if(current_op == None):
current_op = room.op
else:
value = apply_op(value,current_op,room.value)
current_op = None
if(room.num == 16):
if(value == 30):
solution = list(path)
for adj_room in room.rooms:
explore(map,map[adj_room-1],path,current_op,value)
del path[-1]
def print_map():
print """SOLUTION MAP
+----+----+----+----+
| 13 | 14 | 15 | 16 |
+----+----+----+----+
| 9 | 10 | 11 | 12 |
+----+----+----+----+
| 5 | 6 | 7 | 8 |
+----+----+----+----+
| 1 | 2 | 3 | 4 |
+----+----+----+----+
"""
def build_maze():
room1 = Node(1,None,22,[5,2])
room2 = Node(2,"-",0,[6,3])
room3 = Node(3,None,9,[7,4,2])
room4 = Node(4,"*",0,[8,3])
room5 = Node(5,"+",0,[9,6])
room6 = Node(6,None,4,[10,7,2,5])
room7 = Node(7,"-",0,[11,8,3,6])
room8 = Node(8,None,18,[12,4,7])
room9 = Node(9,None,4,[13,10,5])
rooma = Node(10,"*",0,[14,11,6,9])
roomb = Node(11,None,11,[15,12,7,10])
roomc = Node(12,"*",0,[16,8,11])
roomd = Node(13,"*",0,[14,9])
roome = Node(14,None,8,[15,10,13])
roomf = Node(15,"-",0,[16,11,14])
room10 = Node(16,None,1,[])
return [room1,room2,room3,room4,room5,room6,room7,room8,room9,rooma,roomb,roomc,roomd,roome,roomf,room10]
map = build_maze()
print_map()
print "Finding shortest solution..."
while(solution == None):
explore(map,map[0],[],"+",0)
MAX_DEPTH += 1
print solution