## Google Code Jam: Alien Numbers

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:

- a number system represented by X distinct characters is a base X number system
- any "number", Z, in abitrary base X can be converted to a "number" in base Y using the polynomial form:
z = c

_{n}.Y^{n}+ c_{(n-1)}.Y^{(n-1)}+ c_{(n-2)}.Y^{(n-2)}+ ... + c_{2}.Y^{2}+ c_{1}.Y^{1}+ c_{0}.Y^{0}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^{n} 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^{0}, 3^{1}, 3^{2}, 3^{3}, ...) and added to give us 79. In fact 79 = 2 x 3^{3} + 2 x 3^{2} + 2 x 3^{1} + 1 x 3^{0} , 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; } }

*18 Jul 2008*
*Damien Wintour*

on 04 Aug 2008 at 1:21 pm 1Necessary and Sufficient » Google Code Jam: Always Turn Left[...] 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 [...]

on 18 Aug 2008 at 9:39 pm 2Necessary and Sufficient » Google Code Jam: Train Timetables[...] from the Save The Universe puzzle the qualification round also had a train timetable problem. Here you are given a train [...]

on 04 Apr 2010 at 5:27 pm 3Mi versión del Alien Number (Google Code Jam) at blog de gin[...] http://www.necessaryandsufficient.net/2008/07/google-code-jam-alien-numbers/ [...]

on 29 Sep 2010 at 2:41 am 4Google code jam solution for alien numbers | united-coders.com[...] found a C# example too by necessaryandsufficient.net - he has posted his java code [...]