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 n
th triangular number will be the n-1
th 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).