#	The primary exercise I want you to try and do is  noughts and crosses (tic tac toe).
#	In this exercise I want you to draw the board as follows:
#	 1 | 2 | 3
#	---+---+----
#	 4 | 5 | 6
#	---+---+----
#	 7 | 8 | 9

#	The user will always be crosses. Ask the user to choose a square to play.
#	Make sure the square is a valid square, I.E.: not occupied and within the range
#	After each valid move by the user have the computer play a move (random).
#	You can use the pythons random module for this. Everytime both players have made a move draw the state of the board again. And after #	each move check if the user or the computer has won.

import random

	##		coordinates
	##			[0,0 0,1 0,2]
	##			[1,0 1,1 1,2]
	##			[2,0 2,1 2,2]

#grid_values = [["1", "2", "3"],
#				["4", "5", "6"],
#				["7", "8", "9"]]

# test grid
grid_values = [["X", "2", "3"],
				["4", "5", "6"],
				["7", "8", "9"]]

game_over = 0


def checkGrid(gv, move):

	#print "checking position:", move
	#print "position contains:", gv[move[0]][move[1]]

	if gv[move[0]][move[1]] == "X" or gv[move[0]][move[1]] == "O":
		#print "occupied"
		return 1

	else:
		#print "empty"
		return 0

def drawGrid(gv, win=0, wh=[[" ", " ", " "],
					[" ", " ", " "],
					[" ", " ", " "]],
				wv=[[" ", " ", " "],
					[" ", " ", " "],
					[" ", " ", " "]],
				wd=[" ", " ", " ", " "]):

	if win == "1":
		print "Player has won the game!"

	if win == "2":
		print "Computer has won the game!"

	print "\n", wd[0], wv[0][0], " ", wv[0][1], " ", wv[0][2], wd[1]
	print wh[0][0], gv[0][0], "|", gv[0][1], "|", gv[0][2], wh[0][2]
	print " ---+---+---"
	print wh[1][0], gv[1][0], "|", gv[1][1], "|", gv[1][2], wh[1][2]
	print " ---+---+---"
	print wh[2][0], gv[2][0], "|", gv[2][1], "|", gv[2][2], wh[2][2]
	print wd[2], wv[2][0], " ", wv[2][1], " ", wv[2][2], wd[3], "\n"


def checkWin(gv):

	win_horiz = [[" ", " ", " "],
				[" ", " ", " "],
				[" ", " ", " "]]

	win_vert = [[" ", " ", " "],
				[" ", " ", " "],
				[" ", " ", " "]]

	win_diag = [" ", " ", " ", " "]


	win = 0
	#win_type = 0
	#win_pos = 0

	i = 0	#print gv

	while i < 3:

		# check if row has match
		if gv[i][0] == gv[i][1] and gv[i][0] == gv[i][2]:

			win_horiz[i][0] = u"\u2192"
			win_horiz[i][2] = u"\u2190"

			if gv[i][0] == "X":
				win = 1

			else:
				win = 2

		# check if column has match
		if gv[0][i] == gv[1][i] and gv[0][i] == gv[2][i]:

			win_vert[0][i] = u"\u2193"
			win_vert[2][i] = u"\u2191"

			if gv[0][i] == "X":
				win = 1

			else:
				win = 2

		i += 1

	#	check for diagonal match
	#	diagonal win, left to right
	if gv[0][0] == gv[1][1] and gv[0][0] == gv[2][2]:

		win_diag[0] = u"\u2198"
		win_diag[3] = u"\u2196"

		if gv[0][0] == "X":
			win = 1

		else:
			win = 2

	#	diagonal win, right to left
	if gv[0][2] == gv[1][1] and gv[0][2] == gv[2][0]:

		win_diag[1] = u"\u2199"
		win_diag[2] = u"\u2197"

		if gv[0][2] == "X":
			win = 1

		else:
			win = 2


	if win == 1:
		print "\nPlayer Wins!"

	if win == 2:
		print "Computer Wins!"

	drawGrid(gv, win, win_horiz, win_vert, win_diag)
	return win



def getPlay(gv):

# get move position value from 1 to 9, enter it into the play grid

	while True:

		next_move = raw_input("\nEnter your next move (grid numbers 1 to 9) or q to quit: ")

		if next_move.isdigit():
			next_move = int(next_move)

			if 1 <= next_move <= 9:

				xcoord = (next_move - 1) % 3
				ycoord = (next_move - 1) / 3

				if (gv[ycoord][xcoord] != "X") and (gv[ycoord][xcoord] != "O"):
					break

				else:
					print("That slot is already taken. Please chose an empty one.")

		if next_move == "q" or next_move == "Q":
			sys.exit(0)


	print "\nPlayer Move:"

	gv[ycoord][xcoord] = "X"

	return gv

def cpuPlay(gv):
##	Random number based computer moves	##

	while True:

		cpu_move = random.randint(1, 9)
		xcoord = (cpu_move - 1) % 3
		ycoord = (cpu_move - 1) / 3

		if (gv[ycoord][xcoord] != "X") and (gv[ycoord][xcoord] != "O"):
			break

	print "\nComputer Move:"

	gv[ycoord][xcoord] = "O"

	return gv



def cpuAI(gv):
##	"Logic" based computer moves	##

##	NESTED FUNCTION

	## check new number is not already in temp list
	def tempCycle(move, temp):

		for tmp in temp:
			#print "tmp:", tmp
			if tmp == move:
				#print "Already Exists!", "tmp:", tmp, "move", move
				return 1

		return 0


	##	check if moves are in a row
	def doublesCheck(moves):

		## NESTED FUNCTIONS

		## find missing number in matched row
		def rowMatchCheck(rmatch):

			new_move = [0, 0]

			for i in range(0, 3):

				if i != rmatch[0][1] and i != rmatch[1][1]:

					new_move[0] = rmatch[0][0]
					new_move[1] = i
#					print "new move:", new_move

			return new_move

		## find missing number in matched col
		def colMatchCheck(cmatch):

			new_move = [0, 0]

			for i in range(0, 3):

				if i != cmatch[0][0] and i != cmatch[1][0]:

					new_move[1] = cmatch[0][1]
					new_move[0] = i

			return new_move

		## NESTED FUNCTION END


		row_match = []
		col_match = []
		diag1_match = []
		diag2_match = []

		row_move = []
		col_move = []

		temp_r = []
		temp_c = []

		i = 0

		print "\nmoves", moves

		#	check for 2 in a same row or column	##
		for mov in moves:
			j = 0

#			print "row match:", row_match, len(row_match)
			for mv in moves:

				if moves[i][0] == moves[j][0] and mov != mv and tempCycle(mov, temp_r) == 0 and tempCycle(mv, temp_r) == 0:

					temp_r.append(mov)
					temp_r.append(mv)

					row_match.append(mov)
					row_match.append(mv)


				if moves[i][1] == moves[j][1] and mov != mv and tempCycle(mov, temp_c) == 0 and tempCycle(mv, temp_c) == 0:

					temp_c.append(mov)
					temp_c.append(mv)

					col_match.append(mv)
					col_match.append(mov)

				j += 1
			i += 1

#		print "row_match ", row_match
#		print "col_match ", col_match
#		print "diag1_match", diag1_match
#		print "diag2_match", diag2_match, "\n"


		## cycle through each row match, call rowMatchCheck() to get move to complete row.

		i = 0
		temp = []

		for mv in row_match:
			j = 0

			for mov in row_match:
				## If 2 rows have the same value, are duplicates, have different col values and are not trasposed versions of the same thing:
				if mov[0] == mv[0] and mov != mv and row_match[i][1] != row_match[j][1] and tempCycle(mov, temp) == 0 and tempCycle(mv, temp) == 0:

					#print "temp", temp
					temp.append(mov)
					temp.append(mv)
					current_match = []

					current_match.append(mov)
					current_match.append(mv)

					#print "current match row:", current_match, "\n"

					row_move.append(rowMatchCheck(current_match))

				j += 1
			i += 1


		## cycle through each column match, call colMatchCheck() to get move to complete column

		i = 0
		temp = []

		for mv in col_match:
			j = 0

			for mov in col_match:
				## If 2 columns have the same value, are duplicates, have different row values and are not trasposed versions of the same thing:
				if mov[1] == mv[1] and mov != mv and col_match[i][0] != col_match[j][0] and tempCycle(mov, temp) == 0 and tempCycle(mv, temp) == 0:

					#print "temp", temp
					temp.append(mov)
					temp.append(mv)
					current_match = []

					current_match.append(mov)
					current_match.append(mv)

					#print "current match col:", current_match, "\n"

					col_move.append(colMatchCheck(current_match))

				j += 1
			i += 1

					#col_move.append(colMatchCheck(current_match))

#		print "matched rows", row_match, "\n"
#		print "row move", row_move, "\n"
#		print "matched columns", col_match, "\n\n"


		#	Check for diagonal

		diag_move = []

		for mov in moves:

			if mov == [0, 0] or mov == [1, 1] or mov == [2, 2]:
				diag1_match.append(mov)

			if mov == [0, 2] or mov == [1, 1] or mov == [2, 0]:
				diag2_match.append(mov)

		if len(diag1_match) > 1:
			for i in range(0, 3):
				if i != diag1_match[0][0] and i != diag1_match[1][0]:
					temp_move = [0, 0]
					temp_move[0] = i
					temp_move[1] = i
			diag_move.append(temp_move)

		if len(diag2_match) > 1:
			for i in range(0, 3):
				if i != diag2_match[0][0] and i != diag2_match[1][0]:
					temp_move = [0, 0]
					temp_move[0] = i
					temp_move[1] = abs(i - 2)

			diag_move.append(temp_move)



		print "Row moves: ", row_move
		print "Col moves: ", col_move
		print "Diag moves:", diag_move, "\n"

		doubles = row_move + col_move + diag_move

		return doubles

##	NESTED FUNCTION END	##


	player_moves = []
	cpu_moves = []

	next_cpu = []

	##	store current moves	##
	for i in range(0, 3):
		for j in range(0, 3):

			temp_player = ["0", "0"]
			temp_cpu = ["0", "0"]

			if gv[i][j] == "X":
				temp_player[0] = i
				temp_player[1] = j

				player_moves.append(temp_player)

			if gv[i][j] == "O":
				temp_cpu[0] = i
				temp_cpu[1] = j

				cpu_moves.append(temp_cpu)

	## Check for player doubles and get blocking move
	print "PLAYER MOVES: 'X'"
	defensive_options = doublesCheck(player_moves)

	## Check for computer doubles and get winning move
	print "COMPUTER MOVES: 'O'"
	attacking_options = doublesCheck(cpu_moves)

	print "Defensive options", defensive_options
	print "Attacking options", attacking_options


	## prioritise winning move over defending
	if attacking_options:
		next_cpu = attacking_options[0]

	## find best defensive move
	if not attacking_options and defensive_options:

		next_cpu = defensive_options[0]

		print "next_cpu:", next_cpu

		i = 0
		for def1 in defensive_options:
			j = 0
			for def2 in defensive_options:
				if def1 == def2 and i != j:
					next_cpu = def1
				j += 1
			i += 1


	## If there are no doubles yet:

	## Check for Completely empty rows, columns and diagonals
	def CheckEmpty(gv):

		for i in range(0, 3):
			#	row i is empty
			if isdigit(gv[i][0]) and isdigit(gv[i][1]) and isdigit(gv[i][2]):
				print "row", i, "is empty"

			#	column i is empty
			if isdigit(gv[0][i]) and isdigit(gv[1][i]) and isdigit(gv[2][i]):
				print "column", i, "is empty"

		#	diagonal 1 is empty
		if isdigit(gv[0][0]) and isdigit(gv[1][1]) and isdigit(gv[2][2])
			print "diagonal 1 is empty"

		#	diagonal 2 is empty
		if isdigit(gv[0][2]) and isdigit(gv[1][1]) and isdigit(gv[2][0])
			print "diagonal 1 is empty"



#	if not attacking_options and not defensive_options:
		## Choose best attacking move




	print "computer move priority", next_cpu
	print "other defense moves", defensive_options
	print "other attack moves", attacking_options





	return gv

##		GAME LOOP		##


drawGrid(grid_values)

turn = 0

#while game_over == 0 and turn <= 5:

grid_values = getPlay(grid_values)
game_over = checkWin(grid_values)

if turn <= 4:

	### ENABLE FOR RANDOM AI
	#grid_values = cpuPlay(grid_values)

	### ENABLE FOR COMPUTER AI
	grid_values = cpuAI(grid_values)
	game_over = checkWin(grid_values)

turn += 1