Fighting with computers

Computers are not always friendly.

Thursday, June 19, 2008

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).

17 Comments:

  • At 11:58 am, Blogger 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'?

     
  • At 12:21 pm, Blogger Miguel Sánchez 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.

     
  • At 1:52 pm, Anonymous Anonymous said…

    1*9 -> F 0*3 -> o 0*1 -> o can understand this line can u explain.

    thanks

     
  • At 2:29 pm, Blogger Miguel Sánchez 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

     
  • At 8:04 am, Anonymous Anonymous said…

    Thanks for last reply

    but can't reslove this one

    Foo oF8 0123456789

     
  • At 9:40 am, Blogger Miguel Sánchez 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

     
  • At 7:44 pm, Anonymous Anonymous said…

    hi miguel

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

    tanks

     
  • At 9:22 pm, Blogger Miguel Sánchez 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!

     
  • At 2:31 pm, Anonymous Anonymous said…

    I was thinking... is there any way to change from base A to base B without necesarily going through decimal? cheers! :)

    carla

     
  • At 2:51 pm, Blogger Miguel Sánchez 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.

     
  • At 3:25 pm, Anonymous 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

     
  • At 3:49 pm, Blogger Miguel Sánchez said…

    here you have


    (Yes, I could have use the newer Scan class).

     
  • At 5:11 pm, Anonymous Anonymous said…

    Thank you very much, Miguel! :)

    carla

     
  • At 9:56 pm, Anonymous Alien Numbers Solution said…

    Check my solution and temme how it is:

     
  • At 8:08 am, Anonymous 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!

     
  • At 10:57 am, Blogger Miguel Sánchez said…

    if lenghts pf both alphabets are the same then it's a mere transposition of characters as you suggest.

     
  • At 9:42 pm, Blogger Christian Harms said…

    The problem can solved general for hex2bin or for the given alien numbers. See the complete solution in python at united-coders.com

     

Post a Comment

<< Home