Project Euler, Challenge #12 in Swift

Question

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Swift Code:

import Foundation

let numberOfRequiredFactors = 500

func nthTriangularNumber( n:Int ) -> Int {
    var number = 0
    
    for iterator in 0...n {
        
        number += iterator
        
    }
    
    return number
}

func findNumberOfFactors( number:Int ) -> Int {
    var numberOfFactors = 0
    
    for iterator in 1...number {
        if number % iterator == 0 {
            numberOfFactors++
        }
    }
    
    return numberOfFactors
}

var countOfTriangularNumbers = 1
var found = false
var foundNumber = 0

while !found {
    
    var numberOfFactors = findNumberOfFactors(nthTriangularNumber(countOfTriangularNumbers))
    
    if numberOfFactors > numberOfRequiredFactors {
        found = true
        foundNumber = nthTriangularNumber(countOfTriangularNumbers)
    }
    
    countOfTriangularNumbers++
    
}

println("The number is: \(foundNumber)")

Comments on making this code more efficient, making it more cleaner or violations of best practices would be highly appreciated. However, it did work for smaller numbers, which is how I tested if the logic is right.

Answer 1

The spacing on your parenthesis in your function declarations is odd and distracting. Try not to fight what autocomplete will give you. It should look like this:

func nameOfFunction(firstArgumentName: Int) -> Int

Notice the lack of spaces inside the parenthesis but the addition of the space between the argument name and its type? This is the expect formatting style for Swift function declaration.

---

Memoization

func nthTriangularNumber( n:Int ) -> Int {
    var number = 0

    for iterator in 0...n {

        number += iterator

    }

    return number
}

We can immediately improve upon this approach. We know that for any number n, the nth triangular number will be the n-1th triangular number + n, right?

So we can improve this approach by using some memoization.

Without changing the rules of this function (although, I think the name needs some work), we can use a local struct to hold an array of the previously calculated triangular numbers.

Since Swift doesn't have the same sort of static function variables as Objective-C and other languages have, we have to consult this Stack Overflow question to figure out how to achieve something similar.

So... we're going to want a nested struct that looks like this:

struct Memoizer {
    static var triangularNumbers: [Int] = []
}

Now we'll use this Memoizer.triangularNumbers array to memoize triangular numbers so nothing is ever calculated more than once. Perhaps this makes sense as an extension to Int though?

extension Int {
    func triangularNumber() -> Int {
        struct Memoizer {
            static var triangularNumbers: [Int] = [0]
        }

        let lastIndex = Memoizer.triangularNumbers.count - 1
        for n in lastIndex...self {
            let next = Memoizer.triangularNumbers[n] + n
            Memoizer.triangularNumbers.append(next)
        }

        return Memoizer.triangularNumbers[self]
    }
}

So, if we try to find 500's triangular number, it still takes just as long as it would have taken using your approach (assuming we've not previously found any other triangular numbers) (and maybe slightly longer since we have to allocate memory for the array). But once we've calculated the 500th triangular number, anything less than 500 is a simply array look up. And calculating the 501st triangular number is a matter of grabbing the 500th and adding 501 to it.

That last point is the most important part here though.

In your current implementation, each iteration of your while loop takes progressively longer than the previous one. Your countOfTriangularNumbers is also the count of addition operations you have to do per loop to calculate that particular triangular numbers.

Using the implementation I just suggested, your number of addition operations to calculate the triangular number stays at a constant one.

The difference between one addition operation and two addition operations may not be measurable. But by the 500th or 1000th or more iteration of your loop, the difference between one addition operation and 500 addition operations starts to become noticeable. (And this is minor addition to the time it takes... but when we do find the number, we have to then recalculate it inside your if branch).

---

There is still a lot to work on for this problem, but I think this answer sets you down a very good path. Think about what this memoization is doing for us, and try to see where we can apply it in other places (especially as you work through Project Euler).