Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: Golf: Buying with exact change

by Anonymous Monk
on Feb 22, 2005 at 10:28 UTC ( #433304=note: print w/ replies, xml ) Need Help??

in reply to Golf: Buying with exact change

Not a golfing solution, but one that doesn't assume an upper bound (although it will loop forever if there's no finite answer):

use strict; use warnings; use Test::More 'no_plan'; $| = 1; my %cache; sub exact { my ($amount, @bills) = @_; return $cache{$amount} if defined $cache{$amount}; return 1 if !$amount; return 0 if $amount < 0; foreach my $bill (@bills) { return $cache{$amount} = 1 if exact($amount - $bill, @bills) } return $cache{$amount} = 0; } sub largest { %cache = (); my @bills = @_; my $smallest = $bills [0]; return -1 if $smallest == 1; my $start = 0; my $prev = 0; for (my $t = 1; 1; $t++) { if (exact($t, @bills)) { if ($prev) { if ($t - $start + 1 == $smallest) {return $start - 1} } else {$start = $t} $prev = 1; } else { $prev = 0; } } } is (largest(6,9,20), 43); is (largest(3,5), 7); is (largest(6,11,20), 27); is (largest(17,18,19,20), 101); is (largest(2,3,5,10), 1); is (largest(1000,1001,1002,1003,1004,1005), 199999); __END__ ok 1 ok 2 ok 3 ok 4 ok 5 ok 6 1..6

Comment on Re: Golf: Buying with exact change
Download Code
Re^2: Golf: Buying with exact change
by dragonchild (Archbishop) on Feb 22, 2005 at 14:44 UTC
    Golfed, I get you down to 140, assuming the inputs are ordered smallest to largest. Interestingly enough, if you have the defined-or patch, I get down to 122. If the inputs aren't ordered, add 13 characters to both solutions.
    Without //= patch: @x=@_;my%c;$e=sub{my$v=pop;exists$c{$v}?$c{$v}:$c{$v}=$v<0?0:$v==0||gr +ep&$e($v-$_),@x};$t=$s=0;{&$e(++$t)?$t-$s>=$x[0]&&last:($s=$t);redo}$ +s With //= patch: @x=@_;my%c;$e=sub{my$v=pop;$c{$v}//=$v<0?0:$v==0||grep&$e($v-$_),@x};$ +t=$s=0;{&$e(++$t)?$t-$s>=$x[0]&&last:($s=$t);redo}$s

    Update: Actually, the inputs don't have to be ordered. It just means that the algorithm will take a little longer, but it will get the right results. Also, drop a character by reordering the assignment to $c{$v}. The //= patched version looks like:
    @x=@_;my%c;$e=sub{my$v=pop;$c{$v}//=$v==0||$v>0&&grep&$e($v-$_),@x};$t +=$s=0;{&$e(++$t)?$t-$s>=$x[0]&&last:($s=$t);redo}$s

    Update: Rewriting the redo-loop as a C-style for-loop drops to 111 characters for the //= patched version.
    @x=@_;my%c;$e=sub{my$v=pop;$c{$v}//=!$v||$v>0&&grep&$e($v-$_),@x};for( +$t=$s=0;$t-$s<$x[0];&$e(++$t)or$s=$t){}$s

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://433304]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (12)
As of 2014-09-23 16:11 GMT
Find Nodes?
    Voting Booth?

    How do you remember the number of days in each month?

    Results (229 votes), past polls