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!
Top comments (0)