Coding challenge

[Ben Rubinstein]

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.