Project Euler #4 (largest palindrome product) in Swift

Question

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.

What I've so far learned about Swift is that while the Playground is very cool for tinkering around, it definitely does not like big loops. So this time, I coded parts in the playground, but moved it over to an actual executable project to run the final code.

I'm interested in knowing any Swift tricks I missed. I did implement a new trick I learned in this solution, the stride feature.

import Foundation

func printTimeElapsedWhenRunningCode(title:String, operation:()->()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed for \(title): \(timeElapsed) s")
}

extension Int {
    func isPalindrome() -> Bool {
        return self == self.reversed()
    }

    func reversed() -> Int {
        var original: Int = self
        var reversed: Int = 0

        while original > 0 {
            reversed *= 10
            reversed += original % 10
            original /= 10
        }

        return reversed
    }
}

func largestPalindrome() {
    var left: Int = 999
    var right: Int = 999

    var largestPalindrome: Int = 0

    for left in stride(from: 999, through: 100, by: -1) {
        for right in stride(from: left, through: 100, by: -1) {
            let product: Int = left * right
            if product > largestPalindrome && product.isPalindrome() {
                largestPalindrome = product
            }
        }
    }

    println(String(largestPalindrome))
}


printTimeElapsedWhenRunningCode("Largest Palindrome", largestPalindrome)

The printTimeElapsedWhenRunningCode function is borrowed from Brad Larson's answer here, and on my computer, it says the code is running in about 0.27 to 0.28 seconds.

Answer 1

Style

The reversed() function is only called from the isPalindrome function. Since the isPalindrome function is a 1-liner, it strikes me that there is no value added by exposing the reversed functionality at all, and that it can all be emedded in to the isPalindrome() call. There is no need for the method extraction in this case, it is overkill, and adds no significant value, while adding bulk to an extension on Int.

The problem constant 999 strikes me as being a good candidate for an input parameter. Instead you have encoded it as a magic number (three times) in the largestPalindrome() method. I feel it is more natural to have the input defined in the same way as the problem, use 3-digit numbers:

func largestPalindrome(limit: Int) -> Int {

note, the function receives the input limit, and it also returns the largestPalindrome from that limit. Note that the single-responsibility principle suggests that a function should return the value, and that you should print the result outside the function. The print in the function is.... ugly.

The code to turn the value 3 (for 3 digit numbers), would be:

• limit max (exclusive) \$10^3\$
• limit min (inclusive) \$10^{(3 - 1)}\$

Performance

There is a trivial, but effective optimization available for you, by breaking the inner loop when the product will always be less than the previously found largest.

Consider the code:

for left in stride(from: 999, through: 100, by: -1) {
    for right in stride(from: left, through: 100, by: -1) {
        let product: Int = left * right
        if product > largestPalindrome {
            if product.isPalindrome() {
                largestPalindrome = product
            }
        } else {
            break
        }
    }
}

In the above code, there is no point in testing smaller right values if they will never beat the current largest palindrome.

Answer 2

Some notes, mainly regarding the use of variables in the Swift language:

• You don't need a type annotation if the type can be inferred from the context, e.g.

  var original: Int = self
  var reversed: Int = 0
  

  can be shortened to

  var original = self
  var reversed = 0
  

  and the same applies to the largestPalindrome and product variable. This reduces the necessary number of changes if at some point you decide to use a different underlying data type, e.g. UInt64 instead of Int.

• You don't have to pre-declare variables that are used only in a for-loop, i.e.

  var left: Int = 999
  var right: Int = 999
  

  can simply be removed.

• Better variable names might be leftFactor and rightFactor.

Your function would then look like this:

func largestPalindrome() {
    var largestPalindrome = 0

    for leftFactor in stride(from: 999, through: 100, by: -1) {
        for rightFactor in stride(from: leftFactor, through: 100, by: -1) {
            let product = leftFactor * rightFactor
            if product > largestPalindrome && product.isPalindrome() {
                largestPalindrome = product
            }
        }
    }

    println(String(largestPalindrome))
}

(where you still have to apply the changes suggested in @rolfl's answer).

---

One final note. @rolfl has already given good arguments for not using an extension for the reversed() and isPalindrome() functions. But if you decide to build a "Project Euler utility library" then these functions should be implemented as generic functions, so that they work not only with Int but with all integer types, such as UInt or UInt64:

func reversedNumber<T : IntegerType>(var original: T) -> T {
    var reversed : T = 0
    while original > 0 {
        reversed *= 10
        reversed += original % 10
        original /= 10
    }
    return reversed
}

func isPalindrome<T : IntegerType>(num: T) -> Bool {
    return num == reversedNumber(num)
}

Example:

let foo = UInt64(123_456_789_123_456_789)
let bar = reversedNumber(foo)