Archive for September 2014

## Software update

(I have been waiting a while to post this picture, it seemed like a good idea to do it today what with the huge flap about the iOS 8.0.1 software update failure…)

I think my computer is trying to tell me that there is a software update…

BTW, Happy Birthday to Justin Bruening, who played Michael Knight on the Knight Rider TV series from 2008.

## Cross a bridge at night

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;

namespace BridgeAtNight
{
public class BridgeState
{
public List peopleOnLeft;
public List peopleOnRight;
public int totalTime;
public string peopleMovement;

public BridgeState(int[] people)
{
totalTime = 0;
peopleMovement = "";
peopleOnLeft = new List(people);
peopleOnRight = new List();
}

public void MoveLeftToRight(int leftToRight1, int leftToRight2)
{
peopleMovement = peopleMovement + string.Format("{0}>> {1}>> ", leftToRight1, leftToRight2);
totalTime += Math.Max(leftToRight1, leftToRight2);

peopleOnRight.Sort();

peopleOnLeft.Remove(leftToRight1);
peopleOnLeft.Remove(leftToRight2);
}

public void MoveRightToLeft(int rightToLeft)
{
peopleMovement = peopleMovement + string.Format("{0}<< ", rightToLeft);
totalTime += 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 bestTimeResults = new List();
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();
}
else if (randomBridgeState.totalTime == bestTime)
{
if (!bestTimeResults.Contains(randomBridgeState.peopleMovement))
{
Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
}
}
}

Console.WriteLine("Press any key to exit the application");