Largest palindrome product

Question

From the Project Euler challenge series:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

The brute force method runs in 1.8s per loop on my machine:

def getGen(n):
    return range(n,-1,-1)

def bruteForce():
    gen = getGen(999)
    sc = maxpalin = 0
    for i in gen:
        for j in gen:
            sc += 1
            prod = i * j
            s = str(prod)
            if s==s[::-1] and prod > maxpalin:
                maxpalin = prod
    print(sc)
    return maxpalin

%timeit bruteForce()

When I initially approached the problem, I tried to use the properties of multiplying 2 different 3-digit numbers to find the solution. This approach, however, takes approximately 16.7s per loop, even though the sc for the bruteForce is 1 million and the sc for Palindrome.main() (see below) is considerably lower at 4536. Why does the Palindrome class run so much slower?

$$(a.b.c) * (x.y.z) = (l.m.n.n.m.l)$$ $$(100a + 10b + c) * (100x + 10y + z) = (100001l + 10010m + 110n)$$ $$(10000ax + 1000ay + 100az) + (1000bx + 100by + 10bz) + (100cx + 10cy + cz) = (100001l + 10010m + 110n)$$ $$10000ax + 1000(ay + bx) + 100(az + by + cx) + 10(bz + cy) + cz = (100001l + 10010m + 1100n)$$ $$10(1000ax + 100(ay + bx) + 10(az + by + cx) + (bz + cy)) + cz = 100001l + 10(1001m + 110n)$$

firstPass $$10(1000ax + 100(ay + bx) + 10(az + by + cx) + (bz + cy) - 1001m - 110n) = 100001l - cz = 10p \implies 10 \mid 10p$$

secondPass $$p = 10(100ax + 10(ay + bx) + (az + by + cx - 11n)) + (bz + cy) - 1001m \implies 10 \mid p + 1001m - (bz + cy) = 10q$$

thirdPass $$q = 10(10ax + (ay + bx)) + (az + by + cx - 11n) \implies 10 \mid q + 11n - (az + by + cx) = 10r$$

main $$r = 10ax + (ay + bx) \implies 10 \mid r - (ay + bx) = 10s$$

class Palindrome(object):
    def __init__(self):
        self.a = 0
        self.b = 0
        self.c = 0
        self.l = 0
        self.m = 0
        self.n = 0
        self.x = 0
        self.y = 0
        self.z = 0

    def firstPass(self):
        gen = getGen(9)
        for l in gen:
            for c in gen:
                for z in gen:
                    p = 100001 * l - (c * z)
                    if (p % 10):
                        continue
                    self.l = l
                    self.c = c
                    self.z = z
                    yield p / 10

    def secondPass(self, p):
        gen = getGen(9)
        for m in gen:
            for b in gen:
                for y in gen:
                    q = p + (1001 * m) - ((b * self.z) + (self.c * y))
                    if (q % 10):
                        continue
                    self.m = m
                    self.b = b
                    self.y = y
                    yield q / 10

    def thirdPass(self, q):
        gen = getGen(9)
        by = self.b * self.y
        for a in gen:
            for x in gen:
                for n in gen:
                    r = q + (11 * n) - (a * self.z + by + self.c * x)
                    if (r % 10):
                        continue
                    self.a = a
                    self.x = x
                    self.n = n
                    yield r / 10

    def main(self):
        sc = 0
        for p in self.firstPass():
            for q in self.secondPass(p):
                for r in self.thirdPass(q):
                    a = self.a
                    b = self.b
                    x = self.x
                    y = self.y

                    s = r - (a * y + b * x)
                    if s == 10 * a * x:
                        sc += 1
                        m = 100 * a + 10 * b + self.c
                        n = 100 * x + 10 * y + self.z

                        yield m * n
        print(sc)

i = Palindrome()
%timeit (max(i.main()))

Answer 1

Complexity brute force algorithm

You iterate by abc and xyz numbers. It's 1000 * 1000 space approach (you need to check 1000000 numbers, i.e. prod = i * j)

Complexity second algorithm

You iterate over abcxyzlmn digits but 3 times drop about every tenth result.

You need to check them same space (1000 / 10) * (1000 / 10) * (1000 / 10). Solutions have the same complexity, but second is more complicate (so is slower).

sc == 4536 numbers in second approach

• you get it after if s == 10 * a * x: but s you calculate about 100 * 100 * 100 times (similar to prod in brute force)

• compare with brute force

  def bruteForce_with_different_sc():
      sc = palindrome = 0
      for first in range(100, 1000): # try check sc with range(1000) also
          for second in range(first, 1000): # try check sc with range(100, 1000) or range(1000) also
              product = first * second
              s = str(product)
              if s == s[::-1]:
                  sc += 1 # the same place as in your second algorithm
                  palindrome = max(product, palindrome)
      print("sc: {}".format(sc))
      return palindrome
  

Answer 2

A quick look at bruteForce.

1. The built-in max computes the maximum value of a collection.

2. Nested loops can often be combined into a single loop using product, combinations, or combinations_with_replacement, depending on how you need to handle repetitions.

3. The loops go downwards from 999, but no use is made of this (no early exit) so you might as well let the loops go upwards, which is simpler.

Revised code:

from itertools import combinations_with_replacement

def palindrome(n):
    """Return True if n is a palindrome in base 10."""
    s = str(n)
    return s == s[::-1]

def problem4():
    """Return the largest palindrome made from the product of two 3-digit
    numbers.

    """
    return max(i * j
               for i, j in combinations_with_replacement(range(1000), 2)
               if palindrome(i * j))