Today’s Advent of Code challenge wants us to model many rectangular intersections. Given a large number of rectangles laid out on a grid, we’re asked to find the total number of square inches of overlap between all of these rectangles.

Using J to parse the input for this challenge string turned out to be incredibly difficult. Frustratingly difficult. It seems there’s no nice, easy, built-in way to do this kind of string processing in J. At least none that I could find.

I could have used this example from the Strings phrase page, but I didn’t want to pull in a helper function I didn’t fully understand, and I didn’t want to rely on a package, if I could avoid it.

At the end of the day, I used the “words” verb (;:) to build a finite state machine that pulls sequences of digits out of my input string. This guide was a huge help in understanding and building out this code.

    parse =. 3 : 0
      m =. a. e. '1234567890'
      s =. 1   2 2 $ 0 0  1 1
      s =. s , 2 2 $ 0 3  1 0
      ". > (0;s;m;0 _1 0 0) ;:"1 y
    )
    parse '#1 @ 1,3: 4x4'
1 1 3 4 4

Once I was able to parse out the offsets and dimensions of each rectangle, solving the problem was relatively straight forward. I first created a width by height matrix of 1s to represent each rectangle. I shifted the matrix down by appending (,) rows of zeros, and right by appending zeros to the beginning of each row. J is nice enough to fill in the gaps.

    cut_cloth =. 1 $~ |.

    cut_and_shift =. 3 : 0
      left  =. 1 {:: y
      top   =. 2 {:: y
      cloth =. cut_cloth (0 0 0 1 1 # y)
      cloth =. 0 ,^:top cloth
      cloth =. 0 ,"1^:left cloth
      cloth
    )
    
    cut_and_shift 0 1 1 2 2
0 0 0
0 1 1
0 1 1

Once each of the rectangles were sized and positioned, we can add them together:

    +/ cut_and_shift"1 parse input
0 0 0 0 0 0 0
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 1 1 2 2 1 1
0 1 1 2 2 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1 1

This gives us a visual depiction of where our rectangles overlaps where each positive number represents the number of intersections at that location. To find the answer to our problem, we ravel this grid (,), filter out all elements that aren’t greater than 1, and count the remaining:

    # (>&1 # ]) , +/ cut_and_shift"1 parse input
4

Part Two

This tweet reply from Raul Miller sent me down a rabbit hole related to improving my string-parsing-fu. After coming out the other side I had learned that the inv adverb, or ^:_1, when paired with # can be used to preserve the gaps on a filtered list, or string:

    ((1 0 1 0 1 1 0)&#^:_1) 'abcd'
a b cd

This led me to a much better parse function:

    parse =. ".@:(]#^:_1]#[) (e.&' 123456789')

Part two of today’s challenge asks us for the ID of the only rectangle in the set of inputs that doesn’t intersect with any other rectangle.

My strategy for this part was different than the first part. Instead of building a matrix representation of each rectangle, I decided to transform each description into a set of left, right, top, and bottom coordinates (with a little destructuring help):

    repackage =. 3 : 0
      'i l t w h' =. y
      i,l,t,(l + w),(t + h)
    )
    repackage 0 1 1 2 2
0 1 1 3 3

Once I had the bounds of each rectangle described, I could determine if any two rectangles intersect:

    intersect =. 4 : 0
      'i_1 l_1 t_1 r_1 b_1' =. x
      'i_2 l_2 t_2 r_2 b_2' =. y
      -.+./(l_2>:r_1),(r_2<:l_1),(t_2>:b_1),(b_2<:t_1)
    )
    0 1 1 3 3 intersect 0 2 2 4 4
1

Using my new intersect verb, I could build an “intersection table”, and find the rectangle that has only one intersection: the intersection with itself!

    parsed =. parse"1 input
    ({."1 parsed) #~ -. 1 i. +/ intersect"1/~ repackage"1 parsed
3

Notes