Recently I stumbled upon google code jam practice page, so I wanted to solve some of those challenges using PHP.

The one that seemed easy enough to start with was Alien Numbers. Here is the original problem. It’s basically converting numbers from one numeral system to another.

Any numeral system can be reproduced in this form:

0123456789

This is decimal system, and the representation means that 0 has the lowest value, than 1 has greater than it, then 2, etc.

If we had a numeral system like oF8, than numbers would go like (starting from lowest):

o, F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF...

The task is to convert number from one numeral system to another. You are given the number, it’s language and target language. Like this:

9 0123456789 oF8

The solution to this particular case would be:

Foo

You can see above that Foo is the 9th number in our custom numeral system (oF8) so it corresponds to number 9 in decimal numeral system.

We can solve this problem by converting the number from any numeral system we are given to decimal system. Then we can convert this decimal number to the target numeral system. Obviously we need two methods, I named them: convertToDecimal and convertFromDecimal (and possibly the third one – “solve” which takes input txt file and returns the result).

Convert To Decimal

The idea behind this is that we can write every number like this:

359 = 3*10^2 + 5*10^1 + 9*10^0

It’s like we multiply digit itself with length of a language powered by digit’s order. So in our example, if we had oF8 as our language, Foo would be:

1*3^2 + 0*3^1 + 0*3^0 = 9

Since 3 is the length of the language and F is the second greatest character, therefore it has the value of 1.

In order to convert given number to decimal we will iterate through characters of our number and multiply character’s order in language with length of the language powered by length of the number itself minus character position in number minus 1. Something like

[character_order] * [language_length] ^ ([number_length] – [character_position] – 1)
1 * 3 ^ (3-0-1) + 0 * 3 ^ (3 – 1 – 1) + 0 * 3 ^ (3 – 2 – 1)

That would look something like this in php:

function convertToDecimal($number, $language)
{
    $numberChars = str_split($number);
    $languageChars = array_flip(str_split($language));
    $numberLength = strlen($number);
    $languageLength = strlen($language);
    $sum = 0;
    foreach($numberChars as $key => $char) {
        $sum += $languageChars[$char] * pow($languageLength, $numberLength - $key - 1);
    }
    return $sum;
}

Decimal To Custom

Now that we have this we can work on a function that converts number that is represented in decimal numeral system to another numeral system.

For this we will need modulus (division remainder) of number and length of the target language. That number will give us the key with which we can get the character we need from target language. Then we need to actually divide those two numbers and repeat the same process.

Let’s convert 9 back to oF8.

9 mod 3 = 0

With index 0 we get the first character, which is “o” in our target language. On to next iteration:

9 / 3 = 3
3 mod 3 = 0

Again we get 0 so our string is “oo” now.

3 / 3 = 1
1 mod 3 = 1

Since 3 is greater than 1 we get 1 as result, so we grab character with index 1 from our target language and our final string looks like “Foo”.

PHP code looks like this:

function convertFromDecimal($number, $language)
{
    $languageLength = strlen($language);
    $final = "";
    while($number != 0){
        $index = $number % $languageLength;
        $final = $language[$index] . $final;
        $number = floor($number / $languageLength);
    }
    return $final;
}

Wrap Up

We can call these two functions in out main function in order to get the result:

function solve($filePath)
{
    $contents = file_get_contents($filePath);
    $lines = explode("\n", $contents);
    unset($lines[0]);
    $output = array();
    foreach($lines as $key => $line){
        list($number, $sourceLanguage, $targetLanguage) = explode(" ", $line);
        $decimalNumber = convertToDecimal($number, $sourceLanguage);
        $targetNumber = convertFromDecimal($decimalNumber, $targetLanguage);
        $output[] = "Case #" . $key . ": " . $targetNumber;
    }
    
    return implode("\n", $output);
}

There are many interesting problems on Google Code Jam page and I think most of them are programming language agnostic. It’s good to step away from daily routine and try solving something different, don’t you think?

Would you like to recommend this article to your friends or colleagues?
Feel free to share.