オイラープロジェクトの問題を解きながらSwiftらしいコーディングを探る #1(問題2) #Swift

この記事について

オイラープロジェクトの問題を解きながらSwiftらしいコーディングを探ります。
Swiftのversionは3.1を想定しています。
この記事では問題2を解いていきます。

#1なのに問題2なのはなぜ？

オイラープロジェクトの問題のうち記事にしやすそうな問題だけを取り上げているからです。

問題

原文

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.

翻訳

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%202 より引用

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

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

数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

解答の指針

まずフィボナッチ数列のSequenceをつくる
prefixで400万までの項を取り出す
filterで奇数の項を除く
reduceで足し合わせる

Sequenceプロトコルに準拠した型をつくれば、map, reduce, filterなど、Swiftの便利メソッドを使うことができます。
したがって、
(フィボナッチ数列のSequence).prefix { $0 < 4_000_000 }.filter { $0 % 2 == 0 }.reduce(0, +)
という計算をすれば解が得られます。

さらに、数列という数学上の概念がSwiftのSequenceプロトコルに準拠することは非常に直感的です。

解答

1. フィボナッチ数列を生成するSequenceを実装する

フィボナッチ数列を生成するSequenceを実装すれば答えはすぐそこです。

FibonacciSequence

struct FibonacciSequence: Sequence {
    // Sequenceに準拠するためにはmakeIterator()でIteratorProtocolに準拠した型を返す
    func makeIterator() -> FibonacciIterator {
        return FibonacciIterator()
    }
}

struct FibonacciIterator: IteratorProtocol {
    private var state = (0, 1)
    // IteratorProtocolに準拠するためにはnext()で列挙したい型のオプショナルを返す
    mutating func next() -> Int? {
        let nextValue = state.0 + state.1
        state = (state.1, nextValue)
        return nextValue
    }
}

2. 華麗にprefix, filter, reduce

answer

let answer = FibonacciSequence().prefix { 
    // 400万までの項を取り出す
    $0 < 4_000_000
}.filter { 
    // 奇数を除く
    $0 % 2 == 0 
}.reduce(0, +) // 合計を足し算

print("answer is \(answer)")

まとめ

Sequenceに準拠するだけで、map, filter, reduceといった便利メソッドを使うことができます。