| 22 August 2025 | Challenge 335 |
Common Tics and Toes
Task 1: Common Characters
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @words = ("bella", "label", "roller")
Output: ("e", "l", "l")
Example 2
Input: @words = ("cool", "lock", "cook")
Output: ("c", "o")
Example 3
Input: @words = ("hello", "world", "pole")
Output: ("l", "o")
Example 4
Input: @words = ("abc", "def", "ghi")
Output: ()
Example 5
Input: @words = ("aab", "aac", "aaa")
Output: ("a", "a")
Solution
Split each word into single characters and build multisets (aka bags) thereof. Then intersect all multisets and replicate the remaining characters according to their multiplicity.
use strict;
use warnings;
use Set::Bag;
use List::MoreUtils 'frequency';
use List::Util qw(reduce pairmap);
sub common_chars {
pairmap {($a) x $b} (
reduce {$a & $b} map Set::Bag->new(frequency split //), @_
)->grab;
}
See the full solution to task 1.
Task 2: Find Winner
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @moves = ([0,0],[2,0],[1,1],[2,1],[2,2])
Output: A
Game Board:
[ A _ _ ]
[ B A B ]
[ _ _ A ]
Note: The moves and the resulting board do not agree for B.
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 ]
Solution
Using a 3x3 matrix as the grid with 0 representing a free space, 1 a space marked by player A and 4 a space marked by player B.
The sum over three elements is 3 if and only if all three elements are 1 and the sum is 12 if and only if all three elements are 4.
I’m going to explain the solution in the PDL
shell using example 2 as input.
Right after defining some constants, starting with the most complex part of the solution: Create an 2x3x8 ndarray holding the coordinates of all rows, columns, the diagonal and the anti-diagonal of a 3x3 matrix. Calling any of these a line in the following.
This ndarray needs to be build only once and can be reused afterwards.
pdl> use constant N => 3
pdl> use Constant::Generate {A => 1, B => N + 1}, dualvar => 1
pdl> do_print 1
1
pdl> $rows = ndcoords indx, N, N
[
[
[0 0]
[1 0]
[2 0]
]
[
[0 1]
[1 1]
[2 1]
]
[
[0 2]
[1 2]
[2 2]
]
]
pdl> $lines = $rows->glue(2, $rows(-1:0)->sever,
> $rows->diagonal(1, 2)->sever, $rows(,-1:0)->diagonal(1, 2)->sever)
[
[
[0 0]
[1 0]
[2 0]
]
[
[0 1]
[1 1]
[2 1]
]
[
[0 2]
[1 2]
[2 2]
]
[
[0 0]
[0 1]
[0 2]
]
[
[1 0]
[1 1]
[1 2]
]
[
[2 0]
[2 1]
[2 2]
]
[
[0 0]
[1 1]
[2 2]
]
[
[2 0]
[1 1]
[0 2]
]
]
Using $lines as an argument to
indexND
on a 3x3 ndarray produces a 3x8 ndarray of all lines.
Visualizing this on a sequence matrix:
pdl> $s = sequence N, N
[
[0 1 2]
[3 4 5]
[6 7 8]
]
pdl> $s->indexND($lines)
[
[0 1 2]
[3 4 5]
[6 7 8]
[0 3 6]
[1 4 7]
[2 5 8]
[0 4 8]
[2 4 6]
]
Now pick the moves from the example:
pdl> $moves = indx [0,0],[1,1],[0,1],[0,2],[1,0],[2,0]
[
[0 0]
[1 1]
[0 1]
[0 2]
[1 0]
[2 0]
]
Create an empty grid:
pdl> $board = zeroes long, N, N
[
[0 0 0]
[0 0 0]
[0 0 0]
]
Select the elements specified by the moves and fill in the values for A and B alternately.
pdl> $board->indexND($moves) .= long(A, B)->range(0, $moves->dim(1), 'p')
[1 4 1 4 1 4]
pdl> $board
[
[1 1 4]
[1 4 0]
[4 0 0]
]
Select $lines from the grid and take the row sums.
This shows the occupation in each line:
pdl> $sum = $board->indexND($lines)->sumover
[6 5 4 6 5 4 5 12]
To extract the winner from the sums, these are intersected with the winning sums:
pdl> setops($sum, 'AND', N * long(A, B)) / N
[4]
Here B (corresponding to 4) is the winner.
If there is no winner, we need to check if all spaces are filled. With a free space the game is pending and otherwise it’s a draw.
Put everything together:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
use constant N => 3;
use Constant::Generate {A => 1, B => N + 1}, dualvar => 1;
{
my $lines;
BEGIN {
my $rows = ndcoords indx, N, N;
$lines = $rows->glue(2, $rows(-1:0)->sever,
$rows->diagonal(1, 2)->sever,
$rows(,-1:0)->diagonal(1, 2)->sever);
}
sub tictactoe {
my $moves = indx @_;
my $board = zeroes long, N, N;
$board->indexND($moves) .= long(A, B)->range(0, $moves->dim(1), 'p');
die "overwritten" if which($board)->nelem < $moves->dim(1);
my $winner = setops(
$board->indexND($lines)->sumover, 'AND', N * long(A, B)
) / N;
die "post-final move" if $winner->nelem > 1;
return $board->all ? "Draw" : "Pending" if $winner->isempty;
$winner == A ? A : B; # return dual-valued constant
}
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.