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