James Pine Has A Blog

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...