Advent of Code 2022 — Day 9

This is the ninth 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.

<Day 8 | Day 10>

Photo by Max Saeling on Unsplash

Before you start reading, I encourage you to solve the puzzle yourself.

Rope Bridge

The expedition continues over the rope bridge. The Elves cross the bridge without any problem, however, once you step on the bridge it starts creak. The load capacity of the bridge is unknown and you aren’t sure whether it can even support your weight.

To be sure you decided to model the behaviour of the ropes as you walk over the bridge. Consider a rope with a knot at each end. We have to simulate how the knots will behave in the two-dimensional grid when we perform a hypothetical series of motions.

The knots have to always touch in one of the directions or diagonally. The hypothetical motion will always move with the head and we have to determine how the tail will behave.

The motions in the input have a form of R 4, the R means right and 4 four steps in that direction. We will represent the knots with the Vector from the previous day and thus we represent the direction with the Direction enum also from the previous day. We have to make a mapping between the letters in the input and the Direction.

private function getDirection(string $str): Direction
{
    return match ($str) {
        'L' => Direction::Left,
        'R' => Direction::Right,
        'U' => Direction::Up,
        'D' => Direction::Down,
    };
}

To determine whether to move the tail we will need the distance between the vectors. So we will add this function to the Vector class.

public function distance(Vector $vector): float
{
    $a = $vector->getX() - $this->x;
    $b = $vector->getY() - $this->y;
    return sqrt($a * $a + $b * $b);
}

We will also need the direction in the grid from one vector to the other. The direction vector is normalized to one's length.

public function gridDirection(Vector $vector): Vector
{
    $x = round(($vector->getX() - $this->x) / 2);
    $y = round(($vector->getY() - $this->y) / 2);
    return new Vector($x, $y);
}

Now we can write a simple function that will perform the movement of the tail.

function moveTail($head): \Closure
{
    return function ($knot) use (&$head) {
        if ($head->distance($knot) >= 2) {
            $knot = $knot->add($knot->gridDirection($head));
        }
        $head = $knot;
        return $knot;
    };
}

The tail is only moved when the distance between the tail and the head is greater than 2. This means that the two knots are not touching. The next step is to apply commands on the knots. The command is applied by moving the head and then responding with the tail movement.

public function applyCommand(): \Closure
{
    return function ($data, $command) {
        list($direction, $steps) = $command;
        list($knots, $visited) = $data;
        $direction = $this->getDirection($direction);

        for ($i = 0; $i < $steps; $i++) {
            $head = $knots[0] = $knots[0]->move($direction);
            $knots = array_map($this->moveTail($head), $knots);

            $last = $knots[array_key_last($knots)];
            $visited["$last"] = 1;
        }

        return [$knots, $visited];
    };
}

And finally the driver code.

public function run(array $input): int|string
{
    $commands = array_map(fn($str) => explode(' ', $str), $input);
    $data = array_reduce($commands, $this->applyCommand(), [
        $this->generateKnots(),
        ["(0, 0)" => 1]
    ]);

    return count($data[1]);
}

protected function generateKnots(): array
{
    return array_fill(0, 2, new Vector(0, 0));
}

Our goal is to compute the number of positions the tail visits. That’s why the visited array.

Part two

The rope now has 10 knots. The goal is the same we have to compute the number of positions the last knot visits. The behaviour of the knots is the same as with just two knots thus only thing we have to change here is the number of generated knots in the beginning.

protected function generateKnots(): array
{
    return array_fill(0, 10, new Vector(0, 0));
}

Conclusion

We utilized the system for work in a 2d grid from the previous day. The movement of the knots was straightforward. The second part was once again more peace of cake because of the preparation from the first part.

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.

<Day 8 | Day 10>