Advent of Code 2020 Day 22
[20201222]
#development #adventofcode #julia
Previous: Advent of Code 2020 Day 21
Next: Advent of Code 2020 Day 23
Part 1
This seems pretty straighforward to do iteratively. I’ll read each deck into a
Vector
(Julia provides dequelike operations on
Vectors instead of
more specialized structures):
Deck = Vector{Int}
Then popfirst!()
the first card off each, compare, and push!()
the cards
onto the winner’s deck. Continue until one deck is empty.
function combat(d1::Deck, d2::Deck)
i = 1
while length(d1) > 0 && length(d2) > 0
c1 = popfirst!(d1)
c2 = popfirst!(d2)
if c1 > c2
push!(d1,c1,c2)
else
push!(d2,c2,c1)
end
@debug "round $i" c1 c2 d1 d2
i += 1
end
length(d1) > 0 ? deckscore(d1) : deckscore(d2)
end
Computing the score is a simple operation:
deckscore(d::Deck) = sum(d .* (length(d):1:1))
Part 2
Well it’s straighforward to make the game naively recursive, but what are the
odds the naive solution will complete without a stack overflow or in a
reasonable time? I’ll start there anyways. I use a Set
containing the product of the two deck scores to catch the infinite game. It may also catch noninfinate games since it’s not necessarily unique, but we’ll see.
rounds = Set(deckscore(d1)*deckscore(d2))
Then we just need to catch the recursive game trigger:
if length(d1) >= c1 && length(d2) >= c2
w = recursivecombat(copy(d1), copy(d2), game=game+1)
if w == 1
push!(d1,c1,c2)
else
push!(d2,c2,c1)
end
Otherwise fall back to the previous “standard” round. I use an incremental game number to decide what the result should be: if it’s greater than 1 then the game will just return the player number that won (1 or 2) since we don’t care about the score. ^{1}
Sure enough, this works for the test case, but isn’t finishing in a reasonable time for the problem input. Is there a clever way to decide the outcome of a game, instead of iterating through it? What about an alternative representation for the decks?
Since the cards are just numbered without repeats, I could use a single array for them, and track whose hand (or none) each card is in, and what order it appears. That would greatly cut down on the allocations, but at the expense of more searching and filtering of the deck.
to be continued…

After getting to use Rust’s “fat” enums I really miss them in other languages  here it would be nice to return an enum indicating which player won and their score. Sure I could use a
Struct
orTuple
, but enums (with rich patternmatching) are just so elegant! ↩︎