Discussion on: AoC Day 9: Marble Mania

[Mustafa Haddara]

My first approach was just to brute force this, using a big array and inserting/removing as needed.

For the Part 1 input, this was...fine. It ran in less than half a second.

For the Part 2 input, however, it didn't simply scale up 100x! (0.5 seconds * 100 = 50 seconds = still Fast Enough). I'm guessing all of the array slicing/copies meant that this brute force algorithm was actually n², so scaling up the input size by 100 meant scaling up the run time by 10,000!

It took me a second to realize the trick was to use a circular doubly-linked list. Then, iterating through "clockwise" is following the next pointer, while iterating "counter-clockwise" is the prev pointer.

Here's what that looks like in Julia:

function find_winning_player(input)
    num_players, final_marble_value = parse_input(input)
    marbles = Circle(0)
    points = map(c->Int(c), zeros(num_players))

    current_marble = 1
    current_player = 1

    while current_marble <= final_marble_value
        if current_marble % 23 == 0
            # do weird point stuff
            points[current_player] += current_marble
            to_remove = marbles
            for _ in 1:7
                to_remove = to_remove.prev
            end
            points[current_player] += to_remove.value
            # delete to_remove
            to_remove.prev.next = to_remove.next
            to_remove.next.prev = to_remove.prev
            marbles = to_remove.next
        else
            # insert
            one_ahead = marbles.next
            two_ahead = one_ahead.next

            next_marble = Circle(current_marble, one_ahead, two_ahead)

            one_ahead.next = next_marble
            two_ahead.prev = next_marble
            marbles = next_marble
        end
        current_marble += 1
        current_player += 1
        if current_player > num_players
            current_player = 1
        end
    end

    return maximum(points)
end

mutable struct Circle
    value::Int
    prev::Circle
    next::Circle
    function Circle(value::Int) 
        c = new()
        c.value = value
        c.prev = c
        c.next = c
        return c
    end

    Circle(value::Int, prev::Circle, next::Circle) = new(value, prev, next)
end

function parse_input(input)
    chunks = split(input, " ")
    num_players = parse(Int, chunks[1])
    point_value = 100*parse(Int, chunks[7])
    return (num_players, point_value)
end

function main()
    filename = ARGS[1]  # julia arrays are 1-indexed!
    input = split(read(filename, String), "\n")[1]
    test_input = "10 players; last marble is worth 1618 points"

    println(find_winning_player(input))
end

main()

Creating an initial node that points to itself feels weird, but to be fair that models the circle idea correctly.

[Joe Zack]

Heh yeah...I put too much thought into how those first couple turns would go with the circular linked list. Turns out it "just worked" :)

[Mustafa Haddara]

I know, right?! It's like magic.