Author Archives: Julia on Eric Burden

Advent of Code 2021 – Day 15

By: Julia on Eric Burden

Re-posted from: https://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!

Advent of Code – Day 14

By: Julia on Eric Burden

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

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 14 – Extended Polymerization

Find the problem description HERE.

The Input – Pairwise Interactions

Today’s puzzle has us calculating the length of “polymer” chains, strings of
characters where new characters are inserted between existing characters in the
string. Now, this might spoil the surprise, but we’re definitely not going to
be making an exponentially growing string. Instead, we’ll be doing another
frequency analysis (I see you, lanternfish…),
where we’ll keep up with counts of the unique pairs of the “elements” at
each round. For that, we need to modify the input slightly to produce a
dictionary that has a “pair => [pair, pair]” structure, as opposed to the
“pair => letter” structure given by the input file.

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

# Type alias for the `pairmap` generated in our input parser
const PairMap    = Dict{String,NTuple{2,String}}

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

# Read and parse the first line into a vector of element pairs, such that "HNH"
# will yield a `template` of ["HN", "NH"].
# Read and parse the remaining lines into a `PairMap` , coercing a line "CH -> B"
# in the input into a "CH" => ["CB", "BH"] entry in the `PairMap`.
function ingest(path)
    return open(path) do f
        # Parse the first line
        templatestr = readuntil(f, "\n\n")
        len = length(templatestr)
        template = map(i -> templatestr[i:i+1], 1:len-1)

        # Parse the remaining lines
        pairmap = Dict{String,NTuple{2,String}}()
        for pairstr in readlines(f)
            (pair, insert) = split(pairstr, " -> ")
            newpairs = (pair[1] * insert, insert * pair[2])
            pairmap[pair] = newpairs
        end

        # Return a tuple of the template and pairmap
        (template, pairmap)
    end
end

Now, each entry in our dictionary will give back the two pairs that result from
inserting that letter in the middle of the original pair. This will come in
handy for…

Part One – Organometallics, Probably

In today’s puzzle, we are set to scrounge up some raw materials so our submarine
can polymerize itself some additional hull integrity. Turns out, our small chain
polymer can be extended by inserting additional “elements” between each polymeric
unit. Sketchy organic chemistry or not, the key insight here is that it’s super
inefficient to keep track of a string directly. In fact, our output doesn’t care
anything about the arrangement of the elements in the final polymer, just their
individual counts. This means: frequency analysis! Each pair of elements can
produce two pairs each round, so “HH” becomes “HN” and “NH”, for example. Now,
you may have noticed that I’m counting “N” twice in this process, so we’ll need
to account for that in our code.

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

# Type alias for keeping up with the count of pairs in our `Polymer`. Instead
# of keeping track of the full sequence of elements in order, we only need
# the counts. By keeping a dictionary of each element pair and their counts,
# we make each step of the analysis run in constant time and space.
const PairCounts = Dict{String,Int}

# A `Polymer` is really just a wrapper around a `PairCounts`
struct Polymer
    paircounts::PairCounts
end


# Setup for Iterating Polymers -------------------------------------------------

# The iterator struct, holds the template and pairmap. The template is needed
# for the first iteration, and the pairmap is used to generate the subsequent
# `PairCounts` objects.
struct PolymerGenerator
    template::Vector{String}
    pairmap::PairMap
end

# First iteration, performs the first insertion and returns a `Polymer` 
# representing the result. Note, again, we're not actually
# inserting letters into a string, just keeping up with a count of letter 
# pairs. This means that, assuming a `PairMap` of {"CH" => ["CB", "BH"]}
# and a `PairCounts`  of {"CH" => 1}, the resulting `PairCounts` will contain
# {"CH" => 0, "CB" => 1, "BH" => 1}.
function Base.iterate(pg::PolymerGenerator)
    paircounts = Dict([(pair, 0) for pair in keys(pg.pairmap)])
    for pair in pg.template
        (first, second) = pg.pairmap[pair]
        paircounts[first]  += 1
        paircounts[second] += 1
    end
    return (Polymer(paircounts), paircounts)
end

# Subsequent iterations, given a `PairCounts` as the state, performs another
# insertion operation and returns the result.
function Base.iterate(pg::PolymerGenerator, paircounts::PairCounts)
    newpaircounts = Dict([(pair, 0) for pair in keys(pg.pairmap)])
    for (pair, count) in paircounts
        (first, second) = pg.pairmap[pair]
        newpaircounts[first]  += count
        newpaircounts[second] += count
    end
    return (Polymer(newpaircounts), newpaircounts)
    
end

# Iterate the `PolymerGenerator` `i` times and return the result
function Base.getindex(pg::PolymerGenerator, i::Int)
    for (iteration, polymer) in enumerate(pg)
        iteration >= i && return polymer
    end
end

# Count the number of elements in the given `Polymer`. Now, since we're keeping up
# with letter pairs instead of the actual string, we need to do a tiny bit of
# math. For example, the string "NNCB" would be represented by a `PairCounts` of 
# {"NN" => 1, "NC" => 1, "CB" => 1}, and would yield a `lettercounts` below of 
# {'N' => 3, 'C' => 2, 'B' => 1}. For letters in the middle, we can get the 
# actual element count as `lettercounts['C'] / 2`. Since letters at the end 
# aren't being counted twice like letters in the middle, just round up the 
# result of `lettercounts['N'] / 2` to get the number of 'N's in the string "NNCB"
function countelements(polymer::Polymer)
    lettercounts = Dict{Char,Int}()
    for (pair, count) in polymer.paircounts
        for letter in pair
            if letter ∉ keys(lettercounts)
                lettercounts[letter] = count
            else
                lettercounts[letter] += count
            end
        end
    end

    elementcounts = Dict{Char,Int}()
    for (letter, count) in lettercounts
        elementcounts[letter] = ceil(count/2)
    end

    return elementcounts
end


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

# With all that setup, this part is easy. Create a `PolymerGenerator` from the 
# input, get the 10th generated polymer, take the minumum and maximum element
# counts, and return the difference.
function part1(input)
    polymergenerator = PolymerGenerator(input...)
    elementcount = countelements(polymergenerator[10])
    (least, most) = extrema(values(elementcount))
    return most - least
end

This is a bit of a convoluted approach, but the upside is that each generation,
no matter how many elements in the current string, runs in O(1) time and space
complexity. This becomes really important in the next part.

Part Two – That Old Chestnut

That’s right. Part one asked us to count the “elements” in an exponentially
growing “polymer”, so part two asks us to do it again, but bigger. Now we
need to count the elements after 40 rounds of growth instead of just 10. Lucky
for us we did all that work in part one, eh?

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

# Exactly the same as Part One, just get the 40th generated Polymer
function part2(input)
    polymergenerator = PolymerGenerator(input...)
    elementcount = countelements(polymergenerator[40])
    (least, most) = extrema(values(elementcount))
    return most - least
end

Ta-da! We’re able to “do part one, just 40 times” without breaking a sweat.

Wrap Up

Today brought in enough familiar elements that it was a nice break from the
challenge of prior days, which is good because I’m still working on getting
caught up on my blog posts. I’m still tweaking how I implement iterators in
Julia, the whole separate iterator/state thing takes a bit of getting used
to, but I think I’m starting to get the hang of it.

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

Advent of Code 2021 – Day 14

By: Julia on Eric Burden

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

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 14 – Extended Polymerization

Find the problem description HERE.

The Input – Pairwise Interactions

Today’s puzzle has us calculating the length of “polymer” chains, strings of characters where new characters are inserted between existing characters in the string. Now, this might spoil the surprise, but we’re definitely not going to be making an exponentially growing string. Instead, we’ll be doing another frequency analysis (I see you, lanternfish…), where we’ll keep up with counts of the unique pairs of the “elements” at each round. For that, we need to modify the input slightly to produce a dictionary that has a “pair => [pair, pair]” structure, as opposed to the “pair => letter” structure given by the input file.

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

# Type alias for the `pairmap` generated in our input parser
const PairMap    = Dict{String,NTuple{2,String}}

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

# Read and parse the first line into a vector of element pairs, such that "HNH"
# will yield a `template` of ["HN", "NH"].
# Read and parse the remaining lines into a `PairMap` , coercing a line "CH -> B"
# in the input into a "CH" => ["CB", "BH"] entry in the `PairMap`.
function ingest(path)
    return open(path) do f
        # Parse the first line
        templatestr = readuntil(f, "\n\n")
        len = length(templatestr)
        template = map(i -> templatestr[i:i+1], 1:len-1)

        # Parse the remaining lines
        pairmap = Dict{String,NTuple{2,String}}()
        for pairstr in readlines(f)
            (pair, insert) = split(pairstr, " -> ")
            newpairs = (pair[1] * insert, insert * pair[2])
            pairmap[pair] = newpairs
        end

        # Return a tuple of the template and pairmap
        (template, pairmap)
    end
end

Now, each entry in our dictionary will give back the two pairs that result from inserting that letter in the middle of the original pair. This will come in handy for…

Part One – Organometallics, Probably

In today’s puzzle, we are set to scrounge up some raw materials so our submarine can polymerize itself some additional hull integrity. Turns out, our small chain polymer can be extended by inserting additional “elements” between each polymeric unit. Sketchy organic chemistry or not, the key insight here is that it’s super inefficient to keep track of a string directly. In fact, our output doesn’t care anything about the arrangement of the elements in the final polymer, just their individual counts. This means: frequency analysis! Each pair of elements can produce two pairs each round, so “HH” becomes “HN” and “NH”, for example. Now, you may have noticed that I’m counting “N” twice in this process, so we’ll need to account for that in our code.

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

# Type alias for keeping up with the count of pairs in our `Polymer`. Instead
# of keeping track of the full sequence of elements in order, we only need
# the counts. By keeping a dictionary of each element pair and their counts,
# we make each step of the analysis run in constant time and space.
const PairCounts = Dict{String,Int}

# A `Polymer` is really just a wrapper around a `PairCounts`
struct Polymer
    paircounts::PairCounts
end


# Setup for Iterating Polymers -------------------------------------------------

# The iterator struct, holds the template and pairmap. The template is needed
# for the first iteration, and the pairmap is used to generate the subsequent
# `PairCounts` objects.
struct PolymerGenerator
    template::Vector{String}
    pairmap::PairMap
end

# First iteration, performs the first insertion and returns a `Polymer` 
# representing the result. Note, again, we're not actually
# inserting letters into a string, just keeping up with a count of letter 
# pairs. This means that, assuming a `PairMap` of {"CH" => ["CB", "BH"]}
# and a `PairCounts`  of {"CH" => 1}, the resulting `PairCounts` will contain
# {"CH" => 0, "CB" => 1, "BH" => 1}.
function Base.iterate(pg::PolymerGenerator)
    paircounts = Dict([(pair, 0) for pair in keys(pg.pairmap)])
    for pair in pg.template
        (first, second) = pg.pairmap[pair]
        paircounts[first]  += 1
        paircounts[second] += 1
    end
    return (Polymer(paircounts), paircounts)
end

# Subsequent iterations, given a `PairCounts` as the state, performs another
# insertion operation and returns the result.
function Base.iterate(pg::PolymerGenerator, paircounts::PairCounts)
    newpaircounts = Dict([(pair, 0) for pair in keys(pg.pairmap)])
    for (pair, count) in paircounts
        (first, second) = pg.pairmap[pair]
        newpaircounts[first]  += count
        newpaircounts[second] += count
    end
    return (Polymer(newpaircounts), newpaircounts)
    
end

# Iterate the `PolymerGenerator` `i` times and return the result
function Base.getindex(pg::PolymerGenerator, i::Int)
    for (iteration, polymer) in enumerate(pg)
        iteration >= i && return polymer
    end
end

# Count the number of elements in the given `Polymer`. Now, since we're keeping up
# with letter pairs instead of the actual string, we need to do a tiny bit of
# math. For example, the string "NNCB" would be represented by a `PairCounts` of 
# {"NN" => 1, "NC" => 1, "CB" => 1}, and would yield a `lettercounts` below of 
# {'N' => 3, 'C' => 2, 'B' => 1}. For letters in the middle, we can get the 
# actual element count as `lettercounts['C'] / 2`. Since letters at the end 
# aren't being counted twice like letters in the middle, just round up the 
# result of `lettercounts['N'] / 2` to get the number of 'N's in the string "NNCB"
function countelements(polymer::Polymer)
    lettercounts = Dict{Char,Int}()
    for (pair, count) in polymer.paircounts
        for letter in pair
            if letter ∉ keys(lettercounts)
                lettercounts[letter] = count
            else
                lettercounts[letter] += count
            end
        end
    end

    elementcounts = Dict{Char,Int}()
    for (letter, count) in lettercounts
        elementcounts[letter] = ceil(count/2)
    end

    return elementcounts
end


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

# With all that setup, this part is easy. Create a `PolymerGenerator` from the 
# input, get the 10th generated polymer, take the minumum and maximum element
# counts, and return the difference.
function part1(input)
    polymergenerator = PolymerGenerator(input...)
    elementcount = countelements(polymergenerator[10])
    (least, most) = extrema(values(elementcount))
    return most - least
end

This is a bit of a convoluted approach, but the upside is that each generation, no matter how many elements in the current string, runs in O(1) time and space complexity. This becomes really important in the next part.

Part Two – That Old Chestnut

That’s right. Part one asked us to count the “elements” in an exponentially growing “polymer”, so part two asks us to do it again, but bigger. Now we need to count the elements after 40 rounds of growth instead of just 10. Lucky for us we did all that work in part one, eh?

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

# Exactly the same as Part One, just get the 40th generated Polymer
function part2(input)
    polymergenerator = PolymerGenerator(input...)
    elementcount = countelements(polymergenerator[40])
    (least, most) = extrema(values(elementcount))
    return most - least
end

Ta-da! We’re able to “do part one, just 40 times” without breaking a sweat.

Wrap Up

Today brought in enough familiar elements that it was a nice break from the challenge of prior days, which is good because I’m still working on getting caught up on my blog posts. I’m still tweaking how I implement iterators in Julia, the whole separate iterator/state thing takes a bit of getting used to, but I think I’m starting to get the hang of it.

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