HiveBrain v1.2.0
Get Started
← Back to all entries
patternswiftModerate

Project Euler #2 (Even Fibonacci numbers) in Swift

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
swiftfibonaccinumbersprojecteulereven

Problem

I figured working through Project Euler problems in Swift would be a good way to learn any tips or tricks. For example, tuples are something I'm not used to using, but they proved useful here. Using things makes me more confident with them, so perhaps this will help me find other uses for them in the future.


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.

Here is my solution:

func swap(inout left: Any, inout right: Any) {
    let swap = left
    right = left
    left = swap
}

func findNextEvenFibonacci(var firstFibonacci: Int = 0, var secondFibonacci: Int = 1) -> (Int, Int) {
    do {
        firstFibonacci += secondFibonacci
        swap(&firstFibonacci, &secondFibonacci)
    } while firstFibonacci % 2 != 0

    return (firstFibonacci, secondFibonacci)
}

let maxFibonacci: Int = 4_000_000
var fibonacci: (first: Int, next: Int) = (0,1)
var sumOfEvenFibonnaccis: Int = 0

while fibonacci.next < maxFibonacci {
    fibonacci = findNextEvenFibonacci(firstFibonacci: fibonacci.first, secondFibonacci: fibonacci.next)
    sumOfEvenFibonnaccis += fibonacci.first
}

let answer = sumOfEvenFibonnaccis

Solution

The following is similar to Flambino's approach, but creates a Swift
SequenceType so that you can use the Swift library functions
filter() and reduce() to iterate over
the elements:

struct FibonacciSequence : SequenceType {
    let upperBound : Int

    func generate() -> GeneratorOf {
        var current = 1
        var next = 1
        return GeneratorOf() {
            if current > self.upperBound {
                return nil
            }
            let result = current
            current = next
            next += result
            return result
        };
    }
}

let fibseq = lazy(FibonacciSequence(upperBound: 4_000_000))
let sum = reduce(fibseq.filter { $0 % 2 == 0 }, 0) { $0 + $1 }


See here for more information about sequences and generators.
This nice application made me actually understand how you can create your own sequences.

lazy() creates a LazySequence, whose filter() method returns the elements "on demand", e.g. as needed in the summation. The
filter() function would return an array of all even Fibonacci numbers
before starting the summation. (Kudos to @jtbandes for his suggestion).

Update: Due to major changes in the Swift programming language,
the above code does not compile anymore with the current Swift 2.1/Xcode 7. Here is an updated version fore anybody's convenience:

struct FibonacciSequence : SequenceType {
    let upperBound : Int

    func generate() -> AnyGenerator {
        var current = 1
        var next = 1
        return anyGenerator {
            if current > self.upperBound {
                return nil
            }
            let result = current
            current = next
            next += result
            return result
        };
    }
}

let fibseq = FibonacciSequence(upperBound: 4_000_000).lazy
let sum = fibseq.filter { $0 % 2 == 0 }.reduce(0) { $0 + $1 }

Code Snippets

struct FibonacciSequence : SequenceType {
    let upperBound : Int

    func generate() -> GeneratorOf<Int> {
        var current = 1
        var next = 1
        return GeneratorOf<Int>() {
            if current > self.upperBound {
                return nil
            }
            let result = current
            current = next
            next += result
            return result
        };
    }
}

let fibseq = lazy(FibonacciSequence(upperBound: 4_000_000))
let sum = reduce(fibseq.filter { $0 % 2 == 0 }, 0) { $0 + $1 }
struct FibonacciSequence : SequenceType {
    let upperBound : Int

    func generate() -> AnyGenerator<Int> {
        var current = 1
        var next = 1
        return anyGenerator {
            if current > self.upperBound {
                return nil
            }
            let result = current
            current = next
            next += result
            return result
        };
    }
}

let fibseq = FibonacciSequence(upperBound: 4_000_000).lazy
let sum = fibseq.filter { $0 % 2 == 0 }.reduce(0) { $0 + $1 }

Context

StackExchange Code Review Q#60875, answer score: 17

Revisions (0)

No revisions yet.