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. 🎅)
Top comments (16)
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 theprev
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.
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
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.
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 the part 1 using 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 2 I 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 about Doubly Circular Linked List. After that implementation was quick and easy :)
Nice find!
PHP
OKAY 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 did today's entry in C, both for fun and because writing linked lists just feels natural in C!
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, orcircle - 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
orArray
I could also use a Circle! Insert the correct number of zeros at the start of the game, then just useplayer += 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
toLong
for part 2 but it's still nothing to a modern computer, even this half-decade old Thinkpad.