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

Uncategorized

Determine the Angle between the Clock Hands

Problem: You are given the time of day in HH:MM format. You need to write a program to return the angle formed between the hands of an analogue clock displaying the given time.

Solution: This is not all that difficult if you think about it. Lets consider each hand in isolation first. The minutes hand of the clock rotates 360 degrees in 60 minutes so each minute represents 6 degrees. The hours hand of the clock rotates 360 degrees in 12 hours so we know it moves a total of 30 degrees after each hour, but you need to factor in the advancement of the hours hand between hours. i.e. at 3:30 the minutes hand is on 6 and the hours hand has progressed past 3. We can calculate this advancement simply by (minutes/60) * 30 degrees which is equivalent to minutes/2.

So once we know the degrees of each hand we simply find the difference. Here's some simple C# code to show this:

        public static void Main()
        {
            int hour = 2;
            int minute = 45;

            double degrees = Math.Abs(((hour*30.0 + minute/2.0) - minute*6.0) % 360);

            Console.WriteLine( string.Format("Angle between clock hands = {0}",degrees) );
        }

Next »