Advent of Code 2021 - Day 15

By Eric Burden | December 16, 2021

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 15 - Chiton

Find the problem description HERE.

The Input - Hello Matrix, My Old Friend

Read the input file. Parse it into a numeric matrix. We’ve seen this one before.

# Ingest the Data -------------------------------------------------------------
function ingest(path)
    return open(path) do f
        outvectors = open(path) do f
            [collect(line) for line in readlines(f)]
        end
        toint(x) = parse(UInt8, x)

        # I transposed the matrix to make debugging easier, since 
        # otherwise it won't print in the same orientation as the input.
        (outmatrix
         =  outvectors
         |> (x -> reduce(hcat, x))
         |> (x -> map(toint, x))
         |> transpose
         |> collect)
        return outmatrix
    end
end

Part One - In Crowded Caves, I Walk Alone

Part one puts us in a cave full of exceptionally tough mollusks and tasks us with finding the safest route through. Frankly, I was a bit confused by our desire to avoid these seemingly harmless invertebrates, until I saw this. Ouch. Ok, dodging chitons it is. At least they move slowly. Our approach is is a pretty straightforward Dijkstra’s algorithm, using the matrix from our input as a map of the cost (or weight) of every edge into a particular node.

# Some Useful Data Structures --------------------------------------------------
using DataStructures: BinaryMinHeap

# Helper Functions -------------------------------------------------------------

function neighbors(idx::CartesianIndex, M::AbstractMatrix)
    offsets = [CartesianIndex( 1, 0), CartesianIndex(0,  1),
               CartesianIndex(-1, 0), CartesianIndex(0, -1)]
    neigbhoridxs = [offset + idx for offset in offsets]
    
    # Only keep neighbor indices that are actually in the grid
    return filter(i -> checkbounds(Bool, M, i), neigbhoridxs)
end

# Find the minimum path from `start` to `finish` on `map` using Dijkstra's algorithm
function minpath(start, finish, map)
    distances = fill(typemax(UInt16), size(map))
    distances[1, 1] = 0

    heap = BinaryMinHeap([(0, CartesianIndex(1, 1))])
    visited = Set{CartesianIndex}()

    while !isempty(heap)
        (distance, current) = pop!(heap)
        current in visited && continue
        current == finish && return distances[finish]
        push!(visited, current)

        for neighbor in neighbors(current, map)
            traveldistance = distance + map[neighbor]

            if traveldistance < distances[neighbor]
                distances[neighbor] = traveldistance
            end

            push!(heap, (distances[neighbor], neighbor))
        end
    end
    error("Could not find a path from $start to $finish!")
end


# Solve Part One ---------------------------------------------------------------

function part1(input)
    start  = CartesianIndex(1,1)
    finish = CartesianIndex(size(input))
    return minpath(start, finish, input)
end

There’s not a lot to say about this one (partially because I’m so close to finally getting caught up on my blog posts for AoC). I’m not really doing any interesting twist here. Check out the link above if you’d like more information about how Dijkstra’s algorithm works. One minor note, the hint in the puzzle description about how you shouldn’t use the ‘risk level’ of the starting position unless you enter it is a bit of a red herring. There’s no possible way that re-entering the start space could be a part of the shortest path.

Part Two - Ten Thousand Chitons, Mabye More

Ah man, looks like we read the map wrong. Turns out, the cave is actually 5 times bigger and filled with way more chitons than we originally thought. Happily, our pathfinding algorithm is just as good for this part. Unfortunately, we need to construct the rest of the map ourselves.

# Helper Functions -------------------------------------------------------------

# Given a matrix `M`, return a matrix expanded by `amt` "tiles" horizontally
# and vertically, where each "tile" is a copy of the `M` matrix with values
# increased by the total row/column offset from the top left corner, as 
# described in the puzzle description.
function expandby(M::Matrix{T}, amt::Int64) where T <: Unsigned
    # Initialize a matrix large enough to hold the output
    expandeddims = size(M) .* (amt + 1)
    expanded = zeros(Int64, expandeddims)
    (rows, cols) = size(M)

    # Loop over each combination of row/column offset from the top
    # left corner
    for (rowoffset, coloffset) in Iterators.product(0:amt, 0:amt)
        # Calculate which portion of the `expanded` matrix to replace with
        # the values of the tile indicated by the row/col offset
        rowindices = collect(1:rows) .+ (rowoffset * rows)
        colindices = collect(1:cols) .+ (coloffset * cols)

        # Replace the zeros in `expanded` with the values from `M` and increase
        # those values by the total offset, wrapping all values greater than 9
        expanded[rowindices, colindices] = M
        expanded[rowindices, colindices] .+= (rowoffset + coloffset)
        expanded[expanded .> 9] .%= 9
    end
    return expanded    
end


# Solve Part Two ---------------------------------------------------------------

# Expand the input map and find the shortest path through it
function part2(input)
    expandedmap = expandby(input, 4)
    start  = CartesianIndex(1,1)
    finish = CartesianIndex(size(expandedmap))
    return minpath(start, finish, expandedmap)
end

The Iterators.product() call produces all combinations (or the ‘inner product’) of the ranges passed to it, so we get all the combinations of row and column offsets. We’re basically creating a big empty Matrix and filling it with ’tiled’ versions of our original map, with values increased according to the instructions in the puzzle. From there, we just use our minpath() function again to find our way through. Safety!

Wrap Up

I have a soft spot in my heart for graph traversal algorithms, in part because I find that a good portion of coding problems can be described in terms of graph structures, and knowing a few of them off the top of my head has proven handy on more than one occasion. I also learned a few more standard function calls today and found out that the BinaryMinHeap needed for Dijkstra’s algorithm was in a package I had already loaded for an earlier puzzle. I’ll probably start branching out for new packages when I can, to help me get more familiar with what’s available outside the Julia standard library. To be honest, so far Julia has been “batteries included” enough that I haven’t often felt the need to go looking for packages. There’s an awful lot in the standard library, and that’s one thing that has made the language such fun to work with.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!

comments powered by Disqus