Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question
    
Isn't swap already built in? Quoting from the docs: "[...] you can use Swift’s existing swap function rather than providing your own implementation." –  Flambino Aug 23 at 15:01
    
Welp, apparently so. I just commented my swap function out and it still works just fine. –  nhgrif Aug 23 at 15:11

4 Answers 4

up vote 12 down vote accepted

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<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 }

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).

share|improve this answer
4  
Welcome to CodeReview Martin R! –  nhgrif Aug 23 at 19:44
4  
Yeah, my first posting here! –  Martin R Aug 23 at 19:45
    
Very nice. I reckoned there'd be a built-in "generator" type of some sort but I didn't know of it (and I failed to find it when I [quickly] looked, it seems) –  Flambino Aug 23 at 19:47
2  
@MartinR Feel free to come join the regulars in the 2nd Monitor sometime! –  syb0rg Aug 23 at 19:55
2  
Have you tried lazy()? There should be a version of filter which is lazy too. –  jtbandes Aug 24 at 17:12

Disclaimer: This is the most I've ever written in Swift. In other words, I barely know what I'm doing.

My gut feeling, Swift or no Swift, is the the findNextEvenFibonacci function is a little too specific on its own. I'd probably have another function that just generates the next Fibonacci number - even or odd. Its parity is then checked when summing up.

Also, I don't know how to feel about the tuple. While it's a simple, direct solution a tuple also feels a little opaque. Given that structs are quite powerful in Swift, a fully declared struct with some functions might be better.

Here's my naïve attempt:

struct FibonacciPair {
    var current: Int
    var previous: Int

    // using the name successor, since that's what Int
    // calls its next-in-sequence function
    func successor() -> FibonacciPair {
        return FibonacciPair(current: current + previous, previous: current)
    }
}

var generator = FibonacciPair(current: 1, previous: 1)
var sum = 0

while generator.current < 4_000_000 {
    if generator.current % 2 == 0 {
        sum += generator.current
    }
    generator = generator.successor()
}

let answer = sum

This is of course the sort of task that can be accomplished in a hundred different ways - the above is just what came to my mind first.

Aside: A few of those hundred other ways would be wholly procedurally without any functions or structs or other such contraptions - just a while loop and some variables. But I figure the idea here is also to play around with Swift.

Perhaps it'd be reasonable to extend Int with an isEven function, while we're at it. It's basic enough to be of general use as a core type extension, and it'd clean up the while loop above a little bit

extension Int {
    func isEven() -> Bool {
        return self % 2 == 0
    }
}

An alternative approach might be a Fibonacci-number generator that takes a closure. If only a closure could break the loop in which it's called instead of returning a bool... oh, well

func eachFibonacciNumber(iterator: (Int) -> (Bool)) {
    var current = 1
    var previous = 0

    while iterator(current + previous) {
        swap(&previous, &current)
        current += previous
    }
}

var sum = 0

eachFibonacciNumber() {
    // note: I definitely should be checking $0 < limit *before*
    // incrementing the sum... but it looks prettier if I don't :P
    if $0.isEven() { sum += $0 }
    return $0 < 4_000_000
}

let answer = sum

eachFibonacciNumber is a terrible Ruby'esque-but-not-really name, but you get the idea.

The limit could also just be an argument of course, which would avoid the bool return:

func fibonacciNumbersUpTo(limit: UInt, iterator: (Int) -> ()) {
    var current = 1
    var previous = 0

    while current < limit {
        iterator(current)
        swap(&previous, &current)
        current += previous
    }
}

var sum = 0
fibonacciNumbersUpTo(4_000_000) {
  if $0.isEven() { sum += $0 }
}

That's is probably the nicest, most straightforward of the bunch, in my opinion.

In either case, though, the idea is to have a way to get the regular Fibonacci sequence, and then deciding what to do with each number, rather than using a specific "only even Fibonacci numbers" device. Of course, either of the above could be form the basis for such a device.

In any case, going through Project Euler with Swift is a nice idea - I'll probably do the same :)

share|improve this answer
3  
Regarding your disclaimer: I think that can be said for most Swift developers. –  syb0rg Aug 23 at 16:48
    
@syb0rg Heh, yeah, I guess so. But considering I was quick to install the Xcode beta, but haven't gotten around to actually using it, I'm a little embarrassed nonetheless :) –  Flambino Aug 23 at 17:06

I can only suggest a faster* math-based algorithm:

The fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and etc.

The even ones are: 0 at index 0, 2 at index 3, 8 at index 6, 34 at index 9 and so on.

This suggests that every third fibonacci number is even (starting from 0). Let's try and prove this by induction:

WARNING MATH AHEAD

We have already proved a few base cases: index 0 and 3 are even fibonacci numbers.

Suppose Fibonacci(3 * n) is even.

Fibonacci(3 * (n + 1)) = Fibonacci(3n + 3)
                       = Fibonacci(3n + 2) + Fibonacci(3n + 1)
                       = 2 * Fibonacci(3n + 1) + Fibonacci(3n)

Since 2 * Fibonacci(3n + 1) is even, and by the induction hypothesis, Fibonacci(3n) is even, which means the sum is even as well, and so Fibonacci(3 * (n+1)) must also be even. Thus induction is complete and we have proved that every third Fibonacci number is even.

Next we have to prove that all the other numbers are not even. Since we know Fibonacci(1) = 1 is odd, then using the same logic as previously, we can show that Fibonacci(3n + 1) = 2 * Fibonacci(3n - 1) + Fibonacci(3n + 1) which is guaranteed to be odd. Similarly the result will be obtained for all n = 2 mod 3.

END OF MATH

This simplifies your task to just summing every third fibonacci number, with no need to check if it is even or not, as we have just proved they are the only even fibonacci numbers.

  • (DISCLAIMER) In the Python scripts I wrote to test this, the difference in time wasn't obvious until roughly 101000
share|improve this answer
    
To be clear, this just eliminates checking whether or not the result is even, right? –  nhgrif Aug 23 at 19:04
    
Interesting. I suspected there was a pattern to the parity, but... math is hard (and I was lazy) :P –  Flambino Aug 23 at 19:50
    
@nhgrif That's my understanding, although there are ways of generating the Nth number in the sequence that look interesting on their own. Of course, if you use an algorithm that still produces the entire sequence, uh, sequentially to find the Nth number, just checking parity along the way is no doubt simpler –  Flambino Aug 23 at 19:51
    
@nhgrif That is indeed correct. It saves on a few modulos. That is all. –  mleyfman Aug 24 at 0:45
    
Your statement about even Fibonacci numbers can also be deduced from the formula \$ \gcd(F_m, F_n) = F_{\gcd(m, n)} \$: \$ \gcd(F_m, 2) = \gcd(F_m, F_3) = F_{\gcd(m, 3)} \$ which is \$ F_3 = 2 \$ or \$ F_1 = 1 \$, depending on whether \$ m \$ is a multiple of 3 or not. –  Martin R Aug 24 at 11:36

Here is an approach using a general RecurrenceRelation struct which can be used to write any recurrence, not just the Fibonacci sequence (the Fibonacci sequence is defined by initial conditions (1,1) and the relation T[n] = T[n-1] + T[n-2]). I also define takeWhile as an extension to LazySequence so the functionality doesn't have to be built into RecurrenceRelation — Swift has a built-in prefix but it seems to be designed for random-access collections only.

struct RecurrenceRelation<E> : SequenceType {
    let initialCondition: [E]
    let relation: (T: [E], n: Int) -> E

    init(_ initialCondition: [E], relation: (T: [E], n: Int) -> E) {
        self.initialCondition = initialCondition
        self.relation = relation
    }

    func generate() -> GeneratorOf<E> {
        var memory = initialCondition
        var i = 0

        return GeneratorOf<E> {
            if i < memory.count { return memory[i++] }
            memory.append(self.relation(T: memory, n: memory.count))
            memory.removeAtIndex(0)
            return memory.last
        }
    }
}

extension LazySequence {
    func takeWhile(pred: S.Generator.Element -> Bool) -> LazySequence<SequenceOf<S.Generator.Element>> {
        return lazy(SequenceOf { () -> GeneratorOf<S.Generator.Element> in
            var g = self.generate()
            return GeneratorOf<S.Generator.Element> {
                let n = g.next()
                if n == nil || !pred(n!) { return nil }
                return n
            }
        })
    }
}

let fib = RecurrenceRelation([1, 1]) { (T, n) in T[n-1] + T[n-2] }

let n = reduce(lazy(fib).takeWhile { $0 < 4_000_000 }.filter { $0 % 2 == 0 }, 0, +)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.