#!/usr/local/bin/perl -w
@p = 0..3;
@w = ( 1, 2, 5, 10 );
$min=99999999;

INI: $it=0; $t=0; @s=(0,0,0,0); @M=();
for (;;){
    $it++;
    $x = int rand(@p);
    if ($it%2==1){ 
	$y = int rand(@p);
	while ($x==$y || $s[$x]+$s[$y]>0){
	    $x = int rand(@p);
	    $y = int rand(@p);
	}
	$t += $w[$y]>$w[$x] ? $w[$y] : $w[$x];
	$s[$x]=$s[$y]=1;
	$M[$it]= "Trip $it: travels ".($x+1)." ".($y+1)." ; time=$t\n";
    }else{
	while ($s[$x]==0){
	    $x = int rand(@p);
	}
	$t += $w[$x];
	$s[$x]=0;
	$M[$it]= "Trip $it: returns ".($x+1)." ; time=$t\n";
    }
    if ($s[0]+$s[1]+$s[2]+$s[3]==4 && $t<=$min){ 
	print "@M\nFinished. Time = $t\n";
	$min = $t;
	goto INI;
    }elsif ($s[0]+$s[1]+$s[2]+$s[3]==4){
	goto INI;
    }
}

__END__
From zebariah@gmail.com Sat Oct  9 11:16:29 2004
Date: 9 Oct 2004 02:16:29 -0700
From: zebariah <zebariah@gmail.com>
Newsgroups: rec.puzzles
Subject: NPR story; Solve the Equation, Get an Interview

I have a question about a problem I encountered on NPR.org.

The story link is here:
http://www.npr.org/templates/story/story.php?storyId=4078172

It is about companies (Microsoft, Google, etc) using math puzzles as a
screening tool for prospective employees. It had four web-only
questions and the fourth one is getting under my skin. Math is not my
strong suit and questions like this drive me crazy, but I always try
them anyway. This one is especially distressing because there is no
answer available! It's 2:15 am and I need to sleep! Anyway, if anyone
could provide me with the correct answer I would appreciate it.

There are 4 women who want to cross a bridge. They all begin on the
same side. You have 17 minutes to get all of them across to the other
side.
It is night. There is one flashlight. A maximum of two people can
cross at one time. Any party who crosses, either 1 or 2 people, must
have the flashlight with them. The flashlight must be walked back and
forth, it cannot be thrown, etc. Each woman walks at a different
speed. A pair must walk together at the rate of the slower woman's
pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross
For example, if Woman 1 and Woman 4 walk across first, 10 minutes have
elapsed when they get to the other side of the bridge. If Woman 4 then
returns with the flashlight, a total of 20 minutes have passed and you
have failed the mission.
What is the order required to get all women across in 17 minutes?

The best I can do is 19... Thanks!