Necessary and Sufficient

Round 1A of Google Code Jam 2008 has a problem called Minimum Scalar Product which, as the name suggests, asks that you find the minimum scalar product of 2 equally-sized vectors. When I read this problem my thoughts immediately went to the golf course. Why? Because if you're a member of a golf club you'll invariable come upon a competition format called 4-Ball Stableford multipler. Simply put, 2 players play as a team and each get a stableford (points) score for each hole, but the team score for each hole is recorded as the product of each players score on that hole with the team with the most point winning. i.e if PlayerA gets 4 points and PlayerB gets 2 points on a given hole, the team score for that hole is 8 points (= 4 x 2). Why am I telling you this? Well the secret to getting the best team score in a 4-Ball Stableford multiplier is to co-ordinate your good holes and your poor holes with your partners' good and bad scoring holes. In order words, to maximise the team score, each player should not only play well but play well on the same holes that their team-mate plays well on. The Google challenge posed here is effectively the same problem with the difference that they ask for the minimum product, rather than the maximum product that you seek on the golf course in the competition format described above.

Once you figure this out it's a simple problem to code. Get 2 vectors/lists and order one in ascending order, and order the other in descending order. There's no great need to procrastinate over which sort algorithm to use, and whether or not to replace the one provided by the .Net framework with your own - you'll be able to solve both the small and large problem with the code shown below:

using System;
using System.IO;
using System.Collections.Generic;

namespace GoogleCodeJam.ScalarProduct
{
    class Program
    {
        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader(basePath + "large.txt");
            StreamWriter outfile = new System.IO.StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read in the input data
                int vectorSize = Int32.Parse(infile.ReadLine());

                List<long> vector1 = new List<long>();
                List<long> vector2 = new List<long>();

                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                foreach (string s in data) { vector1.Add(Int64.Parse(s)); }

                data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                foreach (string s in data) { vector2.Add(Int64.Parse(s)); }

                vector1.Sort();
                vector2.Sort();
                vector2.Reverse();

                long minProduct=0;
                for(int i=0; i< vector1.Count; i++ )
                {
                    minProduct += vector1[i] * vector2[i];
                }

                // write out the results
                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, minProduct));
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}

After the fun and games of alien number systems the next problem I had a crack at was the Always Turn Left problem in the practice area. This problem asks that you try and draw the "perfect maze" given a representation of the path from the entrance to the exit and vice versa. On the surface of things it didn't seem like a super-hard problem and it's not. According to the stats in the practice area it's the easiest problem of the 4 and I have to agree, but it does pose a few little challenges to navigate around...

Some Observations Before We Begin

• By walking a "perfect maze" always touching the left wall, from both the entrance and exit, we are guaranteed to get a complete picture of the maze. If the maze were not a "perfect maze" according to the definition given in the problem description, this would not be the case.
• This is a 2D system so we are going to need to capture the current direction you are facing and cater for "walk" and "turn" functions, but only in 90 degree increments.
• Although we ultimately would like an RxC matrix of values we won't know what R and C are until we make both the forward and reverse journeys through the maze. This means we cannot setup a fixed-dimension data structure at the outset. (Actually we could try using the parameter limits given by Google but pre-allocating huge arrays is not my idea of efficiency.) To my mind this is the twist in the tail in this problem - how to store the intermiediate results during processing. I ended up using a struct in-memory data structure, rather than a class to avoid a heap allocation.
• Each "cell" in the maze can have a wall on any of the 4 edges of the cell. We'll greatly simplify our logic and code if we refer to these using compass directions, {N=1, E=2, S=4, W=8} and use a bitmap value to allow simple representation of combinations using a regular primitive. The use of flags makes it easy to add new data in an additive fashion using bitwise operations.

My Approach in a Nutshell

1. Call your start position (0,0) and imagine you have an infinite grid / cartesian plane surrounding your starting position.
2. Using the input walk from the entrance to the exit, recording the grid positions covered and the wall structure you ascertain as you go, knowing that the person walking the maze is religously following the "always turn left, if possible" algorithm. Note that you will ascertain information about the cell you are currently in, rather than the cell you are moving to.
3. Repeat the previous step but using the reverse direction. That is, the trip from the exit to the entrance.
4. Collate the results of steps (2) and (3) into a nice data structure that you can use to output the results, noting the particular representation of the wall structure that the problem asks that you use.

Recording the Wall Structure

All our movements in the maze are recti-linear with only 3 possible moves : W, L and R and from each of these, regardless of the direction we are travelling, we can elicit a small piece of information about the wall structure of the current cell in the grid as follow:

• W: Unless we just turned left, a W move means we have a wall on our left. If we keep track of which direction we are facing we can identify the "left" wall using a compass direction, N/S/E/W.
• L: We can't derive any information about the walls of the current cell from these types of moves.
• R: This means we must have had a wall directly in front of us and to our left. We can't make any inferences whether there is a wall behind or to the right.

My Code (in C#)

using System;
using System.IO;
using System.Collections.Generic;

namespace GoogleCodeJam.AlwaysTurnLeft
{
    class Program
    {
        [Flags]
        public enum Direction : int
        {   North = 1,
            East = 2,
            South = 4,
            West = 8,
        }

        static Direction TurnLeft(Direction before)
        {
            return TurnRight(TurnRight(TurnRight(before)));
        }

        static Direction TurnRight(Direction before)
        {
            // just right shift one place and do a modulus
            return (Direction)(((int)before << 1)%15);
        }

        // use a struct rather than a class to avoid heap allocation
        public struct CellData
        {
            public int row, col, walls;

            public CellData(int r, int c, int w)
            {
                row = r; col = c; walls = w;
            }
        }

        static void MazeTraverse(ref Direction dir, char lastMove, string moves, ref List<CellData> cells,
            ref int x, ref int y, ref int maxX, ref int maxY, ref int minX, ref int minY)
        {
            for(int i=0; i < moves.Length; i++)
            {
                char c = moves[i];
                bool isLastMove = (i == moves.Length-1);

                switch (c)
                {
                    case ('W'):
                        // moving forward means we have a wall on our left unless we just turned left   
                        if (lastMove != 'L')
                            cells.Add(new CellData(x, y, (int)TurnLeft(dir)));

                        if (!isLastMove)
                        {
                            if (dir == Direction.North) x--;
                            if (dir == Direction.West) y--;
                            if (dir == Direction.South) x++;
                            if (dir == Direction.East) y++;

                            // keep track of the maximum grid size
                            maxX = (x > maxX ? x : maxX);
                            minX = (x < minX ? x : minX);
                            maxY = (y > maxY ? y : maxY);
                            minY = (y < minY ? y : minY);
                        }
                        break;
                    case ('L'):
                        dir = TurnLeft(dir);
                        break;
                    case ('R'):
                        // turning to the right means we have a wall in front and to the left
                        cells.Add(new CellData(x, y, (int)(dir | TurnLeft(dir))));
                        dir = TurnRight(dir);
                        break;
                }
                lastMove = c;
            }
        }

        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader("input.txt");
            StreamWriter outfile = new System.IO.StreamWriter("output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // make this 1-based just for convenience
            {
                List<CellData> cells = new List<CellData>();

                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                string fromEntrance = data[0].ToUpper();
                string fromExit = data[1].ToUpper();

                //trim the initial move into the maze (from both directions)
                fromEntrance = fromEntrance.Substring(1, fromEntrance.Length - 1);
                fromExit = fromExit.Substring(1, fromExit.Length - 1);

                // Pass #1: perform initial walk in forward direction to gather maze info
                int x = 0, y = 0, maxX = 0, minX = 0, maxY = 0, minY = 0;

                // ForwardJourney
                Direction directionFacing = Direction.South;    // entrance is always on the northern edge
                char lastMove = 'W';
                Program.MazeTraverse(ref directionFacing, lastMove, fromEntrance, ref cells,
                                     ref x, ref y, ref maxX, ref maxY, ref minX, ref minY);

                // ReverseJourney
                lastMove = 'W';
                // firstly do a 180 turn
                directionFacing = TurnLeft(TurnLeft(directionFacing));
                Program.MazeTraverse(ref directionFacing, lastMove, fromExit, ref cells,
                                     ref x, ref y, ref maxX, ref maxY, ref minX, ref minY);

                // create a matrix of the compiled data
                int[,] maze = new int[Math.Abs(maxX - minX) + 1, Math.Abs(minY - maxY) + 1];
                foreach (CellData cd in cells)
                {
                    // use bitwise OR since there may be duplicated data
                    maze[cd.row - minX, cd.col - minY] = maze[cd.row - minX, cd.col - minY] | cd.walls;
                }

                // write out the results
                string hexVals = "0123456789abcdef";
                outfile.WriteLine(String.Format("Case #{0}:", caseNo));
                for (int i = 0; i <= maze.GetUpperBound(0); i++)
                {
                    string rowData = "";
                    for (int j = 0; j <= maze.GetUpperBound(1); j++)
                    {
                        int result = 0;
                        if ((maze[i,j] & (int)Direction.North) != (int)Direction.North) result += 1;
                        if ((maze[i,j] & (int)Direction.South) != (int)Direction.South) result += 2;
                        if ((maze[i,j] & (int)Direction.West) != (int)Direction.West) result += 4;
                        if ((maze[i,j] & (int)Direction.East) != (int)Direction.East) result += 8;
                        rowData = rowData + hexVals[result];
                    }
                    outfile.WriteLine(rowData);
                }
            }
            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}

The qualification round started with a problem called Save the Universe which asks that you assign search queries to a finite number of search engines in such a way that won't allocate a query for a search engine to that search engine. When I read the problem description I had a chuckle and reflected on a hilarious episode of The IT Crowd where Jen warned her superiors not to type "Google" into the Google search engine because it would break the internet.  Clearly the good folks at Google took inspiration from this humorous concept.

But back to the problem at hand...The first realization to grasp is that assigning queries to minimize the number of switches between search engines, is logically equivalent to finding the longest runs where a "run" is the use of a given search engine for a series of sequential search queries. We know we can't send an engine a query for itself so making long "runs" is simple - if you have n search engines you defer making a switch until you have received queries for n distinct search engines. At that point you have to switch to a different engine - the one not represented in the (n-1) distinct search engines you've already used.

In essence this is a greedy algorithm and the obvious question that needs to be answered for this (and indeed most greedy algorithms) is - is it globally optimal or does it only result in a local optima? The answer is Yes and you can see this by scribbling down some examples, and that is the real secret to solving this problem in a timely fashion - quickly convincing yourself that such an approach is going to guarantee optimal solutions in all cases. The optimality of the proposed algorithm can be proved using mathematical induction but I'll leave that as an exercise for the reader

In order to determine the complexity of the proposed greedy algorithm consider that:

1. it would be a single-pass solution,
2. according to MSDN, the List.Contains() function internally uses EqualityComparer that uses the overrides of Object.Equals and Object.GetHashCode provided by T. i.e. it uses hash codes hence the search component is constant time
3. in general, the run time of greedy algorithms is O(n * O(choice(n))) where choice(n) is the complexity associated with the decision between n alternatives at each step. So in this case choice(n) is constant time, O(k) = O(1) thus the overall complexity is O(n)

The C# code is shown below:

using System;
using System.Collections.Generic;
using System.IO;

namespace GoogleCodeJam.SaveTheUniverse
{
    class Program
    {
        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader("large.txt");
            StreamWriter outfile = new System.IO.StreamWriter("output.txt");

            int testCases = Int32.Parse(infile.ReadLine());

            for (int caseNo = 1; caseNo <= testCases; caseNo++)
            {
                int switchCount = 0;
                int engineCount = Int32.Parse(infile.ReadLine());

                List<string> engineNames = new List<string>();
                for (int i = 0; i < engineCount; i++)
                {
                    engineNames.Add(infile.ReadLine());
                }

                int queryCount = Int32.Parse(infile.ReadLine());
                List<string> query = new List<string>();
                for (int i = 0; i < queryCount; i++)
                {
                    query.Add(infile.ReadLine());
                }

                // this is a distinct list of engines already used in current run
                List<string> processed = new List<string>();

                // process the queries in the arrival order
                while (query.Count > 0)
                {
                    // pick the first query in the queue
                    string q = query[0];

                    if (processed.Contains(q.ToUpper()))
                    {
                        query.RemoveAt(0);
                        continue;
                    }
                    else
                    {
                        // add this to the processed list
                        processed.Add(q.ToUpper());
                        if (processed.Count == engineCount)
                        {
                            switchCount++;
                            processed.Clear();
                        }
                        else
                        {
                            query.RemoveAt(0);
                        }
                    }
                }

                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, switchCount));
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}