Author Archives: Julia on Eric Burden

Advent of Code 2021 – Day 21

By: Julia on Eric Burden

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

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 21 – Dirac Dice

Find the problem description HERE.

The Input – Two Lines, Please

The input for today is really simple, just two lines, each of which ends with a number representing the starting board space of a player, in order. The major thing here is having structs to hold and represent each Player and the Game overall, which is also pretty straightforward. There may be a more elegant way to represent the data models for today’s problem, but this seems like a really simple and understandable way to do it.

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

# Represents a player's current "state", their current board position and score
struct Player
	position::Int64
	points::Int64
end
Player(pos::Int64) = Player(pos, 0)

# Represents the current state of the game, both players' board position and
# current score
struct Game
	player1::Player
	player2::Player
end


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

# Given a string, return a Player whose position is the number at the end of
# the string.
playerpos(s) = Player(parse(Int, s[end]))


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

# There's only two lines, the first line for player one and the second line for
# player two, both of which end with a single digit representing that
# player's starting space
function ingest(path)
    return open(path) do f
		player1 = playerpos(readline(f))
		player2 = playerpos(readline(f))
		Game(player1, player2)
    end
end

Part One – I Want to Play a Game

Ok, so no more games with giant squids, now we’re playing games with… the submarine. At this point, we’ve done so much work on this submarine’s systems, surely we can outsmart it, right? I certainly hope so, otherwise we may have a tough time with the remaining days’ puzzles. Actually, part one seems suspiciously straightforward. There’s a bit of implementation here, but it all boils down to looping over the die rolls (which we can calculate in advance), finding a winner, then returning some version of the final game state. We’ve got this!

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

# Given a board position and a roll, return the next position that results from
# that roll. The only tricky bit here is that 10 + 1 wraps around to 1 instead
# of zero.
function nextposition(pos::Int64, roll::Int64)
    pos += roll
    pos > 10 && pos % 10 == 0 && return 10
    pos > 10 && return pos % 10
    return pos
end

# Given a player and a roll, return a `Player` at the next position that will 
# result from the given roll with their score updated to reflect the move.
function move(player::Player, roll::Int64)
    position = nextposition(player.position, roll)
    points = player.points + position
    return Player(position, points)
end

# Given a game board, a roll, and an optional boolean value indicating whether
# or not it is Player 1's turn, return a `Game` reflecting the state that would
# be achieved if the indicated player moves by the amount given by `roll`
function move(game::Game, roll::Int64, player1 = true)
    if player1
        player1 = move(game.player1, roll)
        return Game(player1, game.player2)
    else
        player2 = move(game.player2, roll)
        return Game(game.player1, player2)
    end
end

# Take a `Game` an return either the current high score or the current low score
highscore(game::Game) = max(game.player1.points, game.player2.points)
lowscore(game::Game)  = min(game.player1.points, game.player2.points)

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

# Literally an empty struct for the purposes of creating an iterator over the
# possible die rolls
struct Die end

# On the first roll, the die returns `6` (1 + 2 + 3) and the next starting number
# of `4`. On subsequent rolls, return the sum of the next three numbers and the
# fourth number in sequence as a tuple, to keep the iterator going. The `if`
# statements are there for wrapping around 100 if need be (I don't think it
# actually happens).
Base.iterate(::Die) = (6, 4)
function Base.iterate(::Die, start::Int64)
    (nextvalue, nextstart) = if start < 98
        (sum(start:start+2), start + 3)
    elseif start == 98
        (297, 1)
    elseif start == 99
        (200, 2)
    elseif start == 100
        (103, 3)
    end

    return (nextvalue, nextstart)
end


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

# Play the game as described! Roll the die, move the players, check the score. 
# Whenever a winner is found, return the number of rolls (3 * the number of
# rounds) multiplied by the lowest player score
function part1(game)
    die = Die()
    player1turn = true
    round = 0
    for roll in die
        game = move(game, roll, player1turn)
        round += 1
        highscore(game) >= 1000 && break
        player1turn = !player1turn
    end
    rolls = round * 3
    return rolls * lowscore(game)
end

There wasn’t even any tricky input like yesterday. In fact, part one seemed almost… too easy…

Part Two – Wake Up

Oookay… Part two has us playing with the fabric of reality. Neat! Now, every time we roll the ‘special’ die, the universe splits into 27 new alternate realities, one where we rolled a total of 3, three where we rolled a 4, etc. So, we’re keeping up with the number of wins per player, for a given game state. Like, a frequency analysis? It’s lanternfish all the way down!

# Constants --------------------------------------------------------------------

# Of the 27 alternate realities created by three rolls of the 'Dirac Die', we
# already know in how many of those universes we rolled a total of `3` (1), a 
# total of `4` (3), and so on. Since these proportions don't change, we can
# define a constant.
const FREQUENCIES = Dict(3 => 1, 4 => 3, 5 => 6, 6 => 7, 7 => 6, 8 => 3, 9 => 1)


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

# Just a type alias for a Dict to keep track of the number of universes that
# current exist for each found game state.
const GameFreqMap = Dict{Game,Int64}


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

# Shorthand function for convenience
function set!(dict, key, value)
    dict[key] = value
end

# For each round of the game, the active player "moves" 27 time in 27 alternate
# realities. We simulate this by keeping track of the number of games in each
# particular 'state' (a `Game` struct) and creating a new `GameFreqMap` where
# each previous game state is advanced by a roll of 3, 4, 5, 6, 7, 8, or 9 (the 
# possible values from three rolls from 1-3) the number of times those values
# can be made by rolling three three-sided dice. If, say, a particular game
# state existed in 10 alternate realities, then after moving there would exist
# 10 realities where that player rolled 3, 30 realities where that player rolled
# 4, 60 realities where that player rolled 5, etc.
function move(games::GameFreqMap, player1 = true)
    nextgames = GameFreqMap()
    victories = 0
    for (game, count) in games
        for (roll, frequency) in FREQUENCIES
            newstate = move(game, roll, player1)
            newcount = count * frequency
            if newstate.player1.points >= 21 || newstate.player2.points >= 21
                # If either player won, there's no need to continue this game
                # state forward, just count the number of realities where that
                # player won.
                victories += newcount
            else
                # Otherwise, check the next games frequency map for this new
                # state, initialize its count to 0 if it doesn't exist, then
                # add the number of new realities where this new state exists.
                newstate ∈ keys(nextgames) || set!(nextgames, newstate, 0)
                nextgames[newstate] += newcount
            end
        end
    end

    return (nextgames, victories)
end


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

# Play the game, roll the crazy die, move the player, repeat until all the games
# have played themselves out. Each time a player wins a game (or more) in one of 
# the alternate realities, add it (them) to the ongoing sum.
function part2(input)
    games = GameFreqMap(input => 1)
    victoryarray = [0, 0]
    player1turn = true

    while !isempty(games)
        (games, victories) = move(games, player1turn)
        if player1turn
            victoryarray[1] += victories
        else
            victoryarray[2] += victories
        end
        player1turn = !player1turn
    end

    return maximum(victoryarray)
end

Yep. Seems like this year’s theme is frequency analysis. I wonder if this is the last problem of this type we’ll see this year, or of there’s one more waiting in the wings… (since this blog post is coming out after Christmas, I’ll know the answer to this question by the time I post it, but acknowledging that means I’d miss out on the suspense!)

Wrap Up

You know, one of the things I really do enjoy about AoC is how these approaches get re-used and tweaked over several days, which really helps drive home an understanding and recognition of this type of problem in many different circumstances. After this year, I should be a lot better at spotting opportunities for frequency analysis in real life, which can be a huge win in terms of algorithmic run times. This is a good argument in favor of practicing all kinds of algorithmic problems and approaches, since you can often find that at least part of a “real world” problem can be solved better, faster, more efficiently when you have a good grasp on some of these algorithmic building blocks. I’m definitely learning a lot this year, and for that, I am grateful.

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

Advent of Code 2021 – Day 21

By: Julia on Eric Burden

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

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 21 – Dirac Dice

Find the problem description HERE.

The Input – Two Lines, Please

The input for today is really simple, just two lines, each of which ends with a number representing the starting board space of a player, in order. The major thing here is having structs to hold and represent each Player and the Game overall, which is also pretty straightforward. There may be a more elegant way to represent the data models for today’s problem, but this seems like a really simple and understandable way to do it.

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

# Represents a player's current "state", their current board position and score
struct Player
	position::Int64
	points::Int64
end
Player(pos::Int64) = Player(pos, 0)

# Represents the current state of the game, both players' board position and
# current score
struct Game
	player1::Player
	player2::Player
end


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

# Given a string, return a Player whose position is the number at the end of
# the string.
playerpos(s) = Player(parse(Int, s[end]))


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

# There's only two lines, the first line for player one and the second line for
# player two, both of which end with a single digit representing that
# player's starting space
function ingest(path)
    return open(path) do f
		player1 = playerpos(readline(f))
		player2 = playerpos(readline(f))
		Game(player1, player2)
    end
end

Part One – I Want to Play a Game

Ok, so no more games with giant squids, now we’re playing games with… the submarine. At this point, we’ve done so much work on this submarine’s systems, surely we can outsmart it, right? I certainly hope so, otherwise we may have a tough time with the remaining days’ puzzles. Actually, part one seems suspiciously straightforward. There’s a bit of implementation here, but it all boils down to looping over the die rolls (which we can calculate in advance), finding a winner, then returning some version of the final game state. We’ve got this!

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

# Given a board position and a roll, return the next position that results from
# that roll. The only tricky bit here is that 10 + 1 wraps around to 1 instead
# of zero.
function nextposition(pos::Int64, roll::Int64)
    pos += roll
    pos > 10 && pos % 10 == 0 && return 10
    pos > 10 && return pos % 10
    return pos
end

# Given a player and a roll, return a `Player` at the next position that will 
# result from the given roll with their score updated to reflect the move.
function move(player::Player, roll::Int64)
    position = nextposition(player.position, roll)
    points = player.points + position
    return Player(position, points)
end

# Given a game board, a roll, and an optional boolean value indicating whether
# or not it is Player 1's turn, return a `Game` reflecting the state that would
# be achieved if the indicated player moves by the amount given by `roll`
function move(game::Game, roll::Int64, player1 = true)
    if player1
        player1 = move(game.player1, roll)
        return Game(player1, game.player2)
    else
        player2 = move(game.player2, roll)
        return Game(game.player1, player2)
    end
end

# Take a `Game` an return either the current high score or the current low score
highscore(game::Game) = max(game.player1.points, game.player2.points)
lowscore(game::Game)  = min(game.player1.points, game.player2.points)

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

# Literally an empty struct for the purposes of creating an iterator over the
# possible die rolls
struct Die end

# On the first roll, the die returns `6` (1 + 2 + 3) and the next starting number
# of `4`. On subsequent rolls, return the sum of the next three numbers and the
# fourth number in sequence as a tuple, to keep the iterator going. The `if`
# statements are there for wrapping around 100 if need be (I don't think it
# actually happens).
Base.iterate(::Die) = (6, 4)
function Base.iterate(::Die, start::Int64)
    (nextvalue, nextstart) = if start < 98
        (sum(start:start+2), start + 3)
    elseif start == 98
        (297, 1)
    elseif start == 99
        (200, 2)
    elseif start == 100
        (103, 3)
    end

    return (nextvalue, nextstart)
end


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

# Play the game as described! Roll the die, move the players, check the score. 
# Whenever a winner is found, return the number of rolls (3 * the number of
# rounds) multiplied by the lowest player score
function part1(game)
    die = Die()
    player1turn = true
    round = 0
    for roll in die
        game = move(game, roll, player1turn)
        round += 1
        highscore(game) >= 1000 && break
        player1turn = !player1turn
    end
    rolls = round * 3
    return rolls * lowscore(game)
end

There wasn’t even any tricky input like yesterday. In fact, part one seemed almost… too easy…

Part Two – Wake Up

Oookay… Part two has us playing with the fabric of reality. Neat! Now, every time we roll the ‘special’ die, the universe splits into 27 new alternate realities, one where we rolled a total of 3, three where we rolled a 4, etc. So, we’re keeping up with the number of wins per player, for a given game state. Like, a frequency analysis? It’s lanternfish all the way down!

# Constants --------------------------------------------------------------------

# Of the 27 alternate realities created by three rolls of the 'Dirac Die', we
# already know in how many of those universes we rolled a total of `3` (1), a 
# total of `4` (3), and so on. Since these proportions don't change, we can
# define a constant.
const FREQUENCIES = Dict(3 => 1, 4 => 3, 5 => 6, 6 => 7, 7 => 6, 8 => 3, 9 => 1)


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

# Just a type alias for a Dict to keep track of the number of universes that
# current exist for each found game state.
const GameFreqMap = Dict{Game,Int64}


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

# Shorthand function for convenience
function set!(dict, key, value)
    dict[key] = value
end

# For each round of the game, the active player "moves" 27 time in 27 alternate
# realities. We simulate this by keeping track of the number of games in each
# particular 'state' (a `Game` struct) and creating a new `GameFreqMap` where
# each previous game state is advanced by a roll of 3, 4, 5, 6, 7, 8, or 9 (the 
# possible values from three rolls from 1-3) the number of times those values
# can be made by rolling three three-sided dice. If, say, a particular game
# state existed in 10 alternate realities, then after moving there would exist
# 10 realities where that player rolled 3, 30 realities where that player rolled
# 4, 60 realities where that player rolled 5, etc.
function move(games::GameFreqMap, player1 = true)
    nextgames = GameFreqMap()
    victories = 0
    for (game, count) in games
        for (roll, frequency) in FREQUENCIES
            newstate = move(game, roll, player1)
            newcount = count * frequency
            if newstate.player1.points >= 21 || newstate.player2.points >= 21
                # If either player won, there's no need to continue this game
                # state forward, just count the number of realities where that
                # player won.
                victories += newcount
            else
                # Otherwise, check the next games frequency map for this new
                # state, initialize its count to 0 if it doesn't exist, then
                # add the number of new realities where this new state exists.
                newstate ∈ keys(nextgames) || set!(nextgames, newstate, 0)
                nextgames[newstate] += newcount
            end
        end
    end

    return (nextgames, victories)
end


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

# Play the game, roll the crazy die, move the player, repeat until all the games
# have played themselves out. Each time a player wins a game (or more) in one of 
# the alternate realities, add it (them) to the ongoing sum.
function part2(input)
    games = GameFreqMap(input => 1)
    victoryarray = [0, 0]
    player1turn = true

    while !isempty(games)
        (games, victories) = move(games, player1turn)
        if player1turn
            victoryarray[1] += victories
        else
            victoryarray[2] += victories
        end
        player1turn = !player1turn
    end

    return maximum(victoryarray)
end

Yep. Seems like this year’s theme is frequency analysis. I wonder if this is the last problem of this type we’ll see this year, or of there’s one more waiting in the wings… (since this blog post is coming out after Christmas, I’ll know the answer to this question by the time I post it, but acknowledging that means I’d miss out on the suspense!)

Wrap Up

You know, one of the things I really do enjoy about AoC is how these approaches get re-used and tweaked over several days, which really helps drive home an understanding and recognition of this type of problem in many different circumstances. After this year, I should be a lot better at spotting opportunities for frequency analysis in real life, which can be a huge win in terms of algorithmic run times. This is a good argument in favor of practicing all kinds of algorithmic problems and approaches, since you can often find that at least part of a “real world” problem can be solved better, faster, more efficiently when you have a good grasp on some of these algorithmic building blocks. I’m definitely learning a lot this year, and for that, I am grateful.

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

Advent of Code 2021 – Day 20

By: Julia on Eric Burden

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

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 20 – Trench Map

Find the problem description HERE.

The Input – A Tale of Two Inputs

Day 20 was interesting in that we basically had two different inputs in a single file. Granted, we’ve seen files with “chunks” of inputs before, but either my memory is faulty (totally plausible) or this is the first time we’ve seen two totally different inputs. Which, really, isn’t much of a problem, as it turns out. The first input comes from the first line, which we’re going to treat as a BitVector since we only need to know if each character is in one of two possible states. For the second input, we’ll use a Dict where the key is the row/col coordinate of a character in the character grid, and the value is a Bool that indicates whether that character is ‘#’ (on) or ‘.’ (off).

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

const Point = NTuple{2,Int64}
const Image = Dict{Point,Bool}


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

function ingest(path)
    return open(path) do f
		# Parse the first line into a BitVector, with '#' => 1, '.' => 0
		algostr = readuntil(f, "\n\n")
		algo = collect(algostr) .== '#'

		# Parse the rest of the lines into a Dict of (row, col) => true/false, 
		# where the value is true if the corresponding row/col of the input
		# is a '#'
		image = Dict{Point,Bool}()
		imagestr = readchomp(f)
		for (row, line) in enumerate(split(imagestr))
			for (col, char) in enumerate(collect(line))
				image[(row,col)] = char == '#'
			end
		end

		(algo, image)
    end
end

The keyword “infinite” in the problem statement clues us in that using a Matrix or even a BitMatrix is going to be the wrong call for this puzzle.

Part One – Beneath a Sea of Light (Pixels)

Today’s puzzle is (thankfully) pretty straightforward. Given a low resolution image, we just keep enhancing it until it resolves into something useful. As Seen on TV! There’s no way this won’t work, plus, we may get to put on our sunglasses in a really cool way after we solve it. YYeeaaaahhh!! We’ll take the values in a 3×3 grid around any given pixel to determine its new value, and the only really tricky bit (‘bit’, get it?) is to know what value to use for pixels we aren’t actively keeping track of. You might think it would be ‘false’ or ‘0’ for all those, but that’s the tricky part!

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

# Used to get the coordinates of the nine pixels surrounding any given
# pixel in the image
const OFFSETS = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)]


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

# Get a list of the coordinates of the pixels surrounding a given point
offsets(p::Point) = [p .+ offset for offset in OFFSETS]

# Convert binary value to decimal
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))

# Given a point in the image, calculate the value of the point from the
# 3x3 area centered on that point
function valueat(image::Image, point::Point, default=false)
    value = [get(image, p, default) for p in offsets(point)]
    return todecimal(value)
end

# Enhance the image! Creates a new image (expanded by one in all directions) 
# where each pixel is flipped according to its calculated value.
function enhance(image::Image, algo::BitVector, default=false)
    newimage = Dict{Point,Bool}()

    # Need to expand the enhancement area by 1 in all directions each pass
    (minpoint, maxpoint) = extrema(keys(image))
    rng = (minpoint[1]-1):(maxpoint[2]+1)

    # For each possible point in the new image, determine its value
    for point in Iterators.product(rng, rng)
        pointvalue = valueat(image, point, default)
        pixel = algo[pointvalue + 1]
        newimage[point] = pixel
    end

    return newimage
end

# Solve ------------------------------------------------------------------------

function solve(input, rounds; test = false)
    (algo, image) = input
    for round in 1:rounds
        # The 'real' algorithm (not the test) has a '#' in the first position 
        # and a '.' in the last position, which means that the 'empty' pixels
        # surrounding the image all flip from '.' to '#' on odd numbered rounds.
        # The 'test' input does not have this 'feature'.
        default = !test && round % 2 == 0
        image = enhance(image, algo, default)
    end
    return sum(values(image))
end

See, apparently Eric Wastl, creator and designer of Advent of Code, thought that after the last two days we were probably having it too easy and he needed to keep us on our toes… Well played! The ‘enhancing algorithm’ for the actual input (not the test input) had the amusing feature that, each round, it would ‘flip’ all the pixels in the infinite expanse of untracked pixels from on, to off, then back again. I feel like there should have been one of those “photosensitive viewers” warnings for this one. But, knowing that, we could just change the default value every other round to get to the final answer.

Part Two – De Nada

Same as Part One, just more times! We’ve seen this sort of escalation before, and since we’re already taking a rounds argument in our part one solve() function, getting the answer here just requires passing 50 instead of 2 as our rounds argument. No new code!

Wrap-Up

Man, I needed Day 20. Days 18 and 19 really stretched me, either leading me down paths that turned out to have some unsatisfactory conclusions (Day 18) or forcing me to learn math (Day 19), and knocked me off my pace of a solution and a blog post every day. With the holidays looming close, a pretty straightforward implementation for Day 20 with one weird trick thrown in to spice things up was exactly the sort of enjoyable, non-head-bashing sort of day I needed. I will say, that having gotten this far with Julia, I was delighted at how smoothly the code came out of my fingers and how well I was able to think in Julia, even for this relatively easier puzzle. Just in time, too!

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