Today’s challenge is Euler problem #4. I like this one in particular because of the fun I had with the string palindrome function. Got a better solution or a tweak? Drop it into the comments, tweet me, or email me.

```// Project Euler: Problem 4
// https://projecteuler.net/problem=4

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

func isPalindrome(s : String) -> Bool {
let n = countElements(s)
if n < 2 {return true}
if s[s.startIndex] == s[advance(s.endIndex, -1)] {
return isPalindrome(dropLast(dropFirst(s)))}
return false
}

func getPalindrome () -> String {
for d3a in stride(from: 9, through: 1, by: -1) {
for d3b in stride(from: 9, through: 1, by: -1) {
for d2a in stride(from: 9, through: 0, by: -1) {
for d2b in stride(from: 9, through: 0, by: -1) {
for d1a in stride(from: 9, through: 1, by: -1) { // Thanks ChristianGeek
for d1b in stride(from: 9, through: 1, by: -1) {
let first = d3a * 100 + d2a * 10 + d1a
let second = d3b * 100 + d2b * 10 + d1b
let product = first * second
if  isPalindrome(String(product)) {
return String(product)
}
}
}
}
}
}
}
}

getPalindrome()```

• Is there a reason not to just do the two 3-digit numbers as single loops?

func getPalindrome() -> String {
for first in stride(from: 999, through:100, by: -1) {
for second in stride(from: 999, through:100, by: -1) {
let product = first * second
if isPalindrome(String(product)) {
return String(product)
}
}
}
}

• You will be testing them in the wrong order. 999 * 100 will be tested before 998 * 998

• Yup, just discovered this when testing it out. 🙂

• Oh wait, just realized my way won’t do the tests in the correct order 🙂 This requires more thought.

• for first in stride(from: 999, through:100, by: -1) {
for second in stride(from: 999, through: first, by: -1) {

Maintains the right order of tests (highest possible values first), and also avoids testing the same pair twice (with first and second swapped).

• Nice!

• Okay after testing:

My solution took 867 steps, and returned the correct answer.

func getPalindrome () -> String {
for first in stride(from: 999, through:100, by: -1) {
for second in stride(from: 999, through: first, by: -1) {
let product = first * second
if isPalindrome(String(product)) {
return String(product)
}
}
}
}

• d1a and d1b can both go through 1 instead of 0, since having one of the numbers end in 0 will result in a product of the two ending in zero, which would mean the palindrome would have to begin with zero (an impossibility). This results in 709 steps and the correct answer.

• Excellent point!

• Thanks! Also, palindromes with an even number of digits are always divisible by 11 (see Google for proofs). If we assume there is a six digit solution to this particular problem, we can replace the getPalindrome function with:

``` func getPalindrome () -> String { var max = 0 for first in stride(from: 990, through: 110, by: -11) { for second in stride(from: 999, through: first, by: -1) { if (max / first) > 999 { break } let product = first * second if (isPalindrome(String(product)) && product > max) { max = product } } } if (max > 0) { return String(max) } return "Not found" } ```

This drops it down to 388 steps and the correct answer.

• By starting all the second loops with a stride from(first through 0/1 by -1) you remove also the double calculations and you end up with 400 steps. I guess my code is correct

``` func Euler4improved() -> Int? { /* 867 runs //no optimizatoin * 709 runs //ignore zero's on begin/end * 400 runs //no double calculations */ for i1 in stride(from: 9, through: 1, by: -1) { for i2 in stride(from: i1, through: 1, by: -1) { for j1 in stride(from: 9, through: 0, by: -1) { for j2 in stride(from: j1, through: 0, by: -1) { for k1 in stride(from: 9, through: 1, by: -1) { for k2 in stride(from: k1, through: 1, by: -1) { let num1 = 100*i1 + 10*j1 + k1 let num2 = 100*i2 + 10*j2 + k2 let mult = num1 * num2 if(checkPalin(String(mult))) { return mult } } } } } } } return nil } ```