Author Archives: Julia on Eric Burden

Advent of Code 2021 – Day 16

By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2021/12/17/advent-of-code-2021-day-16/

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 16 – Packet Decoder

Find the problem description HERE.

The Input – Read to Bits

Our input for today’s puzzle comes to us in the form of a long string of hexadecimal characters, and we’re told we’ll need to analyze it bit-by-bit, as it were. So, our input parsing converts the hex string into a BitVector.

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

byte2bits(byte)   = digits(byte, base=2, pad=8)
bytes2bits(bytes) = BitVector(mapreduce(byte2bits, vcat, reverse(bytes)))
const hex2bits = bytes2bits ∘ hex2bytes
const read2bits = hex2bits ∘ readchomp


# Ingest the Data -------------------------------------------------------------

function ingest(path)
    return read2bits(path)
end

One important thing to note is that the BitVector will be in reverse order, such that the bits for the first hex character will be at the end of the BitVector. This will allow us to pop!() bits from the end as we process them.

Part One – Packet In

This must be a really important message we’re receiving, full of information that needed to be packed into the smallest possible transmission, hence the encoding. Let’s get to work decoding it so we can see what the elves had to say! There’s a fair amount of code involved here, but the comments should help.

# Some Useful Data Structures --------------------------------------------------

# Types for the different types of packets we might find
abstract type Packet end
struct Literal <: Packet
    version::Int
    value::Int
end
struct Operator <: Packet
    version::Int
    typeid::Int
    packets::Vector{Packet}
end

# Used in lieu of an enum for dispatching which strategy to use for
# parsing the sub-packets of an `Operator` packet.
abstract type SubPacketStrategy end
struct BitwiseStrategy    <: SubPacketStrategy end
struct PacketwiseStrategy <: SubPacketStrategy end


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

# Makes working with the input bits a lot nicer. Since the input bits are 
# arranged in reverse order, we can `pop!()`, to get the first bit and remove
# it from the bits vector. These helpers let us pop multiple bits from the
# bits vector (`popn!()`) or easily extract a decimal number from the end of
# the bits vector (`pop2dec!()`).
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))
popn!(x, n) = [pop!(x) for _ in 1:n]
pop2dec!(x, n) = todecimal(pop!(x) for _ in 1:n)

# Round a BitVector down to the nearest full byte, discarding extra bits. Each
# packet may have extra empty bits at the end, this helps to clean those off
# before searching for the next packet.
function roundtobytes!(bits::BitVector)
    targetlen = (length(bits) ÷ 8) * 8      # Number of bits in full bytes left
    bitstoremove = length(bits) - targetlen 
    popn!(bits, bitstoremove)
end

# Parse a packet off the end of the `bits` BitVector. Start pulling bits from
# the end and working backwards.
function nextpacket!(bits::BitVector; issubpacket = false)::Packet
    version = pop2dec!(bits, 3)
    typeid  = pop2dec!(bits, 3)

    # If the `typeid` is 4, it's a Literal packet. Otherwise, it's an Operator
    packet = if typeid == 4
        value = literalvalue!(bits)
        Literal(version, value)
    else
        # The 'length type ID' mentioned in the puzzle description is a single
        # bit, so either true or false. If it's `1` (true), then we know how
        # many sub-packets we have. Otherwise, we're given the number of bytes
        # in the sub-packets and have to parse from there.
        countingstrategy = pop!(bits) ? PacketwiseStrategy : BitwiseStrategy
        subpackets = subpackets!(countingstrategy, bits)
        Operator(version, typeid, subpackets)
    end

    # Round down to the nearest byte if we're not parsing a sub-packet
    issubpacket || roundtobytes!(bits)

    return packet
end

# The value for a Literal packet comes from the bits following the type ID. The
# bits for the value are split into 5-bit chunks, where the first bit indicates
# whether or not it's the last chunk, and the remaining 4 bits are concatenated
# to provide the binary representation of the final value.
function literalvalue!(bits::BitVector)::Int
    valuebits = BitVector()
    keepgoing = true
    while keepgoing
        keepgoing = pop!(bits)
        append!(valuebits, popn!(bits, 4))
    end
    return todecimal(valuebits)
end

# If we're using the `BitwiseStrategy` for parsing sub-packets (from the 
# 'length type ID' value), then we start by checking the total number 
# of bits left before we start, then parsing bits off the end until we've
# used up the number of bits specified in `bitstoread`.
function subpackets!(::Type{BitwiseStrategy}, bits::BitVector)::Vector{Packet}
    packets = Vector{Packet}()
    bitstoread = pop2dec!(bits, 15)     # Specified in the puzzle description
    bitstostart = length(bits)
    while (bitstostart - length(bits)) < bitstoread
        push!(packets, nextpacket!(bits, issubpacket = true))
    end
    return packets
end

# If we're using the `PacketwiseStrategy`, it means we were given the number of
# sub-packets to parse. So, we just pull that many sub-packets from the end
# of the bits vector. This seems like a superior encoding, honestly.
function subpackets!(::Type{PacketwiseStrategy}, bits::BitVector)::Vector{Packet}
    packetstoread = pop2dec!(bits, 11)  # Specified in the puzzle description
    return [nextpacket!(bits, issubpacket = true) for _ in 1:packetstoread]
end

# This function reads a sequence of packets from the input. Turns out, the 
# actual input is a single large `Operator` containing a bunch of
# sub-packets, so this isn't really necessary. I'm still leaving it in for
# educational purposes, but I don't use it either solution.
function topackets!(bits::BitVector)
    packets = Vector{Packet}()
    while !isempty(bits)
        push!(packets, nextpacket!(bits))
    end
    return packets
end

# Two different functions for summing the versions of a Packet. The sum of 
# versions for a `Literal` packet is just its version number. For an `Operator`, 
# we need to recursively check all the sub-packets and sum their versions.
sumversions(packet::Literal) = packet.version

function sumversions(packet::Operator)
    return packet.version + sum(sumversions(p) for p in packet.packets)
end


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

# Parse the one big packet from our input, then count the versions of all
# its sub-packets (and their sub-packets, and their sub-packets' sub-packets...)
function part1(input)
    bits = deepcopy(input)
    superpacket = nextpacket!(bits)
    return sumversions(superpacket)
end

Ok, interesting… It looks like our message contains a single Operator packet. I wonder what these ‘operations’ are? Must be a really complicated message. Let’s see if we can figure out what it is.

Part Two – Smooth Operator

Turns out the ‘operations’ are mathematical operations. So, the message is a…number? Odd, seems like that could have been encoded in hex directly. Oh well, let’s figure out what it is!

# Multiple Dispatch! -----------------------------------------------------------

# A new sub-type of `Packet` for each of the Operator types. In a 'real' 
# application, I'd probably re-define Operator as an abstract type and
# sub-type from there. 
struct SumPacket  <: Packet version::Int; packets::Vector{Packet} end
struct ProdPacket <: Packet version::Int; packets::Vector{Packet} end
struct MinPacket  <: Packet version::Int; packets::Vector{Packet} end
struct MaxPacket  <: Packet version::Int; packets::Vector{Packet} end
struct GtPacket   <: Packet version::Int; packets::Vector{Packet} end
struct LtPacket   <: Packet version::Int; packets::Vector{Packet} end
struct EqPacket   <: Packet version::Int; packets::Vector{Packet} end

# Honestly, this is just single dispatch. Define a method for each type of
# Packet that evaluates its value. For `Literal`s, that's just the stored
# value and everything else is evaluated in terms of that.
eval(packet::Literal)    = packet.value
eval(packet::SumPacket)  = sum(eval(sub) for sub in packet.packets)
eval(packet::ProdPacket) = prod(eval(sub) for sub in packet.packets)
eval(packet::MinPacket)  = minimum(eval(sub) for sub in packet.packets)
eval(packet::MaxPacket)  = maximum(eval(sub) for sub in packet.packets)
eval(packet::GtPacket)   = eval(packet.packets[1]) >  eval(packet.packets[2])
eval(packet::LtPacket)   = eval(packet.packets[1]) <  eval(packet.packets[2])
eval(packet::EqPacket)   = eval(packet.packets[1]) == eval(packet.packets[2])

# We need to go back and classify the `Packets` from before according to their
# newly revealed `Operator` sub-type. `Literal`s stay the same.
classify(packet::Literal) = packet
function classify(packet::Operator)
    version = packet.version
    subpackets = [classify(sub) for sub in packet.packets]
    packet.typeid == 0 && return SumPacket(version, subpackets)
    packet.typeid == 1 && return ProdPacket(version, subpackets)
    packet.typeid == 2 && return MinPacket(version, subpackets)
    packet.typeid == 3 && return MaxPacket(version, subpackets)
    packet.typeid == 5 && return GtPacket(version, subpackets)
    packet.typeid == 6 && return LtPacket(version, subpackets)
    packet.typeid == 7 && return EqPacket(version, subpackets)
    error("Could not clasify $packet")
end


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

# Parse the superpacket from our input, identify the sub-types of all the 
# `Packet`s, and evaluate them. In an ideal world, we would have known about the
# `Operator` sub-types ahead of time and included that logic in our `nextpacket!()`
# function.
function part2(input)
    bits = deepcopy(input)
    superpacket = nextpacket!(bits)
    classified = classify(superpacket)
    return eval(classified)
end

I love function dispatching so much. By changing the Type of each Operator packet to something a bit more specific, we’re able to adjust the behavior of the eval() function, which results in some incredibly nice-looking code.

Wrap Up

This was a really fun day. I felt particularly clever for the ‘pop bits from the end of the vector’ strategy. I’m not 100% sure if this holds true for Julia, but in general I know that adding/removing items from the end of a vector is more computationally efficient than adding/removing from the beginning, since we don’t need to re-allocate. The small utility functions that are encouraged by Julia’s syntax and Type-based function dispatch really results in some elegant code.

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

Advent of Code 2021 – Day 16

By: Julia on Eric Burden

Re-posted from: https://ericburden.work/blog/2021/12/17/advent-of-code-2021-day-16/

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 16 – Packet Decoder

Find the problem description HERE.

The Input – Read to Bits

Our input for today’s puzzle comes to us in the form of a long string of hexadecimal characters, and we’re told we’ll need to analyze it bit-by-bit, as it were. So, our input parsing converts the hex string into a BitVector.

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

byte2bits(byte)   = digits(byte, base=2, pad=8)
bytes2bits(bytes) = BitVector(mapreduce(byte2bits, vcat, reverse(bytes)))
const hex2bits = bytes2bits ∘ hex2bytes
const read2bits = hex2bits ∘ readchomp


# Ingest the Data -------------------------------------------------------------

function ingest(path)
    return read2bits(path)
end

One important thing to note is that the BitVector will be in reverse order, such that the bits for the first hex character will be at the end of the BitVector. This will allow us to pop!() bits from the end as we process them.

Part One – Packet In

This must be a really important message we’re receiving, full of information that needed to be packed into the smallest possible transmission, hence the encoding. Let’s get to work decoding it so we can see what the elves had to say! There’s a fair amount of code involved here, but the comments should help.

# Some Useful Data Structures --------------------------------------------------

# Types for the different types of packets we might find
abstract type Packet end
struct Literal <: Packet
    version::Int
    value::Int
end
struct Operator <: Packet
    version::Int
    typeid::Int
    packets::Vector{Packet}
end

# Used in lieu of an enum for dispatching which strategy to use for
# parsing the sub-packets of an `Operator` packet.
abstract type SubPacketStrategy end
struct BitwiseStrategy    <: SubPacketStrategy end
struct PacketwiseStrategy <: SubPacketStrategy end


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

# Makes working with the input bits a lot nicer. Since the input bits are 
# arranged in reverse order, we can `pop!()`, to get the first bit and remove
# it from the bits vector. These helpers let us pop multiple bits from the
# bits vector (`popn!()`) or easily extract a decimal number from the end of
# the bits vector (`pop2dec!()`).
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))
popn!(x, n) = [pop!(x) for _ in 1:n]
pop2dec!(x, n) = todecimal(pop!(x) for _ in 1:n)

# Round a BitVector down to the nearest full byte, discarding extra bits. Each
# packet may have extra empty bits at the end, this helps to clean those off
# before searching for the next packet.
function roundtobytes!(bits::BitVector)
    targetlen = (length(bits) ÷ 8) * 8      # Number of bits in full bytes left
    bitstoremove = length(bits) - targetlen 
    popn!(bits, bitstoremove)
end

# Parse a packet off the end of the `bits` BitVector. Start pulling bits from
# the end and working backwards.
function nextpacket!(bits::BitVector; issubpacket = false)::Packet
    version = pop2dec!(bits, 3)
    typeid  = pop2dec!(bits, 3)

    # If the `typeid` is 4, it's a Literal packet. Otherwise, it's an Operator
    packet = if typeid == 4
        value = literalvalue!(bits)
        Literal(version, value)
    else
        # The 'length type ID' mentioned in the puzzle description is a single
        # bit, so either true or false. If it's `1` (true), then we know how
        # many sub-packets we have. Otherwise, we're given the number of bytes
        # in the sub-packets and have to parse from there.
        countingstrategy = pop!(bits) ? PacketwiseStrategy : BitwiseStrategy
        subpackets = subpackets!(countingstrategy, bits)
        Operator(version, typeid, subpackets)
    end

    # Round down to the nearest byte if we're not parsing a sub-packet
    issubpacket || roundtobytes!(bits)

    return packet
end

# The value for a Literal packet comes from the bits following the type ID. The
# bits for the value are split into 5-bit chunks, where the first bit indicates
# whether or not it's the last chunk, and the remaining 4 bits are concatenated
# to provide the binary representation of the final value.
function literalvalue!(bits::BitVector)::Int
    valuebits = BitVector()
    keepgoing = true
    while keepgoing
        keepgoing = pop!(bits)
        append!(valuebits, popn!(bits, 4))
    end
    return todecimal(valuebits)
end

# If we're using the `BitwiseStrategy` for parsing sub-packets (from the 
# 'length type ID' value), then we start by checking the total number 
# of bits left before we start, then parsing bits off the end until we've
# used up the number of bits specified in `bitstoread`.
function subpackets!(::Type{BitwiseStrategy}, bits::BitVector)::Vector{Packet}
    packets = Vector{Packet}()
    bitstoread = pop2dec!(bits, 15)     # Specified in the puzzle description
    bitstostart = length(bits)
    while (bitstostart - length(bits)) < bitstoread
        push!(packets, nextpacket!(bits, issubpacket = true))
    end
    return packets
end

# If we're using the `PacketwiseStrategy`, it means we were given the number of
# sub-packets to parse. So, we just pull that many sub-packets from the end
# of the bits vector. This seems like a superior encoding, honestly.
function subpackets!(::Type{PacketwiseStrategy}, bits::BitVector)::Vector{Packet}
    packetstoread = pop2dec!(bits, 11)  # Specified in the puzzle description
    return [nextpacket!(bits, issubpacket = true) for _ in 1:packetstoread]
end

# This function reads a sequence of packets from the input. Turns out, the 
# actual input is a single large `Operator` containing a bunch of
# sub-packets, so this isn't really necessary. I'm still leaving it in for
# educational purposes, but I don't use it either solution.
function topackets!(bits::BitVector)
    packets = Vector{Packet}()
    while !isempty(bits)
        push!(packets, nextpacket!(bits))
    end
    return packets
end

# Two different functions for summing the versions of a Packet. The sum of 
# versions for a `Literal` packet is just its version number. For an `Operator`, 
# we need to recursively check all the sub-packets and sum their versions.
sumversions(packet::Literal) = packet.version

function sumversions(packet::Operator)
    return packet.version + sum(sumversions(p) for p in packet.packets)
end


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

# Parse the one big packet from our input, then count the versions of all
# its sub-packets (and their sub-packets, and their sub-packets' sub-packets...)
function part1(input)
    bits = deepcopy(input)
    superpacket = nextpacket!(bits)
    return sumversions(superpacket)
end

Ok, interesting… It looks like our message contains a single Operator packet. I wonder what these ‘operations’ are? Must be a really complicated message. Let’s see if we can figure out what it is.

Part Two – Smooth Operator

Turns out the ‘operations’ are mathematical operations. So, the message is a…number? Odd, seems like that could have been encoded in hex directly. Oh well, let’s figure out what it is!

# Multiple Dispatch! -----------------------------------------------------------

# A new sub-type of `Packet` for each of the Operator types. In a 'real' 
# application, I'd probably re-define Operator as an abstract type and
# sub-type from there. 
struct SumPacket  <: Packet version::Int; packets::Vector{Packet} end
struct ProdPacket <: Packet version::Int; packets::Vector{Packet} end
struct MinPacket  <: Packet version::Int; packets::Vector{Packet} end
struct MaxPacket  <: Packet version::Int; packets::Vector{Packet} end
struct GtPacket   <: Packet version::Int; packets::Vector{Packet} end
struct LtPacket   <: Packet version::Int; packets::Vector{Packet} end
struct EqPacket   <: Packet version::Int; packets::Vector{Packet} end

# Honestly, this is just single dispatch. Define a method for each type of
# Packet that evaluates its value. For `Literal`s, that's just the stored
# value and everything else is evaluated in terms of that.
eval(packet::Literal)    = packet.value
eval(packet::SumPacket)  = sum(eval(sub) for sub in packet.packets)
eval(packet::ProdPacket) = prod(eval(sub) for sub in packet.packets)
eval(packet::MinPacket)  = minimum(eval(sub) for sub in packet.packets)
eval(packet::MaxPacket)  = maximum(eval(sub) for sub in packet.packets)
eval(packet::GtPacket)   = eval(packet.packets[1]) >  eval(packet.packets[2])
eval(packet::LtPacket)   = eval(packet.packets[1]) <  eval(packet.packets[2])
eval(packet::EqPacket)   = eval(packet.packets[1]) == eval(packet.packets[2])

# We need to go back and classify the `Packets` from before according to their
# newly revealed `Operator` sub-type. `Literal`s stay the same.
classify(packet::Literal) = packet
function classify(packet::Operator)
    version = packet.version
    subpackets = [classify(sub) for sub in packet.packets]
    packet.typeid == 0 && return SumPacket(version, subpackets)
    packet.typeid == 1 && return ProdPacket(version, subpackets)
    packet.typeid == 2 && return MinPacket(version, subpackets)
    packet.typeid == 3 && return MaxPacket(version, subpackets)
    packet.typeid == 5 && return GtPacket(version, subpackets)
    packet.typeid == 6 && return LtPacket(version, subpackets)
    packet.typeid == 7 && return EqPacket(version, subpackets)
    error("Could not clasify $packet")
end


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

# Parse the superpacket from our input, identify the sub-types of all the 
# `Packet`s, and evaluate them. In an ideal world, we would have known about the
# `Operator` sub-types ahead of time and included that logic in our `nextpacket!()`
# function.
function part2(input)
    bits = deepcopy(input)
    superpacket = nextpacket!(bits)
    classified = classify(superpacket)
    return eval(classified)
end

I love function dispatching so much. By changing the Type of each Operator packet to something a bit more specific, we’re able to adjust the behavior of the eval() function, which results in some incredibly nice-looking code.

Wrap Up

This was a really fun day. I felt particularly clever for the ‘pop bits from the end of the vector’ strategy. I’m not 100% sure if this holds true for Julia, but in general I know that adding/removing items from the end of a vector is more computationally efficient than adding/removing from the beginning, since we don’t need to re-allocate. The small utility functions that are encouraged by Julia’s syntax and Type-based function dispatch really results in some elegant code.

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

Advent of Code 2021 – Day 15

By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2021/12/16/advent-of-code-2021-day-15/

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!