By: Julia on Eric Burden

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

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 6 – Lanternfish

Find the problem description HERE.

The Input – School is in Session

Today’s puzzle has us calculating the number of lanternfish over time, with a
given spawn rate. The key insight here is that there are 9 possible ages of fish
(0-8), and each fish gets ‘reset’ to age 6 after spawning a new fish. New fish
are spawned at age 8. Because we are interested in the total population of fish
at the end of some time period, there’s no need to track each fish individually.
So, for our input parsing, we count the number of fish who are initially at each
possible age and return a vector of length 9, where each index contains the
count of fish whose number of remaining days until spawning is
index - 1 (Julia is 1-indexed).

function ingest(path)
    fish = open(inputpath) do f
        readsplit(x) = split(readchomp(x), ",")
        [parse(Int, s) for s in readsplit(f)]
    end

    # Instead of reporting back the fish individually, return a
    # Vector of length `9` where each index represents the number 
    # of fish of age `idx - 1` . (Julia is 1-indexed)
    groups = zeros(Int64, 9)
    for f in fish
        groups[f+1] += 1
    end
    return groups
end

The Solution – My One and Only

For reasons that will become clear shortly, there’s really not a Part One and
Part Two to today’s puzzle. Because the fish are spawning at a constant rate,
we can keep track of groups of fish by the number of days they have before
spawning. Each day, every fish’s number of remaining days is reduce by one,
except for fish whose remaining days are 0. These fish will have their
remaining days reset to 6, and they will also each produce a fish with
remaining days of 8. So, we can essentially just rotate our array to the
left, and add the value of groups[9] (the new fish spawned) to groups[7]
(the number of fish who spawned).

# Create an Iterator over Generations of Fish Schools -------------------------
struct School
    agegroups::Vector{Int64}
end

# This function is called for the first iteration
function Base.iterate(iter::School)
    groups = copy(iter.agegroups)
    (sum(groups), groups)
end

# This function is called for each subsequent iteration
# Instead of keeping track of each fish and its progeny, we group all
# the fish by age and calculate the size of the next generation. Each
# generation/iteration creates `groups[1]` new fish at age `8` and rotates
# the group counts one to the left (such that the fish that were age `2` 
# are now age `1`)
function Base.iterate(iter::School, groups::Vector{Int64})
    groups = circshift(groups, -1)
    groups[7] += groups[9]
    (sum(groups), groups)
end

# Used to get the `nth` generation of a school. 
function Base.getindex(school::School, i::Int)
    for (generation, groups) in enumerate(school)
        generation > i && return groups
    end
end


# Solve the puzzle ------------------------------------------------------------

# Solve the puzzle, creating an iterator over generations of a 
# `School` and summing the values for a given day.
function solve(input, days)
    school = School(input)
    return sum(school[days])
end

Like yesterday, I found it handy to implement some of the iterator interface
for School, a struct containing only the agegroups array. I also discovered
I could implement getindex() as a method to get the nth element from the
School iterator, which could technically iterate forever (or until the values
overflowed). This works by iterating School forward the indicated number of
‘days’ and taking the last result.

Part one asks us to determine the count of fish at 80 days, and part two asks
for the same thing at 256 days, which means making no change other than the
second argument to solve().

Wrap Up

I spent WAY too much time today trying to figure out how to get the nth value
from an iterator. I’m still not sure my result is the most idiomatic way of
handling this in Julia. In Rust, there’s an nth() function for iterators that
does this, and I was looking for something similar in Julia. I am very happy with
how this code came out, but I do find myself wishing the documentation were
organized differently. Or, maybe it’s just that I don’t understand Julia well
enough yet, which is probably it. Either way, I understand it a bit better today
that I did yesterday, which is really the point of all this. So, a win!

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

By: Julia on Eric Burden

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

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.

By: Julia on Eric Burden

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

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 4 – Giant Squid

Find the problem description HERE.

The Input – Board Stiff

I refuse to discuss this “Input” section any further. It’s here. It’s probably
going to be here for a while. Deal with it. (See my posts for previous days if
you’re curious why I’d be slightly salty about needing this section). For
today’s puzzle, the input parsing does like 90% of the heavy lifting. A quick
read of the instructions tells me that I’m going to need Bingo Boards, and
that I’ll need to be able to “mark off” numbers in a sequence and know when
a particular Board has accumulated five marked off numbers in a vertical
or horizontal line. Importantly, diagonal lines are specifically excluded, which
was a bummer because I specifically included them in my first pass at this.

I know how Bingo works! Who needs directions? – Me

I’m using a Dict in each Board to map values to their positions on the board,
to make number lookups O(1). I’m using a BitArray the same shape as the board
values for “marking off” numbers as they’re called, and I’m using a fancy Dict
to tell when a full line has been marked off, creating a winning board.

# Used to indicate whether a given line index is for a row
# or a column
abstract type AbstractIndexType end
struct RowIndex <: AbstractIndexType idx::Int end
struct ColIndex <: AbstractIndexType idx::Int end

# A struct to represent the state of an individual bingo board
# Contains fields for:
# - indexmap:   A Dict whose keys are values in the board and whose
#               values are the index of that board value
# - numbers:    A 2D matrix of the board values
# - found:      A mask for `numbers` to indicate which board numbers
#               have been called
# - linecounts: A Dict used to determine when a full column or row
#               has been drawn. The keys are an AbstractIndexType
#               indicating the line(s) of the number on the board.
#               The values are the count of numbers in that
#               row/column that have been drawn.
mutable struct Board
    indexmap::Dict{Int, Int}
    numbers::Matrix{Int}
    found::BitMatrix
    linecounts::Dict{AbstractIndexType, Int}
end

# Constructor for a `Board`, generates the other fields from `numbers`
function Board(numbers::Matrix{Int}) 
    # Build the `indexmap`
    mapnumbers(n) = map(i -> (numbers[i], i), n)
    (indexmap
        =  numbers
        |> eachindex
        |> mapnumbers
        |> Dict)
    
    found = falses(size(numbers))
    linecounts = Dict()
    Board(indexmap, numbers, found, linecounts)
end

# Call a number for a particular board. As in bingo, when a number
# is called, it should be marked on the board. This function 
# marks which number was called in the board's `found` BitMatrix
# and updates the board's `linecounts` . If playing that number
# fills out a row or column, return `true`, otherwise return `false`.
function play!(number::Int, board::Board)::Bool
    haskey(board.indexmap, number) || return false
    idx = get(board.indexmap, number, 0)
    board.found[idx] = true

    (row, col) = Tuple(CartesianIndices(board.numbers)[idx])
    boardwins = false
    linecountkeys = [RowIndex(row), ColIndex(col)]
    for key in linecountkeys
        linecount = get(board.linecounts, key, 0)
        board.linecounts[key] = linecount + 1
        if linecount + 1 >= 5; boardwins = true; end
    end

    return boardwins
end

# Read in and parse the contents of the input file
function ingest(path)
    open(inputpath) do f
        # Read the first line of numbers and parse into 
        # an array of Ints
        numstr = readuntil(f, "\n\n")
        numbers = [parse(Int, s) for s in split(numstr, ",")]

        # Utility functions to help with parsing 
        mergevectors(x) = reduce(hcat, x)
        alltoint(x) = parse.(Int, x)
        intoboard = Board ∘ collect ∘ transpose
        boards = []

        # Until the end of the file, read up to the next empty line,
        # split the lines, merge into a Matrix, convert all the Matrix
        # strings to integers, transpose the Matrix, then pass it to
        # the Board constructor.
        while !eof(f)
            boardstr = readuntil(f, "\n\n")
            (boardnums 
                = [split(s) for s in split(boardstr, "\n")]
                |> mergevectors
                |> alltoint
                |> intoboard)
            push!(boards, boardnums)
        end
        (numbers, boards) # Return numbers and boards in a Tuple
    end
end

You can use the same method with the linecounts Dict for determining when
diagonal lines have been made too, but since the puzzle forbids it, I won’t
go into it (if you’re curious, let me know in the comments).

Part One – Squid Game

Ok…. We’re under attack by a giant squid, and our solution is to play Bingo
with it. Cool. Makes sense. At least we’re willing to cheat our way through it!

# Play each number on each board until a winner is found, then
# return the sum of the winning board's unmarked numbers times
# the last number drawn.
function part1(numbers, boards)
    for number in numbers
        for board in boards
            if play!(number, board)
                unmarked = board.numbers[.!board.found]
                return sum(unmarked) * number
            end
        end
    end
    error("Could not find a winning board!")
end

There’s not much to say about this code, other that you need to pass part1()
a copy of a list of Boards if you want to use that list for anything else
later, since the Boards are mutated directly. Otherwise, this does exactly
what the comment says it does. Note that play!() return true if marking the
given number for the given board creates a 5-in-a-row for that board, and false
otherwise.

Part Two – There Can Be Only One

In part two, we come to our senses. No, we didn’t rig up any actual defenses
against the squid, but we did decide to cheat in its favor at Bingo. Now
we need to identify the last board to win and make sure we get that one.

using DataStructures

# Play each number on each board until all winners are found, then
# return the sum of the last winning board's unmarked numbers times
# the last number drawn.
function part2(numbers, boards)
    # Convert the Vector of boards into an OrderedSet to allow for
    # convenient iteration in order and easy removal of boards from
    # the set once they "win"
    boardset = OrderedSet{Board}(boards)
    for number in numbers
        for board in boardset
            if play!(number, board)
                # Return for the last winning board
                if length(boardset) == 1
                    unmarked = board.numbers[.!board.found]
                    return sum(unmarked) * number
                end

                # Remove any winning board from the OrderedSet
                delete!(boardset, board)
            end
        end
    end
    error("Could not find a winning board!")
end

This code is very much like the code for part one, with the twist of using an
OrderedSet for our Boards instead of a Vector. This way, we can iterate
through the Boards in order, while also quickly and easily nixing the winning
boards one at a time until only one remains.

Wrap Up

Yesterday, I remarked on some R-like features of Julia that I really enjoyed.
Today, I had fun tinkering with some more Rust-like features in using Types to
specify row/column indices and in the more OO-style syntax of structs. Granted,
structs aren’t particularly object-oriented, but they’re a lot closer than
S3 or S4 objects, in my opinion (if you don’t know what that is, don’t worry
about it). I do find myself missing Traits (from Rust), but I’m slowly getting
used to Julie’s “multiple dispatch” model. The file parsing functions available
in the Julia standard library were super nice to use, too. I know I’ll miss
those when I’m working in R or Rust. All in all, a really solid day.

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