Rosetta Code

Count the coins: Difference between revisions

Page Discussion

Count the coins (view source)

Revision as of 02:09, 18 May 2021

9,311 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,380:
=={{header|Phix}}==
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:
<!--<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>
<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)</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>
<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.</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>
<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
-- lesscalled thanthis theroutine coin'swith value, hence coins[c]1..amount., but skipping any
for n=-- less than the coin's value, hence coins[c] to ..amount do.</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>
 
<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.
-- Place 2p wherever it fits: 1:0 2:1 3:1 4:1 5:1
-- AddPlace previously2p foundwherever solnsit fits: +1:0 2:1 +3:1 +0 +4:1 +0 [5:1]
-- PlaceAdd 3ppreviously whereverfound it fitssolns: 1:+0 2:0 3:+1 4: +0 +1 5: +0 [1]
-- AddPlace previously3p foundwherever solnsit fits: +1:0 +2:0 +3:1 +0 +4:1 [2]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] andobviously at 42: we added the previously foundbase soln for 2.amount=0,
-- alsoand noteat that4: we added nothingthe forpreviously 2p+3p,found yet,soln for that2.
-- factalso isnote centralthat towe understandingadded whynothing thisfor works.2p+3p, [3]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 43: we added the zero solutions yetbase foundsoln for 1pamount=0,
-- and at 54: we added the previouslyzero foundsolutions solnyet found for 2.1p,
-- youand canat imagine at5: 6,9,12we etcadded allthe addpreviously infound soln for 3,2.
-- albeityou bycan addingimagine thatat as6,9,12 justetc addedall toadd thein precessor.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 notno count 2p+3p andsolns when processing 3p+2p, aswe twodo solutions.
-- 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}.</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>
<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}}
<pre>
Petelomax
7,803

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/204118"