Just another Perl shrine PerlMonks

### Comment on

 Need Help??
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.
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 {
}

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.

 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.

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2018-01-21 15:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (228 votes). Check out past polls.

Notices?