patternswiftModerate
Project Euler #2 (Even Fibonacci numbers) in Swift
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:
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 = sumOfEvenFibonnaccisSolution
The following is similar to Flambino's approach, but creates a Swift
the elements:
See here for more information about sequences and generators.
This nice application made me actually understand how you can create your own sequences.
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:
SequenceType so that you can use the Swift library functionsfilter() and reduce() to iterate overthe 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 numbersbefore 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.