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
				
				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  ]]

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