use Perl

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