From J Wiki
Jump to navigation Jump to search

The Problem << >>

Entire solution

ur=:[+1 i.~ (=&#~.)\
(part1;part2) i6=:freads '06.txt'


The goal of part one and two is find first run of 4 and 14 unique chars in the input. Both parts have thus the same solution, be it with a different window size.

This problem is right up the sleeve of J's infix adverb, x u\ y that applies u to windows of x items of y, e.g.:

|0 1 2 3|1 2 3 4|2 3 4 5|

In this problem we need to find the first window having all unique items, e.g. using the hook =&# ~.. Since infix executes its verb monadically, it is executed as y #&= ~. y, with y being the data window, which would read: are the tally of the original window and its nub the same?

The result of e.g. 4 (=&#~.)\ i6 is a list of zeros and ones indicating for each window of width 4 whether its items are unique. Finding the character at which this occurs (i.e. the last character of the window) requires finding the position of the first unique window (first 1 in the list of ones and zeros) and adding the window width. Writing this as a verb with the window width as left argument yields the solution for both days:

ur=: [ + 1 i.~ (=&#~.)\

Alternatively one could check whether all elements are unique using *./@~:, which turns out to be almost 15% faster too:

   ur2=:[ + 1 i.~ (*./@~:)\
   '14 ur i6' %&(1000&timespacex) '14 ur2 i6'
1.14904 1.00669

The above compares time and memory for 1000 repetitions of both versions using the timespacex verb, and divides them: so ur takes 15% more time and a fraction more memory than ur2. For more detailed profiling of especially explicit code, have a look at the J performance monitor, jpm.