Palindrome Products in Python

Hi,
Below is my attempt at the palindrome_products exercise in the Python track.

All the test on my PC works perfectly fine, however, I get the following error on Exercism, when I run the tests:

Your tests timed out. This might mean that there was an issue in our infrastructure, but more likely it suggests that your code is running slowly. Is there an infinite loop or something similar?

Please check your code, and if nothing seems to be wrong, try running the tests again.

While running the tests locally on my PC, I realize that Tests 7 and Test 8 take really long to return values.

Is there a way to optimize my code? Using Numpy?

Test 7: smallest(min_factor=1000, max_factor=9999)
Test 8: largest(min_factor=1000, max_factor=9999)

NB: The issue is only when min_factor and max_factor are four (4) digit values, as shown above - three (3) digit values return values instantly.

def largest(min_factor, max_factor):
    """Given a range of numbers, find the largest palindromes which
       are products of two numbers within that range.

    :param min_factor: int with a default value of 0
    :param max_factor: int
    :return: tuple of (palindrome, iterable).
             Iterable should contain both factors of the palindrome in an arbitrary order.
    """

    factors_list = get_factors(min_factor, max_factor)
    values = get_values(factors_list)
    largest_value = max(values)
    factor = [factor[:len(factor) - 1] for factor in factors_list if factor[-1] == largest_value]

    return factors_list


def smallest(min_factor, max_factor):
    """Given a range of numbers, find the smallest palindromes which
    are products of two numbers within that range.

    :param min_factor: int with a default value of 0
    :param max_factor: int
    :return: tuple of (palindrome, iterable).
    Iterable should contain both factors of the palindrome in an arbitrary order.
    """

    factors_list = get_factors(min_factor, max_factor)
    values = get_values(factors_list)
    smallest_value = min(values)
    factor = [factor[:len(factor) - 1] for factor in factors_list if factor[-1] == smallest_value]

    return smallest_value, factor


def get_product_list(min_factor, max_factor):
    product_set = set()
    for num in range(min_factor, max_factor + 1):
        for elem in range(min_factor, max_factor + 1):
            product_set.add(num*elem)

    return sorted(list(product_set))


def get_palindromes(nums_list):
    palindromes = []
    for num in nums_list:
        list_to_reverse = [elem for elem in str(num)]
        reversed_list = list(reversed(list_to_reverse))
        if num == int(''.join(reversed_list)):
            palindromes.append(num)

    return palindromes


def get_factors(min_factor, max_factor):
    divisible_nums = []
    for palindrome in get_palindromes(get_product_list(min_factor, max_factor)):
        factors_value = []
        if palindrome == 1:
            factors_value.append([1, 1])
        else:
            for num in range(min_factor + 1, max_factor + 1):
                if palindrome % num == 0:
                    factors_value.append([num, palindrome//num])

        factors_value.append(palindrome)
        divisible_nums.append(factors_value)

    return divisible_nums


def get_values(factors_list):
    values = [item_list[-1] for item_list in factors_list]

    return values

I admit I haven’t reviewed your code thoroughly. A couple of general tips for this exercise:

  • the goal is to find the first palindrome, so you don’t want to calculate them all and extract the first one.
  • Since the goal is to find products, you can start iterating from min * min (or max * max depending on the direction)

I was also hitting this same performance problem when I initially solved this exercise. I took a lot of inspiration from ILoveMuffins’s solution.

Again, I didn’t read your code closely. My apologies if I’m telling you things you already know.

2 Likes

Yes. See Glenn’s response. In order to complete within 10 seconds, you’ll need to reduce the number of values your code explores.

No. The Exercism test runners do not have external packages available. You can only use Python’s Standard Library.

Hi @glennj, thank you so much for your kind feedback.

You’re right, I was collecting values in the given range and then searching for the palindrome and then went on to search for the factors in the given range, again!

Which I now see is very inefficient, I don’t know why I didn’t think to just test each given value in the range?!

The recommended solution you suggested, is very clever and elegant. Trying to give myself a break and try a solution tweaked to my own flavor.

Thanks again, learnt a lot with this exercise! :grin:

Things always seem obvious in hindsight! Not to worry, software is a team sport!