Advent of Code day nine asks us to play a game. The game is played by placing marbles, or numbers, around a circle, or a circular list. If you play a marble that’s a multiple of `23`, you keep that marble, and the marble seven marbles behind your current position. We’re to figure out the winning player’s score after thousands of rounds of this game.

As usual, we start things off by pulling in our input and massaging it into a workable form. Let’s kick things off by defining some replacements:

``````    replacements =. 'players; last marble is worth';''
replacements =. replacements;'points';''
``````

Next let’s load our puzzle input, execute our replacements, and parse the resulting numbers:

``````    path =.  '/Users/pcorey/advent_of_code_2018/day_09/input'
NB. Load the file, remove everything that's not a number, and assign.
'players highest_marble' =. ". replacements rplc~ (1!:1) < path
``````

Some destructing helps us pull out the number of players and the number of turns we should play out, or the highest marble to be played.

Now let’s write a `turn` verb that takes the current state of the board, the current player, the current marble being played, and all players’ scores. We’ll place our marble in the correct position in the circular board, potentially update the current player’s score, and return our modified state:

``````    turn =. 3 : 0
NB. Destructure my arguments.
circle =. 0 {:: y
player =. players | 1 {:: y
marble =. 2 {:: y
scores =. 3 {:: y

if. 0 = 23 | marble do.
NB. Grab the current player's current score.
score =. player { scores
NB. Add the marble they would have placed to their score.
score =. score + marble
NB. Rotate circle 7 counter-clockwise
circle =. _7 |. circle
NB. Add the marble we landed on to the player's score.
score =. score + {. circle
NB. Update the scores list with the player's new score.
scores =. score (player}) scores
NB. Remove the marble we landed on.
circle =. }. circle
else.
NB.
circle =. marble , 2 |. circle
end.

circle;(player + 1);(1 + marble);scores
)
``````

It turns out modeling a circular repeating list is easy using J’s “rotate” (`|.`) verb.

Because we’re returning the same data from `turn` as we’re passing in, we can use the “power” verb (`^:`) to repeatedly apply `turn` to an initial set of inputs:

``````    scores =. 3 {:: (turn^:highest_marble) 0;0;1;(players \$ 0)
``````

Applying `turn` `highest_marble` times to our initial state (`0;0;1;(players \$ 0)`) gives us a final list of player scores.

We find out final answer by returning the maximum score:

``````    >./scores
``````

## Part Two

Part two asks for the highest player’s score if we continue playing for `highest_marble*100` turns. This turned out to be an incredibly difficult problem for me to solve using J.

The problem here is performance. Playing two orders of magnitude more turns increases the runtime of our first solution from a few seconds to significantly longer than I’m willing or capable of waiting. We need a better solution. The obvious solution is to use a data structure that’s better suited to rotations, insertions, and removals than a plain array. A doubly linked, circular linked list would be perfect here.

I started researching how to implement a doubly linked list in J. It turns out that this type of low-level data manipulation goes against the grain of J’s intended use. Apparently J code is intended to be descriptive, while the interpreter does the heavy lifting of optimization. Unfortunately, it wasn’t doing a great job with my part one solution.

I was hell bent on building a doubly linked list. My first implementation was modeled after this (seemingly hacky) exploitation of J “locatives”, or namespaces:

``````    init =. 3 : 0
l =. <": y
v__l =. y
n__l =. 0
p__l =. 0
)

insert =. 4 : 0
l =. <": y
pl =. <": p__nl
v__l =. y
n__l =. n__pl
p__l =. p__nl
n__pl =. y
p__nl =. y
v__l
)

remove =. 3 : 0
l =. <": y
nl =. <": n__l
pl =. <": p__l
n__pl =. n__l
p__nl =. p__l
v__nl
)

rotate_cw =. 3 : 0
l =. <": y
n__l
)

rotate_ccw =. 3 : 0
l =. <": y
p__l
)
``````

Unfortunately, while this was faster than my original solution, it was still too slow to give me my answer in a reasonable amount of time.

My next attempt led me directly allocating, reading, and writing my own data structures directly into memory using J’s `mema`, `memr`, and `memw` utility verbs. At this point I was basically justing writing C code with weird syntax:

``````    init =. 3 : 0
NB. Allocate space for a new node.
NB. Write the value, prev ptr, and next ptr.
)

insert =. 4 : 0
'v pp pn'    =. memr x, 0,3,type
'pv ppp ppn' =. memr pp,0,3,type
'nv npp npn' =. memr pn,0,3,type

NB. Allocate and write new node.

if. *./ x = pp , pn do.
NB. Only 1 element in the list.
else.
if. pp = pn do.
NB. Only 2 elements in the list.
else.
NB. Normal insertion case.
(nv,x,npn) memw pn,0,3,type
end.
end.

)

remove =. 3 : 0
'v pp pn' =. memr y,0,3,type
'pv ppp ppn' =. memr pp,0,3,type
'nv npp npn' =. memr pn,0,3,type

NB. Free the current node.
memf y

NB. Update neighbor nodes
(pv,ppp,pn) memw pp,0,3,type
(nv,pp,npn) memw pn,0,3,type

pn
)

rotate_cw =. 3 : 0
'v pp pn' =. memr y,0,3,type
pn
)

rotate_ccw =. 3 : 0
'v pp pn' =. memr y,0,3,type
pp
)
``````

Mercifully, this solution was much faster than my previous two. I was able to find my answer in roughly two minutes.

Check out the full source for all three solutions on Github, if you’re curious.

• Rotate (`|.`) is awesome.
• J is meant to be descriptive?
• I needed to allocate more than `12` bytes to comfortably fit three integers. But only sometimes. Why?
• You can time things using the `6!:2` foreign.