Golf: Buying with exact change

[blokhead]

Puzzle: The Widget Emporium services a wide range of widget needs, and they sell widgets at every exact-dollar amount ($1, $2, $3,...). You are shopping for a new widget, so you check in your {wallet,purse} to see what you can afford. You find that it contains an infinite supply of $6 bills, $9 bills, and $20 bills. You have an infinite supply of money, but there's a catch -- The Emporium only accepts exact change! What is the most expensive widget you cannot buy using exact change?

The answer for this particular puzzle is $43, but that alone is not very interesting. Of course, we want to generalize the problem to any number of any size denominations. So the challenge is:

Challenge: Given a set of money denominations, what is the largest amount that can not be represented? In other words: write a function, as short as possible, which takes any number of positive integer arguments and returns the largest number that cannot be written as a sum (with repetition) of the arguments.

Rules:

1. Don't worry about input validation, assume the function will always be passed 1 or more distinct positive integers.
2. Assume the arguments are passed in ascending order
3. You can use global variables, but you should be able to call the function several times in the same run and get correct results.
4. For some groups of denominations, there are an infinite number of values you cannot represent. Or, when a $1 denomination is used, all values can be represented. In this case, the solution is undefined, so you can return anything you like (or even loop forever).
5. Assume any reasonable upper bound on the number of arguments, the size of the arguments, or the size of the answer (but don't use bounds that trivialize the problem). State the bounds you have assumed! If you can, your solution should be coded so that it's possible to increase these upper bounds at the cost of a few more characters. For instance, my golf solutions assume that the answer is less than 1000, but I can increase this to 10,000 by adding another character.
6. Don't worry about efficiency.
7. Your score is the number of characters inside of sub largest { ... }
8. Your code should work within the following framework:

   use Test::More 'no_plan';
   
   sub largest {
   ## your code here
   }
   
   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   );
   

   These sample inputs are for your convenience, but of course, your solution should be correct for all inputs.

Think about it for a while, and get golfing. The best I've done so far is 48 characters (two different ways). I'll post my solutions later.

An observation about the problem that might help you out:

If D is any one of the denominations, and you can represent each of X, X+1, ..., X+(D-1) using the denominations given, then you can represent all amounts of size X or higher (by taking one of the X+i and adding copies of D).

I came across this problem during a college radio trivia marathon -- only the problem was phrased in terms of black-market kidneys that come in packages of 6, 9, or 20. ;) I think it's a very neat problem, as it is has interesting ties to formal language theory. Golfing it down was fun, too, and it even led me to discover a bug in Perl! There are also other fun problems relating to currency and change-making that I can post, if you're interested.

Update: This problem is also called the Frobenius problem. The largest number not expressible from a set of coins is called the Frobenius number of that set.

[kvale]

Fun problem. Here is a solution in 72 characters with a bound of 1000:

sub largest {my$r;$r.='('.5x$_.')*'for@_;for($i=1000;;$i--){return$i if(5x$i)!~/^$r$/}}

[!1]

64

sub largest { # 345678 1 2345678 2 2345678 3 2345678 4 2345678 5 2345678 6 234 my$r;$r.='('.5x$_.')*'for@_;for($i=1000;(5x$i)=~/^$r$/;$i--){}$i }

[Thelonious]

59

sub largest { # 345678 1 2345678 2 2345678 3 2345678 4 2345678 5 23456789 @r=map'('.5x$_.')*',@_;for($=**=2;(5x$=)=~/^@r$/x;$=--){}$= }

[fergal]

That's very clever but you do appear to have chosen bounds that trivialise the problem. Try largest(1000, 1001, 1003) 100,000 isn't large enough, try 1,000,000 and then go make a cup of tea (actually you could probably grow a cup of tea in the time this will take)

Update Hmm.... the original did say not to worry about efficiency but it's not hard to produce examples with fairly small numbers that will run for years, maybe even centuries. I've been waiting more than 7 minutes just to find out if 999999 is possible with largest(1000, 1001, 1002, 1003, 1004, 1005) and there's no sign of an answer yet.

Update again I killed it after 100 min of CPU time (1.7Ghz Pentium) and it still hadn't figured out if 999,999 was doable or not.

[blokhead]

I guess we disagree on what trivializing the problem means ;) I didn't mean to imply that all instances of the problem in fact do have solutions which are so small -- that is clearly not true. My intent is that, if it helps you, your solution can solve a restricted but "reasonable" subset of instances (and to make things clear, define what restricted subset your solution is correct for, if you can). What is "reasonable?"

I basically want to rule out smart-ass solutions like this:

sub largest { 43 }

It works for largest(6,9,20), but one instance is a trivial subset of the problem space. Unreasonable.

The set of instances whose solutions are less than 1000.. 10000.. is that a "reasonable" subset? The idea is to find a concise algorithm to solve this particular problem, and to solve all these instances correctly, (a) you must actually carry out some sort of computation, and (b) your algorithm must probably be correct. To me, that's reasonable enough.

[fergal]

Here's a solution with no limits (beyond the memory used by memoize). It answers largest(1000, 1001, 1002, 1003, 1004, 1005) in 19 secs (the answer is 199,999 by the way). If you turn off memoize it takes much longer, although probably just days rather than centuries, It's based on a previous perlmonks challenge: How to generate restricted partitions of an integer.

It's definitely not golf! Is there a golfish answer that runs in similar time?

Read more... (2 kB)

I'm going to bed now so I won't explain in detail. Hopefully someone will have posted a more golfish solution by the time I get to work tomorrow and I won't have to bother.

[fergal]

I'm justpointing out that the regex solution is terrible once the numbers start to get large. Efficiency is not the primary concern in golf but a soution should terminate before the sun dies :-)

Another problem I have with the regex solution is that you don't know how much is enough for any given input. I'd say twice the largest 2 number would do it but I'm not sure, there will be complications when some of the numbers share factors.

It's an interesting puzzle though, it has a very simple solution when there's only 2 numbers:

largest(m, n) = (m - 1) * (n - 1) - 1

[BrowserUk]

The first one I tried was 1,2,3--still waiting:)

[blokhead]

As the other monks observed, the most concise solutions will probably use regular expressions. When looking only at the length of strings, the set of amounts you can represent using $6, $9, and $20 bills is /^(.{6})*(.{9})*(.{20})*$/, or equivalently for our purposes, /^(.{6}|.{9}|.{20})*$/. Now, to get the function arguments into such a regex and find the longest string that doesn't match is the creative part...

Here are my two 48-character solutions:

$"="}|1{";$_=1x999;chop while/^(1{@_})*$/;length $"="}|1{";(grep{(1x$_)!~/^(1{@_})*$/}1..999)[-1]

And if it weren't for a bug I just found in alternations within negative lookaheads, I'm pretty sure this would be equivalent, giving me 46 characters:

$"="}|1{";1x999=~/(1*?)(?!(1{@_})*$)/;length$'

They all use basically the same idea, can you think of a different approach? As I mentioned in the original post, these work for all instances where (a) the solution is 999 or less, and also (b) the arguments are each less than 32k (because they are used in regex quantifiers).

[dragonchild]

I'm down to 111 characters at Re^2: Golf: Buying with exact change using Anonymonk's non-regex solution. I think that with the addition of a few characters, you might be able to remove the 999 restriction on the regex solution.

Update: Melding our solutions gives a 79 character solution that doesn't have the 999 restriction.

$"="}|1{";$r=qr/^(1{@_})+$/;for($t=$s=0;$t-$s<$_[0];(1x++$t)=~/$r/ or$ +s=$t){}$s

[blokhead]

Here's a solution that doesn't have the arbitrary restriction on the solution size, although since it uses the same regex trick as above, the inputs must still be <32k. It's 75 characters:

($",$n,$_)="}|1{";while($n++<$_[-1]){$_.=1;/^(1{@_})*$/ or$n=0}length()-pop

But the non-regex ideas are interesting to me, as I wasn't sure it was easily possible without the regex logic.

[Anonymous Monk]

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

[dragonchild]

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

[Anonymous Monk]

Or, when a $1 denomination is used, all values can be represented. In this case, the solution is undefined, so you can return anything you like (or even loop forever).

Why is the solution undefined if a $1 denomination is used? I'd say there's an obvious answer: 0.

[Anonymous Monk]

The problem was phrased in terms of black-market kidneys that come in packages of 6, 9, or 20.

I'm so glad they fixed the organ donor shortage.

[blazar]

I've not followed this thread in detail so I don't know if it's already been mentioned, but this is indeed a well known mathematical (combinatorial) problem, and a "hard" one, actually called "the money changing problem".

The problem is discussed in some detail e.g. in the beautiful book generatingfunctionology by Prof. Wilf, available for download from http://www.math.upenn.edu/%7Ewilf/DownldGF.html

To quote from Wilf:

There are no general `formulas' for the conductor if M >= 3, and no good algorithms for calculating it if M >= 4.

(M is the number of "changes" and the "conductor" is the smallest quantity N such that all n>=N can be represented as sums of the changes. In this case the latter must be -of course- coprime.)

[tilly]

I find this claim slightly bizarre. I downloaded the PDF and read Wilf's description of the problem (he's looking for a number 1 bigger than the largest function described above). The following fairly obvious code solves the problem for arbitrary M in worst case time proportional to O(M*n*n) where n is the size of the smallest denomination. (If there are only 2 denominations then this will be O(M*n).)

#! /usr/bin/perl -w
use strict;

print largest(@ARGV)."\n";

sub largest {
  # Everything works mod $least
  my $least = min(@_);
  # We start off not knowing how to do anything.
  my @first = map {undef} 1..$least;
  # For technical reasons this needs to be 0 now,
  # and $least later.
  $first[0] = 0;
  for my $num (@_) {
    my @in_process = grep {defined($first[$_])} 0..($least - 1);
    while (@in_process) {
      my $to_process = shift @in_process;
      my $value = $first[$to_process] + $num;
      my $mod = $value % $least;
      if (not defined($first[$mod]) or $value < $first[$mod]) {
        $first[$mod] = $value;
    print "  $value = $mod (mod $least)\n";
    push @in_process, $mod;
      }
    }
  }
  $first[0] = $least;
  if (grep {not defined($_)} @first) {
    # We didn't reach one...
    return undef;
  }
  else {
    my $worst = max(@first);
    return $worst - $least;
  }
}

sub min {
  my $min = shift;
  for (@_) {
    $min = $_ if $_ < $min;
  }
  return $min;
}

sub max {
  my $max = shift;
  for (@_) {
    $max = $_ if $_ > $max;
  }
  return $max;
}

I can only guess that he's measuring complexity in terms of the number of bits required to represent the numbers in the denomination. So he'd consider my solution as taking exponential time.

[Anonymous Monk]

• For those of us "math challanged" you denominations must not have any common factors. i.e. all even, all multiples of some N. Otherwise there is an infinite number of prices which you can't buy:-(

• In a more obscure vein. A closed solution for arbitrary M has been shown to be NP-hard.

  starbolin

[aufflick]

I love the use of black on black as the new rot13!!

[Solo]

UPDATE: Yuk. Note to self: math at 5PM Friday is a bad idea.