programming – Imaginary Billboards http://www.imaginarybillboards.com Imagined things Fri, 23 Mar 2018 15:50:44 +0000 en-US hourly 1 https://wordpress.org/?v=6.0.8 Perl one-liner to see who is hogging all the open filehandles http://www.imaginarybillboards.com/?p=194 http://www.imaginarybillboards.com/?p=194#comments Tue, 22 Mar 2011 13:46:50 +0000 http://www.imaginarybillboards.com/?p=194 Helpful one-liner to help fix a problem we ran into the other day.

perl -e 'map{$c{(split(/\s+/))[2]}++} `lsof`;print "$_ $c{$_}\n" for (keys %c);'

The thinking is:

Use lsof to get all the open filehandles which conveniently also shows who has it open.

`lsof`

Loop through them, using the ` as a cheat that it inputs an array

map {   } `lsof`;

Splitting on whitespace.  The input to each iteration of the map{ } defaults to $_, and if you don't put anything to split in a perl split, it uses $_.  Neat.

split(/\s+/)

Since we just care about the count, only use the 3rd column by forcing the output of the split into an array and using a slice.

(split(/\s+/))[2]

Now, we just want the count for those users so we increment a hash with the user name as they key.

$c{ }++

Of course, the split is returning the name so that gives us the user name and hash key.

$c{(split(/\s+/))[2]}

And increment that.  Unlike python, for example, you can just increment it.

$c{(split(/\s+/))[2]}++

It will do that for every iteration of the map{ }.  i.e. every line in the output of the `lsof`.

After that, it's just a matter of printing out the key/value pairs using a easy hash printing line blatently stolen from an answer on Stack Overflow.

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=194 3
New network – How I find out what’s there http://www.imaginarybillboards.com/?p=96 http://www.imaginarybillboards.com/?p=96#respond Fri, 29 Jan 2010 16:48:21 +0000 http://www.imaginarybillboards.com/?p=96 I switched jobs recently to become sysadmin of a fairly small company.  I think job #1 is to figure out just what is on your new network.  It’s kind of important.  This is the dumb little perl script I re-write every time I go someplace new because frankly – it’s fun!

#!/usr/bin/perl
use  warnings;
use strict;
#this should be run as root, otherwise nmap will probably yell at you

my $net=shift || usage();
#the lazy, lazy regex to get the subnet you're working on...
$net=~s/(\d{1,3}\.\d{1,3}\.\d{1,3}\.)\d// || usage();

foreach my $end(0..255)
{
        my $ip  ="$net$end";
        my ($fwd,$rev,$ud,$os) = ("unknown")x4;
        my $nmap  =`nmap -v -O -sT $ip`; #save for later
        my @nmap  =split("\n",$nmap);

        #get forward and reverse DNS
        chomp(my $host =`host $ip`);
        if($host!~m/NXDOMAIN/)
        {
                $fwd=(split(" ",$host))[-1];
                chomp($rev=`host $fwd`);
                $rev=(split(" ",$rev))[-1];
                $rev= "" unless $ip ne $rev; #only display if it doesn't equal the original ip
        }

        $ud = $nmap=~m/Host seems down/?'Down':'Up';
        #get the o/s
        $os=(grep(/Running/,@nmap))[0] || '';
        if($os)
        {
                $os=~s/Running: //;
                $os=substr $os,0,25;
        }
        $fwd=substr $fwd,0,40;
        printf "%-16s%-5s%-28s%-43s%-20s\n",$ip,$ud,$os,$fwd,$rev;
}
sub usage
{
        print "usage: >#!/usr/bin/perl
use warnings;
use strict;
#this should be run as root, otherwise nmap will probably yell at you

my $net=shift || usage();
#the lazy, lazy regex to get the subnet you're working on...
$net=~s/(\d{1,3}\.\d{1,3}\.\d{1,3}\.)\d/$1/ || usage();

foreach my $end(0..255)
{
        my $ip  ="$net$end";
        my ($fwd,$rev,$ud,$os) = ("unknown")x4;
        my $nmap  =`nmap -v -O -sT $ip`; #save for later
        my @nmap  =split("\n",$nmap);

        #get forward and reverse DNS
        chomp(my $host =`host $ip`);
        if($host!~m/NXDOMAIN/)
        {
                $fwd=(split(" ",$host))[-1];
                chomp($rev=`host $fwd`);
                $rev=(split(" ",$rev))[-1];
                $rev= "" unless $ip ne $rev; #only display if it doesn't equal the original ip
        }

        $ud = $nmap=~m/Host seems down/?'Down':'Up';
        #get the o/s
        $os=(grep(/Running/,@nmap))[0] || '';
        if($os)
        {
                $os=~s/Running: //;
                $os=substr $os,0,25;
        }
        $fwd=substr $fwd,0,40;
        printf "%-16s%-5s%-28s%-43s%-20s\n",$ip,$ud,$os,$fwd,$rev;
}
sub usage
{
        print "usage: $0    ex: $0 192.168.0.0\n";
        exit();
}<    ex: >#!/usr/bin/perl
use warnings;
use strict;
#this should be run as root, otherwise nmap will probably yell at you

my $net=shift || usage();
#the lazy, lazy regex to get the subnet you're working on...
$net=~s/(\d{1,3}\.\d{1,3}\.\d{1,3}\.)\d/$1/ || usage();

foreach my $end(0..255)
{
        my $ip  ="$net$end";
        my ($fwd,$rev,$ud,$os) = ("unknown")x4;
        my $nmap  =`nmap -v -O -sT $ip`; #save for later
        my @nmap  =split("\n",$nmap);

        #get forward and reverse DNS
        chomp(my $host =`host $ip`);
        if($host!~m/NXDOMAIN/)
        {
                $fwd=(split(" ",$host))[-1];
                chomp($rev=`host $fwd`);
                $rev=(split(" ",$rev))[-1];
                $rev= "" unless $ip ne $rev; #only display if it doesn't equal the original ip
        }

        $ud = $nmap=~m/Host seems down/?'Down':'Up';
        #get the o/s
        $os=(grep(/Running/,@nmap))[0] || '';
        if($os)
        {
                $os=~s/Running: //;
                $os=substr $os,0,25;
        }
        $fwd=substr $fwd,0,40;
        printf "%-16s%-5s%-28s%-43s%-20s\n",$ip,$ud,$os,$fwd,$rev;
}
sub usage
{
        print "usage: $0    ex: $0 192.168.0.0\n";
        exit();
}< 192.168.0.0\n";
        exit();
}

Example output:

monitor:~ imaginarybillboards$ sudo perl Documents/check_network.pl 192.168.2.0
192.168.2.0   Down                             unknown                                  unknown
192.168.2.1   Up   SonicWALL SonicOS 3.X       firewall.private.blah.com.
192.168.2.2   Down                             switch.private.blah.com.
192.168.2.3   Up   Cisco IOS 12.X              ck-sw0.private.blah.com.
192.168.2.4   Down                             unknown                                  unknown
192.168.2.5   Down                             unknown                                  unknown

And without down hosts (a little more directly useful, perhaps):

monitor:~ imaginarybillboards$ sudo perl Documents/check_network.pl 192.168.2.0 | grep -v Down
192.168.2.102 Up   Apple Mac OS X 10.5.X       monitor.private.blah.com.             192.168.2.105
192.168.2.103 Up   Linux 2.6.X                 cartman.private.blah.com.
192.168.2.104 Up   Linux 2.6.X                 kenny.private.blah.com.
192.168.2.105 Up   Apple Mac OS X 10.5.X       monitor.private.blah.com.
192.168.2.107 Up   Microsoft Windows XP        unknown                                  unknown
192.168.2.108 Up   Apple iPhone OS 1.X|2.X|3   unknown                                  unknown
192.168.2.110 Up   Apple Mac OS X 10.5.X       unknown                                  unknown
192.168.2.112 Up   Apple Mac OS X 10.5.X       unknown                                  unknown

Obviously, I have a bit of work to do with that monitor DNS.  This gives me a decent idea of what's around.  Servers and desktops (and iphones apparently) are all mixed on the same network.

Also, once I've (re-)written this, I put into a cron job so I can keep a running track of what's going on.  Disk space is cheap, and it can't hurt anything.

crontab -l
0 2 * * * /bin/bash -login -c 'perl /Users/chriskaufmann/Documents/check_network.pl 192.168.200.0 > \
    /Users/chriskaufmann/Documents/NetworkReports/`date +\%y-\%m-\%d`'

And then you can just diff them to see when something came onto the network.

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=96 0
If perl is write-only… http://www.imaginarybillboards.com/?p=61 http://www.imaginarybillboards.com/?p=61#comments Thu, 03 Sep 2009 13:43:52 +0000 http://www.imaginarybillboards.com/?p=61 Then python is read-only.  Think of it.

Both have a shebang line, and after that import (use) lines.  Perl’s are mostly optional – for sysadmin stuff you’re usually just doing your boilerplate strict and warnings.  Of course, even that is optional.  Technically anyway.  For python, you need to import something to do absolutely anything.   Which is okay – it shows you what is being used.

Then on to the real work.  In perl, you start out with the program.  It’s right there.  If you want to see the logic, just open the file – it’s usually at the top.  Python is the opposite – you have to declare your objects and functions higher up in the file before you can use them.   I couldn’t say you have to declare them before you use them because in practice you’re coding along and think “hey, this should be a function” and zoom down a bit and add it, then go back to the logic.  You’re still doing them before.

So you have your listing of objects and functions somewhere, and the actual program logic somewhere.  But this shows one difference between the two.

Perl cares about doing things.  Python cares about defining things.

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=61 3
Bundled mysql inserts http://www.imaginarybillboards.com/?p=50 http://www.imaginarybillboards.com/?p=50#comments Wed, 12 Aug 2009 21:53:12 +0000 http://www.imaginarybillboards.com/?p=50 I often “bundle” my mysql inserts – instead of doing one at a time, I’ll do 5,000 for example. (Or more usually, do a user-specified number at a time). The only trick is remembering to do any leftovers at the end. Here’s the code:

my  $count=0;
my $max_inserts = 15000;
my @inserts=();
my $printed_example=0;  #will be 1 when we print an example of the insert;
my $insert_sql = "insert into some_table (col1,col2,col,etc) values ";
while(my @things=$sth->fetchrow_array())
{
    $count++;
    my $bigline="('".join("','",@things)."')";
    push(@inserts,$bigline);
    #flush the @inserts after 1k (or whatever) rows get pushed onto it
    if(scalar(@inserts)>$max_inserts)
    {
         $dbh->do($insert_sql.join(",",@inserts))
            or die "Couldn't insert: $!\n";
        @inserts=();       #empty back out the array.
    }
}
#don't forget to insert any leftovers :)
$dbh->do($insert_sql.join(",",@inserts)) if scalar(@inserts);
@inserts=();

What it’s doing: Getting a bunch of rows from a database (or whatever). While it’s looping through the giant list it gets, it’s pushing part of an insert statement onto an array. Basically, the back half of an insert statement. Once that array gets big enough, it “flushes” it into the database and empties it out again. Finally, after it’s done looping through the giant list, it “flushes” any left over. I find this is faster than preparing and executing one at a time by a factor of 10 to 50. Must do some number crunching soon…

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=50 2
How I pass parameters to my programs in perl http://www.imaginarybillboards.com/?p=42 http://www.imaginarybillboards.com/?p=42#comments Tue, 04 Aug 2009 16:00:47 +0000 http://www.imaginarybillboards.com/?p=42 I often want to change what a program does with parameters.  Anything from changing a date (very very common) to a log location, to email addresses, etc.  Combined with another favorite unix command line trick, it’s super easy.

Just a couple of notes here – I don’t like the usual unix-style for some reason.  I’m not going to remember that -d is debug, and that -a <email address> is email address.  Plus, one of the problems with programmers is that the first way we learn to do something is the way we’ll do it forever.  When I started with cgi, we did the full “my $cgi = new CGI; my $thing=$cgi->param(‘thing’)”.  You *can* do  just the standara param(‘thing’) but then you have to use “use CGI qw/:standard/;” which I can never remember.  No big deal either way.

So here goes.  For this one, I have a program that gets a bunch of stuff from a bunch of machines and does some manipulation of the data.  I want to be able to limit the machines it goes to, whether or not debug is on, how many threads, how many concurrent inserts, where it logs, and the date it runs for.  (assuming it gets the list of machines from a DB if not specified).

perl loader.pl host=all_hosts threads=10 inserts=15000 logfile=~/logs/`date +\%y-\%m-\%d` debug=0 date=`date +\%y-\%m-\%d`

And the code that runs:

#!/usr/bin/env  perl
use CGI;
my $cgi = new CGI;
my $date = $cgi->param('date') || `date +\%y-\%m-\%d`; chomp($date); #gives a default, with no newline
my $debug = $cgi->param('debug') || 0;
my $host = $cgi->param('host') || usage();  # you have to pass at least one!
my @hosts = $host eq 'all_hosts' ? all_hosts() : split(',',$host);   #ternary test, gets a list, depending on what's passed
my $threads = $cgi->param('threads') || 10;
my $inserts = $cgi->param('inserts') || 15000;
my $logfile = $cgi->param('logfile') || "~/logs/$date";

#do something
foreach my $hostname(@hosts)
{
  #get some data and insert it, log, etc.
}

sub usage()
{
  print "Usage: perl loader.pl host= [threads=10 inserts=15000 logfile=<logfile> debug=1 date=<YYYY-MM-DD>]\n";
  exit();
}

While somewhat on the subject, that date hack is a great one to remember. A lot of the time you want to be explicit about the date to run for. Alternatively, I have a lot of programs I want to run for yesterday. It’s almost as simple.

`date +\%Y-\%m-\%d --date='1 days ago'`

The above line returns the date in YYYY-MM-DD format for yesterday. That’s it! Put it into a cron job the next morning for yesterday and look cool to those windows guys.

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=42 2
Passing parameters by name with perl, plus easier emailing. http://www.imaginarybillboards.com/?p=29 http://www.imaginarybillboards.com/?p=29#respond Thu, 30 Jul 2009 15:41:30 +0000 http://www.imaginarybillboards.com/?p=29 One of the advantages of python et al is that instead of taking parameters in order, you can pass them by name.  In python, this is done using (by convention) the following notation:

def myfunction(self,*args,**kwargs):


param1 = kwargs['param1']
param2 = kwargs['param2']


etc...
mything=myfunction(param1=something, param2=something2)



I can do the same thing in perl with just a tiny bit of extra work. – This is how I actually usually send emails in a program, for example.

package include;
use MIME::Lite;
sub send_email()
{


my $ref = shift || return;
my %pass = %$ref; #this converts it to a hash - broken out for clarity
#from here out, we can just:
my $subj=$pass{'subject'};
my $body=$pass{'body'};
my $file=$pass{'file'};
my $to =$pass{'to'};
my $from=$pass{'from'};
my $debug = $pass{'debug'} || 0;

my $msg=MIME::Lite->new(


To => $to,
From => $from,
Subject => $subj,
Type => 'multipart/mixed'


) or die ("Couldn't create multipart email: $!\n");
$msg->attach(


Type => 'TEXT',
Data => $body


) or die("Couldn't attach the text part: $!\n");
my @filelist=();
@filelist=split(",",$file) if $file;
foreach my $filename(@filelist)
{


print "Attaching file $filename\n" if $debug;
my $suffix=( split(/\./,$filename) )[-1];
if($suffix eq 'png' or $suffix eq 'jpg' or $suffix eq 'gif' or $suffix eq 'jpeg')
{$suffix="image/$suffix";}
else
{
$suffix="appliation/$suffix";
}
$msg->attach(


Type => $suffix,
Path => $filename,
Filename=> $filename,
Disposition=>'attachment'


) or die("Couldn't attach file attachment: $!\n");


}
MIME::Lite->send('smtp','smtp_hostname')
$msg->send


or die("Couldn't send message: $!\n");


}

#usage:
&include::send_email({


subject =>"My email",
to =>$mailto,
from =>'someone@somewhere',
body => $msg_body,
file => join(",",@attachments),


});

So, this is in my include module (as seen in the usage) that other programs import. From then on it’s just a matter of a few lines to send emails, and no remembering the position of the arguments either. This is very similar to how I like to pass paramters to a program using CGI.

The other nice part of this is it’s guaranteed.  No importing another module, having to use an object, etc.

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=29 0
How I return sql in perl http://www.imaginarybillboards.com/?p=26 http://www.imaginarybillboards.com/?p=26#respond Wed, 15 Jul 2009 14:32:56 +0000 http://www.imaginarybillboards.com/?p=26 I often don’t want to instantiate a whole dbi stack just for some quick work.  So in the include module I tend to haul around, there’s a “return_sql” function.  It takes 5 or 6 arguments (the last being an optional debug): the sql statement itself, db,host,user,pass in that order.  After that, it will execute the sql.  Fun use:  if there’s only one row returned, it just returns that one as a scalar – otherwise it returns an array of comma-seperated values (like I said, this is for small quick stuff).

sub  return_sql()
{
    my $sql=shift || return;  #the or is super useful for this!
    my $db=shift || return;
    my $host=shift || '';
    my $user=shift || '';
    my $pass=shift || '';
    my $debug=shift || 0;  #for optional debugging, default is 0
    print "SQL=$sql\n" if $debug;
    #from here I (depending on the host) either use the dbi, or simply echo to mysql's path and get the result
    my $dbh=DBI->connect("DBI:mysql:$db:$host",$user,$pass)
            or die "Couldn't connect to $db:$host,$user: $!\n";
    my $sth=$dbh->prepare($sql)
            or warn "Couldn't prepare sql: $!\n";
    $sth->execute()
            or warn "Couldn't execute sql\n$sql\nReason: $!\n";
    my @ret_ary=();
    #could do this a bunch of other ways, but this is really really easy to explain.  :)
    #while you're fetching a row (i.e. for each row you get) that's put into @val
    #join it into a temp line seperated by commas, and push that onto an array
    while( my @val=$sth->fetchrow_array()){push(@ret_ary,join(",",@val));}
    #then, if there's only one row returned (if the length of the new array is 1), return only it
    return $ret_ary[0] if scalar(@ret_ary)==1;
    #otherwise, return the whole array and use away!
    return @ret_ary;
}

Use in practice:

use include;
my @db=('db','host','user','pass',$debug); #debug being 0 or non-0 :)
#first, let's try just one row
my $name=&include::return_sql("select name from mytable limit 1",@db);
#then, let's get a list
my @names=&include::return_sql("select name from mytable where 1",@db);
#a little more complicated
foreach my $row(&include::return_sql("select name,id from mytable where 1",@db))
{
  my ($name,$id)=split(",",$row);
  print "name=$name,id=$id\n";
}

And that’s my useful snippet for the day!

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=26 0
Perl super-easy parallelization with threadeach http://www.imaginarybillboards.com/?p=24 http://www.imaginarybillboards.com/?p=24#respond Mon, 08 Dec 2008 04:04:08 +0000 http://www.imaginarybillboards.com/?p=24 I’ve been thinking about a good way to make perl more parallelize-able. The thing that keeps coming to my mind is that it should be so easy that you wouldn’t even think about it. Lots of the time in sysadmin-land, you have to just do a ton of things completely identically to a bunch of things. Examples from just the last week at work.

For each thing in a list, connect to its database, get x data, do some analysis on that.

For each server in a list, connect to it and so something. Push a file, get a file, run a command, etc.

For each ip/port in a list, open a socket and listen for x time, then return the results.

So, what to use? I just like the name threadeach(). Normally, in perl, you do this

foreach  my $thing(@list_of_things){... do something }

It’d be nice if you knew this was easily done in parallel, to do it like this:

threadeach my $thing(@list_of_things){function to be performed on each thing}

Right now, you can *sort of* do the same thing with a little work. I’ve got a threadeach module like this I’ve been using.

Threadeach

I whipped up a module for it with three functions in it.

  • threadeach(\&subroutine,@array) #will parallelize, running  (number of cpu cores) threads at a time
  • threadall(\&subroutine,@array) # will parallelize all at once!!!  Kind of crazy but fun actually
  • threadsome(\&subroutine,<num to run>,@array); #will parallelize the number passed of threads at a time

It’s also got another trick in that it waits for them all to be done and then returns the “return” values in order.  A lot of the time, I do a foreach and print something, in this case I can just return what I’d have printed before and print it at the end.  print threadeach(\&sub,@things);

I’ve been using it in my check_network script that looks at things in a given subnet and it works pretty well.  I just had to change the line from foreach my $ip(0..255){…} to threadeach(\&…,0..255);sub {…}  And instead of printing inside, I return the printed value (as stated above).  It’s been working really well in this limited case, I have to try it more on other things, but don’t see why it wouldn’t work fine.  But since this script does an nmap against the host, it uses a good bit of CPU – I tried using threadall() and it almost hung the machine – 255 nmap processes at once will do that.

Timing

Running original version: sudo time perl check_network.pl 192.168.200.0 -> 524.71 real 76.91 user 26.39 sys

Running threadeach version: sudo time perl threaded_check_network.pl 192.168.200.0 -> 189.95 real 77.31 user 28.48 sys

Roughly 1/3 the time.  Which makes sense, because no matter how long one of the machines takes to do, it’s added in to the rest for the original version, and can be “worked around” in the parallel version.  For my example, for some reason the .107 box takes several minutes ( I skipped it in this test) to run – but even not counting that one, there are some that are almost instant(the down boxes) and some that take longer.

How it works

Not counting the deciding how many to run at a time (which depends on how it’s called) – that just tries to get the number of cpus on the machine, and if it can’t, returns an arbitrary number (currently 8), it’s fairly straightforward.  Set up an empty hash to keep track of thread ID vs index, an index variable to keep track of where we are at with the list, and finally an empty array to store anything being returned.

Main loop:  As long  as there are:

  • Threads working
  • Threads done and waiting to return
  • or more things to do

Do:

  • Get the return values of any threads waiting to give them back. (puts the return value of the thread into the return array corresponding to the slot that it was passed originally)
  • launches more threads, until there are either no more left or until it has reached the max number
  • When launching those threads, it puts the value of the index (id corresponding to the slot of original array) into the value side of a hash where the key is the thread ID
  • sleep for one second.

And at the end, returns the @return array.  The @return isn’t strictly necessary if it’s supposed to be a foreach replacement, but works really well for where it’s useful.  The sleep(1); isn’t strictly necessary either, but 1- if you’re doing a bunch of threads, waiting a second at a time isn’t a huge deal, and 2- otherwise it pegs the CPU just doing a tight while loop checking on thread status.

In the future…

Figure out how to make it work as a drop-in replacement for foreach. Calling it as a function seems so hack-ish.  A better way to decide how many threads to call (if Sys::CPU doesn’t work).  Was thinking about the year – 2005, so the number would increase.  Or could just require Sys::CPU…  Could also make sure whatever is in the main block is thread-safe, but should probably just trust the user.  In the meantime, I’m going to use it for a little bit and bang against it on a few systems before throwing it out into the cruel, cold world.

It may also be cool if it can buffer I/O so that for some things it really does act just like foreach, too.

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=24 0
Another insane perl snippet http://www.imaginarybillboards.com/?p=25 http://www.imaginarybillboards.com/?p=25#respond Wed, 03 Dec 2008 20:55:09 +0000 http://www.imaginarybillboards.com/?p=25 This finds out whether an ip address is within a certain range.

example:

between(“192.168.1.29″,”192.168.1.1″,”192.168.1.99”); returns true

between(“192.168.1.29″,”10.1.1.1″,”10.1.1.254”); returns false

sub between
{
my ($tgt,$small,$big)=@_;
if($tgt!~m/\./)
{
if($tgt >= $small and $tgt <= $big){return 1;}
else{return 0;}
}
my @tg=split(/\./,$tgt); my $t=shift(@tg); $tgt=join(‘.’,@tg);
my @sm=split(/\./,$small); my $s=shift(@sm); $small=join(‘.’,@sm);
my @bg=split(/\./,$big); my $b=shift(@bg); $big=join(‘.’,@bg);
if($t!=$s or $t!=$b){return 0;}
else{return &between($tgt,$small,$big);}
}

Recursion is fun!

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=25 0
XKCD menu problem http://www.imaginarybillboards.com/?p=19 http://www.imaginarybillboards.com/?p=19#respond Thu, 22 May 2008 02:10:15 +0000 http://www.imaginarybillboards.com/?p=19 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 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. 🙂 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:


#!/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;
}

]]>
http://www.imaginarybillboards.com/?feed=rss2&p=19 0