2048

You may have seen or played this game on your nearest cell phone: http://en.wikipedia.org/wiki/2048_%28video_game%29. It is becoming a fever across geeks and addictive-games enthusiastic players across the world. IBM "Ponder This" of this month (April 2014) refers to this game, but instead of a 2D version of it, they came up with a simpler 1D version of it. Link is here: http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/April2014.html and here is the problem copied/pasted from their site:

"
Inspired by the viral 2048 game (http://en.wikipedia.org/wiki/2048_%28video_game%29) game, this month's question is a simpler one-dimensional version of it. Assume that random independent numbers, either 2 or 4 with a 50% chance each, come in from the right side of a bar with N slots. The numbers are always squeezed to the left and every time two adjacent numbers are the same - they are replaced by their sum. The game ends when all the N slots are occupied - and therefore there is no room for a new number.
What is the expected maximum number in the array when the game ends?
When N=1, the game ends after one round, leaving either 2 or 4 with the same probability and hence the average is 3.
When N=2, the game can reach 8 (for example, when the input is 2, 2, 4, 2, and the result is 8, 2), but can also be stuck with a 4 (such as when the input is 2, 2, 2, and the result is 4, 2).
Computing the average we get 5.5, or 11/2.

What is the average when N=5? Express this value as a quotient of two coprime integers.
"

Usually the "Ponder This" challenges are not very friendly, but this one seemed to me not that bizarre, so I decided to give it a shot. Of course, using C#, not pencil-n-paper. There are a couple of aspects with this problem:

1) It is a simulation. We need to simulate the numbers coming, merging, and so on
2) It is OK to simulate. We're dealing with only two incoming numbers (2 and 4)
3) It must be recursive

The idea of the solution is simple: keep the incoming numbers coming, keep merging them whenever applicable, whenever the incoming numbers come make sure to bring them with their corresponding probability (which is easy because it will always be 1/2, 1/4, 1/8....), whenever the slots are full, do some simple calculation to tally the probabilities for the largest number in the slot (and keep track of the largest number in the slot). At the end, compute the average number by going thru the hashtable with the largest numbers and their probabilities, multiplying them together, and adding the results up. Takes ~6min to run for N=5. Code is below:

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Collections;

namespace PonderThisApril2014
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("-=-=-= Time Before: {0} -=-=-=", DateTime.Now);
            Hashtable htCount = new Hashtable();
            int N = 5;
            int[] slots = new int[N];
            int nSlots = -1;
            GenerateAllVariations(slots,
                                  Int32.MinValue,
                                  nSlots,
                                  N,
                                  -1 /*init*/,
                                  1,
                                  htCount);
 
            double solution = 0;
            foreach (int k in htCount.Keys)
            {
                solution += (k * (double)htCount[k]);
                Console.WriteLine("{0}: {1}", k, htCount[k]);
            }

            Console.WriteLine();

            Console.WriteLine("Solution (average number for N={0}): {1}", N, solution);

            Console.WriteLine("-=-=-= Time After: {0} -=-=-=", DateTime.Now);
        }

        static void GenerateAllVariations(int[] inputSlots, int maxNumberInSlot, int nSlots, int N, int incomingNumber, double probability, Hashtable htCount)

        {
            //Local slots
            int[] slots = (int[])inputSlots.Clone();

            //Base case
            if (nSlots >= N)
            {

                if(htCount.ContainsKey(maxNumberInSlot))
                {
                    htCount[maxNumberInSlot] = (double)htCount[maxNumberInSlot] + probability;
                }
                else
                {
                    htCount.Add(maxNumberInSlot, probability);
                }
                return;
            }

            //Current computation
            if (incomingNumber != -1)
            {
                if (incomingNumber > maxNumberInSlot)
                {
                    maxNumberInSlot = incomingNumber;
                }

                slots[nSlots] = incomingNumber;

                for (int i = nSlots - 1; i >= 0; i--)
                {
                    if (slots[i + 1] == slots[i])
                    {
                        slots[i] += slots[i + 1];
                        slots[i + 1] = 0;
                        nSlots--;

                        if (slots[i] > maxNumberInSlot)
                        {

                            maxNumberInSlot = slots[i];
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }

            //Induction
            for (int n = 2; n <= 4; n += 2)
            {
                GenerateAllVariations(slots,
                                      maxNumberInSlot,
                                      nSlots + 1,
                                      N,
                                      n,
                                      probability / 2,
                                      htCount);
            }

        }

    }
}