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