united-coders

Time again for a new google code jam article about alien numbers. This time instead of decoding words from an other alien language we have to convert numbers from one alien digit system to another.

The problem: 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.

convert binary to hex numbers

The basic idea was to convert binary numbers to hex numbers.

def bin2hex(binStr):
    binChar = "01"
    binBase = 2
    hexChar = "0123456789ABCDEF"
    hexBase = 16
    n = 0
    for c in binStr:
        n=n*binBase+binChar.find(c)
    res = ""
    while n:
        res = hexChar[n%hexBase] + res
        n = n / hexBase
    return res

binBase and hexBase are imported to calculate the integer n, but the both values are the same like the length of the digit string.

• binBase == len(binChar)

• hexBase == len(hexChar)

common function convert hex to binary numbers

def convert(num, src, trg):
    n = 0
    for c in num:
        n=n*len(src)+src.find(c)
    res = ""
    while n:
        res = trg[n%len(trg)] + res
        n/=len(trg)
    return res

convert examples as yoda condition from binary, hex or octal into decimal:

• '13' == convert('1101', '01', '0123456789')

• '31' == convert('1F', '0123456789ABCDEF', '0123456789')

• '80' == convert('88', '012345678', '0123456789')

convert examples as yoda condition from decimal to binary, hex or octal:

• '1101' == convert('13', '0123456789', '01')

• '1F' == convert('31', '0123456789', '0123456789ABCDEF')

• '88' == convert('80', '0123456789', '012345678')

You can use the code to convert from hex-decimal to binary or octal numbers. This works with any other char mapping based number system.

the solution

To solve this problem use the alien char mappings, convert the source alien number into an integer and produce from the integer the target alien number. Because the integer in python is not limited to 32bit, there is no need to use any big-int library.

To solve the complete task you have to convert every input line (which has the alien number num, the source digits and the target digits) and print the solution.

#!/usr/bin/python
import sys
fp = file(sys.argv[1])
for case in range(int(fp.next())):
    (num, src, trg) = fp.next().split()
    n = 0
    for c in num:
        n=n*len(src)+src.find(c)
    res = ""
    while n:
        res = trg[n%len(trg)] + res
        n/=len(trg)
    print "Case #%d: %s" % (case+1, res)
fp.close()

run time

The two input files was not large and the run time was not the challenge.

time python 2010_alien_numbers.py A-large.in > A-large.out

real	0m0.063s
user	0m0.052s
sys	0m0.012s

other solutions

Because the alien number problem is in the practice section you can find solutions in other programming languages:

• longer python solution from masteranza.wordpress.com
• 300 lines java example by illya-keeplearning.blogspot.com
• and a 100 lines c++ example by tausiq.wordpress.com or Cpp by utensil.javaeye.com
• my solution in java – longer but the same – by 3x-w.blogspot.com
• I found a C# example too by necessaryandsufficient.net – he has posted his java code too
• as response of my article a scheme solution (and haskel as comment)

• Bio
• Latest Posts

Christian Harms

I am working as a software developer and project manager in germany. After my graduate computer science I started in 2000 as a developer for a warehouse management system. my python knowledge grow up as a team member for one of the TOP3 german portal and freemail services. 2012 switched to the automotive industry to share my knowledge about open source and agile development. In spare time I submit to some coding contests and interesed in smaller developments.

Latest posts by Christian Harms (see all)

• google code jam 2013 – tic-tac-toe-Tomek solution - April 16, 2013
• Google code jam 2013 – the lawnmower - April 14, 2013
• code puzzles and permutations - April 11, 2013