Written by Pete Corey on Dec 5, 2018.

Today’s Advent of Code problem is to repeatedly remove corresponding “units” from a “polymer” until we’re left with an unreducable polymer string. Unit pairs that can be removed are neighboring, matching characters, with differing cases, like C and c. The answer to the problem is the length of the resulting string.

I’m really happy with my J-based solution to this problem, which is a relief after yesterday’s disaster. I started by writing a function that compares two units and returns a boolean that says whether they react:

    test =. ([ -.@:= ]) * tolower@:[ = tolower@:]
    'C' test 'c'
1

Next, I wrote a dyadic verb that takes a single unit as its x argument, and a string of units as its y argument. If x and the head of y react, it returns the beheaded (}.) y. Otherwise it returns x appended to y:

    pass =. ([,]) ` (}.@:]) @. ([ test {.@:])
    'C' pass 'cab'
ab

This pass verb can be placed between each element of our polymer string using the insert (/) adverb. This gives us a reduced polymer string.

    pass/ 'dabAcCaCBAcCcaDA'
dabCBAcaDA

Finally, we can repeatedly apply pass until the result is stable, essentially converging on a solution. Once we’ve got our fully reduced polymer string, we count its length and print the result:

    echo # pass/^:_ 'dabAcCaCBAcCcaDA'
10

And that’s it!

Part Two

Part two tells us that one of the unit pairs is causing trouble with our polymer reduction. It wants us to remove each possible unit pair from the input string, count the length of the resulting reduction, and return the lowest final polymer string length.

My solution to part two builds nicely off of part one.

We’ll keep test and pass as they are. We’ll start by writing a remove verb that takes a character to remove as x, and a string to remove it from as y. I use i. to build a map that shows me where x isn’t in y, and then use # to omit those matching characters.

    remove =. ] #~ [ i. [: tolower ]
    'y' remove 'xyz'
xz

Next I wrote a remove_nubs verb that calculates the nub of our polymer string, and uses remove to remove each nub from our original string. I box up the results to avoid J appending spaces to end of my strings to fill the matrix.

    remove_nubs =. [ <@:remove"1 (1 , #@:nub) $ nub =. [: ~. tolower
    remove_nubs 'aabc'
┌──┬───┬───┐
│bc│aac│aab│
└──┴───┴───┘

Finally, I apply remove_nubs from my input, and converge on a solution for each new polymer string, count their resulting lengths, and return the minimum length:

    echo <./ ([: # [: pass/^:_"1 >)"0 remove_nubs 'dabAcCaCBAcCcaDA'
4

Notes

  • The application of / modified verbs is from right to left. I would have expected left to right, for some reason. This makes sense though, considering J’s execution model.
  • Visualizing verb trains makes it so much easier to write them. I actually found myself getting them right the first time, thanks to “tree view” ((9!:3) 4.
  • Boxing can be helpful when I don’t want J to pad the value to fit the dimensions of the array it lives in.