Project Euler solution #2 using Swift 3

Question

I just wanted some review and opinions. Any better implementations or suggestions would be great.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

var sequence = [1,2]
var index = 1
var sum = 0
repeat {
 sequence.append(sequence[index-1] + sequence[index])
 index = index + 1
} while sequence[sequence.endIndex - 1] < 4000000
sequence.popLast()
for numbers in sequence {
 if (numbers % 2 == 0) {
 sum += numbers
 }
}
print(sum)

• Alexander John: I know it's not the most abstract but that is what I need work on.
• Raziman T V: You can do this without keeping all the sequence in memory. Each time you find an element, process it and discard a previous element.

Answer 1

This post from Martin R is a good step in the right direction toward generalizing your problem.

The helper function at the top of the post is already what you need for making a more generalized loop:

public func sequence<T>(first: T, while condition: @escaping (T)-> Bool, next: @escaping (T) -> T) -> UnfoldSequence<T, T> {
 let nextState = { (state: inout T) -> T? in
 // Return `nil` if condition is no longer satisfied:
 guard condition(state) else { return nil }
 // Update current value _after_ returning from this call:
 defer { state = next(state) }
 // Return current value:
 return state
 }
 return sequence(state: first, next: nextState)
}

And the first example he uses with the above function is also a good hint toward what you need:

for f in sequence(first: (0, 1), while: { 1ドル <= 50 }, next: { (1,ドル 0ドル + 1ドル)}) {
 print(f.1)
}

As written, that loop prints the all the Fibonacci numbers up to 34, which is the largest Fibonacci number under 50.

So... how can we generalize this further?

First, let's make a function that simply sums and returns the value:

func sumFibonacciEvens(limit: Int) -> Int {
 // TODO: Implement
}

This is the basic form we want. Now, after implementing, we'd just pass in 4 million to get the answer we want, but we can easily reuse for any limit.

I'd say let's go one further though. Let's also make the "even only" part of this generic.

func sumFibonacciNumbers(lessThan limit: Int, condition: (Int) -> Bool) -> Int {
 // TODO: Implement
}

Now then, for this function, we pass in the limit (again, for the case we care about, four million). But we also pass in a closure that defines what elements to sum and what elements to ignore. So for your case, calling this function would look like:

let isEven: (Int) -> Bool = { number in
 return number % 2 == 0
}
let answer = sumFibonacciNumbers(lessThan: 4_000_000, condition: isEven)

This looks pretty good, right? So... how do we do it?

We're going to keep the sequence function defined earlier exactly as is and use it in our sumFibonacciNumbers function, which should look something like this:

public func sumFibonacciNumbers(lessThan limit: Int, condition: (Int) -> Bool) -> Int {
 var sum = 0
 for f in sequence(first: (0,1), while: { 1ドル <= limit }, next: { (1,ドル 0ドル + 1ドル)}) where condition(f.1) {
 sum += f.1
 }
 return sum
}

• Martin R: Haven't seen you for a while!
• nhgrif: Yeah, I've been super busy but lurking
• Sulthan: I would probably sum using reduce, that is, something like sequence(...).map { 0ドル.1 }.filter(condition).reduce(0, +)

Answer 2

@nhgrif already wrote a good review, but I'd like to point out the sequence(state:next:) function, which allows you to iterate over the actual numbers in the fibonacci sequence, rather than pairs of fibonacci numbers.

Also, Swift 3.1 contains the prefix(while:) function, which we can use together with sequence(state:next:) to avoid having to implement our own sequence(first:condition:next:) function.

let fibonacci = sequence(state: (0, 1)) { (pair: inout (Int, Int)) -> Int in
 pair = (pair.1, pair.0 + pair.1)
 return pair.0
}
fibonacci
 .prefix { 0ドル < 4_000_000 }
 .filter { 0ドル % 2 == 0 }
 .reduce(0, +) // => 4613732