Advent of Code: Memory Maneuver

Written by Pete Corey on Dec 8, 2018.

Today’s Advent of Code challenge asks us to parse a sequence of numbers that describe a tree. Each node of the tree consists of metadata, a list of numbers, and zero or more children. We’re asked to find the sum of all metadata entries throughout the tree. Let’s use the J programming language to solve this problem!

My gut reaction when I hear the word “tree” is to reach for recursion. Let’s write a recursive verb in J that processes each node described by our input and builds up our tree as we go:

    process =. 3 : 0
      siblings =. 0 {:: y
      childrens =. 0 { 1 {:: y
      metadatas =. 1 { 1 {:: y
      rest =. 2 }. 1 {:: y
      if. childrens = 0 do.
        children =. 0 1 $ 0
      else.
        next =. process^:childrens (0 1 $ 0);rest
        children =. 0 {:: next
        rest =. 1 {:: next
      end.
      metadata =. (i. metadatas) { rest
      rest =. metadatas }. rest
      (siblings,children,metadata);rest
    )

The recursion here is fairly straight forward. If the current node has children, I’m using the ^: adverb to repeatedly, recursively apply the process verb to each of its sibling nodes.

I return any passed in siblings appended to the children we just processed, along with the set of metadata on each node.

We can find our final answer by raveling together all of the collected metadata and summing them together:

    echo +/,0{::process (0 1 $ 0);input

Part Two

Part two revealed that the metadata in each node actually refers to the (1-based) indexes of that node’s children. Calculating the cost of nodes with children is done by adding up the cost of each node specified in the metadata list. The cost of a leaf node is the sum of its metadata.

I figured that the best way to tackle this was to rework my process verb to return the entire, correctly structured tree:

    process =. 3 : 0
      siblings =. 0 {:: y
      childrens =. 0 { 1 {:: y
      metadatas =. 1 { 1 {:: y
      rest =. 2 }. 1 {:: y
      if. childrens = 0 do.
        children =. 0 1 $ 0
      else.
        next =. process^:childrens (0 1 $ 0);rest
        children =. 0 {:: next
        rest =. 1 {:: next
      end.
      metadata =. (i. metadatas) { rest
      node =. metadata;<children
      rest =. metadatas }. rest
      (siblings,node);rest
    )

The final structure of the sample input looks like this:

┌─────┬─────────────────┐
│1 1 2│┌────────┬──────┐│
│     ││10 11 12│      ││
│     │├────────┼──────┤│
│     ││2       │┌──┬─┐││
│     ││        ││99│ │││
│     ││        │└──┴─┘││
│     │└────────┴──────┘│
└─────┴─────────────────┘

For each node, the metadata is on the left, and the boxed list of children is on the right.

I wrote a count verb that recursively counts the cost of a given node. If the node has no children, I return the sum of its metadata. Otherwise, I return the sum of count applied to its children:

    count =. 3 : 0
      metadata =. 0{::y
      children =. 1{::y
      if. 0 = # children do.
        +/ metadata
      else.
        indexes =. 1 -~ metadata
        indexes =. indexes #~ _1 < indexes
        indexes =. indexes #~ -. (1 -~ # children) < indexes
        +/ count"_1 indexes { children
      end.
    )

I can use these two together to get my final answer:

    tree =. 0{0{::process(0 1 $ 0);input
    echo count tree

Notes

  • This page on working with trees in J was incredibly helpful.
  • I’ve been using #~ quite a bit to build a mask and remove items from an array based on that mask.
  • I made heavy use of the if control structure when solving these problems. No need to be a hero.

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.