Google Code Jam – Alien Numbers
The problem:
This problem is basically asking us to do conversions from base-X to base-Y. To do that, we’re going to do 2 conversions: one from base-X to base-10, then one from base-10 to base Y.
The conversion for base-10 is pretty simple. If we have a number in base-3 such as 201, then that can be represented in base-10 by the following: (2 * 3^2) + (0 * 3^1) + (1 * 3^0) = 19.
To convert to base-Y, we’re going to use the following method (using base-5 for our conversion and 19 (base-10) as our example).
19 / 5 = 3 R 4
3 / 5 = 0 R 3
We then take those remainders and write them down in reverse, so 19 (base-10) = 34 (base 5). Converting the numbers to the “Alien” numbers is a simple process of matching up the digits with their corresponding index in the given alien numbers.
Here’s the C# code that I used to solve the problem.
| C# | | copy code | | ? |
| 01 | using System.Collections; |
| 02 | using System.IO; |
| 03 | using System; |
| 04 | |
| 05 | namespace Alien_Numbers |
| 06 | { |
| 07 | class Program |
| 08 | { |
| 09 | static void Main(string[] args) |
| 10 | { |
| 11 | string path = args[0]; |
| 12 | int numTestCases = 0; |
| 13 | ArrayList input = new ArrayList(); |
| 14 | StreamReader reader = new StreamReader(path); |
| 15 | StreamWriter writer = new StreamWriter(path + ".out", true); |
| 16 | |
| 17 | numTestCases = Int32.Parse(reader.ReadLine()); |
| 18 | |
| 19 | while (!reader.EndOfStream) |
| 20 | input.Add(reader.ReadLine()); |
| 21 | |
| 22 | string alien_number = null; |
| 23 | string source_language = null; |
| 24 | string target_language = null; |
| 25 | |
| 26 | string[] line; |
| 27 | |
| 28 | foreach (string s in input) |
| 29 | { |
| 30 | line = s.Split(new char[] {' '}); |
| 31 | |
| 32 | alien_number = line[0]; |
| 33 | source_language = line[1]; |
| 34 | target_language = line[2]; |
| 35 | |
| 36 | writer.WriteLine("Case #" + (input.IndexOf(s) + 1) + ": " + ConvertToAlienLanguage(source_language, alien_number, target_language)); |
| 37 | writer.Flush(); |
| 38 | } |
| 39 | } |
| 40 | |
| 41 | static string ConvertToAlienLanguage(string source_language, string source_number, string target_language) |
| 42 | { |
| 43 | long srcbase = source_language.Length; |
| 44 | long trgbase = target_language.Length; |
| 45 | |
| 46 | long srcnum_base10 = 0; |
| 47 | string strConvertedNum = ""; |
| 48 | |
| 49 | // --------- Convert the source number to base 10 ------------ |
| 50 | |
| 51 | for (int i = 0; i < source_number.Length; i++) |
| 52 | srcnum_base10 += source_language.IndexOf(source_number[i]) * (long)(Math.Pow(srcbase, (source_number.Length - 1) - i)); |
| 53 | |
| 54 | // --------- Convert our Base 10 number into the target base and "Alien" numbers |
| 55 | |
| 56 | while (true) |
| 57 | { |
| 58 | strConvertedNum = strConvertedNum.Insert(0, (target_language[(int)(srcnum_base10 % trgbase)]).ToString()); |
| 59 | |
| 60 | if (srcnum_base10 / trgbase == 0) |
| 61 | break; |
| 62 | |
| 63 | srcnum_base10 = srcnum_base10 / trgbase; |
| 64 | } |
| 65 | |
| 66 | return strConvertedNum; |
| 67 | } |
| 68 | } |
| 69 | } |
