Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (15)
As of 2015-07-01 17:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (13 votes), past polls