Day 4 of Advent of Code has us playing bingo against a giant squid. (Don't ask; I don't understand it either.) More specifically, we want to take an input file that consists of a series of numbers that will get called, followed by a series of boards. We then need to compute which board will be the first to win, following the standard rules of bingo (although with no free space in the middle, the cheating squid...).
This sort of problem is inherently very stateful, and thus, frankly, not a good fit for functional code. It absolutely can be done in a functional way, but it's not the best fit. We're not interested in the best fit in this series, though, just how it could be done functional-style. So let's do it functional style just to say we did. Along the way we will really exercise the function composition concept, and show a few other tricks along the way.
Onwards!
Parsing the problem
There's two main chunks to this problem: Parsing the input data and then running the game. We'll tackle those separately.
For reference, the input file looks like this, only way bigger:
7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1
22 13 17 11 0
8 2 23 4 24
21 9 14 16 7
6 10 3 18 5
1 12 20 15 19
3 15 0 2 22
9 18 13 17 5
19 8 7 25 23
20 11 10 24 4
14 21 16 12 6
14 21 17 24 4
10 16 15 9 19
18 8 23 26 20
22 11 13 6 5
2 0 12 3 7
First, we need to parse the input file. As previously noted, parsing is a crazy complicated subject. In the ideal case, we'd read the data in as a stream, collecting data until we had enough to form a board, then emitting a board lazily as needed. However, functional stream processing is a tricky business, especially in a language like PHP that has no native support for it. While possible to do, I opted instead to read the whole file at once and treat it as a string to get mapped into the data structure we want. It's less elegant, but was easier to write. (Maybe a future challenge will offer us an opportunity to get fancy; we'll see.)
This challenge has the most moving parts to date, so let's start off by defining our data model. We want some structure to represent the whole input. The input consists of a sequence of plays plus a collection of boards. Sounds like this:
class Game
{
public function __construct(
public readonly array $plays,
/** Board[] */
public readonly array $boards,
) {
}
}
Each board consists of a 2D array of values, as well as a 2D array of which places have been "marked." Let's start that off like this:
class Board
{
/** @var bool[][] */
protected readonly array $marked;
public function __construct(
public readonly array $numbers,
) {
$line = array_fill(0, 5, false);
$this->marked = array_fill(0, 5, $line);
}
}
The board always starts with nothing marked, so that's not a constructor argument, just an internal value.
Now we can try to parse the incoming data into those objects. This is a bit involved, so let's wrap it into its own function.
function parseInstructions(string $inputFile): Game
{
$data = pipe($inputFile,
file_get_contents(...),
explode(PHP_EOL),
);
$plays = pipe($data[0],
explode(','),
amap(trim(...)),
amap(intval(...)),
);
$boards = pipe($data,
fn(array $data): array => array_slice($data, 1),
extractBoardData(...),
amap(makeBoard(...)),
);
return new Game($plays, $boards);
}
First, we read in the data all at once using file_get_contents() and split it by line. The first line is the list of numbers that will get called, so the second statement pulls off the first line, breaks it up by commas, trims it, and casts everything to an int. That should be all fairly fairly mundane by now.
The board parsing is where it gets tricky. Starting from the same data, we skip over the first line to get just the board data. Then we call extractBoardData() on what's left, which will get to in a moment. It returns an array of the initial board states of each board, which are themselves arrays. All of these arrays are horribly ugly; the next step takes that collection of board states and makes them into Board objects. Then we create a Game object with the play list and board list. Pretty elegant.
makeBoard() is trivially simple:
function makeBoard(array $numbers): Board
{
return new Board($numbers);
}
We could also have just inlined it as an anonymous function if we wanted. Either works.
extractBoardData() is a bit more interesting. The input data has newlines between each board, and also has normalized spacing. That means we cannot simply explode() our input on a space, because that will result in extra values where there are two spaces.
However, we can rely on the knowledge that board are always 5x5, so we can ignore the newlines. We can also use preg_split() instead of explode(), which is more powerful and flexible. That gives us this:
function extractBoardData(array $input): array
{
return pipe($input,
afilter(),
amap(explodeBoardLine(...)),
fn(array $in): array => array_chunk($in, 5),
);
}
function explodeBoardLine(string $line): array
{
return pipe($line,
trim(...),
static fn ($line) => preg_split("/\s+/", $line),
amap(intval(...)),
);
}
First, we filter out any blank lines. Then we take each line and break it up into an array using preg_split(), and force all of the values to integers. That gives us a huge 2D array of boards. Since we know a board is 5 lines, PHP's array_chunk() function takes that one big array and breaks it up into an array of arrays (yes, now a 3D array, it's gross), each of which is a 5x5 grid. And... that's exactly what makeBoard() wants, so we're done.
We now have our parsed game state. Not too hard, once you wrap your head around it.
Structuring the solution
There's more state we are going to need in order to compute the game, but we'll get there in a moment. First, let's think about how we are going to handle playing at all. Since the game state is immutable, each play step is going to have to produce a new, modified game state. That is, we're going to apply a "do next step" operation to the state, and get a new state. And keep doing that until one of the boards wins.
I was really tempted to use a state monad here, but decided against it. Since this is a loop of indeterminate length, that would be possible but require being wrapped in a while loop. (Maybe a fewer challenge will give us that opportunity.) The next thought is to use a reduction: We reduce across all the plays, giving each step a game state and a play to make, then producing a game state. That's very tempting, but the reduce() we've seen plays through the whole list of plays; it doesn't stop when a board wins. What we want is an operation that will reduce "until" some condition is met, or "while" some condition is met. (Those are the same thing, just inverses.)
Turns out, some languages like Elixir have a function called reduce_while for exactly that sort of situation. PHP does not, but that doesn't stop us from writing one.
function reduceUntil(mixed $init, callable $c, callable $stop): callable
{
return static function (iterable $it) use ($init, $c, $stop): mixed {
foreach ($it as $v) {
$init = $c($init, $v);
if ($stop($init)) {
return $init;
}
}
return $init;
};
}
This is nearly identical to the pipe-able reduce() we've been using; the only difference is the new $stop argument, which is called after every iteration. If it returns true, the operation stops and we return the value at that point. (We could also have made reduceWhile() and passed in a $keepGoing callback. Either is equally capable.)
Fun aside: It looks an awful lot like the StoppableInterface::isPropagationStopped() operation out of PSR-14, the Event Dispatcher interface, doesn't it...
In any event (no pun intended), we now have a way to walk our game state until some win condition is met. Now we need the reducing operation that represents a single game "step".
We're going to use the with() method we saw in an earlier exercise for both the Game and Board objects. Since it's the same for both, we'll put it into a trait and use it in both. That lets us set state for the next iteration without having to go through the constructor, which we need to keep clean for the initial parsing.
Let's write our idealized next-step reducing function, then we can fill in the bits needed to make it work. (It took a bit of experimentation to get here that I'm skipping over for clarity and time.)
function gameStep(Game $game, int $next): Game
{
$markBoard = static fn (Board $board) => $board->play($next);
$newBoards = array_map($markBoard, $game->boards);
$winner = first(static fn (Board $b) => $b->won)($newBoards);
return $game->with(
lastPlay: $next,
boards: $newBoards,
winner: $winner,
);
}
The first stanza calls play() on each board with the next value, so the board can be marked with any matches. The second checks to see if any of the boards are "won." The third just creates a new Game with the value just played, the new boards, and the winner if any.
But first!
Wait, what's that first() call? first() is another common functional operation that does not exist in PHP, but is easy enough to implement ourselves. The version in Crell/fp is designed to be piped, but can be used standalone by just calling the return value directly as here. first() is kinda similar to the reduceWhile() function, in that it iterates until some callback is true. Specifically, it passes each value in turn to the checking function, and if that function returns true, that's the value we want. If none succeed, it returns null.
function first(callable $c): callable
{
return static function (iterable $it) use ($c): mixed {
foreach ($it as $k => $v) {
if ($c($v, $k)) {
return $v;
}
}
return null;
};
}
Finish the game
That gameStep() function implies a lot of additional functionality on the Game and Board classes, so let's go ahead and add that, starting with Board as it's simplier.
All we need on Board is two additional properties: $lastPlay and $winner. However, in order to clone properly with with() they need to have initialized values. We cannot set defaults on readonly properties, but we can set them in the constructor. Our final Game looks like this:
class Game
{
use Evolvable;
public readonly int $lastPlay;
public readonly bool $done;
public readonly ?Board $winner;
public function __construct(
public readonly array $plays,
/** Board[] */
public readonly array $boards,
) {
$this->winner = null;
$this->lastPlay = -1;
}
}
(Evolvable is a trait that includes the with() method we saw in a previous challenge.)
Feeling board
Board is a bit more involved. We know there's now a play() method, so let's implement that first.
public function play(int $num): static
{
foreach ($this->numbers as $i => $line) {
foreach ($line as $j => $cell) {
if ($cell === $num) {
return $this->mark($i, $j);
}
}
}
return $this;
}
There's really no fancy logic going on here; we just brute-force through the data and see if any are a match. If not, return the board unmodified. If there is, mark the board at that coordinate. OK, so what is mark()?
public function mark(int $i, int $j): static
{
$marked = $this->marked;
$marked[$i][$j] = true;
$won = $marked[$i] === self::WinRow || array_column($marked, $j) === self::WinRow;
return $this->with(
marked: $marked,
won: $won,
);
}
We cannot modify the grid of marks directly, of course, so make a new one and mark that new one. Then return the current board, but with the new list of marked values. But first, we check to see if the board is now in a "won" state. It's been won if there is a row that is all marked, or a column that is all marked. We know no row or column could have just changed to a win state if it's not the row or column we're actively modifying, so we need check only that. The easiest way to check is to just compare the row vs a pre-made constant array of all true, or the column against the same constant. So we need two additional values on the class, a $won boolean and the constant.
class Board
{
use Evolvable;
/** @var bool[][] */
protected readonly array $marked;
const WinRow = [true, true, true, true, true];
public readonly bool $won;
public function __construct(
public readonly array $numbers,
) {
$line = array_fill(0, 5, false);
$this->marked = array_fill(0, 5, $line);
$this->won = false;
}
// ...
}
And done.
Run away!
With all of our pieces now assembled, running the game is trivial:
$game = parseInstructions($inputFile);
$done = pipe($game->plays,
reduceUntil($game, gameStep(...), static fn (Game $game): bool => (bool)$game->winner),
);
We start by parsing our initial game state out of the input. Then we reduce across the $plays list (which is carried along with every game object, but thanks to PHP's copy-on-write behavior we don't care), applying the gameStep() to each play to produce a new game state. And we keep doing that until there is a non-null $winner on the game, at which point we're $done. We can now compute the winning "score". According to the instructions the score is the sum of all non-marked spaces on the board, multiplied by the number that won the board. (This is a very silly game.)
We have the data we need, so let's put that computation into the Board: print $done->winner->score($done->lastPlay) . PHP_EOL;
The score() method is a little interesting. Let's show it first, then break down the pieces it needs.
public function score(int $lastPlay): int
{
$sum = pipe($this->marked,
flatten(...),
amap(static fn (bool $is): bool => !$is),
fn ($marks) => array_combine(flatten($this->numbers), $marks),
afilter(),
array_keys(...),
array_sum(...),
);
return $sum * $lastPlay;
}
We need to get all of the unmarked numbers. We could double-iterate the list, again, then check its corresponding marked coordinate, then keep a running total... but what fun is that?
Instead, we'll flatten() both arrays to a sigle linear array. We no longer care about the coordinates, just that they match up, so that makes it easier. flatten() is another simple utility, common in functional languages but we can make it ourselves in PHP. Here's the version out of Crell/fp:
function flatten(array $arr): array
{
$flat = [];
array_walk_recursive($arr, static function ($v) use (&$flat) {
$flat[] = $v;
});
return $flat;
}
It's really just piggybacking on PHP's built-in array walker and building up a flat list. Works for me.
So we first flatten the marked list. Then we invert it; we want to keep the UNmarked values, so by negating each entry we get a list of true for the values we want to keep. Then we flatten the board data itself, and array_combine() it with the marks. The result is a list of numbers from the board as keys with true or false as values. We can then afilter() that list to get just the ones whose value are true, then use array_keys() to get back the keys whose values were true. Then array_sum() them up, and multiply that with the $lastPlay.
It's a bit clever, but works pretty well and is nicely pipe-friendly.
A lose-lose situation
The second part wants us to let the giant squid win. (It must be related to Wookies.) That means finding the board that is last to win.
As usual, let's see if we can reframe the problem. To get to the last winner, we need to find the earlier winners first. So really, what we want is to find all winners, then compute the score of the last one. So how do we find all winners?
The changes here are subtle. None of the initial parsing changes, so we can ignore that. What does change is that the Game no longer tracks which one board has one, but a list of winning boards, in the order they won.
class Game
{
use Evolvable;
public readonly int $lastPlay;
public readonly bool $done;
/** @var Board[] */
public readonly array $winners;
public function __construct(
public readonly array $plays,
/** Board[] */
public readonly array $boards,
) {
$this->winners = [];
$this->lastPlay = -1;
}
}
Next, we need to update gameStep() to track multiple winners. The definition of winning hasn't changed.
function gameStep(Game $game, int $next): Game
{
$markBoard = static fn (Board $board) => $board->play($next);
$newBoards = array_map($markBoard, $game->boards);
$newWinners = array_filter($newBoards, static fn (Board $b) => $b->won);
$remainingBoards = array_diff($newBoards, $newWinners);
return $game->with(
lastPlay: $next,
boards: $remainingBoards,
winners: [...$game->winners, ...$newWinners],
);
}
Now, instead of one winner, we check any remaining boards for $won status. Any boards that are done we can then exclude from future iterations. Then we save the new remaining boards and the updated list of winning boards to the next game state.
There's one last bit of machinery we need here. array_diff() returns all elements of its first argument that are not found in its subsequent arguments... when comparing those arguments as arrays of strings. But our lists are arrays of objects. Drat.
Fortunately, PHP allows objects to have their own string representation, which is close-enough to a string for array_diff(). We could make it anything, but for convenience we'll make it just the concatenation of all numbers on that board, in order.
class Board implements Stringable
{
// ...
public readonly string $identifier;
public function __construct(
public readonly array $numbers,
) {
// ...
$this->identifier = $this->stringify();
}
protected function stringify(): string
{
return pipe($this->numbers,
flatten(...),
implode(''),
);
}
public function __toString(): string
{
return $this->identifier;
}
// ...
}
Now array_diff() works. That means we can modify the main routine like so:
$done = pipe($game->plays,
reduceUntil($game, gameStep(...), fn(Game $game):bool => count($game->boards) === 0),
);
$loser = $done->winners[array_key_last($done->winners)];
print $loser->score($done->lastPlay) . PHP_EOL;
Fin.
Today's challenge has been a lot of code, so I definitely recommend checking out the full code on GitHub. I'll see you back here for the next one.
Want to know more about functional programming and PHP? Read the whole book on the topic: Thinking Functionally in PHP.
Congratulations @crell! You have completed the following achievement on the Hive blockchain and have been rewarded with new badge(s):
Your next target is to reach 80 posts.
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPTo support your work, I also upvoted your post!
Check out the last post from @hivebuzz: