2
\$\begingroup\$

I just finished Project Euler #9 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^2 + b^2 = c^2 For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

import Foundation

func getSpecialPythagoreanTriplet(sum:Int) -> Int {

    for var c = 2; c < sum; c++ {

        for var b = 1;b < c; b++ {

            for var a = 0; a < b; a++ {

                if (sum % (a + b + c)) == 0 && a * a + b * b == c * c {
                    let minSum = a + b + c
                    a *= sum / minSum
                    b *= sum / minSum
                    c *= sum / minSum
                    return a * b * c
                }
            }
        }

    }
    return -1
}

func euler9() {
    let number = getSpecialPythagoreanTriplet(1_000)

    println(number)
}

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

printTimeElapsedWhenRunningCode(euler9)

The code executes in 0.000274002552032471 s

\$\endgroup\$
2
\$\begingroup\$

Your program is quite fast, but that is a bit of a lucky coincidence. The Pythagorean triplet with sum 1000 is (200, 375, 425). This is not a primitive Pythagorean triplet but (8, 15, 17) multiplied by 25.

So your program finds (8, 15, 17) quickly and from there "jumps" to the solution. That is fine and solves the Project Euler problem. But if you want a solution for arbitrary sums then one can do better. On my computer, your program needs

  • 0.0004 seconds to find the solution for sum = 1000, but
  • 0.014 seconds to find the solution for sum = 928, and
  • 1.9 seconds to find that there is no solution for sum = 1001.

The key point is that your method uses three nested loops, which is not necessary because only two of the variables a, b, c can be chosen freely and the last is determined by \$ a+b+c = \text{sum} \$.

From the condition a < b < c one can also restrict the possible ranges. If we start with a in the outermost loop then

$$ \text{sum} = a + b + c \ge a + (a + 1) + (a + 2) = 3 \, a + 3 \implies a \le (\text{sum} - 3)/3 $$

and for b we have

$$ \text{sum} = a + b + c \ge a + b + (b + 1) = a + 2 \, b + 1 \implies b \le (\text{sum} - 1 - a)/2 \quad . $$

So your function would be

func getSpecialPythagoreanTriplet(sum:Int) -> Int {

    for var a = 1; a <= (sum - 3)/3; a++ {
        for var b = a + 1; b <= (sum-1-a)/2; b++ {
            let c = sum - a - b
            if a*a + b*b == c*c {
                return a*b*c
            }
        }
    }
    return -1
}

This method needs about 0.0002 seconds to find the solution (or it's non-existence) in all three test cases (sum = 1000, 928, 1001).

One note regarding your function name: It might be unclear what is "special" in getSpecialPythagoreanTriplet(). Also the "Coding Guidelines for Cocoa" recommend the "get" prefix only for functions that return some value indirectly. A better name for your function would be something like

func pythagoreanTripletWithSum(sum:Int) -> Int
\$\endgroup\$
  • \$\begingroup\$ Very elegant solution! I did not think to write down the equations. Thanks. \$\endgroup\$ – Mehdi.Sqalli Dec 25 '14 at 12:04
  • \$\begingroup\$ @Mehdi.Sqalli: You are welcome! I have added a note about the function naming. \$\endgroup\$ – Martin R Dec 25 '14 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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