### re: AoC Day 9: Marble Mania VIEW POST

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

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

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

code of conduct - report abuse