Advent Of Code 2021, Day 15: Chiton

Before we dive into the main solve, we will first look at implementing a heap, as we will be using one.

Heaps are used to quickly insert values, and find/extract a minimum value. The heap we will be using is a binary tree structure, with the feature that the value in each node is less than the value of each of its children. We call this feature the heap condition. Our particular implementation will use an array to implement a heap. The root of a heap will be at index $0$. And for a node on index $i$, its children will be on indices $2 \cdot i + 1$, and $2 \cdot i + 2$; if an index of a child exceeds the size of the array, the node doesn't have that child.

We'll be using a single heap in our program, so we just have a global variable for the heap. The elements in the heap will be 3-element array (see below) — for the heap, we are only interested in the value on index 2.

Initialization is as follows:

my @heap;
sub init_heap () {
    @heap = ([0, 0, 0])
}

That is, we initialize a heap with just one element: [0, 0, 0].

Before we discussing adding or removing elements from the heap, we need two rebalance functions. Adding or removing an element leaves a datastructure which is almost a heap: it will have at most one node which violates the heap condition.

The first rebalance function is one which we will call if a node at the top of the heap violates the heap condition. In such a case, we first find the smaller of its children, then compare the child with the parent. If the parent is less than the child, the heap condition is restored, and we're done. Else, we swap the values in the parent and the smaller of children. This restores the heap condition in the parent, but now the heap condition in the child may be violated; hence, we recurse:

sub rebalance_d ($root = 0) {
    return unless 2 * $root + 1 < @heap;
    # 
    # Find smaller of the children.
    #
    my $smaller = 2 * $root + 1;
    if (2 * $root + 2 < @heap && $heap [2 * $root + 2] [2] <
                                 $heap [2 * $root + 1] [2]) {
        $smaller ++;
    }
    # 
    # If childer are larger, we're done.
    #
    return if $heap [$root] [2] < $heap [$smaller] [2];

    # 
    # Swap and recurse
    #
    @heap [$root, $smaller] = @heap [$smaller, $root];

    rebalance_d ($smaller);
}

The other rebalance function we use if the heap condition is violated near the bottom of the heap. We then compare the node with its parent. If the value in the parent is less than the node, the heap condition is restored (and we are done). Else, we swap the node with its parent, and recurse with the parent:

sub rebalance_u ($index = @heap - 1) {
    # 
    # If at root, we're rebalanced.
    #
    return unless $index;

    # 
    # If the element is larger than its parent, we're done.
    #
    my $parent = int (($index - 1) / 2);
    return unless $heap [$index] [2] < $heap [$parent] [2];

    # 
    # Else, swap and recurse.
    #
    @heap [$index, $parent] = @heap [$parent, $index];
    rebalance_u ($parent);
}

We are now ready to add an element to the heap. We do so by just pushing an element to the array. This may make the last element of the heap violate the heap condition, so we call rebalance_u to restore the heap condition:

sub add_to_heap ($element) {
    push @heap => $element;  
    rebalance_u;
}

Extracting the minimum value we do by removing the last element of the heap (so, popping an element of the array), and putting this element in the top of the heap. Since this may violate the heap condition, we have to rebalance from the top. We will also return the element which was at the top of the heap:

sub extract () {
    my $min = $heap [0];
    $heap [0] = pop @heap;
    rebalance_d;
    $min;
}

Main Solve

First, we are going to read in the data. We'll store the map (which in the long description of the challenge is a cave, hence the variable name) in a 2-dimensional array, @cave:

To access the entries in the map, we could just do a direct lookup, and, for part two, use a much larger 2-dimensional array, but instead, we use a subroutine cell to return the risk value of a particular set of x/y coordinates. It gets a third argument ($factor) indicating how many times the base map has been tiled (so, for part one, this argument will be 1, and for part two, this will be 5). We also have a hash %seen which will contain the coordinates of the map we have already processed. If cell is called with coordinates outside of the map, or coordinates of a point we have already processed, undef is returned, otherwise, the risk value.

Now, we are ready to solve the map, using a subroutine solve. It gets an argument $factor with the same meaning as cell above.

We start off by clearing out %seen: we haven't visited any cells yet. We also initialize the heap. In the heap, we store 3-element arrays, the first two elements of this array are the x and y coordinates of a cell; the third is the total risk accumulated to get to this cell. (Each cell could appear at most four times in the heap: once for each direction).

We now loop as long as there are entries in the heap. We start off by extracting the value with the lowest value from the heap, putting the coordinates of the cell in $x and $y, and the accumulated risk in $risk:

First thing we now do is check if we have reached the bottom-right. If so, we're done, and $risk contains the minimum accumulated risk to reach this point. Which is why we return at this point:

We now check whether we have visited this cell before. If so, we did this with risk equal or less than $risk, so whatever we do now, it cannot lead to a better path than we already have. Hence, we continue with the next iteration of the loop. We also mark that we have visited this cell:

We will now inspect all neigbhours of the current cell. If they are unvisited, and within bounds, we add the new cell (with the total risk to get there) to the heap:

Advent Of Code 2021, Day 15: Chiton

Challenge

Part One

Part Two

Solution

Perl

Heap

Main Solve