arraysdesign-patternsapl

# Is another way to write this APL pattern?

## CONTEXT

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∘+)⌈/⍵)~⍵}
``````

explanation:

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`.

## QUESTION

Is there a way to optimize my solution further?

## HUNCHES

• I don't even know if my solution is correct or not (i.e. misses a corner case)
• the max-reduce `⌈/` function is used twice in `⍳⌈/⍪(1∘+)⌈/`. the 3-train fork turns `fgh ⍵` into `(f ⍵) g (h ⍵)` but in this particular case the pattern is `(h (f ⍵)) g (h' (f ⍵))` can remove the redundancy in `f`?

Solution

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

``````smp←{⌊/(0<N)/N←⍵~⍨1+0,⍵}
``````

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 `⊢⍤/`.