# Create A Tic-Tac-Toe Game and Topological Sort in Python Assignment Solution.

## Instructions

Objective
Write a program to create a tic-tac-toe game and topological sort in python.

## Requirements and Specifications

Exercise 1: Tic-tac-toe
Please write a Python program that plays tic-tac-toe against a human player. The program will have a single entry point function called tic_tac_toe which, when called from a Python terminal (or from a standalone python script) will display a blank tic-tac-toe board, and invite the user to choose a square to place his/her first move. The program will plot the user’s move and then counter with a move of its own. This cycle will repeat until either the player or the computer wins (or draws).
Exercise 2: Topological sort
Please write a standalone Python function that performs a topological sort (or “top sort” for short) on arbitrary graph like input data.

Source Code

```TIC-TAC-TOE import random import time class TicTacToe:     """     Class, representing single TicTacToe game     """     def __init__(self):         """         Instance constructor         """         self.symbols = [' ', 'o', 'x']         self.grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]         self.is_over = 0     def show(self):         """         Method, outputting current game state to the console         :return: None         """         print()         print(' 1 2 3')         print('1', self.symbols[self.grid[0][0]], '|', self.symbols[self.grid[0][1]], '|',               self.symbols[self.grid[0][2]], sep ='')         print(' -+-+-')         print('2', self.symbols[self.grid[1][0]], '|', self.symbols[self.grid[1][1]], '|',               self.symbols[self.grid[1][2]], sep='')         print(' -+-+-')         print('3', self.symbols[self.grid[2][0]], '|', self.symbols[self.grid[2][1]], '|',               self.symbols[self.grid[2][2]], sep='')     def update_state(self):         """         Method for updating current game state         :return: 0 - game is not over; 1 - player 1 won; 2 - player 2 won; 3 - draw         """         # checking rows         for i in range(3):             curr = self.grid[i][0]             if curr > 0:                 matches = True                 for j in range(3):                     if curr != self.grid[i][j]:                         matches = False                         break                 if matches:                     self.is_over = curr                     return         # checking columns         for i in range(3):             curr = self.grid[0][i]             if curr > 0:                 matches = True                 for j in range(3):                     if curr != self.grid[j][i]:                         matches = False                         break                 if matches:                     self.is_over = curr                     return         # checking diagonals         curr = self.grid[0][0]         if curr > 0:             matches = True             for j in range(3):                 if curr != self.grid[j][j]:                     matches = False                     break             if matches:                 self.is_over = curr                 return         curr = self.grid[2][0]         if curr > 0:             matches = True             for j in range(3):                 if curr != self.grid[2-j][j]:                     matches = False                     break             if matches:                 self.is_over = curr                 return         # checking if whole grid is filled         count = 0         for i in range(3):             for j in range(3):                 if self.grid[i][j] > 0:                     count += 1         if count == 9:             self.is_over = 3         else:             self.is_over = 0     def make_comp_move(self, player):         """         Method for making computer move         :param player: number of player to move         :return: None         """         print('My move, thinking')         time.sleep(1)         # keep iterating until correct move is randomly generated         while True:             i = random.randint(0, 8)             r = i // 3             c = i % 3             if self.grid[r][c] == 0:                 self.grid[r][c] = player                 self.update_state()                 return             time.sleep(1)     def make_user_move(self, player):         """         Method for making user move         :param player: number of player to move         :return: None         """         # keep iterating until correct move is inputted by user         while True:             parts = input('Your move: ').split()             if len(parts) != 2:                 print('Invalid input')                 continue             try:                 r = int(parts[0])                 c = int(parts[1])                 if 1 <= r < 4 and 1 <= c < 4 and self.grid[r-1][c-1] == 0:                     self.grid[r-1][c-1] = player                     self.update_state()                     break                 else:                     print('Invalid input')             except:                 print('Invalid input')     def get_state(self):         """         Getter for is_over field         :return: current game state         """         return self.is_over def tic_tac_toe():     """     Method for playing single tic tac toe game with user as player 1 and computer as player 2     :return: None     """     ttt = TicTacToe()     current_player = 1     while ttt.get_state() == 0:         ttt.show()         if current_player == 1:             ttt.make_user_move(current_player)         else:             ttt.make_comp_move(current_player)         current_player = 3 - current_player     state = ttt.get_state()     if state == 1:         print('User WON')     elif state == 2:         print('Computer WON')     else:         print('DRAW') if __name__ == '__main__':     tic_tac_toe() TOPOLOGICAL SORT def top_sort(keys, dependencies_fn):     """     Perform topological sort of some directed acyclic graph     Arguments:     keys –     list of (hashable) objects representing nodes of the graph     dependencies_fn –     function taking a key and returning a list of dependencies     Returns:     List of keys in top sort order     """     # final sorted list     result = []     # keep iterating until keys list contains unsorted values     while len(keys) > 0:         next_key = None         # searching for next key to extract         for key in keys:             # key to extract must have no dependencies             if len(dependencies_fn[key]) == 0:                 next_key = key                 break         if next_key:             # removing extracted key from all dependencies             for kk in dependencies_fn:                 if next_key in dependencies_fn[kk]:                     dependencies_fn[kk].remove(next_key)             # removing extracted key from key list             result.append(next_key)             keys.remove(next_key)         else:             raise ValueError('Not Sortable')     return result if __name__ == '__main__':     graph = {         'A': [],         'B': ['A', 'D'],         'C': [],         'D': ['C', 'E'],         'E': [],         'F': ['B', 'G'],         'G': ['I'],         'H': [],         'I': ['H']     }     # calling top sort for graph key list and graph itself     print(top_sort(list(graph.keys()), graph))```