Of course I can't be sure about speed. If you make a recursive call it
will need to check all the guarded cases, by computing the range of
quantity it is doing the same work one additional time to get most, but
then avoid the work of checking the final failing case that the other
solutions relied
inh Tien Tuan Anh <[EMAIL PROTECTED]>
CC: [EMAIL PROTECTED], haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Coin changing algorithm
Date: Wed, 13 Jul 2005 18:41:41 +0300
On 7/13/05, Dinh Tien Tuan Anh <[EMAIL PROTECTED]> wrote:
> i guess i have to learn Monads then, ^_^
That&
On 7/13/05, Dinh Tien Tuan Anh <[EMAIL PROTECTED]> wrote:
> i guess i have to learn Monads then, ^_^
That's probably a good idea. But what about this problem made you
think "monads"? Caching? The imperative solution you mentioned?
--
regards,
radu
http://rgrig.blogspot.com/
___
rt <[EMAIL PROTECTED]>
Reply-To: Kurt <[EMAIL PROTECTED]>
To: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Coin changing algorithm
Date: Wed, 13 Jul 2005 11:19:03 -0400
Here's mine, which is similar to Cale's, although done before I saw his:
coins = reverse [1,5,10,2
Okay, I like Cale's extra guard short circuit so much I must add it to
my pseudo-example.
Cale's guard:
> amount `div` maximum coins > maxCoins = [] -- optimisation
Mine, updated.
>
> partition (x:xs) m k | x>m = partition xs m k-- x is too big
>
> parititon (x:_) m k | x*k < m = []
On 7/13/05, ChrisK <[EMAIL PROTECTED]> wrote:
> Sort the list of integers, highest at the front of the list.
> (And perhaps remove duplicates with nub)
The first time I wrote in the comments that 'partition' takes a
"decreasing list of integers..." and then I decided to drop
"decreasing". Weakest
Here's mine, which is similar to Cale's, although done before I saw his:
coins = reverse [1,5,10,25]
change' 0 = [[]]
change' amt =
concat $ map subchange $ filter (amt >=) coins
where
-- recursively make change
subchange c =
map (\l -> c:l) $ filter (canon c)
heh, just noticed that the (amount > 0) test in the last guard is
unnecessary (other cases added since then leave only that as a
possibility) and it can be replaced by "otherwise", not that it makes
too much of a difference:
> import Monad
> import List
>
> makeChange :: [Integer] -> Integer -> I
Well, I don't have time to do more than comment, but here are few
improvements:
Sort the list of integers, highest at the front of the list.
(And perhaps remove duplicates with nub)
When you pop the first element you can already compute the range of
quantity you will need, and can perhaps special
Here's my little recursive solution:
import Monad
import List
makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]
makeChange coins amount maxCoins
| amount < 0 = []
| amount == 0 = [[]]
| null coins = []
| amount `div` maximum coins > maxCoins = [] -- optimisation
|
On 7/13/05, Dinh Tien Tuan Anh <[EMAIL PROTECTED]> wrote:
> Any idea ?
This is the first thing I wrote when i read your problem:
=== begin integer_partition.lhs ===
This is a solution to a question asked on Haskell cafe. The problem
looks like a classical one.
You are given a list of positive in
On Wed, 13 Jul 2005, Dinh Tien Tuan Anh wrote:
(snip)
> eg: m = 75, k = 5
> => [50, 20, 5]
> [50, 20, 1,2,2]
(snip)
> Is this problem suitable for functional programming language ?
Oh, what fun. I like this sort of thing. My quick attempt is:
module Coins where
import Data.Ma
Hi,
The problem is:
Given an amount of money m, and unlimited coins of value 1p, 2p, 5p, 10p,
20p, 50p, £1 and £2
List ALL (distinct) ways of change for m, using no greater than k coins
eg: m = 75, k = 5
=> [50, 20, 5]
[50, 20, 1,2,2]
..
..
13 matches
Mail list logo
