The function Count below calculates the minimal number of coins which sums up to a given amount.
∇ R ← d AppendQuotRem qrs; oldR; q; r
oldR ← 2 ⊃ (⍴qrs) ⊃ qrs
q ← ⌊oldR ÷ d
r ← oldR - d × q
R ← qrs , ,⊂(q r)
∇
∇ R ← Count amount; ds; qrs; qs
ds ← 1 5 10 25 50 ⍝ coin denominations in cents
qrs ← ⊃AppendQuotRem/ ds , ⊂,⊂(0 amount)
qs ← 1 ⊃¨ qrs
R ← ds ,[0.5] ⌽1 ↓ qs
∇
For each denomination I calculate a quotient and a remainder. The remainder is used in the calculation involving the next denomination. Is there a shorter and/or more straight forward way to solve the problem?
The change-making problem is actually quite hard. A full APL approach is included in the dfns workspace.
Your algorithm is greedy, which gives the wrong result for certain sets sets of coin denominations. It just happens to work out with the set you use in your example. Let's modify your Count function:
∇ R ← Count134 amount; ds; qrs; qs
ds ← 1 3 4 ⍝ coin denominations in cents
qrs ← ⊃AppendQuotRem/ ds , ⊂,⊂(0 amount)
qs ← 1 ⊃¨ qrs
R ← ds ,[0.5] ⌽1 ↓ qs
∇
Count134 6
1 3 4
2 0 1
This uses three coins, but two 3-cent coins is the correct answer:
1 3 4
0 2 0
That being said, common coinage systems are designed such that a greedy algorithm will produce the optimal result. Here is thus a simplification of your code:
∇ R ← d AppendQuotRem qrs; oldR; q; r
oldR ← 1 ↑ qrs
q ← ⌊oldR ÷ d
r ← d | oldR
R ← r , q , 1 ↓ qrs
∇
∇ R ← Count amount; ds
ds ← 1 5 10 25 50 ⍝ coin denominations in cents
R ← ds ,[0.5] ⊃AppendQuotRem/ 1 ↓ ds , amount
∇