## DEV Community is a community of 606,099 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

# Discussion on: AoC Day 9: Marble Mania Mustafa Haddara • Edited

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)
point_value = 100*parse(Int, chunks)
return (num_players, point_value)
end

function main()
filename = ARGS  # julia arrays are 1-indexed!
input = split(read(filename, String), "\n")
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.