{"id":19,"date":"2008-05-21T19:10:15","date_gmt":"2008-05-22T02:10:15","guid":{"rendered":"http:\/\/www.imaginarybillboards.com\/?p=19"},"modified":"2010-01-27T19:13:04","modified_gmt":"2010-01-28T02:13:04","slug":"xkcd-menu-problem","status":"publish","type":"post","link":"http:\/\/www.imaginarybillboards.com\/?p=19","title":{"rendered":"XKCD menu problem"},"content":{"rendered":"

So everyone is doing the menu problem (comic<\/a>) – even job postings for places. It looks like the most common way is to recurse through, starting at the cheapest item and going through again until either the price is right or it goes over the target, then going down and back up, etc. Which is nice and all, but for some reason when I was doing it I felt bad for the diners. Why? Cause you always end up with a bunch of the cheapest appetizers. Solution?(without computing all possible solutions…) Randomize how you go through the list of menu items. \ud83d\ude42 This is pretty much the first one I went through, since the problem is solved and my interest goes away. But I’m amused enough about feeling bad for the diners that I wanted to remember it later on. So here goes:<\/p>\n


\n#!\/usr\/bin\/perl -w
\nuse strict;
\nuse CGI;
\nmy $cgi=new CGI;
\nmy $file=$cgi->param('file');
\n$file='menu.txt' if !$file;#reasonable default.<\/code><\/p>\n

#slurp the lines of the file \ud83d\ude42
\nopen(F,$file) or die(“Couldn’t open file $file:$!\\n”);
\nmy @lines=;
\nclose(F) or die(“Couldn’t close file $file:$!\\n”);
\nchomp(@lines); #remove newlines<\/p>\n

#first line is the target price
\nmy $tgt=shift(@lines);
\n#don’t need $signs
\n$tgt=~s\/\\$\/\/g;<\/p>\n

my %price_hash=(); #empty hash to put prices and labels in<\/p>\n

#dump the the data into a hash, removing $signs again
\n#format is ${‘label’}=$price;
\nforeach my $line(@lines)
\n{
\nmy($lbl,$price)=split(‘,’,$line);
\n$price=~s\/\\s\/\/g; #remove whitespace also
\n$price=~s\/\\$\/\/g;
\nif($price > $tgt){next;}
\n$price_hash{$lbl}=$price;
\n}
\n#get an array with the names of a match from the function
\nmy @retvals=&compute(\\%price_hash,0);
\nif($retvals[0])
\n{
\nprint join(“,”,@retvals).”\\n”;
\n}
\nelse
\n{
\nprint “No matches found\\n”;
\n}<\/p>\n

#compute($hashref,$ongoing_sum); – returns array of names for a match.
\nsub compute
\n{
\nmy $hashref =shift;
\nmy $sum =shift;
\nmy @keys =randomise(keys %{$hashref});
\nforeach my $lbl(@keys)
\n{
\nmy $price=$$hashref{$lbl};
\nmy $tmpsum=$price+$sum;
\nif($tmpsum eq $tgt){return $lbl;}#if it matches, return the lbl
\nif($tmpsum > $tgt){next;}
\nmy @retvals=&compute($hashref,$tmpsum);#none yet, recurse!
\nif($retvals[0])
\n{
\npush (@retvals,$lbl);
\nreturn @retvals;
\n}
\n}
\n}<\/p>\n

#function to randomise the elements in an array – for fun
\nsub randomise
\n{
\nmy @arr = @_;
\nmy $i = @arr;
\nwhile ($i–)
\n{
\nmy $j = int rand ($i+1);
\n@arr[$i,$j] = @arr[$j,$i];#do the swap – this is a linear algorithm;
\n}
\nreturn @arr;
\n}<\/p>\n","protected":false},"excerpt":{"rendered":"

So everyone is doing the menu problem (comic) – even job postings for places. It looks like the most common way is to recurse through, starting at the cheapest item and going through again until either the price is right or it goes over the target, then going down and back up, etc. Which is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[15],"tags":[12,10,11],"_links":{"self":[{"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=\/wp\/v2\/posts\/19"}],"collection":[{"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=19"}],"version-history":[{"count":1,"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=\/wp\/v2\/posts\/19\/revisions"}],"predecessor-version":[{"id":93,"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=\/wp\/v2\/posts\/19\/revisions\/93"}],"wp:attachment":[{"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.imaginarybillboards.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}