#!/usr/bin/perl -w
use strict;
use CGI;
my $cgi=new CGI;
my $file=$cgi->param('file');
$file='menu.txt' if !$file;#reasonable default.

#slurp the lines of the file
open(F,$file) or die(“Couldn’t open file $file:$!\n”);
my @lines=;
close(F) or die(“Couldn’t close file $file:$!\n”);
chomp(@lines); #remove newlines

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

my %price_hash=(); #empty hash to put prices and labels in

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

#compute($hashref,$ongoing_sum); – returns array of names for a match.
sub compute
{
my $hashref =shift;
my $sum =shift;
my @keys =randomise(keys %{$hashref});
foreach my $lbl(@keys)
{
my $price=$$hashref{$lbl};
my $tmpsum=$price+$sum;
if($tmpsum eq $tgt){return $lbl;}#if it matches, return the lbl
if($tmpsum > $tgt){next;}
my @retvals=&compute($hashref,$tmpsum);#none yet, recurse!
if($retvals[0])
{
push (@retvals,$lbl);
return @retvals;
}
}
}

#function to randomise the elements in an array – for fun
sub randomise
{
my @arr = @_;
my $i = @arr;
while ($i–)
{
my $j = int rand ($i+1);
@arr[$i,$j] = @arr[$j,$i];#do the swap – this is a linear algorithm;
}
return @arr;
}