Google, codejam and number conversions
June 26th, 2008
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 above was exactly one of the practice problems of the google codejam (I still don’t know if I could join the event since I’ll probably be very busy with university exams in the day of the qualification round) and more generally the problem is the conversion of a number (that isn’t necessarily composed by the usual digits) from any base to any base. I just figured a solution out and passed both the the small input test and the large one. My solution is simple: convert the source base number in base 10 and then convert the produced base 10 number in another base. There are known algorithms for doing this (just think that 1986 for example is nothing but 1 * 10^3 + 9 * 10^2 + 8 * 10^1 + 6 * 10^0) and I finished implement my own solution in python.
The biggest issue here is that the source base can have symbols instead of digit and I solved this issue by mapping the symbols to an array and using the index value of the symbols as digit value. Here it is my solution:
#!/usr/bin/env python
import sys, array
def main(argv=None):
if not argv:
argv = sys.argv
try:
f = open(argv[1])
except IOError:
print "File doesn't exist"
return 0
try:
i = 0
for line in f:
if i == 0:
# first line
line_num = int(line)
else:
number, input_b, output_b = line.strip('\n').split(' ')
print 'Case #%d: %s' % (i, convert(number, input_b, output_b))
i += 1
finally:
f.close()
return 1
def convert(number, input_b, output_b):
"""
Convert a number from any base to any base
"""
return convert_from_10(convert_to_10(number, input_b), output_b)
def convert_to_10(input, base):
"""
Input can be a number in any base, even in an 'alien' base.
For example: 'Foo' could be a number in a numerical system
whose digits are 'oF8'.
Base is exactly the digits representation.
If you want to convert that 'Foo' to base 10 then you must
call ``convert_to_10('Foo', 'oF8')``.
Remember that the number in ``base`` must be written in an
ordered form
Returns a string of the number in base 10
"""
current_base = len(base)
map_to_base = array.array('c')
map(map_to_base.append, base)
i = len(input) - 1
base_10 = 0
for digit in input:
base_10 += map_to_base.index(digit) * current_base**i
i -= 1
return str(base_10)
def convert_from_10(input, base):
"""
``input`` is a number in base 10, while ``base`` is the digit
representation of the new base (for example, for base 16 this
could be '0123456789ABCDEF' or for an alien base 3 could be
'oF8').
Returns the number converted from base 10 to the specified
base
"""
map_to_base = array.array('c')
map(map_to_base.append, base)
current = int(input)
base_n = ''
while current != 0:
base_n = map_to_base[current % len(base)] + base_n
current = current / len(base)
return base_n
if __name__ == '__main__':
sys.exit(main())And giving this input (the first line is number of the following lines):
4
9 0123456789 oF8
Foo oF8 0123456789
13 0123456789abcdef 01
CODE O!CDE? A?JM!.I have the correct output:
Case #1: Foo
Case #2: 9
Case #3: 10011
Case #4: JAM!Of course this is one of the practice problems and you should try to solve it by your own (otherwise it’s useless to try to join the event).
Pownce