Project Euler #14 in Swift - Longest Collatz sequence

Question

I just finished Project Euler #14 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.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

import Foundation

func collatzSequenceForNumber(var number:Int, inout steps:[Int]) -> Int {

    var numberOfSteps = 0
    var found = false
    let initialNumber = number

    while (found == false) {

        if number % 2 == 0 {
            number /= 2
        } else {
            number = (number * 3 + 1) / 2
            numberOfSteps++
        }

        found = number < steps.count ? steps[number] > 0 : false
        numberOfSteps++
    }

    numberOfSteps += steps[number]
    steps[initialNumber] = numberOfSteps

    return numberOfSteps
}

func longestCollatzSequence(maxNumber:Int) -> (Int, Int) {
    var collatzSequence = (number:0, steps:0)
    var steps:[Int] = [Int](count: maxNumber, repeatedValue: 0)
    steps[1] = 1

    for var number = 2; number < maxNumber; number++ {

        let steps = collatzSequenceForNumber(number, &steps)
        if steps > collatzSequence.steps {
            collatzSequence = (number, steps)
        }
    }

    return collatzSequence
}

func euler14() {

    let result:(number:Int, steps:Int) = longestCollatzSequence(999_999)

    println(result.number)
}

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

printTimeElapsedWhenRunningCode(euler14)

The code executes in 0.07s.

Answer 1

collatzSequenceForNumber() returns the length of the Collatz sequence and not a sequence itself, so a better name might be collatzLength():

func collatzLength(var number:Int, inout steps:[Int]) -> Int {
    var numberOfSteps = 0
    let initialNumber = number
    // ...
}

The steps parameter is an array used as cache. But in longestCollatzSequence(), the same name steps is used for both the caching array and the computed number of steps. For more consistence, I would suggest to use steps for the number of steps only and a different name cache for the caching array:

func collatzLength(var number:Int, inout cache:[Int]) -> Int {
    var steps = 0
    let initialNumber = number
    // ...
    return steps
}

The number parameter is declared as a variable and modified in the function. That is fine generally, but here you need the original value of the parameter at the end of the function. It might be clearer to treat the parameter as constant and modify a local copy:

func collatzLength(number:Int, inout cache:[Int]) -> Int {
    var steps = 0
    var n = number
    // ...
    cache[number] = steps
    return steps
}

The expression

found = number < steps.count ? steps[number] > 0 : false

can simpler be written as

found = number < steps.count && steps[number] > 0

and I prefer if (!found) to if (found == false). But you don't need the found variable at all, as this condition can be put directly into the while() expression.

So now we have

func collatzLength(number:Int, inout cache:[Int]) -> Int {
    var steps = 0
    var n = number

    while n >= cache.count || cache[n] == 0 {
        if n % 2 == 0 {
            n /= 2
        } else {
            n = (n * 3 + 1) / 2
            steps++
        }
        steps++
    }

    steps += cache[n]
    cache[number] = steps
    return steps
}

Interestingly, this is a tiny bit faster than your original version (0.027 s instead of 0.032).

You can improve the performance a bit by taking advantage of the fact that the caching array is filled sequentially. So (in the context of this program)

    while n >= cache.count || cache[n] == 0 {

can be replaced by

   while n >= number {

and this reduces the time to 0.016 s.

In longestCollatzSequence() you are using a tuple with named components (number:0, steps:0) internally, but return an unnamed tuple (Int, Int). In the calling function euler14() the return value is assigned to a named tuple again. I would recommend to stick to one variant, e.g. the named tuple:

func longestCollatzSequence(maxNumber:Int) -> (number: Int, steps: Int) {
    var collatzSequence = (number:0, steps:0)
    var cache:[Int] = [Int](count: maxNumber, repeatedValue: 0)
    cache[1] = 1

    for var number = 2; number < maxNumber; number++ {
        let steps = collatzLength(number, &cache)
        if steps > collatzSequence.steps {
            collatzSequence = (number, steps)
        }
    }

    return collatzSequence
}

The for loop can equivalently be written using a Swift range:

for number in 2 ..< maxNumber { ... }

The main function can now be simplified to

func euler14() {
    let result = longestCollatzSequence(999_999)
    println(result.number)
}

or alternatively

func euler14() {
    let (number, steps) = longestCollatzSequence(999_999)
    println(number)
}

Finally note that your longestCollatzSequence() function considers all number below the given parameter, so you should either call

longestCollatzSequence(1_000_000)

or change the function to include the given upper bound.

Answer 2

The only optimisation I can think of is to move to Bitwise operations:

if number & 1 {  // Check if number is Odd
    number = (number * 3 + 1)>>1
    numberOfSteps++
} else {
    number >>=1
}

One more could be to run an internal for loop after the calculation is done like this: for var start= number; number < maxNumber; number>>1 { steps[start] = ++steps; }

So you can check this for loop if it performs better:

for var number = 2; number < maxNumber; number++ {

    let steps = ( steps[number] > 0)? steps[number] : collatzSequenceForNumber(number, &steps)
    if steps > collatzSequence.steps {
        collatzSequence = (number, steps)
    }
    for var start= number>>1; number < maxNumber; number>>1 {
        steps[start] = ++steps;
    }
}