Is there a faster way of converting a number to a name?
converters, namespaces, python
Solution
This is a fun little problem full of off by 1 errors.
Without loops:
import string
first_digits = sorted(string.ascii_letters + '_')
rest_digits = sorted(string.digits + string.ascii_letters + '_')
def convert(number):
if number < len(first_digits):
return first_digits[number]
current_base = len(rest_digits)
remain = number - len(first_digits)
return convert(remain / current_base) + rest_digits[remain % current_base]
And the tests:
print convert(0)
print convert(26)
print convert(52)
print convert(53)
print convert(1692)
print convert(23893)
Output:
A
_
z
A0
_1
FAQ
Problem
The following code defines a sequence of names that are mapped to numbers. It is designed to take a number and retrieve a specific name. The class operates by ensuring the name exists in its cache, and then returns the name by indexing into its cache. The question in this: how can the name be calculated based on the number without storing a cache? The name can be thought of as a base 63 number, except for the first digit which is always in base 53. ``` class NumberToName: def __generate_name(): def generate_tail(length): if length > 0: for char in NumberToName.CHARS: for extension in generate_tail(length - 1): yield char + extension else: yield '' for length in itertools.count(): for char in NumberToName.FIRST: for extension in generate_tail(length): yield char + extension FIRST = ''.join(sorted(string.ascii_letters + '_')) CHARS = ''.join(sorted(string.digits + FIRST)) CACHE = [] NAMES = __generate_name() @classmethod def convert(cls, number): for _ in range(number - len(cls.CACHE) + 1): cls.CACHE.append(next(cls.NAMES)) return cls.CACHE[number] def __init__(self, *args, **kwargs): raise NotImplementedError() ``` The following interactive sessions show some of the values that are expected to be returned in order. ``` >>> NumberToName.convert(0) 'A' >>> NumberToName.convert(26) '_' >>> NumberToName.convert(52) 'z' >>> NumberToName.convert(53) 'A0' >>> NumberToName.convert(1692) '_1' >>> NumberToName.convert(23893) 'FAQ' ``` Unfortunately, these numbers need to be mapped to these exact names (to allow a reverse conversion). Please note: A variable number of bits are received and converted unambiguously into a number. This number should be converted unambiguously to a name in the Python identifier namespace. Eventually, valid Python names will be converted to numbers, and these numbers will be converted to a variable number of bits. Final solution: ``` import string HEAD_CHAR = ''.join(sorted(string.ascii_letters + '_')) TAIL_CHAR = ''.join(sorted(string.digits + HEAD_CHAR)) HEAD_BASE, TAIL_BASE = len(HEAD_CHAR), len(TAIL_CHAR) def convert_number_to_name(number): if number < HEAD_BASE: return HEAD_CHAR[number] q, r = divmod(number - HEAD_BASE, TAIL_BASE) return convert_number_to_name(q) + TAIL_CHAR[r] ```