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

#### Aristotle (5147)

Aristotle
pagaltzis@gmx.de
http://plasmasturm.org/

Blah blah blah blah blah [technorati.com]

### 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.

#!/usr/bin/perl
use strict;
use warnings;
use re 'eval';

'mixed fruit'       => 215,
'french fries'      => 275,
'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 })
)*
},
);

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

my \$total_units = "x" x \$total;

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Full
Abbreviated
Hidden
• #### Pseudo-Polynomial Time Solutions(Score:1)

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.
• #### Re:(Score:1)

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? :-)

• #### Re:(Score:1)

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.
• #### Re:(Score:1)

Ah, oh. Yeah, the general case. Are you referring to things like Branch&Bound?

• #### Re:(Score:1)

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