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:
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
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
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
current_marble += 1
current_player += 1
if current_player > num_players
current_player = 1
mutable struct Circle
c = new()
c.value = value
c.prev = c
c.next = c
Circle(value::Int, prev::Circle, next::Circle) = new(value, prev, next)
chunks = split(input, " ")
num_players = parse(Int, chunks)
point_value = 100*parse(Int, chunks)
return (num_players, point_value)
filename = ARGS # julia arrays are 1-indexed!
input = split(read(filename, String), "\n")
test_input = "10 players; last marble is worth 1618 points"
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.
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.