extends Node
## Text-based tic-tac-toe simulation
##
## Randomly determine a legal move for a game of tic-tac-toe until
## either (1) x wins, (2) o wins, or (3) the game ends in a tie.

## Denotes X
const X_MOVE = "X"
## Denotes O
const O_MOVE = "O"
## Denotes a square where a play has not yet been made.
const EMPTY_MARK = " "
## Dimension of tic-tac-toe board
const DIMENSION = 3
## Tic-Tac-Toe board representation
var tic_tac_toe: Array


## Create a new tic-tac-toe board.
func _init() -> void:
	tic_tac_toe = new_game()
	

## Simulate one game of tic-tac-toe.
func _ready() -> void:
	simulate_game(tic_tac_toe)


## Create an empty tic-tac-toe board.
func new_game() -> Array:
	# tic-tac-toe board, a 2D array
	var board: Array = []
	for row in range(DIMENSION):
		board.append([])
		for col in range(DIMENSION):
			board[row].append(EMPTY_MARK)
	return board


## Create a printing representaitno of the tic-tac-toe board.
func board_representation(board) -> String: 
	# The entire board
	var game: String = ""
	# The row separator, e.g. "---+---+---"
	var separator: String = ""
	
	for n in DIMENSION:
		separator += "---+"
	separator = separator.substr(0, separator.length() - 1) + "\n"
	
	for row in board:
		var line = " "
		for col in row:
			line += col + " | "
		game += line.substr(0, line.length() - 2) + "\n" + separator
		
	return(game.substr(0, game.length() - DIMENSION*4) + "\n")
	
	
## Find a random empty space to make the next play.
func one_play(board, player) -> void:
	# Candidate row
	var x: int = randi() % DIMENSION
	# Candidate column
	var y: int = randi() % DIMENSION
	
	while (board[x][y] != EMPTY_MARK):
		x = randi() % DIMENSION
		y = randi() % DIMENSION
	board[x][y] = player
	
	
## Determine whether the player who made the last move has won on a specific line.
func line_won(board, x_start, x_inc, y_start, y_inc, player) -> bool:
	# Number of squares in a row for the player
	var count: int = 0
	# The current row to check
	var x: int = x_start
	# The current column to check
	var y: int = y_start
	
	for n in DIMENSION:
		if board[x][y] == player:
			count += 1
		x += x_inc
		y += y_inc
	return (count == DIMENSION)
	
	
## Determine whether the player who made the last move has won the game.
func game_won(board, player) -> bool:
	for n in DIMENSION:
		if line_won(board, n, 0, 0, 1, player):    # test row
			return true
		if line_won(board, 0, 1, n, 0, player):    # test column
			return true
			
	# test diagonals
	if line_won(board, 0, 1, 0, 1, player) or line_won(board, DIMENSION-1, -1, 0, 1, player):   #test diagonals
		return true
		
	return false    # no one has won
	
	
## Simulate one game of tic-tac-toe.
func simulate_game(board) -> void:
	# The total number of Xs and Os played
	var moves: int = 0
	# The player to move next
	var player: String = O_MOVE
	
	print(board_representation(board))
	
	# Play one game
	while (not game_won(board, player)) and (moves < DIMENSION * DIMENSION):
		player = X_MOVE if player == O_MOVE else O_MOVE
		one_play(board, player)
		moves += 1
		print(board_representation(board))
		
	# Determine outcome of game
	if game_won(board, player):
		if player == X_MOVE:
			print("X wins!")
		else:
			print("O wins!")
	else:
		print("Cat's Game")