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.
Article "Google Code Jam Practice Alien Numbers solved in PHP" has 5 responses
In more general cases, when converting between numeral systems, core method
base_convert
might be used. However, when converting from numeral system 10 to numeral system n, where 0 < n <= 10 this method is interesting for the practicing (might be optimized more as well)function decimal2n($x, $n) {
$m = ' ';
while($x >= 1) {
$a = $x % $n;
$x = floor($x / $n);
$m .= $a;
}
return(strrev($m));
}
Nice article ;)
Thanks Vlad, Yes you are right, I think that’s an easier way, and base_convert for those bigger than 10.
This is cool. Thanks for sharing.
Question: Why not convert to binary and convert from binary? I haven’t thought it through entirely, but I think you would get decimal-to-binary for free (just see how it’s stored) and you can use bitwise operators to do the powers math.
I get the feeling that using binary would be the Google-like answer, at least based on similar problems I solved in the past similar to you here and then discovered a “geekier” binary math solution.
Thanks for your comment Jason. Yes I think that would be an interesting way to solve it, although have not tried it myself :)
Pingback: Google Code Jam Practice Alien Numbers solved in PHP | Zend Tutorial