Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Aristotle (5147)


Blah blah blah blah blah []

Journal of Aristotle (5147)

Monday July 09, 2007
02:59 PM

Regex-based solution to xkcd #287

[ #33760 ]

In Perl Appetizers, Randall Munroe writes that he missed a solution when double-checking xkcd #287 with some Perl that used floating point math. Naturally, since this is an NP-complete problem and you need backtracking to solve it in the general case (well, unless you know how to solve NP-complete problems in polynomial time…), I had to post how to do it with Perl regexes…

Unfortunately his comment section mangled the indentation of the generalised code, so I’m posting this here instead, so I have something linkable that’s more permanent than a pastebin.

use strict;
use warnings;
use re 'eval';

my %menu = (
    'mixed fruit'       => 215,
    'french fries'      => 275,
    'side salad'        => 335,
    'hot wings'         => 355,
    'mozarella sticks'  => 420,
    'sampler plate'     => 580,

my $total = 1505;


my %order;

my @order_test = (
    map qq{
            (?: x{$menu{$_}} ) # consume the given number of units

            # worked, so increase the number of orders for this thing;
            # `local` makes this temporally scoped
            (?{ local \$order{ "\Q$_\E" } = \$order{ "\Q$_\E" } + 1 })
    keys %menu,

my $menu_evaluator_regex = qr{
    \A @order_test \z  # find a match for these orders
        my $order = join ', ', (
            map "$order{$_} $_",
            sort { $menu{$a} <=> $menu{$b} }
            keys %order
        print "$order\n";
    (?!) # fail at last possible moment
         # so engine will backtrack for more matches

my $total_units = "x" x $total;

$total_units =~ m/$menu_evaluator_regex/;

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.
  • Actually, backtracking is not required.

    By using dynamic programming, one can find all solutions in pseudo-polynomial time.

    Let me know if you want example code for this.
    • Oh, I know that this particular problem can be done with no backtracking.

      I mean, do you think I am seriously proposing regexes as the best approach to this problem? :-)

      • No - I was replying to your "Obviously, backtracking is needed" comment, that is all.

        Using regular expressions for this is a nifty hack that I enjoyed reading about.
        • Ah, oh. Yeah, the general case. Are you referring to things like Branch&Bound?

          • I'm referring to general dynamic programming.

            Building a table can help solve this problem in O(M+N), where M is linear with the price goal (the higher the price, the longer this algorithm takes) and N is linear with the number of items you have to choose from.

            If one builds a table where the rows represent a price (0 cents, 5 cents, 10 cents, etc, up to the goal price) and the columns represent the items, then moving from the top-left to the bottom-right, one can fill in the table based only on information a