Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
"Playground [...] definitely does not like big loops" Yeah, I can attest to that too. Kinda ridiculous actually –  Flambino Aug 25 at 15:33

2 Answers 2

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.

share|improve this answer
7  
Are you teaching yourself Swift via reviewing my Project Eulers? ;) –  nhgrif Aug 25 at 1:55
    
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 Aug 25 at 14:46
    
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. –  DarkDust Aug 25 at 14:51
1  
@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 Aug 25 at 15:05
1  
@DarkDust: Yes, I think you can add if left * left <= largestPalindrome { break } to the start of outer loop. –  Martin R Aug 25 at 16:27

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)
share|improve this answer
2  
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. –  nhgrif Aug 25 at 11:21
    
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. –  Colin Young Aug 25 at 14:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.