Google Code Jam '08
I've just got a notice about the new edition of Google Code Jam. I guess if you like challenges it is a place to go. I've spent part of the evening solving the "Alien Numbers" problem just to discover how rusted I am. It was fun though, and it was satisfying to make it right (though not very fast I would say).
Comments
9 0123456789 means that the alien number is 9 expressed in decimal. Now the translation to 'oF8' means you have just three symbols (think of base-3, but with other symbols instead of 012).
A number can be expressed in polynomial form as
digit * base ^ n + digit * base ^ (n-1) + ... + digit * base ^ 1 + digit * 1
So you translate decimal 9 into base-3 as 1*9 + 0*3 + 0*1
As oF8 (think of 012 ) means
o equiv 0
F equiv 1
8 equiv 2
Then 1*9 -> F 0*3 -> o 0*1 -> o
So 9 it's Foo
The opposite way works the same.
thanks
Number nine (decimal 9) is expressed as 100 as a base-3 number.
Our symbol system is not using numbers but oF8 where o stands for 0, F stands for 1 and 8 stands for 2.
As the number to represent is 100 (base-3) then we change each digit for the corresponding digit it represents:
Number 1 is replaced by a F
Number 0 is replaced by a o
Number 0 is replaced by a o
So 9 turns into Foo
but can't reslove this one
Foo oF8 0123456789
o turns into 0
F turns into 1
8 turns into 2
this turns into 9 when using base-10
it is the reverse transformation than previous case
how do you can resolve this?
CODE O!CDE? A?JM!.
tanks
Let's see, the equivalence ...
O!CDE?
012345
so it's base-6 (6 different symbols)
and CODE is 2034 in base-6
it's decimal value is
2*6^3+0*6^2+3*6^1+4*6^0 = 454 in decimal
A?JM!. has 6 symbols, so it's a base-6
012345
it just uses other symbols,
454 decimal expressed base-6 is 2034
which turns into
JAM!
carla
The fact that we go through decimal is just a question of abstraction (our computer will represent these 'decimal' numbers in binary).
I think that explaining the transformation through decimal may make it more obvious to us but what we only need it is to transform a list of symbols into a digits to be able to make a number out of a sequence of those symbols.
Base translation is just a mathematical operation. Maybe other people may focus their solution on grammar transformation but mine used numbers theory (and it worked). Java code is available if you need it.
It would be great to have that java code. I'm currently trying to solve this problem in java and to have some working code to compare to would be very useful. Where can I get it?
Or this is my email crucio_curse[at]hotmail.com if you can send it to me.
Thanks for you help.
carla
(Yes, I could have use the newer Scan class).
carla
CODE O!CDE? A?JM!
C is in index 2 of the source language
O is in index 0 ''
D " 3 "
E " 4 "
so if you get indices 2, 0, 3, and 4 of the target language you get JAM!