Advent of Code: Chronal Charge

Written by Pete Corey on Dec 14, 2018.

Advent of Code’s day eleven puzzle asks us to compute a three hundred square grid of values and to find the three by three sub-grid that contains the highest sum of values. In my heart of hearts I knew that this would be a problem well suited to the J programming language.

I started by working on a verb to break a grid into a number of sub-grids of a given size. This reminded me quite a bit of Elixir’s Enum.chunk_every/4 function, so I decided to name it accordingly:

    grid =. 5 5 $ i. 25
    grid
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
    chunk_every =. [ <\"2 [: |:"2 [: > <\ 
    3 chunk_every grid
┌────────┬────────┬────────┐
│0 5 10  │1 6 11  │2 7 12  │
│1 6 11  │2 7 12  │3 8 13  │
│2 7 12  │3 8 13  │4 9 14  │
├────────┼────────┼────────┤
│5 10 15 │6 11 16 │7 12 17 │
│6 11 16 │7 12 17 │8 13 18 │
│7 12 17 │8 13 18 │9 14 19 │
├────────┼────────┼────────┤
│10 15 20│11 16 21│12 17 22│
│11 16 21│12 17 22│13 18 23│
│12 17 22│13 18 23│14 19 24│
└────────┴────────┴────────┘

To be totally transparent, I originally came up with this verb by tinkering in the REPL, and converted it into a tacit verb after the fact.

Now that we have chunk_every, we can define a few more needed values, like our initial grid, our grid size, and our grid serial number:

    size =. 300
    grid =. (size,size) $ i. size * size
    grid_serial_number =. 9424

The puzzle tells us how to convert our initial grid’s x/y coordinates into “fuel cell values”. Let’s write an init verb that takes our initial verb and calculates and populates those values:

    init =. 3 : 0
      'cy cx' =. (0,size)#:y
      rack_id =. cx + 10
      power =. rack_id*cy
      power =. power + grid_serial_number
      power =. power * rack_id
      power =. 10 | power <.@% 100
      power =. power - 5
      power
    )

Now we’re ready to start. We’ll begin by generating our grid of fuel cells:

    grid =. init"0 grid

Next, we’ll break our grid into three by three chunks:

    chunks =. 3 chunk_by grid

Once we have our sub-grids, we’ll calculate the sum of each and flatten that into a one dimensional array of sums:

    flat_chunks =. , +/"1 ,"2 > chunks

And find the maximum sub-grid sum:

    max =. >./ flat_chunks

And the corresponding index of that maximum sum:

    highest =. flat_chunks i. >./ flat_chunks

Finally, we can turn that index into a pair of x/y coordinates:

    |. (0,(size-2))#:highest

This is the answer to our puzzle. Victory!

Our fuel cells, visualized.

Just for fun, we can check out what our newly initialized fuel cell matrix looks like with the help of viewmat. We can see some cool Moiré patterns in the resulting visualization as a side effect of our calculations.

Part Two

Part two wants us to vary the size of our sub-grids, and find the sub-grid size, and x/y coordinate pair that has the most amount of available fuel, or the highest sum.

My first instinct was to run chunk_by multiple times against chunk sizes ranging from 1 to 300:

    chunks =. (grid&(<@:chunk_by~))"0 (1 + i. size)

I wrote a verb to count the amount of available fuel within each new set of sub-grids, and ran that against all of the sub-grid sets I was generating:

    count =. 3 : 0
      chunks =. > y
      chunk_size =. # 0 0 {:: chunks
      flat_chunks =. , +/"1 ,"2 > chunks
      max =. >./ flat_chunks
      highest =. flat_chunks i. >./ flat_chunks
      coord =. |. (0,(size-(chunk_size-1)))#:highest
      max;coord,chunk_size
    )

    counts =. count"_1 chunks

From there, I could grab the best score of all of the sub-grid sizes, find the max, and return a tuple of that winning sub-grid’s size, and its x/y coordinate:

    scores =. > 0 {"1 counts
    idx =. scores i. >./ scores
    1 {:: idx { counts

Unfortunately, this turned out to be too slow of a solution.

Thankfully, there were some patterns to be found that let us speed things up considerably! If we plot our counts with a max grid size of 10, 50, and 100, we can see that our score always peaks almost immediately. We don’t need to test larger sub-grid sizes because we know our answer won’t be there.

A plot of our sub-grid size vs our maximum fuel availability.

Let’s change our solution to only check sub-grid sizes from one to twenty:

    chunks =. (grid&(<@:chunk_by~))"0 (1 + i. size)

And just like that, we get an answer almost immediately.

Thanks J!

Advent of Code: The Stars Align

Written by Pete Corey on Dec 13, 2018.

The day ten Advent of Code challenge gives us a list of points and velocity pairs. Each point is updated by its corresponding velocity every second. At some point in time, these points will converge and spell out a message. Our task is to find that message using the J programming language!

As usual, we’ll start by loading our input and massaging it into a form we can work with:

    replacements =. 'position=<';'';',';'';'> velocity=<';' ';'>';'';'-';'_'
    path =.  '/Users/pcorey/advent_of_code_2018/day_10/input'
    input =. ". > cutopen replacements rplc~ (1!:1) < path

I’m using a trick I learned from zxw on Twitter to easily replace and reformat the data before passing it into the “numbers” verb (".).

Next let’s write a tick verb that updates each point with its corresponding velocity. We’ll also keep track of the maximum spread between Y coordinate values and return that as the second value in a boxed tuple along with our next set of points and velocities:

    tick =. 3 : 0
      input =. 0 {:: y
      prev =. 1 {:: y
      next =. +/"1 |:"2 (2 2 $ ])"1 input
      max =. >./ 1 {"1 next
      min =. <./ 1 {"1 next
      diff =. | max - min
      if. diff < prev do.
        (next (0 1})"1 input);diff
      else.
        y
      end.
    )

Notice that if applying the next tick results in a lower spread, we return the new values. Otherwise, we return the old values. This means we can “converge” (^:_) on a result for this verb. The result we converge on will be the set of points with the lowest spread in the vertical dimension.

It turns out that this is our answer!

We can use J’s viewmat library to quickly visualize our answer (after some more rotating and massaging):

    load 'viewmat'

    to_mat =. 3 : 0
      min_x =. <./ 0 {"1 y
      min_y =. <./ 1 {"1 y
      max_x =. >./ 0 {"1 y
      max_y =. >./ 1 {"1 y
      coords =. 0 1 {"1 y
      coords =. (min_x,min_y) -~"1 coords
      mat =. ((1 + | max_y - min_y),(1 + | max_x - min_x)) $ 0
      updates =. (<@:;/@:|.)"1 coords
      1 updates} mat
    )

    viewmat to_mat 0 {:: tick^:_ input;_

The stars align.

Part Two

Part two turned out to be a simple modification of our part one solution. The challenge asked us to return how many ticks we went through before we found our message.

All we need to do to figure this out is to add a third element to the tuple we pass in and out of tick that holds an incrementing count:

    tick =. 3 : 0
      input =. 0 {:: y
      prev =. 1 {:: y
      count =. 2 {:: y
      next =. +/"1 |:"2 (2 2 $ ])"1 input
      max =. >./ 1 {"1 next
      min =. <./ 1 {"1 next
      diff =. | max - min
      if. diff < prev do.
        (next (0 1})"1 input);diff;(count + 1)
      else.
        y
      end.
    )

    2 {:: tick^:_ input;_;0

The answer to our challenge is the value of this final count.

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.