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