Is another way to write this APL pattern?


let ns be an unsorted array of unique integers of arbitrary length, return the smallest missing positive number of that array. for example

ns = {-1, -3, -2} -> 1
ns = {1, 2, 3, 4, 5, 6, 7, 8, 9} -> 10
ns = {-1, 5, 1} -> 2

I saw this on an APL youtube video and decided to give it a try myself, my solution is

smallestMissingPositive ← {⌊/(⍳⌈/⍪(1∘+)⌈/⍵)~⍵}


  1. the ⍳⌈/⍪(1∘+)⌈/ part is is just all positive number up to N+1 where N is the greatest number in . Using a fork to concatenate ⍳⌈/ (a list of positive integers up to the greatest number in ) with (1∘+)⌈/ (the greatest number in plus 1)
  2. ~⍵ just takes the difference of the previous point to the original list
  3. ⌊/ then finally taking the minimum value on that list

so for ns = {-1, 1, 3, -2, 5} first we generate {1, 2, 3, 4, 5, 6} then take the difference of ns from that which is {2, 4, 6} then taking the minimum element which is 2.


Is there a way to optimize my solution further?



  • Your initial idea is almost there, it just needs a little improvement:


    Or go full tacit smp←⊢(0∘<⌊/⍤/⊢)⍤~⍨1+0,⊢

    Let's first prove my solution is correct:

    when is empty, it gives 1. when has all numbers greater equal than 0, {⍵~⍨1+0,⍵} gives all the next numbers of that exclude the numbers already in give a ⌊/ to the result is just what we want. when are all negative numbers, it gives 1. when is a mixture of negative and positive numbers, the result is still correct.

    And if we do a bit equational reasoning,

    ⍵>0 IMPLIES {⌊/⍵~⍨⍳1+⌈/⍵} ←→ {⌊/⍵~⍨1+0,⍵}

    We can see that you don't need the iota at all!

    Still, it is obvious that you are struggling with the binding precedence of APL.

    There are a few patterns that could help:

    (XXXX)~⍵ can be written as ⍵~⍨XXXX

    (1∘+)⌈/⍵ is just 1+⌈/⍵, and ⌈/1+⌈/⍵ is equal to ⌈/1+⍵, and there is one thing you get wrong: ⍳⌈/⍪(1∘+)⌈/⍵ is not a fork train! Your original answer didn't use any tacit programming features, is just used as a nop there. Only (f g h) X with the parenthesis is the tacit train (f X) g (h X), f g h X is just plain f (g (h X)).

    The (0∘<⌊/⍤/⊢) I used is derived from the base form ⊢⍤/.