Necessary and Sufficient

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();
        }
    }
}

Google Code Jam is an annual competition held by the search giant that allows programmers to try their hand at solving increasingly complex problems using the language of their choice. I managed to register for the competition in time but alas, due to various commitments, wasn't able to make it to the actual competition. Damn!!!

Rather than sit on the sidelines waiting for next year to roll around I decided to take a stab at a number of these problems and found them interesting, challenging and a whole bunch of fun. I like the fact that Google lets you work through the problems even if you are officially excluded from the competition. What follows is my attempt at these mind benders starting with the practice problems...

The alien numbers problem asks that you translate from one arbitrary alien numeral system to another alien numeral system...

The decimal numeral system is composed of ten digits, which we represent as "0123456789" (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as "oF8", then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that's written in one alien system into a second alien system.

You can read complete details about the it here: Alien Numbers Problem

My Approach

Firstly you need to understand a few key facts:

1. a number system represented by X distinct characters is a base X number system
2. any "number", Z, in abitrary base X can be converted to a "number" in base Y using the polynomial form:

   z = c_n.Yⁿ + c_(n-1).Y^(n-1) + c_(n-2).Y^(n-2) + ... + c₂.Y² + c₁.Y¹ + c₀.Y⁰

   where c_i is a co-efficient digit taken from the target base system.

Fact (1) above means that we can easily ascertain the source and target base sizes from the input given to us as the problem description clearly indicates that "no digit will be repeated in any representation, and all digits in the alien number will be present in the source language". Those 2 conditions are the necessary and sufficient conditions to ascertain the base sizes. Furthermore, we know that the digits are always given to us in ascending order so we know everything we need to about the base systems. The problem is therefore reduced to a simple base conversion problem which is where Fact (2) comes into play.

Fact (2) tells us we need to think in multiples of Yⁿ when expressing numbers in the new base, Y. For example, if we want to convert the number 79 from base10 to, say base3 represented by the digits {0,1,2}, we need to identify the co-efficients, c_i ∈ {0,1,2}, that can be mutliplied against the powers of 3 (3⁰, 3¹, 3², 3³, ...) and added to give us 79. In fact 79 = 2 x 3³ + 2 x 3² + 2 x 3¹ + 1 x 3⁰ , so 79 would be written as 2221 in a base 3 number system using the characters "0","1" and "2". If that base system used the characters "o", "F" and "8" and that represented their ascending order then 79 would be written as 888F.

With respect to the polynomial expression given above you may be asking what the value of n will be. i.e. what the highest-order of Y is needed. This is needed to determine the value of the most significant bit and you can use the formula below to do so:

n=⌊log_Y(x)⌋

Essentually you take the floor of the base-Y logarithm of the input number, x.

My Code (in C#)


The Code Jam competition places an emphasis on getting the correct result within a time constraint for problems of a certain magnitude. As such you needn't bother with input validation - the input data is always going to be well formatted so the code below has no error handling or input validation around this.


You could also further optimise the code to make use of memoization and perhaps make the function better handle really, really large numbers by using a lowest-highest order bit approach rather than starting with the calculation of the most-significant bit and working down as I have done. But I'll leave that as an excerise for the reader.

using System;
using System.IO;

namespace GoogleCodeJam.AlienNumbers
{
    class Program
    {
        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader(@"c\:input.txt");
            StreamWriter outfile = new System.IO.StreamWriter(@"c:\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
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                string alienNoFromSrc = data[0];
                string srcLang = data[1];
                string tgtLang = data[2];

                // we are effectively converting from base(source) to base(target)
                string alienNoFromTgt = Convert(alienNoFromSrc, srcLang, tgtLang);

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

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

        static string Convert(string number, string baseFrom, string baseTo)
        {
            double input=0;
            double srcBase = baseFrom.Trim().Length;
            double tgtBase = baseTo.Trim().Length;
            string result = "";

            // convert the input "number" to a numeric value first
            for (int i = 0; i< number.Length; i++)
            {
                input = input + (baseFrom.IndexOf(number[i]) * Math.Pow(srcBase, number.Length - 1 - i));
            }

            double index = Math.Floor(Math.Log(input, tgtBase)); // the leftmost index
            while (index >= 0)
            {
                int digit = (int)(Math.Floor(input / Math.Pow(tgtBase, index)));
                result = result + baseTo[digit].ToString();
                input = input - (digit * Math.Pow(tgtBase, index));
                index--;
            }
            return result;
        }
    }
}

And my Java code to do the same:

import java.io.*;

class Main implements Runnable {

    public static void main(String[] args) {
        new Thread(new Main()).start();
    }

    @Override
    public void run() {
        try
        {
            BufferedReader infile = new BufferedReader(new FileReader("/usr/local/data/workspace/AlienNumbers/A-large-practice.in"));
            BufferedWriter outfile = new BufferedWriter(new FileWriter("/usr/local/data/workspace/AlienNumbers/output.txt"));

            int testCases = Integer.parseInt(infile.readLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read the input data
                String[] data = (infile.readLine()).split(" ");
                String alienNoFromSrc = data[0];
                String srcLang = data[1];
                String tgtLang = data[2];

                // we are effectively converting from base(source) to base(target)
                String alienNoFromTgt = Convert(alienNoFromSrc, srcLang, tgtLang);

                // write out the results
                outfile.write(String.format("Case #%s: %s\n", caseNo, alienNoFromTgt));
            }
            infile.close();
            outfile.close(); // flush and close
        }
        catch(Exception e) {
            e.printStackTrace();
        }
    }

    public static String Convert(String number, String baseFrom, String baseTo)
    {
        double input=0;
        double srcBase = baseFrom.trim().length();
        double tgtBase = baseTo.trim().length();
        String result = "";

        // convert the input "number" to a numeric value first
        for (int i = 0; i< number.length(); i++)
            input += baseFrom.indexOf(number.charAt(i)) * Math.pow(srcBase, number.length() - 1 - i);

        // Java doesn't let us specify the required base so we use the change-of-base theorem
        double index = Math.floor( Math.log(input) / Math.log(tgtBase)); // the leftmost index
        while (index >= 0)
        {
            int digit = (int)(Math.floor(input / Math.pow(tgtBase, index)));
            result += baseTo.charAt(digit);
            input -= digit * Math.pow(tgtBase, index);
            index--;
        }
        return result;
    }

}