I'm interested that nobody went recursive. My first solution (I read Mark's
email and stopped reading until I'd done a version) was
command testChange
local t
put empty into t
repeat 10 times
get random(99)
put format("to make %d:%s\n", it, makeChange(it)) after t
end repeat
put t
end testChange
function makeChange iAmount, tChangeSoFar
constant kCoins = "50 20 10 5 2 1"
if iAmount < 1 then return tChangeSoFar
repeat for each word c in kCoins
if iAmount >= c then
return makeChange(iAmount - c, tChangeSoFar && c)
end if
end repeat
return "error"
end makeChange
(note the especially crafty thing here: that by citing my test function, I've
justified leaving a leading space in my output...).
So far, effectively like the rest - I don't think the recursion is better, I
was just surprised that nobody else naturally went that way.
When I replaced the coins list with the unusual denominations of Craig$, 6
came out as 4+1+1, as you'd expect. Here I think is where recursion makes
things better, because it's easy to adjust:
function makeChange iAmount, tChangeSoFar
local tCandidates
constant kCoins = "40 30 10 4 3 1" -- 50 20 10 5 2 1"
if iAmount < 1 then return tChangeSoFar
put empty into tCandidates
repeat for each word c in kCoins
if iAmount < c then next repeat
put makeChange(iAmount - c, c) & return after tCandidates
end repeat
sort lines of tCandidates ascending numeric by the number of words in each
return tChangeSoFar && first line of tCandidates
end makeChange
With these small changes this works, and I'm confident returns the optimal
solution - but it gets shockingly slow for values above about 20.
The first reason it was so slow is because I'm being lazy above - allowing the
code to try options in the wrong order, as each call tries the full set of
coins again. I tried speeding it up by making it having found a coin it can
use, try with that and the next one down, but not all possibles. I'm
reasonably confident that this produced the right result for all cases with
Craig's currency - but I wasn't absolutely sure, and it's certainly not a
general solution, eg asked to make 27 out of "40 30 23 20 9 1" - admittedly a
really crazy currency - it would offer "23 1 1 1 1" rather than the optimal "9
9 9".
So in the end I had to rewrite it more substantially:
command testChange
constant kCoins = "40 30 10 4 3 1" -- "50 20 10 5 2 1"
local t
put empty into t
repeat 10 times
get random(99)
put format("to make %d:%s\n", it, makeChange(it, kCoins)) after t
end repeat
put t
end testChange
function makeChange iAmount, tCoins, tChangeSoFar
local tCandidates, i, c, j
if iAmount < 1 then return tChangeSoFar
-- trim coins that couldn't possibly be used
repeat with i = number of words in tCoins down to 1
if word i of tCoins > iAmount then delete word i of tCoins
end repeat
-- find possible combinations
put empty into tCandidates
repeat with i = 1 to number of words in tCoins
put word i of tCoins into c
put makeChange(iAmount - c, word i to -1 of tCoins, c) \
& return after tCandidates
end repeat
-- return shortest combination
sort lines of tCandidates ascending numeric by the number of words in each
return tChangeSoFar && first line of tCandidates
end makeChange
This definitely returns the optimal combination. It's quite slow (fractions
of a second, but noticeable fractions). But I feel entirely justified in
playing LiveCode's joker:
local saAmountCoins2Change
function makeChange iAmount, tCoins, tChangeSoFar
local tCandidates, i, c, j
if iAmount < 1 then return tChangeSoFar
-- have we done this before?
get saAmountCoins2Change[iAmount, tCoins]
if it <> empty then return tChangeSoFar && it
-- trim coins that couldn't possibly be used
repeat with i = number of words in tCoins down to 1
if word i of tCoins > iAmount then delete word i of tCoins
end repeat
-- find possible combinations
put empty into tCandidates
repeat with i = 1 to number of words in tCoins
put word i of tCoins into c
put makeChange(iAmount - c, word i to -1 of tCoins, c) \
& return after tCandidates
end repeat
-- return shortest combination
sort lines of tCandidates ascending numeric by the number of words in each
put first line of tCandidates into saAmountCoins2Change[iAmount, tCoins]
return tChangeSoFar && first line of tCandidates
end makeChange
Interestingly, even if the array is emptied before each run of tests, this
changes the typical time for a run of tests from approx 1 second for the ten,
to approx 7 milliseconds for the ten. Of course, if the array isn't emptied,
after a few runs it approaches zero. (If the array is emptied before each
single test, which could be described as fairer, it averages around 20
milliseconds for ten tests).
But of course, all of that is only necessary if we move to Craig's Crazy
Currency zone.
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
