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   );
   [download]

   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.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.