Count the coins: Difference between revisions
Content added Content deleted
Drkameleon (talk | contribs) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 2,380: | Line 2,380: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Very fast, from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change |
Very fast, from http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change |
||
<!--<lang Phix>--> |
|||
<lang Phix>function coin_count(sequence coins, integer amount) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">coin_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">amount</span><span style="color: #0000FF;">)</span> |
|||
sequence s = repeat(0,amount+1) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
s[1] = 1 |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
for c=1 to length(coins) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
for n=coins[c] to amount do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">to</span> <span style="color: #000000;">amount</span> <span style="color: #008080;">do</span> |
|||
s[n+1] += s[n-coins[c]+1] |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return s[amount+1] |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end function</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<!--</lang>--> |
|||
An attempt to explain this algorithm further seems worthwhile: |
An attempt to explain this algorithm further seems worthwhile: |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Phix>function coin_count(sequence coins, integer amount) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">coin_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">coins</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">amount</span><span style="color: #0000FF;">)</span> |
|||
-- start with 1 known way to achieve 0 (being no coins) |
<span style="color: #000080;font-style:italic;">-- start with 1 known way to achieve 0 (being no coins) |
||
-- (nb: s[1] holds the solution for 0, s[n+1] for n) |
-- (nb: s[1] holds the solution for 0, s[n+1] for n)</span> |
||
sequence s = repeat(0,amount+1) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
s[1] = 1 |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
-- then for every coin that we can use, increase number of |
<span style="color: #000080;font-style:italic;">-- then for every coin that we can use, increase number of |
||
-- solutions by that previously found for the remainder. |
-- solutions by that previously found for the remainder.</span> |
||
for c=1 to length(coins) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
-- this inner loop is essentially behaving as if we had |
<span style="color: #000080;font-style:italic;">-- this inner loop is essentially behaving as if we had |
||
-- called this routine with 1..amount, but skipping any |
|||
-- |
-- called this routine with 1..amount, but skipping any |
||
-- less than the coin's value, hence coins[c]..amount.</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">to</span> <span style="color: #000000;">amount</span> <span style="color: #008080;">do</span> |
|||
s[n+1] += s[n-coins[c]+1] |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">coins</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return s[amount+1] |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">amount</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
-- The key to understanding the above is to try a dry run of this: |
<span style="color: #000080;font-style:italic;">-- The key to understanding the above is to try a dry run of this:</span> |
||
printf(1,"%d\n",coin_count({2,3},5)) -- (prints 1) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (prints 1) |
|||
-- You'll need 4 2p coins, 3 3p coins, and 5 spaces marked 1..5. |
-- You'll need 4 2p coins, 3 3p coins, and 5 spaces marked 1..5. |
||
-- Place 2p wherever it fits: 1:0 2:1 3:1 4:1 5:1 |
|||
-- |
-- Place 2p wherever it fits: 1:0 2:1 3:1 4:1 5:1 |
||
-- |
-- Add previously found solns: +0 +1 +0 +1 +0 [1] |
||
-- |
-- Place 3p wherever it fits: 1:0 2:0 3:1 4:1 5:1 |
||
-- Add previously found solns: +0 +0 +1 +0 +1 [2] |
|||
-- [1] obviously at 2: we added the base soln for amount=0, |
|||
-- |
-- [1] obviously at 2: we added the base soln for amount=0, |
||
-- |
-- and at 4: we added the previously found soln for 2. |
||
-- |
-- also note that we added nothing for 2p+3p, yet, that |
||
-- fact is central to understanding why this works. [3] |
|||
-- [2] obviously at 3: we added the base soln for amount=0, |
|||
-- |
-- [2] obviously at 3: we added the base soln for amount=0, |
||
-- |
-- at 4: we added the zero solutions yet found for 1p, |
||
-- |
-- and at 5: we added the previously found soln for 2. |
||
-- |
-- you can imagine at 6,9,12 etc all add in soln for 3, |
||
-- albeit by adding that as just added to the precessor. |
|||
-- [3] since we add no 3p solns when processing 2p, we do |
|||
-- |
-- [3] since we add no 3p solns when processing 2p, we do |
||
-- not count 2p+3p and 3p+2p as two solutions. |
|||
--For N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. |
--For N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.</span> |
||
printf(1,"%d\n",coin_count({1,2,3},4)) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span><span style="color: #000000;">4</span><span style="color: #0000FF;">))</span> |
|||
--For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. |
<span style="color: #000080;font-style:italic;">--For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.</span> |
||
printf(1,"%d\n\n",coin_count({2,3,5,6},10)) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span><span style="color: #000000;">10</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"%d\n",coin_count({25, 10, 5, 1},1_00)) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">1_00</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"%,d\n",coin_count({100, 50, 25, 10, 5, 1},1000_00))</lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">coin_count</span><span style="color: #0000FF;">({</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">1000_00</span><span style="color: #0000FF;">))</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |