Ponder This Sept 2016: permutations, DFS and an aggressive tree trimmer

IBM has a nice monthly programming challenge called IBM Ponder This. If you solve the challenge, you get your name stamped on their page. That's all. Some of the challenges are purely mathematical. Others are purely algorithmic. During the month of September 2016 they released a very nice problem which you can read here: http://www.research.ibm.com/haifa/ponderthis/challenges/September2016.html

The solution requires a couple of interesting steps:

• Build a simple permutation function (not necessarily needed, you can do the first step to come up with the 4-people permutation by hand. The good thing though is that this would be a good training for he main algorithm)
• Do a simple DFS generating all the possibilities but not repeating any configuration (which cuts down the tree already)
• During the DFS calculate the current local penalty
• Finally, the most important step: trim aggressively by returning right away as soon as the current penalty goes over the best penalty thus far

In few seconds you get your answer:

Code below - cheers! Marcelo

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

namespace PonderThisSept2016
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] seats = ArrayOfPermutations("ABCD");
            string[] bestConfiguration = new string[seats.Length];
            string[] currentConfiguration = new string[seats.Length];
            int penaltyBestConfiguration = Int32.MaxValue;
            Hashtable htSeatsUsed = new Hashtable();

            CalculateBestConfiguration(seats,
                                       htSeatsUsed,
                                       currentConfiguration,
                                       0,
                                       0,
                                       bestConfiguration,
                                       ref penaltyBestConfiguration);

            Console.WriteLine();
            Console.WriteLine("Solution :)");
            Console.WriteLine();

            PrintConfiguration(bestConfiguration, penaltyBestConfiguration);
        }

        static void PrintConfiguration(string[] configuration,
                                       int penalty)
        {
            for (int i = 0; i < configuration[0].Length; i++)
            {
                for (int j = 0; j < configuration.Length; j++)
                {
                    Console.Write("{0}", configuration[j][i]);
                }
                Console.WriteLine();
            }

            Console.WriteLine();
            Console.WriteLine("Penalty: {0}", penalty);
            Console.WriteLine();
            Console.WriteLine("-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=");
        }

        static void CalculateBestConfiguration(string[] seats,
                                               Hashtable htSeatsUsed,
                                               string[] currentConfiguration,
                                               int currentIndexConfiguration,
                                               int currentPenalty,
                                               string[] bestConfiguration,
                                               ref int penaltyBestConfiguration)
        {
            //Trimming down the searh
            if (currentPenalty >= penaltyBestConfiguration)
            {
                return;
            }

            if (currentIndexConfiguration == seats.Length)
            {
                if (currentPenalty < penaltyBestConfiguration)
                {
                    penaltyBestConfiguration = currentPenalty;
                    for (int i = 0; i < currentIndexConfiguration; i++)
                    {
                        bestConfiguration[i] = currentConfiguration[i];
                    }

                    PrintConfiguration(bestConfiguration, penaltyBestConfiguration);
                }
                return;
            }

            for (int i = 0; i < seats.Length; i++)
            {
                if (!htSeatsUsed.ContainsKey(seats[i]))
                {
                    htSeatsUsed.Add(seats[i], true);
                    currentConfiguration[currentIndexConfiguration] = seats[i];

                    int localPenalty = 0;
                    for (int j = 0; j < currentConfiguration[0].Length; j++)
                    {
                        for (int pi = 1; pi < 3; pi++)
                        {
                            if (currentIndexConfiguration - pi >= 0 &&
                                currentConfiguration[currentIndexConfiguration][j] == currentConfiguration[currentIndexConfiguration - pi][j])
                            {
                                localPenalty++;
                            }
                        }
                    }

                    CalculateBestConfiguration(seats,
                                               htSeatsUsed,
                                               currentConfiguration,
                                               currentIndexConfiguration + 1,
                                               currentPenalty + localPenalty,
                                               bestConfiguration,
                                               ref penaltyBestConfiguration);

                    htSeatsUsed.Remove(seats[i]);
                }
            }
        }

        static string[] ArrayOfPermutations(string letters)
        {
            LinkedList<string> list = new LinkedList<string>();

            Permutation(letters, "", list);

            return list.ToArray<string>();
        }

        static void Permutation(string letters,
                                string current,
                                LinkedList<string> list)
        {
            if (current.Length == letters.Length)
            {
                list.AddLast(current);
                return;
            }

            for (int i = 0; i < letters.Length; i++)
            {
                if (!current.Contains(letters[i]))
                {
                    Permutation(letters, 
                                current + letters[i].ToString(),
                                list);
                }
            }
        }
    }
}