I was planning to do this in J, but gave up.

My next initial attempt was in Haskell but was something awful like O(n^4) with bad constant factors, as seen in part2_tooslow.hs