hbk_interview

palindromic numbers

#!/bin/python

import sys
import os
import math

"""
convert base-10 to base-17 in string
"""


def convert_10_to_17(number):
    digits = {10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f', 16: 'g', 17: 'h'}
    base = 17
    representation = []
    while number > 0:
        cur = number % base
        if (cur > 9):
            representation.insert(0, digits[cur])
        else:
            representation.insert(0, str(cur))
        number //= base
    return "".join(representation)


"""
check if a string is a palindrome
"""


def check_palindrome(str):
    if str and str == str[::-1]:
        return True
    else:
        return False


"""
take the binary sequence as

A 1111...111 B

with 17 bits in between A and B.

Suppose B is a n-digit bits representaion in binray, then in base-10, the
number is B + (2**17 - 1) * (2**n) + A * (2**(17 + n))
"""


def calculate(prefix, postfix, post_len):
    return postfix + (2 ** 17 - 1) * (2 ** post_len) + prefix * (2 ** (17 + post_len))


"""
find the nth number, consider A's digit length and B's digit length, take
their summation as a criteria. When we have enough numbers in pocket, we sort
all the numbers before.

Then sorting can be faster, if we do it round by round, since if the summation of the digits
are smaller, then the numbers are smaller.
"""


def find_number(n):
    record = []
    digit_sum = 0
    while True:
        """current record for digit sum, start from 0"""
        current_record = []
        for prefix in range(2 ** digit_sum):
            """prefix and postfix, their digit sum must be digit_sum"""
            prefix_digits = prefix.bit_length()
            postfix_digits = digit_sum - prefix_digits

            """lower and upper bound for postfix"""
            lower_bound = 0
            upper_bound = 2 ** (digit_sum - prefix_digits)

            """search all postfix"""
            for postfix in range(lower_bound, upper_bound):
                candidate = calculate(prefix, postfix, postfix_digits)
                if check_palindrome(convert_10_to_17(candidate)) and candidate not in current_record:
                    # print prefix_digits, postfix_digits
                    current_record.append(candidate)

        """current round is done, sort it and merge into record"""
        record += sorted(current_record)

        """if we have enough results, output"""
        if len(record) >= n:
            return record[n - 1]
        """into next round"""
        digit_sum += 1


if __name__ == "__main__":
    for i in range(1, 20):
        print find_number(i)