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.

      NB. Return our updates arguments.
      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
      head =. x
      l =. <": y
      nl =. <": head
      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.
      addr =. mema 8*type
      NB. Write the value, prev ptr, and next ptr.
      res =. (0,addr,addr) memw (addr,0,3,type)
      addr
    )

    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.
      addr =. mema 8*type

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

      addr
    )

    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.

Notes