Advent of Code - Day 9

Note: This topic is to talk about Day 9 of the Advent of Code.

For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.


Here’s my solution to Day 9:

Inspired by @josevalim, I live streamed the creation of it for the first time. You can watch the video here (until it falls off Twitch 14 days from now):

The main idea is just that I hand-rolled a doubly linked list and used that to solve both problems. It does part two in a little under a minute. I’m looking forward to seeing how others do it faster.


This is my solution to day 9. On my machine it takes some 3.5 sec for the second part. The key idea in my solution is to use zippers to implement a circular list.


Here’s my naive solution use a single list. The implementation was too slow to solve the second part.


I liked your implementation of a linked-list as a Map structure. Also, the way you’ve found the 7th marble counter clockwise from the current one using Stream.iterate was awesome. I need to get acquainted with the Stream module more that’s for sure. I’ve enjoyed your stream. Thank you!

My very naive implementation wouldn’t complete Part 2 within the time I was willing to wait for it to do so. I got Part 1 and the given tests passing, so I’m cool with that.

Thank you so much to reply here !!@sasajuric. It is the most important key to solve this problem using your zipper list. I learn a lot from this zippers.

1 Like

My solution is here and it calculates the part 2 solution in about 30 seconds.

I need to now look at what others have done but I think I was on roughly the right track by creating a map where the key is the turn number and the value is a struct containing the previous and next keys so that you can step forwards and backwards from the current marble.

My code to update the struct isn’t terribly concise and that may be a good place for performance improvements but @sasajuric’s solution seems to be the one I need to look at in depth as well as the aforementioned zippers.