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)
}
}
}
}
}
}
}
return "Not found"
}
getPalindrome()
12 Comments
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)
}
}
}
return “Not Found”
}
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.
Your solution took 2888 steps and returned the wrong 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)
}
}
}
return “Not found”
}
From David Grandinetti: http://twitter.com/dbgrandi/status/494548213127729152
His #4 https://t.co/mdJc7fC9JO
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
}