Advent of Code: The Sum of Its Parts

Written by Pete Corey on Dec 7, 2018.

Day seven of this year’s Advent of Code asks us to find the order in which we must complete a set of steps in a directed graph. Let’s see how well we can do with this task using the J programming language!

My high level plan of attack for this task is to keep each pair of dependencies in their current structure. I’ll build a verb that takes a list of “completed” steps, and the list of pairs relating to uncompleted steps. My verb will find the first (alphabetically) step that doesn’t have an unmet dependency in our list, append that step to our list of completed steps, and remove all pairs that are waiting for that step being completed.

Thankfully, parsing our input is easy today:

    parse =. (5 36)&{"1
    pairs =. |."1 parse input
AC
FC
BA
DA
EB
ED
EF

We can write a helper that takes our list of pairs and returns all of the steps referenced in them in a raveled list:

    steps =. [: /: [: . ,
    steps pairs
ABCDEF

Now we can write our verb that completes each step of our instructions:

    next =. 3 : 0
      done =. 0 {:: y
      pairs =. 1 {:: y
      steps =. steps pairs
      left =. {."1 pairs
      right =. {:"1 pairs
      next_step =. {. steps #~ -. steps e. ~. left
      next_pairs =. pairs #~ -. right e. next_step
      remaining_pairs =. pairs #~ right e. next_step

      append =. (done,next_step)"_
      return =. (done)"_
      next_step =. (append ` return @. (0 = # remaining_pairs)"_) _

      next_step;next_pairs
    )

I’m trying to be more explicit here, and rely less on tacit verbs. Last time I found myself getting lost and hacking together solutions that I didn’t fully understand. I’m trying to pull back and bit and do things more intentionally.

We can converge on the result of repeatedly applying next to our list of pairs and an empty starting set of completed steps:

    0{:: next^:_ '' ; pairs
CABDF

An unfortunate side effect of our algorithm is that our last step in our graph is never appended to our list. We need to find this step and append it ourselves:

    append_last =. 4 : 0
      steps =. steps x
      missing =. steps #~ -. steps e. ~. y
      y,missing
    )
    echo pairs append_last 0{:: next^:_ '' ; pairs
CABDFE

And that’s all there is to it!

Part Two

Part two was much more complicated than part one. Each step takes a specified amount of time to complete, and we’re allowed to work on each step with up to four workers, concurrently.

This was the hardest problem I’ve solved so far throughout this year’s Advent of Code. My general strategy was to modify my next verb (now called tick) to additionally keep track of steps that were actively being worked on by concurrent workers.

Every tick, I check if there are any available steps and any space in the worker queue. If there are, I move the step over. Next, I go through each step being worked on by each worker and subtract 1. If a step being worked on reaches 0 seconds of work remaining, I add it to the done list.

Eventually, this solution converges on my answer.

I’m not at all happy with my code. I found myself getting deeply lost in the shape of my data. After much struggling, I started to make heavy use of $ to inspect the shape of nearly everything, and I peppered my code with echo debug statements. The final solution is a nasty blob of code that I only just barely understand.

Enjoy.

Notes

Advent of Code: Chronal Coordinates

Written by Pete Corey on Dec 6, 2018.

Today’s Advent of Code challenge asked us to plot a Manhattan distance Voronoi diagram of a collection of points, and to find the area of the largest, but finite, cell within our diagram.

I’ll be honest. This was a difficult problem for me to solve with my current level of J-fu.

My high level plan of attack was to build up a “distance matrix” for each of the points in our diagram. The location of a point would have a value of 0, neighbors would have a value of 1, and so on. In theory, I’d be able to write a verb that combines two matrices and returns a new matrix, with tied distances represented as _1. I could insert (/) this verb between each of my matrices, reducing them down to a final matrix representing our Voronoi diagram.

I wrote some quick helper verbs to find the distance between two points:

    d =. [: +/ |@-

Find the width and height of the bounding rectangle of my input:

    wh =. 1 + >./ - <./

Generate the set of coordinates for my matrices (this one took some serious trial and error):

    coords =. 3 : 0
      'w h' =. (1 + >./ - <./) y
      (<./y) +"1  (i. h) ,"0~ ((h,w) $ i. w)
    )

And to fill that matrix with the distances to a given point:

    grid =. 4 : 0
      (x d ])"1 coords > y
    )

The process of adding together two matrices was more complicated. I went through many horribly broken iterations of this process, but I finally landed on this code:

    compare =. 4 : 0
      'vx ix' =. x
      'vy iy' =. y
      vx = vy
    )

    tie =. 4 : 0
      (0 {:: x);_1
    )

    pick =. 4 : 0
      'vx ix' =. x
      'vy iy' =. y
      v =. vx ((y"_) ` (x"_) @. <) vy
    )

    add =. 4 : 0
      x (pick ` tie @. compare) y
    )

With that, I could compute my final grid:

    numbers =. ". input
    grids =. ([ ;"0 i.@#) numbers grid"1 <numbers
    sum =. add"1/ grids

Our sum keeps track of closest input point at each position on our grid, and also the actual distance value to that point. The closest input point is what we’re trying to count, so it’s probably the more interesting of the two values:

    groups =. (1&{::)"1 sum
 0  0  0 0 _1 2 2  2
 0  0  3 3  4 2 2  2
 0  3  3 3  4 2 2  2
_1  3  3 3  4 4 2  2
 1 _1  3 4  4 4 4  2
 1  1 _1 4  4 4 4 _1
 1  1 _1 4  4 4 5  5
 1  1 _1 4  4 5 5  5
 1  1 _1 5  5 5 5  5

We could even render the grid using J’s viewmat utility. Awesome!

Our sample inputs, visualized with viewmat.

Using viewmat to visualize my matricies like this actually helped my find and fix a bug in my solution incredibly quickly. I’m a big fan and plan on using it more in the future.

Because of how Manhattan distance works, cells with infinite volume are the cells that live on the border of our final matrix.

To find those infinite groups that live along the edges of my final matrix, I appended the edge of each edge of my matrix together and returned the nub of those values. I found the idea for this matrix rotation helper from this video on J I watched many months ago. I’m glad I remembered it!

    rot =. [: |. |:

    edges =. 3 : 0
      top =. 0 { y
      right =. 0 { rot^:1 y
      bottom =. 0 { rot^:2 y
      left =. 0 { rot^:3 y
      ~. top , right , bottom , left
    )

To find my final answer, I raveled my matrix, removed the infinite groups, used the “key” (/.) adverb to count the size of each group, and returned the size of the largest group.

    without =. _1 , edges groups
    raveled =. ,groups
    0 0 {:: \:~ ({. ;~ #)/.~ raveled #~ -. raveled e. without

This definitely isn’t the most efficient solution, but it works. At this point, I’m happy with that.

Part Two

Part two turned out to be much easier than part one. We simply needed to iterate over each point in our grid, counting the total distance to each of our input points. The set of points that was less than a fixed number from all input points defined a circular “landing area”. We were asked to find the size of that area.

I gutted most of my part one solution and replaced the values returned by my grid verb with the total distance to each input point:

    distances =. 4 : 0
      +/ ((>x) d"1~ ])"1 y
    )

    grid =. 3 : 0
      (<y) distances"1 coords y
    )

Finding my final answer was as easy as calculating my grid, checking which points were less than 10000, removing all of the 0 values, and counting the result.

    numbers =. ". input
    # #~ , 10000 > grid numbers

Notes

  • Rotating a matrix (|. |:) is a great trick.
  • viewmat is awesome. It very quickly helped me find and fix a bug in my solution.
  • Boxes can be treated like arrays in most cases. I was under the wrong impression that a box was a single unit in terms of rank.

Advent of Code: Alchemical Reduction

Written by Pete Corey on Dec 5, 2018.

Today’s Advent of Code problem is to repeatedly remove corresponding “units” from a “polymer” until we’re left with an unreducable polymer string. Unit pairs that can be removed are neighboring, matching characters, with differing cases, like C and c. The answer to the problem is the length of the resulting string.

I’m really happy with my J-based solution to this problem, which is a relief after yesterday’s disaster. I started by writing a function that compares two units and returns a boolean that says whether they react:

    test =. ([ -.@:= ]) * tolower@:[ = tolower@:]
    'C' test 'c'
1

Next, I wrote a dyadic verb that takes a single unit as its x argument, and a string of units as its y argument. If x and the head of y react, it returns the beheaded (}.) y. Otherwise it returns x appended to y:

    pass =. ([,]) ` (}.@:]) @. ([ test {.@:])
    'C' pass 'cab'
ab

This pass verb can be placed between each element of our polymer string using the insert (/) adverb. This gives us a reduced polymer string.

    pass/ 'dabAcCaCBAcCcaDA'
dabCBAcaDA

Finally, we can repeatedly apply pass until the result is stable, essentially converging on a solution. Once we’ve got our fully reduced polymer string, we count its length and print the result:

    echo # pass/^:_ 'dabAcCaCBAcCcaDA'
10

And that’s it!

Part Two

Part two tells us that one of the unit pairs is causing trouble with our polymer reduction. It wants us to remove each possible unit pair from the input string, count the length of the resulting reduction, and return the lowest final polymer string length.

My solution to part two builds nicely off of part one.

We’ll keep test and pass as they are. We’ll start by writing a remove verb that takes a character to remove as x, and a string to remove it from as y. I use i. to build a map that shows me where x isn’t in y, and then use # to omit those matching characters.

    remove =. ] #~ [ i. [: tolower ]
    'y' remove 'xyz'
xz

Next I wrote a remove_nubs verb that calculates the nub of our polymer string, and uses remove to remove each nub from our original string. I box up the results to avoid J appending spaces to end of my strings to fill the matrix.

    remove_nubs =. [ <@:remove"1 (1 , #@:nub) $ nub =. [: ~. tolower
    remove_nubs 'aabc'
┌──┬───┬───┐
│bc│aac│aab│
└──┴───┴───┘

Finally, I apply remove_nubs from my input, and converge on a solution for each new polymer string, count their resulting lengths, and return the minimum length:

    echo <./ ([: # [: pass/^:_"1 >)"0 remove_nubs 'dabAcCaCBAcCcaDA'
4

Notes

  • The application of / modified verbs is from right to left. I would have expected left to right, for some reason. This makes sense though, considering J’s execution model.
  • Visualizing verb trains makes it so much easier to write them. I actually found myself getting them right the first time, thanks to “tree view” ((9!:3) 4.
  • Boxing can be helpful when I don’t want J to pad the value to fit the dimensions of the array it lives in.