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