#!/usr/local/bin/perl -w

use Algorithm::FastPermute ('permute');
 
@order = ( 0, 1, 2, 3, 4, 5, 6, 7 );
@names = (Agravain, Bors, Caradoc, Dagonet, Ector, Feirefiz, Gareth, Hatty);   
@t  = (    1 ,     1,      2,      2,        3,          4,      5,     6);
@trec = (  15,       5,      15,     5,      10,      15,     10,      5); 
$tlimit = 20;

%hash=();
permute {
    $totaltime1=0;
    @a=();
    @tinit=();
    for (@order){                # I suppose that liberation takes acumulated time
	$a[$_]=1;
	if ($totaltime1+$t[$_]+$trec[$_]>$tlimit) { $a[$_]=0; }
	else{
	    $tinit[$_] = $totaltime1;
	    $totaltime1 += $t[$_];
	}
    }
    $maxtt=0;
    @tt=();
    for (@order){
	if ($a[$_]==1) { 
	    $tt[$_] = $tinit[$_]+$t[$_]+$trec[$_];  # I suppose than concurrent washing
	    if ($tt[$_]>$tlimit) { $a[$_]=0; }
	    elsif ($tt[$_] > $maxtt) { $maxtt = $tt[$_]; }   # therefore MAX is the time
	}
    }
    $totaltime2 = $maxtt;
    if ($totaltime2<=$tlimit) { 
	$numlib=0;
	for (@order){
	    if ($a[$_]==1 && $tt[$_]<=$tlimit ) { $numlib++; }
	}
	if ($numlib>=$NUM){
	    $NUM=$numlib;
#	    print "@order - $totaltime1 $totaltime2 - $NUM liberated\n";
	    $str="";
	    for (@order){
#		print "$_ " if ($a[$_]==1);
		if ($a[$_]==1){
		    $str .= $_;
		}
	    }
	    $hash{$str}=$NUM;
#	    print " - $totaltime1 $totaltime2 - $NUM liberated\n";
	}
    }
}@order;

open OUT, ">ver" or die "Cannot open ver";
for $i (keys %hash){
    print OUT "$hash{$i} ";
    @j = split "", $i;
    for (@j){
	print OUT "$names[$_] ";
    }
    print OUT "\n";
}
close OUT;


__END__

From martin.chlond@btinternet.com Sat Apr  6 01:30:47 2002
Date: Fri, 5 Apr 2002 19:09:21 +0000 (UTC)
From: Martin <martin.chlond@btinternet.com>
Newsgroups: sci.op-research
Subject: Something for the weekend sir? (An IP puzzle)

The puzzle that follows was taken from 'Mathematical Puzzles in Fantasy
Games' by Jonathan R. Partington to be found at
http://amsta.leeds.ac.uk/~pmt6jrp/personal/tms.html.

"Finally, a puzzle that is mathematically quite intricate - a scheduling
problem from Sangraal. This occurs in the endgame, when the Sangraal (Holy
Grail) is almost won. You arrive at the castle where the Foul Fiend has
imprisoned 8 knights. These are as follows:

Agravain - lightly bound - badly wounded;
Bors - lightly bound - scratched;
Caradoc - bound a bit more - badly wounded;
Dagonet - bound as C - scratched;
Ector - bound and gagged - somewhat wounded;
Feirefiz - in chains - badly wounded;
Gareth - in chains and gagged - somewhat wounded;
Harry - bound really tight in chains (poor chap) - scratched.

Here the state of binding means that it will take 1, 1, 2, 2, 3, 4, 5 and 6
minutes (respectively) to free them: a freed knight then goes away to wash
and recover himself physically in time for the Sangraal's arrival. The time
he takes for this second stage is 5, 10 or 15 minutes, according to injury.
In twenty minutes' time the sun will set and the Sangraal will arrive. How
many knights can you bring? We see, for example that if you want F, you must
free him almost at once, as he can only be ready in 19 minutes at the
earliest. Freeing Harry, though it takes 6 minutes, is not urgent, as he
only needs to be freed by the 15th minute. This sort of puzzle has standard
algorithms for solving it, but it is at least a bit more interesting than
the average optimization exercise!"

The puzzle may be solved quite easily using brute force but nevertheless
presents an interesting little IP formulation.

You may use it to help you keep off the booze over the weekend

All the best

Martin