OK, here is a scenario. Four people on a journey together need to cross a bridge at night as quickly as possible. Among the four of them, they have one flashlight. They cannot continue their journey until all four reach the other side together. Since the bridge is narrow and slippery, and it is pitch black out being night and all, they decide to have two people cross with the flashlight, then one person returns with the flashlight back to the original side, and they continue until everyone is on the other side.
Oh, and also, the people can all walk at different paces, so when two people cross together, it takes them the amount of time that it takes the slower person to cover the distance.
For example, let’s say that the four people that need to cross can cover the distance of the bridge in 1 minute, 2 minutes, 5 minutes, and 10 minutes. What would be the shortest possible time?
The naive solution would be to have the 1 minute person be the primary flashlight runner and send them with the 2 minute person, return, then the 5 minute person, return, and finally cross with the 10 minute person, for a grand total of 19 minutes.
Now of course this is not the optimal solution, but more on that in a minute.
So how would we design an algorithm to solve this problem? Conventional wisdom says to create some kind of tree where you iterate through all of the possible combinations of initial crossings, then off those branches, combinations of reverse crossings, etc. Then once the tree is built, you can walk to all the branch tips and calculate the times, and then just display the shortest time.
But why do something logical? With all this computing power, I say that we implement my favorite algorithm for producing solutions to problems… The Monte Carlo method.
Here is the code for a C# .NET console app I threw together to solve this issue:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BridgeAtNight
{
public class BridgeState
{
public List<int> peopleOnLeft;
public List<int> peopleOnRight;
public int totalTime;
public string peopleMovement;
public BridgeState(int[] people)
{
totalTime = 0;
peopleMovement = "";
peopleOnLeft = new List<int>(people);
peopleOnRight = new List<int>();
}
public void MoveLeftToRight(int leftToRight1, int leftToRight2)
{
peopleMovement = peopleMovement + string.Format("{0}>> {1}>> ", leftToRight1, leftToRight2);
totalTime += Math.Max(leftToRight1, leftToRight2);
peopleOnRight.Add(leftToRight1);
peopleOnRight.Add(leftToRight2);
peopleOnRight.Sort();
peopleOnLeft.Remove(leftToRight1);
peopleOnLeft.Remove(leftToRight2);
}
public void MoveRightToLeft(int rightToLeft)
{
peopleMovement = peopleMovement + string.Format("{0}<< ", rightToLeft);
totalTime += rightToLeft;
peopleOnLeft.Add(rightToLeft);
peopleOnLeft.Sort();
peopleOnRight.Remove(rightToLeft);
}
public void SolveWithNaivete()
{
peopleOnLeft.Sort();
while (peopleOnLeft.Count > 1)
{
// move 2 people from the left to the right
int leftToRight1 = peopleOnLeft[0];
int leftToRight2 = peopleOnLeft[1];
MoveLeftToRight(leftToRight1, leftToRight2);
// move 1 person from right to left if there are any remaining people on the left
if (peopleOnLeft.Count > 0)
{
int rightToLeft = peopleOnRight[0];
MoveRightToLeft(rightToLeft);
}
}
Console.WriteLine("Solution with naivete:");
Console.WriteLine(string.Format("Time: {0} minutes", totalTime));
Console.WriteLine(string.Format("Sequence: {0}", peopleMovement));
}
public void SolveRandomly()
{
Random rnd = new Random();
while (peopleOnLeft.Count > 1)
{
// move 2 people from the left to the right
var leftToRightRandom = peopleOnLeft.OrderBy(x => rnd.Next()).Take(2).ToList();
int leftToRight1 = leftToRightRandom[0];
int leftToRight2 = leftToRightRandom[1];
MoveLeftToRight(leftToRight1, leftToRight2);
// move 1 person from right to left if there are any remaining people on the left
if (peopleOnLeft.Count > 0)
{
var rightToLeftRandom = peopleOnRight.OrderBy(x => rnd.Next()).Take(1).ToList();
int rightToLeft = rightToLeftRandom[0];
MoveRightToLeft(rightToLeft);
}
}
}
}
class Program
{
static void Main(string[] args)
{
BridgeState naiveBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 });
naiveBridgeState.SolveWithNaivete();
List<string> bestTimeResults = new List<string>();
int bestTime = 999999;
for (int idx = 1; idx < 1000000; idx++)
{
BridgeState randomBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 });
randomBridgeState.SolveRandomly();
if (randomBridgeState.totalTime < bestTime)
{
Console.WriteLine(string.Format("Better random solution found in pass {0}:", idx));
Console.WriteLine(string.Format("Time: {0} minutes", randomBridgeState.totalTime));
Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
bestTime = randomBridgeState.totalTime;
bestTimeResults = new List<string>();
bestTimeResults.Add(randomBridgeState.peopleMovement);
}
else if (randomBridgeState.totalTime == bestTime)
{
if (!bestTimeResults.Contains(randomBridgeState.peopleMovement))
{
Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
bestTimeResults.Add(randomBridgeState.peopleMovement);
}
}
}
Console.WriteLine("Press any key to exit the application");
Console.ReadKey();
}
}
} |
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BridgeAtNight
{
public class BridgeState
{
public List<int> peopleOnLeft;
public List<int> peopleOnRight;
public int totalTime;
public string peopleMovement;
public BridgeState(int[] people)
{
totalTime = 0;
peopleMovement = "";
peopleOnLeft = new List<int>(people);
peopleOnRight = new List<int>();
}
public void MoveLeftToRight(int leftToRight1, int leftToRight2)
{
peopleMovement = peopleMovement + string.Format("{0}>> {1}>> ", leftToRight1, leftToRight2);
totalTime += Math.Max(leftToRight1, leftToRight2);
peopleOnRight.Add(leftToRight1);
peopleOnRight.Add(leftToRight2);
peopleOnRight.Sort();
peopleOnLeft.Remove(leftToRight1);
peopleOnLeft.Remove(leftToRight2);
}
public void MoveRightToLeft(int rightToLeft)
{
peopleMovement = peopleMovement + string.Format("{0}<< ", rightToLeft);
totalTime += rightToLeft;
peopleOnLeft.Add(rightToLeft);
peopleOnLeft.Sort();
peopleOnRight.Remove(rightToLeft);
}
public void SolveWithNaivete()
{
peopleOnLeft.Sort();
while (peopleOnLeft.Count > 1)
{
// move 2 people from the left to the right
int leftToRight1 = peopleOnLeft[0];
int leftToRight2 = peopleOnLeft[1];
MoveLeftToRight(leftToRight1, leftToRight2);
// move 1 person from right to left if there are any remaining people on the left
if (peopleOnLeft.Count > 0)
{
int rightToLeft = peopleOnRight[0];
MoveRightToLeft(rightToLeft);
}
}
Console.WriteLine("Solution with naivete:");
Console.WriteLine(string.Format("Time: {0} minutes", totalTime));
Console.WriteLine(string.Format("Sequence: {0}", peopleMovement));
}
public void SolveRandomly()
{
Random rnd = new Random();
while (peopleOnLeft.Count > 1)
{
// move 2 people from the left to the right
var leftToRightRandom = peopleOnLeft.OrderBy(x => rnd.Next()).Take(2).ToList();
int leftToRight1 = leftToRightRandom[0];
int leftToRight2 = leftToRightRandom[1];
MoveLeftToRight(leftToRight1, leftToRight2);
// move 1 person from right to left if there are any remaining people on the left
if (peopleOnLeft.Count > 0)
{
var rightToLeftRandom = peopleOnRight.OrderBy(x => rnd.Next()).Take(1).ToList();
int rightToLeft = rightToLeftRandom[0];
MoveRightToLeft(rightToLeft);
}
}
}
}
class Program
{
static void Main(string[] args)
{
BridgeState naiveBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 });
naiveBridgeState.SolveWithNaivete();
List<string> bestTimeResults = new List<string>();
int bestTime = 999999;
for (int idx = 1; idx < 1000000; idx++)
{
BridgeState randomBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 });
randomBridgeState.SolveRandomly();
if (randomBridgeState.totalTime < bestTime)
{
Console.WriteLine(string.Format("Better random solution found in pass {0}:", idx));
Console.WriteLine(string.Format("Time: {0} minutes", randomBridgeState.totalTime));
Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
bestTime = randomBridgeState.totalTime;
bestTimeResults = new List<string>();
bestTimeResults.Add(randomBridgeState.peopleMovement);
}
else if (randomBridgeState.totalTime == bestTime)
{
if (!bestTimeResults.Contains(randomBridgeState.peopleMovement))
{
Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
bestTimeResults.Add(randomBridgeState.peopleMovement);
}
}
}
Console.WriteLine("Press any key to exit the application");
Console.ReadKey();
}
}
}
There are undoubtedly some optimizations I can make to this code above, such as ordering the times in the MoveLeftToRight function. However, I was kind of surprised to see this run, as sometimes the optimal solution of 17 minutes was found in the first few thousand random walk throughs, and other times it would take a few hundred thousand walk throughs before the 17 minute solution was found. To me, it did not seem like there were enough different combinations that would make it so difficult to randomly find the solution.
For those who cannot/will not run this code, the crux of the biscuit, given the times of the walkers above (1 minute, 2 minutes, 5 minutes, and 10 minutes), is to send the slowest people across together once there is someone faster on the other side. Or in other words, first send 1 and 2 across, then have 1 come back. Then, send 5 and 10 across, and have 2 come back. Then 1 and 2 make the final crossing.
BTW, Happy Talk Like A Pirate Day today.