#### Sunday, July 12th, 2009...15:55

## Project Euler Problem #4

As I work through these projecteuler problems, it’s become apparent that my brain tends towards a particular style of solution. When I know one way to solve a problem, I tend to just implement it, as I want to get to the next one. In the future, I’m going to start trying to find multiple solutions right off the bat, before I check to see if I’ve answered the problem correctly. Here’s an example; problem 4 requested the largest number that is a product of two 3 digit numbers as well as being a palindrome.

It’s obvious the answer will be <= 999 x 999 and >= 100 x 100. I came up with this solution relatively quickly:

def findLargestPalindrome(): factorA = 999 factorB = factorA maxToCheck = 100 maxPalindrome = 0 while factorA > maxToCheck: factorB = factorA while factorB > maxToCheck: temp = factorA * factorB if temp < maxPalindrome: maxToCheck = factorB break else: tempStr = str(temp) if tempStr == tempStr[::-1]: maxToCheck = factorB maxPalindrome = temp break factorB -= 1 factorA -= 1 return maxPalindrome

Answer: 906609. 100 iterations took 2.677 seconds

I want to call out that the syntax for reversing a string, string[::-1] is pretty odd looking. It asks for the representation of the string from the beginning to the end in -1 steps/strides. So position -1 from the start is the end, and then position -1 from the end is the second to last character, etc.

When I was playing with Erlang, one of the fundamental aspects of the language is the notion of single assignment i.e. a variable can only be assigned to once, and then never changes. Obviously the code above reassigns numerous variables over and over again during execution. As an exercise I decided to re-write the answer recursively and pretend I was constrained by the single assignment rule.

def findLargestPalindrome2(factorA, factorB, maxToCheck, maxPalindrome): if factorA < maxToCheck: return maxPalindrome elif factorB < maxToCheck: newFactor = factorA - 1 return findLargestPalindrome2(newFactor, newFactor, maxToCheck, maxPalindrome) else: candidate = factorA * factorB if candidate < maxPalindrome: newFactor = factorA - 1 return findLargestPalindrome2(newFactor, newFactor, factorB, maxPalindrome) else: tempStr = str(candidate) if tempStr == tempStr[::-1]: newFactor = factorA - 1 return findLargestPalindrome2(newFactor, newFactor, factorB, candidate) else: return findLargestPalindrome2(factorA, factorB - 1, maxToCheck, maxPalindrome)

This function has a very different look to it as state must be passed to each recursive call. I also apparently exceeded the default recursion limit and had to: sys.setrecursionlimit(7000). The recursive solution is also almost twice as slow.

Answer: 906609. 100 iterations took 4.350 seconds

This is also another example of a problem that can be optimized further, and even solved with pen and paper...

## Comments are closed.