nth number for which a filter verb returns true

user_438615 0
Viewed 76

This comes up fairly often in code golf, and I'm looking for the canonical technique in J.

You have a filter verb (ie, a boolean returning verb) that operates on the natural numbers. You wish to find the nth number for which this verb returns true.

To be clear, we are considering the infinite list of all positive integers, and f is a black box verb.

Using Do...While ^:^:_ is awkward because you need to both increment the "current number" as well as conditionally update the number of "true" results thus far, which means your y-arg is a list that must be broken apart with {. and {: on each iteration.

Recursive solutions $: are open to the same criticism.

Is there a better approach to these kinds of problems?

j
1 Answers

I think that I would filter the list to return a boolean string. Use a standard (#~ filter) hook to return the values in the list that pass the filter and then use { to select the index 0 value required.

   6&> 49 56 39 2  3 4 6 45 25  NB. filter verb
0 0 0 1 1 1 0 0 0
   (#~ 6&>) 49 56 39 2  3 4 6 45 25  NB. values that pass the filter
2 3 4
   2 ({(#~ 6&>)) 49 56 39 2  3 4 6 45 25 NB. select index 0 of filtered list
4
   nth=.{(#~ 6&>)  NB. as a tacit verb
   1 nth 49 56 39 2  3 4 6 45 25
3
user_24121780
Related