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)
Christian Harms
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