Palindrome with PQ

palindrome_pq.py

# %time find_biggest_palindrome()
# CPU times: user 103 ms, sys: 3.15 ms, total: 106 ms
# Wall time: 106 ms

from Queue import PriorityQueue
import time


class DecreasingFactors(object):
    def __init__(self, num):
        self.number = num
        self.current_factor = num

    def __repr__(self):
        return self.__class__.__name__ + str(self.number)

    def __cmp__(self, other):
        '''actually this is reverse sorting since i'm gonna use this in a priority
        queue, which returns the lowest (ie first item in sorted(items)) item from
        the queue.'''
        if hasattr(other, 'next_number'):
            return other.next_number.__cmp__(self.next_number)

    @property
    def next_number(self):
        return self.number * self.current_factor

    def consume_next_number(self):
        next_number = self.next_number
        self.current_factor -= 1
        return next_number


def is_palindrome(n):
    num_string = str(n)
    return num_string == num_string[::-1]

def _true():
    while True: yield True

def find_biggest_palindrome(_start):
    pq = PriorityQueue()
    for i in range(_start, int(_start/2), -1):
        pq.put(DecreasingFactors(i))

    for i, _ in enumerate(_true()):
        # pop the one with the highest `next_number` from the queue
        factor_generator = pq.get_nowait()
        # consume the number from the "factor generator"
        current_number = factor_generator.consume_next_number()
        if is_palindrome(current_number):
            # the first one we find is the one we want
            # print("num: {}, factor: {}".format(factor_generator.number, factor_generator.current_factor + 1))
            # print("queue_size: {}, iterations: {}".format(len(pq.queue), i))
            return current_number
        else:
            # but if it isn't a palindrome, we need to put it back into the queue
            pq.put(factor_generator)

if __name__ == '__main__':
    for x in [999,9999,99999,999999]:
        start = time.time()
        pal = find_biggest_palindrome(x)
        elapsed = time.time() - start
        print("time: {:.4}, initVal: {}, result: {}".format(elapsed, x, pal))

palindrome_pq2.py

# $ /usr/bin/time python palindrome_pq2.py
# time: 0.0378, initVal: 999, result: 906609
# time: 0.04918, initVal: 9999, result: 99000099
# time: 0.5817, initVal: 99999, result: 9966006699
# time: 5.615, initVal: 999999, result: 999000000999
#         6.34 real         6.28 user         0.02 sys

# optimization of this wonderful script by alexandrinaw:
# https://gist.github.com/alexandrinaw/c9af50d02174c5bc708ea23792b0be4a
# 
# these are similar timings for that script:
# 
# $ /usr/bin/time python palindrome_pq.py
# time: 0.06619, initVal: 999, result: 906609
# time: 0.1179, initVal: 9999, result: 99000099
# time: 1.575, initVal: 99999, result: 9966006699
# time: 16.68, initVal: 999999, result: 999000000999
#       18.48 real        18.32 user         0.13 sys

from Queue import PriorityQueue
import time


class DecreasingFactors(object):
    def __init__(self, num):
        self.number = num
        self.current_factor = num

    def __repr__(self):
        return self.__class__.__name__ + str(self.number)

    def __cmp__(self, other):
        '''actually this is reverse sorting since i'm gonna use this in a priority
        queue, which returns the lowest (ie first item in sorted(items)) item from
        the queue.'''
        if hasattr(other, 'next_number'):
            return other.next_number.__cmp__(self.next_number)

    @property
    def next_number(self):
        return self.number * self.current_factor

    def consume_next_number(self):
        next_number = self.next_number
        self.current_factor -= 1
        return next_number


def is_palindrome(n):
    num_string = str(n)
    return num_string == num_string[::-1]

def _true():
    while True: yield True

def find_biggest_palindrome(_start):
    pq = PriorityQueue()
    for i in range(_start, int(_start/2), -1):
        pq.put(DecreasingFactors(i))

    for i, _ in enumerate(_true()):
        # pop the one with the highest `next_number` from the queue
        factor_generator = pq.get_nowait()
        # consume the number from the "factor generator"
        current_number = factor_generator.consume_next_number()
        if is_palindrome(current_number):
            # the first one we find is the one we want
            # print("num: {}, factor: {}".format(factor_generator.number, factor_generator.current_factor + 1))
            # print("queue_size: {}, iterations: {}".format(len(pq.queue), i))
            return current_number
        else:
            # but if it isn't a palindrome, we need to put it back into the queue
            pq.put(factor_generator)

if __name__ == '__main__':
    for x in [999,9999,99999,999999]:
        start = time.time()
        pal = find_biggest_palindrome(x)
        elapsed = time.time() - start
        print("time: {:.4}, initVal: {}, result: {}".format(elapsed, x, pal))