RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved character sieving and noughts and crosses. (Note that this ends today.)

Task 1: Common Characters

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.

A fairly straightforward flow of logic. In JavaScript:

function commoncharacters(a) {

Set up the counter.

    let mc = new Map;
    let first = true;

Look at each string.

    for (let s of a) {

Turn it into a counted hash (utility function not included here, but it's in the full source).

        const mk = counterify(s.split(""));

First time through, make the working counter a copy of this one.

        if (first) {
            mc = mk;
            first = false;
        } else {

Otherwise, look through each key and take the minimum, reducing or deleting entries as found.

            for (let k of mc.keys()) {
                if (mk.has(k)) {
                    mc.set(k, Math.min(mc.get(k), mk.get(k)));
                } else {
                    mc.delete(k);
                }
            }
        }
    }

Now to assemble the output.

    let out = [];

Sort the keys into order.

    let kl = [...mc.keys()];
    kl.sort();

For each key…

    for (let c of kl) {

The relevant number of times…

        for (let n = 1; n <= mc.get(c); n++) {

Append the key value.

            out.push(c);
        }
    }
    return out;
}

In Rust, using the counter class lets me do intersections as a single operation, so the chunk under "Otherwise, look through each key" can be trivially replaced:

            mc = mc & mk;

Maybe that doesn't save a lot of code, but I like to shift that stuff onto someone else's code.

Task 2: Find Winner

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.

My approach is to build the board state, then check exhaustively for a winner.

Perl:

sub findwinner($a) {

Set up the empty board.

  my @board = (
    [ 0, 0, 0 ],
    [ 0, 0, 0 ],
    [ 0, 0, 0 ],
      );

We will call the first player "1".

  my $player = 1;

Iterate through the plays provided, mapping them into the board.

  foreach my $play (@{$a}) {
    $board[$play->[0]][$play->[1]] = $player;
    $player = 3 - $player;
  }

Check for possible winning rows. Each line is X base, Y base, X offset, Y offset; so the first line will generate (0, 0), (1, 0) and (2, 0).

  foreach my $pattern (
    [0, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 2, 1, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 1],
    [2, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 2, 1, -1],
      ) {

Initialise a set (a hash in Perl which doesn't have sets) to hold the values found in a given line.

    my %cellvals;

Look at the three positions along the line, and store the contents in the set.

    foreach my $i (0 .. 2) {
      my $x = $pattern->[0] + $i * $pattern->[2];
      my $y = $pattern->[1] + $i * $pattern->[3];
      $cellvals{$board[$y][$x]}++;
    }

If there is only one distinct value (i.e. all three cells had the same value):

    if (scalar keys %cellvals == 1) {

Pull out that value.

      my $winner = (keys %cellvals)[0];

If it's a valid player, return that player as the winner.

      if ($winner == 1) {
        return "A";
      } elsif ($winner == 2) {
        return "B";
      }
    }
  }

If we get to the end, we have no winner. If the board is full, call it a draw, otherwise call it pending.

  if (scalar @{$a} == 9) {
    return "Draw";
  } else {
    return "Pending";
  }
}

This algorithm does not attempt to distinguish between incomplete and winnable games as in example 4,

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

and incomplete but unwinnable games (e.g., with X to play):

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

Either type is returned as "Pending". The game is after all fairly trivial, and with players of more than elementary competence every game will be a draw anyway.

Full code on github.