Advent of Code 2022 — Day 5
This is the fifth article in the series where I share my solutions to the puzzles from the Advent of Code 2022. This year I am using PHP and created a platform for comfortable development. You can find more details about the platform here and feel free to use it.
Before you start reading, I encourage you to try to solve the puzzle by yourself.
Supply Stacks
Before the expedition can launch the final batch of supplies is waiting for unloading from the ship. On the ship there are stacks of marked crates with supplies, however, they are not in the required order and thus need to be rearranged.
The giant cargo crane on the ship responsible for the operation will rearrange the crates in a series of carefully-planned steps. Once the crates are rearranged, the desired crates will be at the top of each stack.
The Elves don’t want to interrupt the crane operator during this delicate procedure, but they forgot to ask her which crate will end up where, and they want to be ready to unload them as soon as possible so they can embark.
Today’s input is a drawing of the starting arrangement of the stack.
[D]
[N] [C]
[Z] [M] [P]
1 2 3 And the list of the commands the crane will perform.
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2Our goal is to simulate the rearrangement and determine which crates will end at the top of each stack.
First of all, we have to parse the input. To read the content of the stacks we need to read every fourth character of the line starting from the second character. This function is what we want.
function everyNthChar(string $str, int $nth, int $offset = 0): array
{
$count = mb_strlen($str);
$range = range($offset, $count - $offset, $nth);
return array_reduce($range, function ($res, $i) use ($str) {
return [...$res, $str[$i]];
}, []);
}To parse commands we can use a simple regex. Then we have to subtract one from the stack identifiers to match the index of the stack in the array of stacks.
protected function parseCommand(string $command): array
{
preg_match("/move (\d*) from (\d*) to (\d*)/", $command, $matches);
array_shift($matches);
return [
intval($matches[0]),
intval($matches[1]) - 1,
intval($matches[2]) - 1
];
}Now we are ready to parse the input. To determine whether to parse stacks of the command we can use the first character of the line.
protected function parseInput(array $input): mixed
{
return array_reduce($input, function ($res, $line) {
if (!empty($line) && $line[0] === 'm') {
$res[1][] = $this->parseCommand($line);
} else {
$res[0][] = everyNthChar($line, 4, 1);
}
return $res;
}, [[], []]);
}This is fine, but the stacks aren’t quite usable yet. They contain labels of stacks and one empty line. What's more they as rows but we need them as columns.
The first issue can be solved by removing the last two elements, but to fix the second one we have to transpose the array.
function transpose(array $array): array
{
return array_map(null, ...$array);
}Finally, we have to filter out empty items.
protected function filterEmptyItems(array $stacks): array
{
return array_map(function ($stack) {
return array_filter($stack, function ($item) {
return (trim($item) != "");
});
}, $stacks);
}For easier manipulation with stack in the future we can reverse them. All the previous steps lead to this final function that processes the input.
protected function preprocessInput(array $input): array
{
list($stacks, $commands) = $this->parseInput($input);
array_pop($stacks);
array_pop($stacks);
$stacks = transpose($stacks);
$stacks = $this->filterEmptyItems($stacks);
$stacks = array_map('array_reverse', $stacks);
return [$stacks, $commands];
}Today’s input was quite complex to parse compared with previous days. On the other hand, the simulation looks quite easy. We have to move items between the stacks. Since the crane can only move one item at a time the movement is straightforward. Immediately after we pop one item from starting stack we append it to the destination stack. In other words, the crane operates on the FIFO (First In, First Out) principle. To make it explicit, that we use a queue I divided the process into the step of loading and unloading the crane even though the crane moves one item at a time in reality.
protected function applyCommandOnStacks(): \Closure
{
return function ($stacks, $command) {
list($count, $from, $to) = $command;
$crane = [];
for ($i = 0; $i < $count; $i++)
$this->cranePick($crane, array_pop($stacks[$from]));
for ($i = 0; $i < $count; $i++)
$stacks[$to][] = $this->cranePut($crane);
return $stacks;
};
}Here are the functions that procure a behaviour of the queue.
protected function cranePick(array &$crane, string $item)
{
$crane[] = $item;
}
protected function cranePut(array &$crane)
{
return array_shift($crane);
}If we combine all the code above we get the final look of the program.
public function run(array $input): int|string
{
list($stacks, $commands) = $this->preprocessInput($input);
$stacks = array_reduce($commands, $this->applyCommandOnStacks(), $stacks);
return array_reduce($stacks, fn($msg, $stack) => $msg . $stack[array_key_last($stack)], '');
}The only additional step here is the composition of the message from the top items on each stack.
Part two
Oh no, we missed one important detail. A piece of mud was covering the label on the crane. The ship has a newer version of the crane. That crane is capable of moving multiple crates at once.
That implies that during the movement the order of the crates is preserved. In other words, the crane works on the LIFO (Last In, Last Out). We have to edit our crane to work as a stack. Thankfully that’s easy!
protected function cranePut(array &$crane)
{
return array_pop($crane);
}Conclusion
Besides the cryptic parsing of today’s input, the task for day five was about the use of basic data structures Queue and Stack. In our program, we have been able to swap those data structures in a blink of an eye that’s the reason why we were able to save the day quickly :]
The complete source code of today’s solution can be found on my GitHub.
Do you want to know how I solve the other days? Please follow me here on Medium and don’t miss the following articles.