Project Euler problem #14 (longest Collatz chain) in Swift

Question

This is my Swift code for finding the starting number, under one million, which produces the longest collatz chain.

var x = 1
var max = 0
var originalNum = 0

func collatzFunc(number: Int, originalNumber: Int){
    let oNum = originalNumber
    var num = number
    if num % 2 == 0{
        num = num/2
    } else {
        num = (3 * num) + 1
    }

    if num == 1{
        x += 1
    if max < x{
        max = x
        originalNum = oNum
    }
    return
    } else {
        x += 1
        collatzFunc(number: num, originalNumber: oNum)
    }
    }

for numbers in 1...1000000{
    x = 1
    collatzFunc(number: numbers, originalNumber: numbers)
}

print(originalNum)

This code is giving correct result but it's taking almost 5 seconds on my system to execute. I believe it can be done well under 1 sec. Where could I be wasting all that time?

Answer 1

Some suggestion to improve your code:

• The global variables max and originalNum should be named differently to match their purpose, possibly with explaining comments.

• The global variable x is used to keep track of the length of the current Collatz chain, this is better done by making the function return a value. That also allows to eliminate the second originalNumber parameter.

• collatzFunc() should just compute the Collatz chain length for a given number, and the caller of that function should compare that with previously computed values.

• Why assign var num = number if that value is then overwritten? You can simplify that to

  let num = number % 2 == 0 ? number / 2 : 3 * number + 1
  

• The indenting is not always correct, and the spacing is not consistent (e.g. always put a space before opening curly braces).

• The challenge asks for a number below 1 million, therefore the loop must be

  for number in 1..<1000000 { ... }
  

  and the singular form number is more appropriate here.

Putting it all together, this is how I would modify your code:

/// Compute the length of the Collatz chain starting at `number`.
func collatzFunc(number: Int) -> Int {
    if number == 1 {
        return 1
    }
    return 1 + collatzFunc(number: number % 2 == 0 ? number / 2 : 3 * number + 1)
}

var maxLength = 0 // Maximal length of Collatz chain found so far.
var maxNumber = 0 // Number for which this length is achieved.

for number in 1 ..< 1_000_000 {
    let length = collatzFunc(number: number)
    if length > maxLength {
        maxLength = length
        maxNumber = number
    }
}

print(maxNumber)

This is perhaps not faster than your version, but definitely better to read and therefore better to maintain.

You can also replace the recursive function by an iterative version

/// Compute the length of the Collatz chain starting at `number`.
func collatzFunc(number: Int) -> Int {
    var length = 1
    var num = number
    while num != 1 {
        num = num % 2 == 0 ? num / 2 : 3 * num + 1
        length += 1
    }
    return length
}

and check if that performs better.

As already mentioned in the comments, caching (or memoization) increases the performance dramatically. You'll find some caching solutions in the various answers to Project Euler problem 14 (longest Collatz sequence) in Swift 3. Here is a version using an array to cache all results for number up to a certain limit, this turned out to be quite fast:

var cache = [Int](repeating: 0, count: 1_000_000)
cache[1] = 1

func collatzFunc(number: Int) -> Int {
    if number < cache.count && cache[number] > 0 {
        return cache[number]
    }
    let length = 1 + collatzFunc(number: number % 2 == 0 ? number / 2 : 3 * number + 1)
    if number < cache.count {
        cache[number] = length
    }
    return length
}