GCJ 2008 - Alien Numbers

'Alien Numbers' problem statement:


The decimal numeral system is composed of ten digits, which we represent as "0123456789" (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as "oF8", then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that's written in one alien system into a second alien system.


The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as

alien_number source_language target_language

Each language will be represented by a list of its digits, ordered from lowest to highest value. No digit will be repeated in any representation, all digits in the alien number will be present in the source language, and the first digit of the alien number will not be the lowest valued digit of the source language (in other words, the alien numbers have no leading zeroes). Each digit will either be a number 0-9, an uppercase or lowercase letter, or one of the following symbols !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~


For each test case, output one line containing "Case #x: " followed by the alien number translated from the source language to the target language.


1 ≤ N ≤ 100.

Small dataset

1 ≤ num digits in alien_number ≤ 4,
2 ≤ num digits in source_language ≤ 16,
2 ≤ num digits in target_language ≤ 16.

Large dataset

1 ≤ alien_number (in decimal) ≤ 1000000000,
2 ≤ num digits in source_language ≤ 94,
2 ≤ num digits in target_language ≤ 94.

Sample Input

9 0123456789 oF8
Foo oF8 0123456789
13 0123456789abcdef 01

Sample Output

Case #1: Foo
Case #2: 9
Case #3: 10011
Case #4: JAM!

There are a couple of ways you can code a solution for this, but if you know (or did some research on) number systems, you can figure out the easiest solution.

My Solution:

Since the 'decimal system' is the easiest that we humans and the programming languages (Higher-Level Languages) can comprehend, I converted the 'Alien Number' (using 'Source Language' input) into a decimal number and then divided that number with the 'base of the 'Target Language' number system) . The remainder is found and if its not zero, the division has to be done repeatedly on the quotient of the previous division until the remainder is '0' and collect all the 'remainders'. Form a number from the remainders, in the reverse order....and....VOILA!

Example: (Converting '19' (decimal) to 'base 5')

19/5 = 3 ------> 4 (remainder)
3/5 = 0 - -----> 3 (remainder)

So, the decimal number 19 is equal to 34 in 'base 5'. Simple! :-)

Then I uploaded the output files and found the solution to be 'Correct'.

Here's the code for my solution:


  1. Your solution seems ok (a bit verbose in variable names I would say). Better than any opinion is the fact that your code works ok.

    Not sure how powerful VB is for handling complex data structures (though Basic is the first language I learned in the late seventies I am not using it lately).

  2. First off, Thanks for the reply, Miguel! Well, I agree that the variables are a bit verbose. But I just tried to make it clearly understandable, as thats how Java standards are. It indeed applies to any code, as its easier to maintain, debug and understand the code in a easier and faster way (specially for an other person in reviewing/maintaining the code). Also, I didn't optimize the code, as I just wrote it and posted here.

    And coming to VB, I haven't worked extensively on that, but can say that it aint as capable as Java in handling complex data structures.

  3. Thanks for the comment! I have a friend who took the same approach you did to this problem and his implementation was much more efficient than mine :) Unfortunately I missed the qualification round for the Jam so this was all for nothing heh

  4. HOW I GOT MY LOAN (Lexieloancompany@yahoo.com)!!!

    My Name is Nicole Marie, I live in USA and life is worth living comfortably for me and my family now and i really have never seen goodness shown to me this much in my life, As i am a struggling mum with two kids and i have been going through a serious problem as my husband encountered a terrible accident last two weeks, and the doctors stated that he needs to undergo a delicate surgery for him to be able to walk again and i could not afford the bills for his surgery then i went to the bank for a loan and they turn me down stating that i have no credit card, from there i ran to my father and he was not able to help me, then when i was browsing through yahoo answers i came across a God fearing man (Mr Martinez Lexie) who provides loans at an affordable interest rate and i have been hearing about so many scams on the Internet mostly Africa, but at this my desperate situation, i had no choice than to give it an attempt due to the fact that the company is from United State of America, and surprisingly it was all like a dream, i received a loan of $82,000.00 USD and i payed for my husband surgery and thank GOD today he is ok and can walk, my family is happy and i said to myself that i will shout to the world the wonders this great and God fearing Man Mr Martinez Lexie did for me and my family; so if anyone is in genuine and serious need of a loan do contact this GOD fearing man via Email: ( Lexieloancompany@yahoo.com ) or through the Company website: http://lexieloans.bravesites.com OR text: +18168926958 thanks


Note: Only a member of this blog may post a comment.