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:

funinsertClockwise(value:T):Circle<T>{valnode=Circle(value,this,next)next.prev=nodethis.next=nodereturnnode}funinsertAnticlockwise(value:T):Circle<T>{valnode=Circle(value,prev,this)prev.next=nodethis.prev=nodereturnnode}funremove():Circle<T>{if(prev==this&&next==this)throwIllegalStateException("can't remove the last node in a circle")prev.next=nextnext.prev=prevreturnnext}

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:

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.

## re: AoC Day 9: Marble Mania VIEW POST

FULL DISCUSSIONCircular 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.