Re: [Unicon-group] 13 Coins (in a fountain?)

[Steve Wampler]

There was a lot of unneeded code in that last solution (left over from
the previous one), so here's a cleaned-up version in case anyone
is interested...

-Steve
-- 
Steve Wampler -- [EMAIL PROTECTED]
The gods that smiled on your birth are now laughing out loud.

global cMap

# Given a monetary amount TARGET in US cents, and a number N of
#   coins, generates all possible combinations of N US coins that
#   exactly match TARGET cents.
#
procedure main(args)
    target := integer(args[1]) | 110
    nCoins := integer(args[2]) | 13

    # US coin demoninations...and their worth in cents.
    allCoins := "DFQdnp"
    cMap := table()
    cMap["D"] := 100; cMap["F"] :=  50; cMap["Q"] :=  25
    cMap["d"] :=  10; cMap["n"] :=   5; cMap["p"] :=   1
 
    write("Combinations of ",n," US coins to make ",target," cents:")
    every i := 1 to *allCoins do {
        coin  := allCoins[i]
        coins := allCoins[i:0]
        process(genCoins(genDenom(coin,target,nCoins), nCoins, target, coins))
        }
end

# Generate solutions.
#
procedure genCoins(s, i, t, coins)
    if (i < *s) | (t < 0) then fail
    if i = *s then suspend ((t-cMap[s]) = 0, s)
    else {
        t -:= cMap[s]
        every k := 2 to *coins do {
            suspend s || genCoins(genDenom(coins[k],t,i-*s),i-*s,t,coins[k:0])
            }
        }
end

# Generate longer sequences of a given demonination, stop when it
#   makse sense to stop (too many coins or too much money).
#
procedure genDenom(c, t, nc)
    coins := c
    repeat {
        if (*coins > nc) | ((t - cMap[coins]) < 0) then fail
        suspend coins
        /cMap[coins ||:= c] := cMap[c] * (*coins)
        }
end

# Have a solution, output it.
#   (Could produce a more human-friendly form here, if desired.)
# 
procedure process(answer)
    write("\t",answer)
end