# AoC Day 9: Marble Mania

### Ryan Palo Dec 9 '18 ・1 min read

It's the weekend, and I'm using that to get caught up since I was starting fall behind throughout last week. Hopefully, you're able to keep up with this hectic pace!

On Day 9's challenge, the elves are teaching us marble games! Given a series of moves, we'll be simulating the game and calculating scores.

Let's get rolling! (Eh? Eh? A little bit of marble humor there, just for you. 🎅)

Classic DEV Post from Jan 30

## JavaScript solution

The trick for this one is to use a circular linked list. You need to handle pointers to both right and left nodes for each addition and removal.

Then, traversing clockwise is just moving rightward and counter-clockwise is leftward.

## reader.js

## 09-common.js

## 09a.js

## 09b.js

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

actuallyn^{2}, 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:

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.

Python has a super-powered C doubly linked list built in, so I feel like I'm totally cheating here, but:

When I was whiteboarding this out, I was noticing a mathematical pattern. Didn't fully go down that road, but I'd be super interested to see if someone did this using arithmetic instead of a linked list.

Circular data structures always come up in Advent of Code. You can obviously implement it with a linear array or list and modulo arithmetic but I think I'm going to have some fun with Kotlin today. Let's implement a real circular data structure:

An interesting property of this data structure is that a reference to any node is a reference to the whole structure. So we don't need to separately keep track of the overall structure and the current node. Which implies some interesting possible operations on it:

That is we can say

`circle + 2`

to get the node 2 positions clockwise around the circle, or`circle - 7`

to get the node 7 positions counter-clockwise. It doesn't matter if this loops around one or more times past the starting point as it is a genuinely circular data structure.The puzzle involves inserting and removing nodes, so let's implement those:

Simple stuff, hard to get wrong. Just one corner case around removing the last node as we don't have a representation of an empty circle. The game doesn't require it anyway as we always start with the 0 marble.

Finally we need to see the content of the nodes in the circle. Kotlin's subscript syntax makes sense for this:

When I started implementing the game I realised the players play in a round-robin fashion, and instead of keeping their scores in a

`Map`

or`Array`

I could also use a Circle! Insert the correct number of zeros at the start of the game, then just use`player += 1`

to move to the next player at each step. I also had to add a subscript setter operation analagous to the getter, so the scores could be updated.One final thing was needed to allow Circle to be used for the players: I had to be able to find the highest score. A simple approach is to allow extraction of a certain number of values:

This data structure made implementing the game really easy:

There is likely a numerical solution to this puzzle - there certainly looks like there's some kind of binary pattern in the example - but this data structure is so simple my solution worked for all the test cases and the part 1 problem on first try. I had to up the default JVM heap size and change the score type from

`Int`

to`Long`

for part 2 but it's still nothing to a modern computer, even this half-decade old Thinkpad.For the part 1, I used the naive solution with an array. It took about 0.55s.

For part 2, it took 2h 47m, so I decided to switch to linked lists. Using POSIX::_exit I skipped the final global destruction, which saved me almost 1 second, so the program finished in 8s.

I think this has been my favorite problem so far.

I wrote a helper method "cycle" that would move $x left or right and made for an easy translation from the problem description to code.

Part B was a nice surprise for a lazy Sunday morning :)

I managed to do this in elixir! As elixir is immutable it cant have real circular data structures so i had to use zippers

The second challenge took 3 s :)

I did today's entry in C, both for fun and because writing linked lists just feels natural in C!

I did the

part 1using array and splicing and it took ~30 seconds to finish (and it was getting exponentially slower as the number of marbles increased).So for the

part 2I tried to find the correct data structure, but not having CS background I spent a lot of time just googling around not finding anything suitable. Finally I looked at reddit for a hint and learned aboutDoubly Circular Linked List. After that implementation was quick and easy :)Nice find!

PHPOKAY FINALLY. I had to up the PHP default memory limit by 8x to actually get the second part to run because I kept running into memory allocation problems, haha. Also learned a bunch about how references work in PHP to stop the program from segmentation faulting! Exciting!

Part 1 (brute force-ish):

Part 2: (double circular linked list implementation)

I found out (seems like a lot of other people did too) that rotating a doubly-linked list is way faster than inserting/removing with indices. Still felt like a boss when my code cranked through seven million possibilities in a few seconds :) Man, I love coding.

@ben , I just realized that this series is going to be a nice stress-test of your Series dots CSS. 😬

It’s true. At some point we’ll have to adjust it so it looks a bit better with many posts, but if it looks a bit goofy for a bit it’s not the end of the world.