Tic Tac Toe - For Recurse Pair Interview

tic_tac_toe.py

"""
Before your interview, write a program that lets two humans play a game of Tic Tac Toe
in a terminal. The program should let the players take turns to input their moves. The
program should report the outcome of the game.

During your interview, you will pair on adding support for a computer player to your
game. You can start with random moves and make the AI smarter if you have time.

---

devlog:

stuff we'll need
- representation of game state
- user input
- win state checking
- display
- game flow

game state:
- 3x3 grid, 3 states each (X,O,blank)
- could explicitly represent full grid, or represent only filled coordinates
- my default would be to explicitly represent full grid, so let's instead try
  representing only filled for fun
- let's do a map. so:
    - empty map = empty grid
    - otherwise we'll have 0-based coordinates 0,1,2
    - let's do (row, col) coordinate system
    - let's say player 1 = 0 = X, and player 2 = 1 = 0

display
- seems reasonable to do next, so we can just make board states and print them
- fancy would be to erase screen and redraw, but I probably need a library (to work
  with... ncurses?) so just going to print each time instead
- let's sketch out a board to see general counts, ascii art time

-------------
| X | O |   |
|---+---+---|
| X | O |   |
+---+---+---+
|   |   | X |
-------------

win state checking
- did next as natural once we have and can display board state

game flow and user input seem natural to do next together.
"""

from collections import Counter
from typing import Literal, Optional  # , Counter as tCounter

Board = dict[tuple[int, int], int]


def display(board: Board) -> None:
    """Prints the board like this (0 = X, 1 = 'O'):

    -------------
    | X | O |   |
    |---+---+---|
    | X | O |   |
    +---+---+---+
    |   |   | X |
    -------------
    """
    end = "-------------"
    sep = "|---+---+---|"

    print(end)
    for row in range(3):
        buf = []
        for col in range(3):
            symbol = " "
            if (row, col) in board:
                symbol = "X" if board[(row, col)] == 0 else "O"
            buf.append(symbol)
        print(f"| {' | '.join(buf)} |")
        if row < 2:
            print(sep)
    print(end)


def test_display() -> None:
    empty: Board = {}
    display(empty)

    partial: Board = {(0, 0): 0, (0, 1): 1, (1, 0): 0, (1, 1): 1, (2, 2): 0}
    display(partial)


def result_v1(board: Board) -> Optional[int]:
    """NOTE: old (correct but unused) version with redundant logic. improved below.

    Returns:
    - the player who has won (0 or 1) if there's a winner
    - -1 if there's a draw (full board and no winner)
    - None no winner and still empty slots

    No smart lookahead draw detection, just full board detection.
    """
    # check whether any row, col, or diagonal filled with one player's marks
    # check rows
    for row in range(3):
        tally: Counter[int] = Counter()
        for col in range(3):
            if (row, col) in board:
                tally[board[(row, col)]] += 1
        if len(tally) > 0 and tally.most_common()[0][1] == 3:
            return tally.most_common()[0][0]
    # check cols
    for col in range(3):
        tally: Counter[int] = Counter()
        for row in range(3):
            if (row, col) in board:
                tally[board[(row, col)]] += 1
        if len(tally) > 0 and tally.most_common()[0][1] == 3:
            return tally.most_common()[0][0]
    # check diagonals
    diagonals = [[(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)]]
    for diagonal in diagonals:
        tally: Counter[int] = Counter()
        for coord in diagonal:
            if coord in board:
                tally[board[coord]] += 1
        if len(tally) > 0 and tally.most_common()[0][1] == 3:
            return tally.most_common()[0][0]

    # at this point, full board = draw
    if len(board) == 9:
        return -1

    # at this point, no winner and not full board, so just game in progress
    return None


def result(board: Board) -> Optional[int]:
    """Returns:
    - the player who has won (0 or 1) if there's a winner
    - -1 if there's a draw (full board and no winner)
    - None no winner and still empty slots

    No smart lookahead draw detection, just full board detection.
    """
    # check whether any row, col, or diagonal filled with one player's marks.
    # pre-generate coordinates of all lines, then check each one.
    lines = (
        [[(row, col) for col in range(3)] for row in range(3)]  # rows
        + [[(row, col) for row in range(3)] for col in range(3)]  # cols
        + [[(i, i) for i in range(3)]]  # diagonal: tl to br
        + [[(i, 2 - i) for i in range(3)]]  # diagonal: tr to bl
    )
    for line in lines:
        # print("line:", line)  # uncomment to verify above list nesting
        tally = [board.get(coord) for coord in line]  # will be 0, 1, or None
        # a winning tally has 3 non-None entries that are all the same, so same as first
        if tally[0] is not None and all(mark == tally[0] for mark in tally):
            return tally[0]

    # at this point, full board = draw
    if len(board) == 9:
        return -1

    # at this point, no winner and not full board, so just game in progress
    return None


def test_result() -> None:
    empty: Board = {}
    display(empty)
    print("want None, got", result(empty), "\n")

    partial: Board = {(0, 0): 0, (0, 1): 1, (1, 0): 0, (1, 1): 1, (2, 2): 0}
    display(partial)
    print("want None, got", result(partial), "\n")

    p1woncol: Board = {(0, 0): 0, (0, 1): 1, (1, 0): 0, (1, 1): 1, (2, 0): 0}
    display(p1woncol)
    print("want 0, got", result(p1woncol), "\n")

    p2wonrow: Board = {
        (0, 0): 0,
        (0, 1): 1,
        (0, 2): 0,
        (1, 0): 1,
        (1, 1): 1,
        (1, 2): 1,
        (2, 0): 0,
    }
    display(p2wonrow)
    print("want 1, got", result(p2wonrow), "\n")

    p1wondiag: Board = {
        (0, 0): 0,
        (0, 1): 1,
        (0, 2): 0,
        (1, 1): 0,
        (2, 2): 0,
    }
    display(p1wondiag)
    print("want 0, got", result(p1wondiag), "\n")

    draw: Board = {
        (0, 0): 0,
        (0, 1): 1,
        (0, 2): 0,
        (1, 0): 0,
        (1, 1): 1,
        (1, 2): 0,
        (2, 0): 1,
        (2, 1): 0,
        (2, 2): 1,
    }
    display(draw)
    print("want -1, got", result(draw), "\n")


def player2mark(player: int) -> Literal["X"] | Literal["O"]:
    """Returns 'X'/'O' from 0-based player in [0, 1]"""
    return "X" if player == 0 else "O"


def player_input(board: Board, player: int) -> tuple[int, int]:
    """Returns coordinate of player's input.

    NOTE: player (0-based) just used for display not logic, could be removed into prompt
    """
    while True:
        print(
            "Input move in coordinates 1 through 9 (row 1: 1 2 3, row 2: 4, 5, 6, row 3: 7, 8, 9"
        )
        raw = input(f"Player {player + 1}'s turn ({player2mark(player)})> ")
        try:
            if int(raw) < 1 or int(raw) > 9:
                raise ValueError()
        except:
            print(f"Error: bad input ({raw}), input number in 1 through 9")
            continue

        # at this point should have number 1--9, shift 0--8 and turn into coordinate
        n = int(raw) - 1
        row = n // 3
        col = n % 3
        if (row, col) in board:
            print(
                f"Error: chosen slot ({raw}) already filled ({player2mark(board[(row, col)])})"
            )
            continue

        return (row, col)


def test_stuff() -> None:
    """Alternative main() to check functions in development"""
    test_display()
    test_result()


def main() -> None:
    """Plays 1 game of tic tac toe."""
    board: Board = {}
    player = 0
    while True:
        # we display board and check the result at the beginning of each loop. this is a
        # bit counter-intuitive because playing a move ends a loop, and the move's
        # result is checked on the next iteration. but it's satisfying to always see the
        # board, before the game starts and after someone won, and we can do it once
        # here.

        print("Current board:")
        display(board)

        state = result(board)
        if state is not None:
            # game-ending state reached
            if state >= 0:
                print(f"Player {state + 1} ({player2mark(state)}) wins!")
            if state == -1:
                print("Draw!")
            break

        # otherwise, we play
        coord = player_input(board, player)
        board[coord] = player
        player = (player + 1) % 2
        print("")


if __name__ == "__main__":
    # test_stuff()
    main()