re: AoC Day 9: Marble Mania VIEW POST

FULL DISCUSSION
 

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 n2, 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.

 

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" :)

 
code of conduct - report abuse