3
\$\begingroup\$

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()))
\$\endgroup\$
  • \$\begingroup\$ You should move sc+=1 in Palindrome().main() one line above. You should detect how many times you are in loops: for p, for q, for r. \$\endgroup\$ – vaeta May 14 '16 at 1:52
  • \$\begingroup\$ A tip for further optimization: 123*456 == 456*123 \$\endgroup\$ – Kenny Lau May 14 '16 at 9:22
  • \$\begingroup\$ As seen in this example, it is faster to build a look-up table of all products and then check each palindrome. \$\endgroup\$ – Kenny Lau May 14 '16 at 9:47
  • \$\begingroup\$ @vaeta: I just tried it and it's coming out to 1000000. Why would that be? Surely the yield statements of firstPass, secondPass and thirdPass should filter out most of the candidates? \$\endgroup\$ – AJS May 14 '16 at 10:54
  • \$\begingroup\$ @KennyLau: That's a good point...I'm not sure exactly how to implement that optimization, though, because neither $a.b.c$ or $x.y.z$ are fully implemented until thirdPass. Why is the look-up faster, though...mathematically, shouldn't my break-down be most efficient? \$\endgroup\$ – AJS May 14 '16 at 10:56
1
\$\begingroup\$

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
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Superb, vaeta! Thank you, I've marked your answer as solved. I made the incorrect assumption that the firstPass, secondPass and thirdPass would filter out more than 90% of the results when, in fact, they filter out exactly 90%. But I notice in your code, you've managed to implement your earlier optimisation with the range(first, 1000). Great work. \$\endgroup\$ – AJS May 14 '16 at 22:16
2
\$\begingroup\$

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))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you, Gareth, I'll definitely take those points moving forward as I use Python, but the question was less about optimising bruteForce and more about trying to understand why the Palindrome class' main() is so slow? \$\endgroup\$ – AJS May 14 '16 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.