Pete Corey Writing Work Contact

Advent of Code: Repose Record

Written by Pete Corey on Dec 4, 2018.

Today’s Advent of Code challenge asks us to parse and process a set of time-series data that describes when guards start their shift, when they fall alseep, and when they wake up. Our task is to find the guard that sleeps the most. We need to multiple their ID together with the minute they’re asleep the most.

This was an incredibly difficult problem for me to solve using J. My plan of attack was to build a “sleep matrix” for each guard. Each matrix would have a row for each day the guard was on duty, and each row would be sixty columns wide, with each row/column representing whether the guard was asleep during that minute of the twelfth hour of that day.

I was immediately stumped by how to parse each string and organize all of the data into useful, easily manipulatable structures.

After sorting my lines (/:~ input), I checked if each line had a 'G' character at index nineteen. If it did, I raised a boolean and used +/\ e. and # to build a set of groups for each guard’s shift. Once I’d grouped each shift, I could build my sleep matrix and box it together with the guard’s ID:

    sleep_map =. 3 : 0
      1 y } 60 $ 0
    )

    filter =. (' ' -.@:= 0&{)"1 # ]

    parse_log =. 3 : 0
      head =. {. y
      rest =. filter }. y
      'Y M D h m id' =. numbers head
      sleep =. sleep_map"0 ({:"1 numbers"1 rest #~ (# rest) $ 1 0)
      wake =. _1 * sleep_map"0 ({:"1 numbers"1 rest #~ (# rest) $ 0 1)
      id&;"2 +/\"1 sleep + wake
    )

    parse =. 3 : 0
      groups =. +/\ ('G' = 19&{::)"1 y
      masks =. groups&e."0 ~. groups
      parse_log"_1 masks # y
    )

Next I needed to consolidate each guard’s set of shifts and sleep matrices into a single sleep matrix:

    group_days =. 3 : 0
      id =. 0 {:: {. y
      days =. ,/ 1 {::"_1 y
      id;days
    )

    group =. 3 : 0
      ids =. 0 {::"1 y
      ids group_days/. y
    )

Finally I could box up the needed statistics for each guard and sleep matrix, sort the results, and return the desired calculation:

    stats =. 3 : 0
      id =. 0 {:: y
      days =. 1 {:: y
      overlap =. +/ days
      most =. overlap i. >./ overlap
      slept =. +/ overlap
      slept; most; id; days
    )

    result =. (2&{:: * 1&{::) {. \:~ stats"1 group parse log

Part Two

Part two just wants us to find the guard that is asleep most frequently on the same minute of the night. We’re to return that guard’s ID multiplied by the minute they’re usually asleep.

Thankfully, I was able to recycle all of the hard work I put into part one when it came time to solve part two. All I really needed to do was make a change to the set of statistics I boxed up in my final step:

    stats =. 3 : 0
      id =. 0 {:: y
      days =. 1 {:: y
      overlap =. +/ days
      most =. >./ overlap
      minute =. overlap i. most
      most; minute; id; days
    )

The rest of my code was left unchanged.

Notes

  • The “key” verb (/.) can be incredibly useful for grouping data and performing actions on those subsets.
  • Sorting is interesting in J.
  • Any type of data can be sorted. Sorting arrays of boxes behaves like sorting lists of tuples in Elixir, which is a very handy trick.
  • (9!:3) 4 renders verb trains in “tree view” which I find very helpful.

Allow Yourself to do Things Poorly

Written by Pete Corey on Dec 3, 2018.

I often find myself stuck at the beginning of things. Haunted by past mistakes, I vow to myself that “I’ll do things right this time.” Unfortunately, insisting on doing everything “right” is crippling. Largely because doing everything “right” is impossible.

Lately I’ve stopped beating myself over the head for doing things that I know aren’t “best practice”, and instead I’ve given myself the freedom to start doing things poorly.

It’s been liberating.

Analysis Paralysis

My Elixir-based Chord project is coming along nicely. While my ASCII-based chord chart renderer is incredibly helpful for visualizing chords in the terminal, it’s still difficult to sift through several thousand chords at a time.

Reluctantly, I realized that my Chord project needed a web-based front-end.

These days, my go-to tool for building a front-end is React. However, I’ve built enough React applications for clients and in my personal work to know that if you’re not vigilant and strict, the complexity of a React project can quickly spiral out of control. I was determined not to allow that to happen this time around.

Not only that, but I wasn’t sure how best to build the user interface. Chord offers users a huge number of potential knobs to tweak, and the resulting sets of data can be massive and hard to sift through. How do we best present everything to the user?

I was paralyzed.

Get Going

After several days of hemming, hawing, and wringing my hands over architectural decisions and uncertainties over how I wanted the user experience to go, I decided that I was wasting my time.

It’s better, I convinced myself, to just get something built. Even if it’s built poorly and even if it isn’t an ideal interface for the tool, something is better than nothing. I essentially decided to start building a rough draft of the application.

The first thing I needed was a way to render chord charts in the browser. After an hour or so of writing some absolutely awful React code, I was there.

Randomly generated chords.

Next, I needed a way to pull chords from the back-end Elixir server and render them using our new chord chart component. After another couple hours of hacking together a (poorly designed and roughly implemented) GraphQL data layer, I was greeted with several hundred Cmaj7 chords:

All Cmaj7 chords.

At this point, I was stuck on how to proceed. How could I easily let users build chord progressions from the possibilities presented? I started iterating on a few ideas, mostly involving nested trees, but nothing seemed to click.

Awash in Inspiration

Several days later, I was browsing Reddit and I stumbled across this screenshot from /r/unixporn. I was completely inspired. This is what I wanted my project to look like!

My inspiration.

I fired up CodePen and started hashing out some mockups of how the application might look.

Codepen mockup.

Happy with the direction I was heading, I quickly translated the hard-coded, mocked-up HTML into my already existing React components. The results were promising.

With data.

Seeing real data on the screen gave me even more ideas on how to interact with the application.

With data.

I was awash in inspiration.

Riding the Wave

This cycle of building and playing with what I’d built kept up for days. Every few hours I’d pester my wife and show her what I’d added, because I was so excited. I didn’t take the time during this process to focus on best practices or code quality. Instead, I focused on getting results.

Eventually, that wave rolled back, and I was left with a mostly functional and mostly ugly codebase. It became more difficult to make changes to the codebase, and with my inspiration fading, I wasn’t motivated to push through the pain.

At this point, I turned my attention towards refactoring my original code. Now was the time to focus on best practices and doing things “right”.

While I’m still not fully happy with the codebase or the user interface, I’m very happy with how far I’ve come in such a short time. I never would have made this progress if I didn’t allow myself to do things poorly, just for the sake of getting things done. If I was still at the beginning, fixated on engineering a “correct” solution, I wouldn’t have had the raw materials required to turn my inspiration into a tangible product.

The current state of things.

Advent of Code: No Matter How You Slice It

Written by Pete Corey on Dec 3, 2018.

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

  • I had trouble with the subtle differences between intersect"1/~ and intersect/~"1. I need to dig deeper here.
  • The inversion (^:_1) of # is a special case.