⍝ -*- mode:dyalog -*-
vin←{
    ⎕IO←0
    C←(⊢,10 0 9,⊢)⌽2+⍳7
    check←(⎕D,'X')⌷⍨11|C+/⍤×10|(⎕D,' ',⎕A/⍨(3@17)(2@8)26⍴1)⍳⊢
    ~∧⌿⍵∊⎕D,⎕A~'IOQ':¯1 ⍝ Case: invalid charset
    16=≢⍵:(check x)@8⊢x←((2@8)16⍴1)/⍵
    17=≢⍵:⍵[8]=check ⍵
    ¯1 ⍝ Case: invalid length
}

⍝⎕←vin vin'1M8GDM9AKP042788'
⍝⎕←vin¨'5GZCZ43D13S812715' 'SGZCZ43D13S812715'

sortVersions←{
    ⎕IO←1
    V←{⊂2⊃'.'⎕VFI⊃⍵}@3¨'-'∘(~⍤∊⍨⊆⊢)¨⊆⍵
    ⍝ Yes, grade works on nested array too
    ⍵[⍋V]
}

⍝⎕←sortVersions'a-b-1.2.1' 'a-b-1.2.10' 'a-b-1.2.2'
⍝pkgs←⎕JSON⊃⎕NGET'pkgs.json'
⍝⎕←sortVersions'a-b-1.2.3-test' 'a-b-1.2.3-prod' 'a-c-1.2.3-dev' 'a-b-1.2.3-dev'
⍝⎕←⍪sortVersions,pkgs

⍝ An obviously correct brutal force method is:
⍙makeChange←{⎕IO←0 ⋄ M⌿⍨⍵=⍺+.×⍨M←⌽⍉B⊤⍳×⌿B←1+⌽⌊⍵÷⍺}
⍝ Using  i←B⊤n  to exhaustive search the combination.
⍝ The initial  B  is  1+⌊⍵÷⍺  which sets the upper
⍝ bound of each type of currency.
⍝ However, the upper bounds for  i  can
⍝ shrink as  i  increases. To ensure the
⍝ algorithm terminates, B  needs to be
⍝ recomputed after each time  i  changes, but
⍝ that is only necessary when the sum of  i
⍝ is bigger than  A .
⍝ We could also fast forward the last digit when
⍝ the sum is less than  A  instead
⍝ of test out every combination.
⍝ BENCHMARK:
⍝ Using structured programming keywords
⍝ can enhance performance compared to old school
⍝  →  based control flow.
⍝ Unfortunately, compiling this function would
⍝ compromise its performance.
⍝ TRIVIA:
⍝ A few thing I tried but didn't work:
⍝ This seems to be similar to knapsack problem,
⍝ however, since the goal is to list all
⍝ combinations instead of optimizing, the
⍝ various related algorithms just won't apply.
⍝
⍝ I have heard dfs works well for this problem
⍝ but to be honest I never had the idea
⍝ of using dfs in APL.
⍝
⍝ I worried that my algorithm would
⍝ be less efficient when the  denom  would
⍝ be co-prime to each others. Since the
⍝ it is much less likely to be the case of
⍝ currency amount, I stopped worry about
⍝ optimization for this, but still paid some
⍝ attention to correctness on this case.
⍝
⍝ I did some test to show the above issue:
⍝ euro makeChange 200  would need 147080 iterations
⍝ for 73682 results.
⍝ euro makeChange 100  needs 9084 for 4563 results.
⍝ 3 7 9 11 12 makeChange 100  needs 2254 iterations
⍝ for only 346 result.

⍝ Feedback:
⍝ The drafting version I had has more overlapping
⍝ conditions, redundant safe guards and variables.
⍝ Still, I think doing the prototype in other
⍝ non-array languages would be more difficult.
⍝ By working in the mindset of equation
⍝ rewriting approach, I derived an optimized
⍝ answer from the brutal forced search algorithm.
∇R←W makeChange A;B;O;i;t
 W←⌽W ⍝ Reversed denom
 R←0⍴⍨0,≢W ⍝ Result
 O←⎕io+¯1+≢W ⍝ lowest digit
 i←1↑⍨-≢W ⍝ i: search index
 :Repeat
     t←W+.×i
     :If t<A ⍝ Fast forward
         i[O]+←⌈(A-t)÷⊢/W
     :Else
         :If t=A ⋄ R⍪←i ⋄ :EndIf
         ⍝ Shrink the search bound
         i←B⊤B⊥(¯1↓i),⊢/B←1+0⌈⌈W÷⍨A-0,+\¯1↓W×i
     :EndIf
 :Until t=0 ⍝ i overflows
 R←⌽R
∇
euro←1 2 5 10 20 50 100 200 500 1000 5000 10000 20000
usa←1 5 10 25 50 100 500 1000 2000 5000 10000
⍝⎕←≢usa makeChange 132
⍝⎕←≢usa makeChange 200
⍝ Requires about 0.6 secs
⍝⎕←≢euro makeChange 200
⍝a←euro makeChange 60
⍝b←euro ⍙makeChange 60
⍝⎕←a≡b
⍝⎕←3 7 9 11 12 makeChange 40
⍝⎕←3 7 9 11 12 ⍙makeChange 40

partition←{
    ⎕IO←1
    M←1⍴⍨≢1⊃,⍺ ⍝ move
    C←1⍴⍨≢⍴⍵ ⍝ coordinates
    _←⍎'←,⍺',⍨⊃(≢,⍺)⌷'S' '(S M)' '(S M C)'
    S←S,⍨1⍴⍨C-⍥≢S ⍝ window size rank padding
    M←M,⍨1⍴⍨C-⍥≢M ⍝ movement rank padding
    MS←S-⍨1+⍴⍵ ⍝ shape mask to remove stencil padding
    MM←,⊃∘.∧⌿(C-1)(≢⍤⊢↑⊢,⍨0⍴⍨⊣)¨MS⍴¨↑∘1¨M ⍝ move/start mask
    MM/({∧⌿,0=⍺}⌺S(⊢⍤/⍥,){⊂⍵}⌺S)⍵ ⍝ select subarray
}

⍝⎕←3 partition 5 5⍴⎕A
⍝⎕←(2 2)(2 3)partition 5 5⍴⎕A
⍝⎕←(3 2)(2 1)(2 2 2)partition 4 5 6⍴⍳120
⍝⎕←⍴¨1partition⍳5