Find winner

You are given an array of all the moves by the two players in a game of TicTacToe (otherwise known in the UK as Noughts and Crosses). Write a script to find the winner of the game, if one is found, based on the moves provided in the given array, which are those of A, B, A, B and so on.

Examples

Example 1
Input: @moves = ([0,0],[2,0],[1,1],[2,1],[2,2])
Output: A
Game Board:
[ A _ _ ]
[ _ A _ ]
[ B B A ]

Example 2
Input: @moves = ([0,0],[1,1],[0,1],[0,2],[1,0],[2,0])
Output: B
Game Board:
[ A A B ]
[ A B _ ]
[ B _ _ ]

Example 3
Input: @moves = ([0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,
   1],[0,2],[2,2])
Output: Draw
Game Board:
[ A A B ]
[ B B A ]
[ A B A ]

Example 4
Input: @moves = ([0,0],[1,1])
Output: Pending
Game Board:
[ A _ _ ]
[ _ B _ ]
[ _ _ _ ]

Example 5
Input: @moves = ([1,1],[0,0],[2,2],[0,1],[1,0],[0,2])
Output: B
Game Board:
[ B B B ]
[ A A _ ]
[ _ _ A ]

Analysis

I imagine most 5-year-olds can play this game, and it doesn't take them long to find the winning strategy if they're A or the blocking strategy if they are B. So maybe this code will be of little practical use.

There are several ways that we can represent the TicTacToe board. A 2D array is the obvious one, but a simple array, a character string or a hash are all candidates. In an effort to be original I represent the board as a 9-digit binary string - or to be precise as such a string for each player.

The string starts as 000000000 for each player, and for each play the corresponding 0 is changed to 1. I then logically AND the string with each of the 8 winning solutions, which are:

111000000, 000111000, 000000111, 100100100,
010010010, 001001001, 100010001, 001010100.

If the result of the AND is the same as the winning solution, then that player has won.

So, for example, if the board looks like this:

[ A _ A ]
[ B A B ]
[ B _ A ]

then A's string will be 101010001 which ANDs with 100010001 to give 100010001 - so A has won.

OK, that sounds rather complicated, but it works and doesn't take much code.

Solutions demonstrate strong problem-solving skills with particular excellence in the binary representation approach for Task 2, which is both computationally optimal and elegantly implemented.

This review may cover either or both challenges for this week.

Try it 

Try running the script with any input:

Your @moves =

example: [0,0], [0,1], [1,1], [1,0], [2,2]

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-08-18
use utf8;     # Week 335 - task 2 - Find winner
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

find_winner([0,0],[2,0],[1,1],[2,1],[2,2]);
find_winner([0,0],[1,1],[0,1],[0,2],[1,0],[2,0]);
find_winner([0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]);
find_winner([0,0],[1,1]);
find_winner([1,1],[0,0],[2,2],[0,1],[1,0],[0,2]);

sub find_winner {
    
    my ($input, @wins, @moves, $player, @owned, $move, $win, $output, $j, @board);
    
    # initialise
    @moves = @_;
    $player = 0;
    @owned = (0, 0);
    $board[$_] = '_' for 0 .. 8;
    
    # the 8 winning patterns
    @wins = (0b111000000, 0b000111000, 0b000000111,
             0b100100100, 0b010010010, 0b001001001,
             0b100010001, 0b001010100);
    
    # loop over moves and set player as owning the cell
    for $move (@moves) {
        $owned[$player] |= (2 ** (3 * $move->[0] + $move->[1]));
        $board[$move->[1] + 3 * $move->[0]] = chr(ord('A') + $player);
        $player = 1 - $player;
    }
    
    # check to see if this move makes a win
    for $win (@wins) {
        for $j (0, 1) {
            if (($win & $owned[$j]) == $win) {
                $output = chr(ord('A') + $j) . ' wins';
                last;
            }
        }
    }
    
    # draw if no win with 9 moves or pending id <9 moves
    $output = scalar @moves == 9 ? 'Draw' : 'Pending' unless $output;
    
    # report
    $input .= qq{[$_->[0], $_->[1]], } for @moves;
    say qq[\nInput:  ] . substr($input, 0, -2); 
    say qq[Output: $output];
    
    # show board
    say qq{        [ $board[0] $board[1] $board[2] ]\n} .
        qq{        [ $board[3] $board[4] $board[5] ]\n} .
        qq{        [ $board[6] $board[7] $board[8] ]};
}

25 lines of code

Output from script

Input:  [0, 0], [2, 0], [1, 1], [2, 1], [2, 2]
Output: A wins
        [ A _ _ ]
        [ _ A _ ]
        [ B B A ]

Input:  [0, 0], [1, 1], [0, 1], [0, 2], [1, 0], [2, 0]
Output: B wins
        [ A A B ]
        [ A B _ ]
        [ B _ _ ]

Input:  [0, 0], [1, 1], [2, 0], [1, 0], [1, 2], [2, 1],
   [0, 1], [0, 2], [2, 2]
Output: Draw
        [ A A B ]
        [ B B A ]
        [ A B A ]

Input:  [0, 0], [1, 1]
Output: Pending
        [ A _ _ ]
        [ _ B _ ]
        [ _ _ _ ]

Input:  [1, 1], [0, 0], [2, 2], [0, 1], [1, 0], [0, 2]
Output: B wins
        [ B B B ]
        [ A A _ ]
        [ _ _ A ]