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.

• Flambino: "Playground [...] definitely does not like big loops" Yeah, I can attest to that too. Kinda ridiculous actually

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.

• nhgrif: Are you teaching yourself Swift via reviewing my Project Eulers? ;)
• DarkDust: Actually, you can immediately break after the assignment largestPalindrome = product. Since the loops already search from the "top", the first palindrome found will be the largest. And once we have that, there is no need executing any else afterwards. So the only if you need is this: if product.isPalindrome() { largestPalindrome = product ; break }
• DarkDust: Oh, and then we need a check after the inner loop to break the outer loop as well: if largestPalindrome != 0 { break }. IMHO an Int? would be nicer/"swifter" here, though.
• Martin R: @DarkDust: You are right that you can break the inner loop if you have found a palindrome. But you can not break the outer loop. There may be a larger palindrome product with a smaller left factor (and this actually happens).
• Martin R: @DarkDust: Yes, I think you can add if left * left <= largestPalindrome { break } to the start of outer loop.

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)

• nhgrif: You don't need a type annotation if the type can be inferred from the context -- I'm not sure if I'll ever be okay with this. I'm fully aware that Swift works like this--but I really, really don't like it. I prefer to be explicit.
• Colin Young: C# developer here... you'll get used to it, eventually, and may even start to prefer it. It's a small mindset shift -- you're still being explicit, it's in the value being assigned where the explicitness is, instead of having a variable type listed. It really does make code easier to read once you get used to it.