Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) 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.
  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.

blokhead


In reply to Golf: Buying with exact change by blokhead

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!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chilling in the Monastery: (8)
    As of 2014-08-28 02:29 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (255 votes), past polls