from search import *
import copy
import random

class HappyProblem(Problem):
	def __init__(self, unhappy_mat):
		self.unhappy_mat = unhappy_mat
		self.n = len(unhappy_mat)
		self.initial = range(self.n)
		random.shuffle(self.initial)
		self.initial_cost = self.unhappy(self.initial)
		self.i = 0
		
	def successor(self, state):
		succ = []
		for i in range(self.n):
			for j in range(i):
				if j == i:
					continue
				
				s = copy.deepcopy(state)
				t = s[i]
				s[i] = s[j]
				s[j] = t
				yield ("seat", s)
#				succ.append(("seat", s))
#		self.i += 1
#		random.shuffle(succ)
#		return succ
	
	def path_cost(self, c, state1, action, state2):
		#print 'Path cost:', c, state1, '(', self.unhappy(state1),')', state2, '(',self.unhappy(state2),')'
		return self.unhappy(state2)
	
	def unhappy(self, state):
		s = 0
		for i in range(self.n):
			q = self.unhappy_mat[state[i]][state[(i+1) % self.n]]
			
			if q == 0:
				q = self.unhappy_mat[state[(i+1) % self.n]][state[i]]
			s += q
		
		return s

mat=[
[0  , 25 , 40 ,  4 , 80 , 31 , 65 , 62 ],
[ 0 ,  0 , 95 , 55 , 95 , 11 ,  1 , 18 ],
[ 0 ,  0 ,  0 , 80 , 60 , 77 , 86 , 64 ],
[ 0 ,  0 ,  0 ,  0 , 94 , 0  , 59 , 41 ],
[ 0 ,  0 ,  0 ,  0 ,  0 , 85 , 74 , 71 ],
[ 0 ,  0 ,  0 ,  0 ,  0 ,  0 , 40 , 57 ],
[ 0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 , 44 ],
[ 0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  0 , 0  ]]

def rand_mat(n):
	m = []
	for i in range(n):
		z = []
		for j in range(n):
			z.append(random.random())
		m.append(z)
	
	for i in range(n):
		for j in range(i):
			m[i][j] = 0
	for i in range(n):
		m[i][i] = 0
		
	return m

mat = rand_mat(100)
#for l in mat:
#	print l

mat = [
[0,25,40,4,80,31,65,62,104,199,],
[0,0,95,55,95,11,1,18,106,116,],
[0,0,0,80,60,77,86,64,82,256,],
[0,0,0,0,94,0,59,41,75,237,],
[0,0,0,0,0,85,74,71,42,206,],
[0,0,0,0,0,0,40,57,187,172,],
[0,0,0,0,0,0,0,44,243,252,],
[0,0,0,0,0,0,0,0,228,71,],
[0,0,0,0,0,0,0,0,0,125,],
[0,0,0,0,0,0,0,0,0,0,],
]

p = HappyProblem(mat)
state = hill_climbing(p)
print "Guests ordering:", state, "Expansions:", p.i, 'Final score:', p.unhappy(state)

l = ""
for i in range(len(state)):
	l +=  ("%i<-" % state[i])
	if i+1 < len(state):
		if mat[state[i]][state[i+1]] != 0:
			l += ("(%i)-" % mat[state[i]][state[i+1]])
		else:
			l += ("(%i)-" % mat[state[i+1]][state[i]])
print l