Advent of Code 2020 Day 22

Part 1

This seems pretty straighforward to do iteratively. I’ll read each deck into a Vector (Julia provides deque-like 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 non-infinate 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. ¹

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…