Regex-based solution to xkcd #287

Aristotle on 2007-07-09T19:59:31

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

---

Pseudo-Polynomial Time Solutions

Serpent on 2007-10-30T19:53:06

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:Pseudo-Polynomial Time Solutions

Aristotle on 2007-10-30T23:08:39

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:Pseudo-Polynomial Time Solutions

Serpent on 2007-10-31T04:37:25

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:Pseudo-Polynomial Time Solutions

Aristotle on 2007-11-01T16:19:36

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

Re:Pseudo-Polynomial Time Solutions

Serpent on 2007-11-04T07:21:29

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 above and to the left. When the table is filled in, the bottom-right-hand cell contains the information needed to print all solutions to the problem.

I have code, if you are interested.