Weekly Challenge: The Common Winner

Weekly Challenge 335

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Common Characters

Task

You are given an array of words.

Write a script to return all characters that is in every word in the given array including duplicates.

My solution

The task doesn't mention the order in which the list should be generated. Based on the examples, both "order they appear in the first word" and "alphabetical order" seem to be valid solutions. I've chose alphabetical order for this.

For this challenge, I've turned the supplied word_list into a list of Counters (array of hashes in Perl) of letter frequencies called freq_list.

I then iterate through each unique letter in the first word (in alphabetical order), calling the variable letter. I calculate the minimum number of occurrences of that letter in all the words. The Counter object will return 0 if the letter does not exist. If the letter occurs in all words, I append it to the solution list the required number of times.

def common_characters(word_list: list[str]) -> list[str]:
    solution = []

    freq_list = [Counter(word) for word in word_list]

    for letter in sorted(freq_list[0]):
        min_freq = min(freq[letter] for freq in freq_list)
        if min_freq > 0:
            solution.extend(letter * min_freq)

    return solution

The Perl solution follows the same logic, but generates the %freq hash by hand.

Examples

$ ./ch-1.py bella label roller
['e', 'l', 'l']

$ ./ch-1.py cool lock cook
['c', 'o']

$ ./ch-1.py hello world pole
['l', 'o']

$ ./ch-1.py abc def ghi
[]

$ ./ch-1.py aab aac aaa
['a', 'a']

Task 2: Find Winner

Task

You are given an array of all moves by the two players.

Write a script to find the winner of the TicTacToe game if found based on the moves provided in the given array.

Order move is in the order - A, B, A, B, A, ….

My solution

My sisters never liked playing Noughts and Crosses (as it is known as here) when I was young because I figured out a way to never lose. You have to remember this was a long time before the Internet was available to do research on this :-)

For this task I take the command line input and convert it into pairs of moves. I initialize the board variable with 3 × 3 grid of underscores, and the current_player variable to A.

def find_winner(moves: list[list[int]]) -> str:
    board = [['_' for _ in range(3)] for _ in range(3)]
    current_player = 'A'

I then iterate through each move, starting by ensuring the move is within the bounds of the board, and the player isn't using a position that is already used.

    for move in moves:
        if not 0 <= move[0] <= 2 and not 0 <= move[1] <= 2:
            return "Invalid move (out of bounds)"
        if board[move[0]][move[1]] != '_':
            return "Invalid move (already taken)"

I then make the move on the board, check if there is a result, and switch to the other player in preparation for the next move. If there is a result, I return the player that won.

        board[move[0]][move[1]] = current_player

        result = check_winner(board)
        if result:
            return result

        current_player = 'B' if current_player == 'A' else 'A'

If all the moves have been made, and there is no winner, I checked for any _ on the board. If there are, I return Pending, or Draw if there are none.

    return "Pending" if any('_' in row for row in board) else "Draw"

The check_winner function takes the board and sees if there is a row, column, or one diagonal that has the same letter.

def check_winner(board: list[list[str]]) -> str | None:
    for i in range(3):
        if board[i][0] == board[i][1] == board[i][2] != '_':
            return board[i][0]
        if board[0][i] == board[1][i] == board[2][i] != '_':
            return board[0][i]

    if board[0][0] == board[1][1] == board[2][2] != '_':
        return board[0][0]
    if board[0][2] == board[1][1] == board[2][0] != '_':
        return board[0][2]

    return None

The Perl solution follows the same logic as the Python one.

Examples

$ ./ch-2.py 0 0 2 0 1 1 2 1 2 2
A

$ ./ch-2.py 0 0 1 1 0 1 0 2 1 0 2 0
B

$ ./ch-2.py 0 0 1 1 2 0 1 0 1 2 2 1 0 1 0 2 2 2
Draw

$ ./ch-2.py 0 0 1 1
Pending

$ ./ch-2.py 1 1 0 0 2 2 0 1 1 0 0 2
B