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

Monday July 09, 2007

02:59 PM

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';

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

}x;

my $total_units = "x" x $total;

$total_units =~ m/$menu_evaluator_regex/;

Full

Abbreviated

Hidden

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.

## Pseudo-Polynomial Time Solutions (Score:1)

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)

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)

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