Advent of Code: Subterranean Sustainability

Written by Pete Corey on Dec 20, 2018.

Day twelve of this year’s Advent of Code essentially asks us to implement a basic one dimensional cellular automata that can look two spaces to the left and right of itself. We’re given an infinite row of “pots”, and an initial configuration of pots that contain living plants. We’re asked, after twenty generations, the sum of the pot numbers that contain living plants.

Let’s take a stab at this using the J programming language.

Our sample starting state already looks a lot like a bit mask, so let’s do a little massaging and get it into a form we can work with:

    replacements =. 'initial state: ';'';'=> ';'';'.';'0 ';'#';'1 '
    path =.  '/Users/pcorey/advent_of_code_2018/day_12/input'
    replaced =. cutopen replacements rplc~ (1!:1) < path

    NB. Parse out initial state as boolean array
    initial =. ". > {. replaced
1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1

Great. Now let’s work with the patterns, or cellular automata rules, we were given and work them into a structure we can deal with:

    NB. Build matrix of replacement patterns
    patterns =. }:"1 ". > }. replaced
1 1 1 1 0
1 1 1 0 1
1 1 1 0 0
...

Similarly, we’ll build up our list of resulting pot values, or replacements, if we find any of those matching patterns:

    NB. Build array of replacement values
    replacements =. {:"1 ". > }. replaced
0 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0

Great. Now let’s write a monadic verb that takes a 5-length array of bits, or booleans, and returns the corresponding replacement value:

    NB. Replace a length-5 y with a replacement value
    replace =. replacements"_ {~ patterns&i.

    replace 0 1 0 1 0
1

And now we can tie everything together with an iterate verb that takes our initial configuration, breaks it into overlapping chunks of 5-length arrays, and repeatedly applies replace to each chunk (with some extra padding thrown in to catch edge cases):

    iterate =. 3 : 0
      (1 ,: 5) replace;._3 (0,0,0,0,y,0,0,0,0)
    )

We can iterate twenty times over our initial starting configuration:

    iterated =. iterate^:20 initial

At this point we could iterate <20 times to build up an array of each iteration, and visualize the growth of our plants using viewmat:

Our plants' growth over time.

Finally we can convert our bit mask of pots with living plants into a list of coordinates, and print the sum:

    echo +/ iterated # (iterations * 2) -~ i. # iterated
325

Part Two

Part two asks us for the sum of the pot numbers with living plants after fifty billion (50,000,000,000) generations. Obviously, we can’t run our simulation for that long! We need to find some kind of pattern in our iterations.

To help, I decided to refactor my part one solution to simply keep track of an array of pot numbers with living plants, instead of a bit mask of all possible pots:

    NB. Build matrix of replacement patterns
    patterns_and_output =. ". > }. replaced
    patterns_to_keep =. {:"1 patterns_and_output
    patterns =. patterns_to_keep # ([: < 2 -~ I.)"1 }:"1 patterns_and_output
    NB. patterns =. patterns #~ 1 {:: patterns

    check_pattern =. 4 : 0
      pot_to_check =. 0 {:: x
      pots_with_plants =. 1 {:: x
      pattern_to_check =. > y

      pots_above_cutoff =. pots_with_plants >: pot_to_check - 2
      pots_below_cutoff =. pots_with_plants <: pot_to_check + 2
      pots_to_check =. pots_above_cutoff *. pots_below_cutoff
      pots_to_check =. pots_to_check # pots_with_plants

      (pot_to_check + pattern_to_check) -: pots_to_check
    )

    check_pot =. 4 : 0
      pot_to_check =. y
      pots_with_plants =. x
      +./ (pot_to_check;pots_with_plants)&check_pattern"0 patterns
    )

    iterate =. 3 : 0
      pots_with_plants =. > y
      pots_to_check =. (2 -~ <./ pots_with_plants) + i. 4 + (>./ - <./) pots_with_plants
      next_pots_with_plants =. < pots_to_check #~ pots_with_plants&check_pot"0 pots_to_check
      next_pots_with_plants
    )

As you can see, I tried to be extra clear and verbose with my naming to keep myself from getting confused. I think the result is some fairly readable code.

As an example, I can grab the twentieth generation of pots with living plants like so:

    iterate^:20 <initial
┌─────────────────────────────────────────────────────┐
│_2 3 4 9 10 11 12 13 17 18 19 20 21 22 23 28 30 33 34│
└─────────────────────────────────────────────────────┘

My plan of attack for finding the repeating pattern was to look for a cycle. If a generation, offset to zero, or normalized, ever matches a normalized generation we’ve seen previously, we’ve found a cycle.

I wrote two verbs to help me find this cycle and return some information about it:

    normalize =. <@:(<./ -~ ])@:>

    find_cycle =. 3 : 0
      previous =. 0 {:: y
      previous_normalized =. 1 {:: y
      next =. iterate {: previous
      next_normalized =. normalize next
      if. (next_normalized e. previous_normalized) do.
        next_min =. <./ > next
        previous_min =. <./ > {: previous
        (# previous);(previous_normalized i. next_normalized);(next_min - previous_min);({: previous)
      else.
        if. 1000 < # previous do.
          return.
        end.
        find_cycle (previous,next);<(previous_normalized,next_normalized)
      end.
    )

The find_cycle is a recursive verb that maintains a list of previous generations, and their normalized form. Every call it calculates the next generation and its normalized form. If it finds a cycle, it returns the number of previous generations we’ve seen, the index the repeated generation loops back to, the number of pots we’ve moved, and the last non-cyclical generation we processed, all boxed together.

    find_cycle (<initial);(<normalize<initial)                                
┌──┬──┬─┬───────────────────────────────────────────────────────────┐
│87│86│1│12 14 20 22 28 30 40 42 48 50 61 63 69 71 76 78 87 89 96 98│
└──┴──┴─┴───────────────────────────────────────────────────────────┘

So it looks like our cycle starts at pot eighty six, and has a cycle length of one. This actually simplifies things quite a bit. This basically means that after reaching generation eighty six, our plants just move to the right each generation.

Let’s change our find_cycle function to return just the generation the cycle starts, and the set of pots with living plants at that generation. We can use that to find out how many position we need to add to that set of pots before we sum them for our final answer:

    result =. find_cycle (<initial);(<normalize<initial)
    to_add =. 50000000000 - (0 {:: result)
    final_pots_with_plants =. to_add + (1 {:: result)
    +/ final_pots_with_plants

Notes

  • Pass a boxed number into ^: to return an array of applications of the verb, not just the last result.
  • Use the cut verb (;.) to chunk an array into overlapping sub-arrays.

Optional Notes and Exact Pitches in Chord

Written by Pete Corey on Dec 17, 2018.

Currently my Elixir-powered Chord project does a lot of really cool things. It can generate a huge number of guitar chords given a set of notes you want included in those chords. It also computes the voice leading distance and fingering distance between those chords, which let’s us map out “ideal” chord progressions.

While this functionality is awesome in and of itself, it’s missing a few key features that would bring it to the next level.

Traditionally, musicians quickly learn song with the help of lead sheets. A lead sheet consists of a melody laid out over a set of chords. It’s up to the musician to interpret and play those chords with the given melody in a way that makes sense for both the player and the listener.

An example lead sheet.

I want Chord to be able to generate possible interpretations of a lead sheet by giving us chord progressions that include optional notes and specific melody notes.

Supporting Optional Notes

It may be surprising to hear, but often times many of the notes that make up a chord are entirely optional!

For example, if I’m playing a Cmaj7 chord, which is made up of the root of the chord, the third, the fifth, and the major seventh, it’s usually acceptable to omit the fifth of the chord. The fifth usually just serves to add harmonic stability to the root note, and isn’t necessary to convey the color of the chord to the listener.

The ability to mark a note as optional drastically expands the possible set of chords we can generate for a given set of notes. For each optional note, we need to generate all of the possible chords that include that note, all of the possible chords that do not include it, and merge the results together.

Let’s update our Chord.Voicing module to do that now.

Within our Chord.Voicing module is a function, all_note_sets/1 that takes a set of notes, and returns a list of all possible “note sets” that can be spread across the strings of the guitar to build chords.

A note set is really just a collection of notes we want to play. For example, if we’re trying to play a Cmaj7 with an optional fifth, some of our note sets might look like this:


[[0, 4, 11],            # root, third, seventh
 [0, 4, 11, 0],         # root, third, seventh, root
 [0, 4, 11, 4],         # root, third, seventh, third
 [0, 4, 11, 11],        # root, third, seventh, seventh
 [0, 4, 11, 7],         # root, third, seventh, fifth
 [0, 4, 11, 7, 0],      # root, third, seventh, fifth, root
 ...
 [0, 4, 7, 11, 11, 11]] # root third, seventh, seventh, seventh, seventh

Notice that the smallest note set is the set of all three required notes. Also note that after those first three required notes is every possible permutation of every possible note in the chord, required and optional notes included.

We can implement this fairly easily in our all_note_sets/1 function. Let’s start by filtering the provided set of notes down to just the required notes:


required_notes =
  Enum.filter(notes, fn
    {:optional, note} -> false
    _ -> true
  end)

We’ll assume that optional notes are keyword tuples with :optional as the first element and the actual note as the second value. Require notes are simply bare note values.

Next, let’s filter notes down to the list of just optional notes:


optional_notes =
  Enum.filter(notes, fn
    {:optional, note} -> true
    _ -> false
  end)

Finally, let’s get a list together of all possible notes, optional and required included:


all_notes =
  Enum.map(notes, fn
    {_, note} -> note
    note -> note
  end)

Now that we’ve put our ducks in a row, generating all of our possible note sets if fairly straight forward.

We know that every note set will start with our set of required notes. That means that the length of each note set will range in length from the length of the required notes to 6, the number of strings on a guitar:


length(required_notes)..6

We also know that after the set of required notes the remaining space in the note set will be filled by every permutation of all possible notes (allowing repetition):


Permutation.generate(all_notes, length - length(required_notes), true)

We can loop over each of these sets of values and combine the results in a list comprehension to come up with our final list of note sets:


for length <- length(required_notes)..6,
    tail <- Permutation.generate(all_notes, length - length(required_notes), true) do
  required_notes ++ tail
end

Supporting Exact Pitches

Once we’ve built our note sets, we need to translate them into actual chords. Our Chord.Voicing module does this with the help of the all_notes/3 function, which takes a single note from our note set and finds all possible locations on the fretboard where that note can be played.

As we talked about in a previous article, it does this by building a complete fretboard and then filtering out, or sieving, any notes on the fretboard that aren’t the note we’re trying to play.

The original code that decided if the provided target_note matched the note at the given fret (index) and string looked something like this:


if rem(note, 12) == target_note do
  {string, index}
else
  nil
end

If the pitch class of the note (rem(note, 12)) matches our target_note, add the current string and fret to the list of tuples to be returned by our all_notes/3 function.

This solution assumes that all of the notes in our note sets are pitch classes, or values between 0 and 11. If we’re looking for a C and our target_note is 0, it will match on any octave of C it finds across the fretboard.

We can modify this solution to support exact pitches with minimal effort. If we assume that exact pitches will be passed in through the target_note parameter just like pitch classes (as plain numbers), we can add a fallback check to our condition that checks for exact equality:


cond do
  rem(note, 12) == target_note -> {string, index}
  note == target_note -> {string, index}
  true -> nil
end

If the pitch class of the current note doesn’t match our target_note, the untouched value of note still might. For example, if we’re looking specifically for a middle C (60), this condition would match on only those exact pitches, and not any higher or lower octaves of C.

Final Thoughts

Our Chord.Voicing module now supports building chords out of note sets that include both optional notes and exact pitches. We’re one step closer to modeling lead sheets!

As an interesting aside, when I started this refactor, I noticed that the original implementation of all_note_sets/1 was completely wrong. I’m not sure what was going through my mind when I wrote that first version, but it was only returning a small subset of all possible note sets. Equipped with the new implementation, Chord is generating many times the number of possible chords for us to play with.

Be sure to check out the entire Chord project on Github, and stay tuned for more updates and experiments.

Advent of Code: Marble Mania

Written by Pete Corey on Dec 14, 2018.

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

  • 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.