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

Christine said…
hey, i also spend some time to work out on the alien numbers problem.. but i do not reli understand the problem.. how come the solution for '9 0123456789 oF8' will be 'Foo' and 'Foo oF8 0123456789' will be '9'?
misan said…
Hi Christine,

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.
Anonymous said…
1*9 -> F 0*3 -> o 0*1 -> o can understand this line can u explain.

thanks
misan said…
Sure:

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
Anonymous said…
Thanks for last reply

but can't reslove this one

Foo oF8 0123456789
misan said…
Foo using alphabet oF8 means 100 in base-3 (again) as

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
Anonymous said…
hi miguel

how do you can resolve this?
CODE O!CDE? A?JM!.

tanks
misan said…
CODE O!CDE? A?JM!

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!
Anonymous said…
I was thinking... is there any way to change from base A to base B without necesarily going through decimal? cheers! :)

carla
misan said…
Hi 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.
Anonymous said…
Hi, Miguel!
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
misan said…
here you have


(Yes, I could have use the newer Scan class).
Anonymous said…
Thank you very much, Miguel! :)

carla
Anonymous said…
Check my solution and temme how it is:
Anonymous said…
I think when the bases are the same, you can just use the index numbers. For example
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!
misan said…
if lenghts pf both alphabets are the same then it's a mere transposition of characters as you suggest.
wingi said…
The problem can solved general for hex2bin or for the given alien numbers. See the complete solution in python at united-coders.com

Popular posts from this blog

VFD control with Arduino using RS485 link

How to get sinusoidal s-curve for a stepper motor

Stepper motor step signal timing calculation