#!/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