dimanche 4 juin 2023

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?

Aucun commentaire:

Enregistrer un commentaire