Program To Create a Tic-Tac-Toe Game and Topological Sort

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.

Program to create a tic tac toe game and topological sort in python language

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

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

Instructions

Requirements and Specifications