Archive for July, 2010

Uncategorized

Two Man Money Grab

Problem: Say you and your mate Gordon are playing a game called 2-Man Money Grab. In front of you are n bags of money lined up in an orderly fashion. You both know exactly how much is in each bag. The game goes as follows: each player in turn can pick a single bag from either end. Players alternate picking a bag and the person with the most money when all bags are chosen (there are an even number of bags) wins. You get to go first. What is your strategy?

Solution: This problem can be solved using dynamic programming because it exhibits the classic traits of optimal substructure and overlapping sub-problems. To see this let's first define some terminology.

Let mi = the amount of money in the bag in position i
Let M[i,j] = the maximum amount of money you can win from the bags in position i through j inclusive.

Now faced with a choice from the range [i,j], per the rules of the game, you can only select the bag of money in position i or position j. Once you do this, and assuming Gordon isn't a dumb ass, he's going to make an optimal selection based on the remaining items, either [i+1,j] or [i,j-1]. Thus the amount of money you'd collect would be equal to the sum of the money available in this range less the money that Gordon made off with. We can express this algebraically as follows:

when j>i, otherwise when i=j it follows that M[i,j] = M[i,i] = mi

This is a recurrence relationship. The solution for M[i,j] is expressed in terms of sub-problems. Thus, to solve the problem we need to pre-calculate all the "sigma" terms (the summations) then use these in the above formula using memoization to ensure that we don't repeat processing. This implies a run time complexity of O(N2) from the time required to compute the summations.

Here's some C# code to solve it:

private static int[,] _sum;
private static int[] _moneyBags;
private static int[,] _seen;
 
public static void Main(string[] args)
{
    _moneyBags = new[] {20, 11, 42, 13, 34, 5, 16, 27, 28, 25 };
    _sum = new int[_moneyBags.Length, _moneyBags.Length];
    _seen = new int[_moneyBags.Length, _moneyBags.Length];
 
    // initialise history table
    for (int i = 0; i < _moneyBags.Length; i++)
        for (int j = 0; j < _moneyBags.Length; j++)
            _seen[i, j] = -1;
 
    // find all summations
    for (int i = 0; i < _moneyBags.Length; i++)
    {
        int sum = 0;
        for (int j = i; j < _moneyBags.Length; j++)
        {
            sum += _moneyBags[j];
            _sum[i, j] = sum;
        }
    }
    var answer = BestSelection(0, _moneyBags.Length-1);
    Console.WriteLine( answer );
}
 
public static int BestSelection(int from, int to)
{
    if (_seen[from, to] != -1)
        return _seen[from, to];
 
    if (from == to)
        return _sum[from, to];
 
    var takeFirst = _sum[from,to] - BestSelection(from+1,to);
    var takeLast = _sum[from,to] - BestSelection(from,to-1);
 
    _seen[from, to] = takeFirst > takeLast ? takeFirst : takeLast;
    return _seen[from, to];
}

Uncategorized

The Mountain Climber Puzzle

Problem: On a weekend 2 young mountain climbers decided to climb and then descend a local mountain peak. Together they started off on Saturday morning and reached the peak Saturday night. They camped overnight on the summit and promptly started down the mountain on Sunday morning reaching their starting point Sunday afternoon. Prove that at some time of day they were at the exact same altitude on Saturday and Sunday. The two climbers always stay together.

Solutiuon: This isn't too difficult when you think it through. For any time t, let f(t) be the altitude of the climbers at time t on Sunday minus their altitude at the same time on Saturday. Now, as they climbers start their ascent on Saturday morning f(t) must be positive however, on Saturday night f(t) must be negative. Thus, by virtue of the intermediate value theorem, f(t) must be 0 at some point meaning that the climbers were at the same altitude on both Saturday and Sunday at some point in time. QED