Advent of Code 2022 — Day 8

6 min readDec 24, 2022

This is the eighth 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 solve the puzzle yourself.

Treetop Tree House

The expedition continues and after an exhausting fight with the jungle, they come across a grid of trees planted by previous expeditions as a reforestation effort. The Elves would like to know whether it’s a good location for a tree house.

One of the criteria is the visibility of the tree from the outside of the grid. The Elves generated a map with the height of each tree by utilization of their quadcopter. The map looks like this:

A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.

Our goal is to count how many trees are visible. First of all, let’s split the input containing lines to the 2d array.

protected function splitInputToField(array $input): array
{
    return array_map(fn($i) => mb_str_split($i), $input);
}

To keep track of visible trees we will create an array of the same size as the field initialized with null. It means all trees are not visible. The algorithm will later mark visible trees.

protected function initVisible(array $field): array
{
    return array_fill(0, count($field), array_fill(0, count($field[0]), $this->getDefaultVisible()));
}

protected function getDefaultVisible(): ?int
{
    return null;
}

To calculate we will later use array_walk_recursive. This function call provided function for all the items in a multidimensional array. The provided callback will increment the accumulator when the tree is visible.

protected function accumulateArray(int &$acc): \Closure
{
    return function ($i) use (&$acc) {
        $acc += is_null($i) ? 0 : 1;
    };
}

To determine whether the tree is visible we will walk the field and for each tree try to move our position to the edge of the field. If the position runs out of the field it means that the tree is visible. For easier manipulation, with position, we will introduce a class Vector.

class Vector
{
    private float $x;
    private float $y;

    public function __construct(float $x, float $y)
    {
        $this->x = $x;
        $this->y = $y;
    }

    public function getX(): float
    {
        return $this->x;
    }

    public function getY(): float
    {
        return $this->y;
    }
}

This class keeps track of the position it the plane. The idea is to keep vectors immutable, that's why there are only getters. What about changing the position? In that case, we create a new vector with modified coordinates.

public function add(Vector $vector): Vector
{
    $x = $this->x + $vector->getX();
    $y = $this->y + $vector->getY();
    return new Vector($x, $y);
}

In our program, we have 4 well-defined directions.

enum Direction
{
    case Up;
    case Down;
    case Left;
    case Right;

    public function vector(): Vector
    {
        return match ($this) {
            self::Up => new Vector(0, 1),
            self::Down => new Vector(0, -1),
            self::Left => new Vector(-1, 0),
            self::Right => new Vector(1, 0),
        };
    }
}

This enum will keep track of them and return the respective vectors when asked. We can even add a helper function to the Vector class to move the position in the specified direction with one function call.

public function move(Direction $direction): Vector
{
    return $this->add($direction->vector());
}

And two additional helper functions that will return the item of the position in the specified array or check whether the current position is in the boundaries of the array.

public function getSelfInField(array $field, $default = null)
{
    return $field[$this->y][$this->x] ?? $default;
}

public function isSelfInField(array $field): bool
{
    return !is_null($this->getSelfInField($field));
}

The preparation is ready. Now about the iteration of the array. First, we need to iterate over the rows.

protected function searchField(array &$visible): \Closure
{
    return function ($line, $y, $field) use (&$visible) {
        array_walk($line, $this->searchLine($visible, $y), $field);
    };
}

Then over the trees in each line. For each tree, we will search each direction until we found the direction in which the tree is visible or run out of options and consider the tree to be invisible from the outside.

protected function searchLine(array &$visible, $y): \Closure
{
    return function ($tree, $x, $field) use (&$visible, $y) {
        foreach (Direction::cases() as $direction) {
            $pos = new Vector($x, $y);

            do {
                $pos = $pos->move($direction);
            } while (
                $pos->isSelfInField($field) &&
                $pos->getSelfInField($field) < $tree
            );

            if (!$pos->isSelfInField($field)) {
                $visible[$y][$x] = $tree;
                break;
            }
        }
    };
}

In the while cycle, you can see how easy is to move the position utilizing the Vector class and the Direction enum. Also, the iteration over the direction is peace of cake. The condition of the cycle checks whether the current position is in the boundaries of the array and whether the tree in the position is lower than the examined tree. After the cycle ends we check where we are in the boundaries of the grid. If not it means we successfully found the path from the tree to the edge and thus the tree is visible and we can move to the next tree.

The only missing piece is the small amount of the driver code.

public function run(array $input): int|string
{
    $field = $this->splitInputToField($input);

    $visible = $this->initVisible($field);
    array_walk($field, $this->searchField($visible), $field);

    $count = 0;
    array_walk_recursive($visible, $this->accumulateArray($count));

    return $count;
}

Part two

The Elves are content with the amount of available space. The second step is to find the best spot for their tree house. The criterium for the location is the product of the number of trees visible from that location in each direction.

The viewing distance in each direction is the number of trees lower than the examined tree including the tree of the same or greater height which blocks the view in that direction.

The algorithm is the same as in the first part with slight modifications in the part that examines individual trees.

protected function searchLine(array &$visible, $y): \Closure
{
    return function ($tree, $x, $field) use (&$visible, $y) {
        foreach (Direction::cases() as $direction) {
            $pos = new Vector($x, $y);
            $viewScore = 0;

            do {
                $pos = $pos->move($direction);

                if (!$pos->isSelfInField($field)) break;

                $viewScore++;
            } while (
                $pos->getSelfInField($field) < $tree
            );

            $visible[$y][$x] *= $viewScore;
        }
    };
}

To make the code above work we need to modify the initial value of the visible array.

protected function getDefaultVisible(): int
{
    return 1;
}

And since we are not interested in the number of visible trees, but in the maximum product of viewing distances, we have to modify the accumulation function as well.

protected function accumulateArray(int &$acc): \Closure
{
    return function ($i) use (&$acc) {
        $acc = max($i, $acc);
    };
}

Note on the performance

Today's solution isn’t the fastest you can imagine. The used algorithm is one of the reasons. In the first part, we could search from the outside of the grid and find all visible trees in the line/column in two passes. However, this approach is not possible in the second part.

The main reason why the solution is slow is the Vector. It’s mainly PHP specific problem here. With two variables representing the current position, the code would be almost 2x faster (I tried to do some benchmarks).

Since PHP is the language for web development and not for high-performance computation I decided to keep the code as it is. I found it more readable that way and that is something you often want in web development where maintainability matters more than performance. Sure, the performance is important, but in this context, you usually don’t work with big data on the PHP side. You rather use an external service (eg. database) to handle this job for you.

Conclusion

Finding the best location for the house isn’t an easy task this is especially true for the tree house. Although the algorithm wasn't the most effective the code remains somewhat nice and the main part is abstracted to one function where you can forget about the iteration over the field and fully focus on the decision about the concrete tree.

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.

Advent of Code 2022 — Day 8

Treetop Tree House

Part two

Note on the performance

Conclusion

Written by Vaclav Hrouda