http://qs321.pair.com?node_id=87681

Odud's recent posting on Junior Perl came with a little puzzle to do with giving change, which is simple enough, and is certainly golf material. Suppose you are trying to write a function c that, give the amount you want, and an array reference to the units of currency that you have available in order from lowest to highest, will return a list of the required change.

For instance, if $22.50 was specified, along with a US currency specification, assuming no $2 bills are available in the area:     print join(',',c(22.50,[.01,.05,.1,.25,1,5,10,20,50,100])); Would output:     20,1,1,0.25,0.25 Of course, other countries use different units, such as:     print join(',',c(22.50,[.01,.05,.1,.20,1,2,5,10,20,50,100])); Which would show:     20,2,0.2,0.2,0.1 Amounts less than the smallest unit of currency are not handled, so they can be ignored.

Here's my baseline, which is 115 characters, not including linebreaks required for presentation: 
sub c{
($t,$p,@r)=@_;@p=map{int($_*100)}@$p;
$t=int($t*100);while($v=pop@p and$t>0
){while($t>=$v){push@r,$v/100;$t-=$v;
}}@r
}

[download]
You will note the use of integer math only. I am perplexed by the floating point math. As Obdud says, this exercise should teach "simple arithmetic, looping, lists, sorting, etc." where 'etc.' apparently refers to floating point idiosyncrasies, such as the following:      print "$t != $v\n" if ($t != $v); Which surprisingly shows:      0.1 != 0.1 Where the values were actually: $t = 0.099999999999999977795540, $v = 0.100000000000000005551115, due to some minor floating point issues in the 17th decimal place.

Replies are listed 'Best First'.
Re: (Golf) Giving Change
by Trimbach (Curate) on Jun 12, 2001 at 06:37 UTC
    By taking a few liberties with the output format here's my entry at 98: 
    sub c {($a,$c)=@_;@c=@$c;return map{$a>$_?
&{sub{$a-=$_*($b=int($a/$_));"$b x $_"}}:""} reverse @c}

    [download]
    The output format this way looks like this: 
    ,,1 x 20,,,2 x 1,2 x 0.25,,,

    [download]
    ...which is both cooler (it tells you how many of each denomination) and uglier (empty commas are bad) at the same time. You could always reformat when the sub is called, but I felt I was taking lots of liberties as it was. :-D

    I don't normally bother golfing, but this was educational: I found out you can't coerce a trinary operator to do more than one thing at a time in the "then" part without resorting to an anonymous sub. (At least, I think that's right. That's why it's a trinary operator, I guess. :-D) It was fun, and educational...

    Gary Blackburn
    Trained Killer

[reply]
[d/l]
[select]
      Nice solution. There is room for improvement, though. No need for return, use that for filtering out empty items: 
      sub c {($a,$c)=@_;@c=@$c;grep$_,map{$a>$_?
  &{sub{$a-=$_*($b=int($a/$_));"$b x $_"}}:""} reverse @c}

      [download]
      Char-neutral, but leaving the grep out gains 7 chars.

      You don't need the parens after the int, and leave out the spaces around the reverse. Gains you 4 char: 

      sub c{($a,$c)=@_;@c=@$c;grep$_,map{$a>$_?
  &{sub{$a-=$_*($b=int$a/$_);"$b x $_"}}:""}reverse@c}

      [download]

      Jeroen
      "We are not alone"(FZ)

[reply]
[d/l]
[select]
        Ooooooooo... I like the grep idea. Duh. Can you tell I don't golf much? :-D Spiffy!

        Gary Blackburn
        Trained Killer

[reply]
      You don't need to use an anonymous sub; use a do { ... } block instead. 
         MeowChow                                   
               s aamecha.s a..a\u$&owag.print
[reply]
Re: (Golf) Giving Change
by iakobski (Pilgrim) on Jun 12, 2001 at 15:14 UTC
    Here's my entry at 67: 
    #2345678901234567890123456789012345678901234567890123456789012345678
sub c{($t,$p)=@_;for(reverse@$p){until($t<$_){push@r,$_;$t-=$_}}@r}

    [download]
    Based on tadman's original.

    update

    boo_radley just pointed out this is in fact 54. Where do I find the rules to this sport?

    -- iakobski

[reply]
[d/l]
      I'm not sure how boo_radley counted 54 - it's actually 60. You count only the characters inside the sub. You should also add three characters to reset @r (thereby making this sub usable more than once).

      Anyway, here's a solution at 54: 

      sub c{($t,$p)=@_;map{$t-=($x=int$t/$_)*$_;($_)x$x}reverse@$p}

      [download]
         MeowChow                                   
               s aamecha.s a..a\u$&owag.print
[reply]
[d/l]
Re: (Golf) Giving Change
by bikeNomad (Priest) on Jun 12, 2001 at 04:27 UTC
    Assuming that your lowest denomination >= 0.000001, you can get around the scaling in your code using sprintf (94 chars here):
    sub c{($t,$p,@r)=@_;while($v=pop@$p and$t>0)
{while($t>=$v){push@r,$v;$t=sprintf"%f",$t-$v}}@r}

    [download]

    update: added reinit of @r, comment about limits on smallest denomination (change %f to "%9f" for 1e-9 limit), change %g to %f
    Works for larger numbers:
    print join(',',c(22500020,[.01,.05,.1,1,2,5,10,20,50,100,1e3,1e4,1e5,1e6])); 1000000,1000000,1000000,1000000,1000000,1000000,1000000, 1000000,1000000,1000000,1000000,1000000,1000000,1000000, 1000000,1000000,1000000,1000000,1000000,1000000,1000000, 1000000,100000,100000,100000,100000,100000,20

[reply]
[d/l]
[select]
      In the process of your function, you consume the array given to you. If this were a fixed array provided by reference, you would trash it, rendering it useless for subsequent operations. Penalty is 7 characters:      @p=@$p; Further, I don't know of any currencies which use millionths of a unit, so why 1e-9 is even relevant is beyond me. Yikes!
[reply]
[d/l]
      You'll lose precision if $t has more than 6 digits.
[reply]
Re: (Golf) Giving Change
by no_slogan (Deacon) on Jun 12, 2001 at 04:04 UTC
    1. Is the set of denominations guaranteed to contain a penny? If not, this is the knapsack problem (which is NP-complete, BTW).
    2. Is 2,250 pennies a valid solution for $22.50?
[reply]
      No, it does not correspond to the 0-1 Knapsack problem (which is NP-complete), but to the fractional knapsack problem, which can be solved using a greedy algorithm (put as many of the largest denomination as will fit, then continue to the next lower denomination, and so on until you reach the target amount).

      --ZZamboni

[reply]
        Your change is 2.25 10-dollar bills.

        Update: If we could give back part of a bill, we would be talking about the fractional knapsack problem. We can't.

[reply]
      1. The demoninations are not guaranteed to contain a penny, as this might be for Japanese Yen, which do not use fractional currency (smallest unit is 1 Yen). Fortunately, you are not required to give "change" for these trifling units smaller than the smallest "coin" or "bill".
      2. 2,250 may add up to $22.50, but it is not a valid solution. You would get this if you fed the currency into the function backwards, though. As ZZamboni points out, proceed in order from largest to smallest and all will be well.
[reply]
        With certain combinations of currency, the greedy strategy won't work so well. Imagine you need to give 30 cents change, using US coins but not nickels. The intuitively "correct" solution is three dimes, but the greedy strategy will give one quarter and five pennies. If you want to define the greedy answer to be the correct one, that's fine, but you didn't make that clear in the problem statement.

        If the coins are a little stranger, the greedy strategy will fail altogether. Maybe the land of Frobozz has 2-frob and 3-frob coins, but no 1-frob coin. You can make 7 frobs with one 3 and two 2s, but if you start out by giving two 3s, you're stuck.

        We could define a "generalized penny" to be a coin which every other coin is a multiple of. The penny and the yen are both "pennies" by this definition. If such a coin exists, the greedy method will always produce an answer. There's no frob-penny in my example, though.

[reply]

Back to Meditations