TDD ✕ Property-based Testing (SwiftCheck) で数学パズルを検証してみる

Tl;Dr

TDD、Example-based Testing、Property-based Testing を組み合わせると良い感じ（かも？）

きっかけ

こんなTweetがタイムラインに流れていました。

数学の先生方との飲み会の席で、次のような算数マジックを見せてもらった。
6つの数字を書く。
となりあう数字を足した値の1桁目を1段下に書く。
これを繰り返して最後に出てくる数字を、6つの数字を書き終えた瞬間に言い当てるというもの。

いま自分でも納得できたので娘にもやってみせよう pic.twitter.com/ANhVNT21cs

— 三谷 純 Jun MITANI (@jmitani) 2017年7月27日

なるほどこれは面白い、と。

引用ツイートで解説がされていますが、以下のような法則があるようです。

（解説）
6つの数字をabcdefで表す。
bとeが「偶数と奇数」の組み合わせなら「a+f+5」の1桁目の数字が答え。
そうでないなら「a+f」の1桁目の数字が答え。

おもしろいですね。
なぜこのようになるかは・・。考えてみましょう(^^

話のネタとしても楽しそうですね

— 三谷 純 Jun MITANI (@jmitani) 2017年7月27日

しかしながら本当にすべての数字に対してこの答えが得られるのか？
気になります、気になりますが・・・私の数学力ではおよそ証明できないのは目に見えています。

そこで Property-based Testing な Framework である
SwiftCheckを利用して、無数のランダム値で検証してみたいと思います。
（ゆるい証明ってところでしょうか）

せっかくなので Example-based Testing も交えて TDD で行っていきます。

TDD

もう今日では、TDD（テスト駆動開発）は市民権を得ているので多くの方がご存知かと思いますが、
端的に言うと、テストを先に書いてからプロダクトコードを書くという開発手法の一つです。

RED -> GREEN -> リファクタリング、というリズムで進めていくのが特徴です。

Property-based Testing について

関数型言語HaskellのQuickCheckが元のテスティングフレームワークの一つで、
多数のランダム値を自動生成して、それをもとに検証を行うというものです。

明示的な入力値と期待値を持つ「Example-based Testing」に対して、
性質（Property）に注目するため「Property-based Testing」と呼ばれているようです。

英語のWikipediaを見ると、かなり多数の言語にポートされているのが分かります。
https://en.wikipedia.org/wiki/QuickCheck

今回はそのSwift版であるSwiftCheckを利用していきたいと思います。
https://github.com/typelift/SwiftCheck

SwiftCheckの導入

今回は手軽にCocoaPodsで導入したいと思います。

$ pod init

Podfile

target 'SwiftCheckMathMagic' do
  pod 'typelift/SwiftCheck'
end

$ pod install

Example-based で最初のテストを書く（RED）

まずは通常のAssert-equalベースのテスト、つまりExample-basedでテストを書きたいと思います。

func test_solveNumbers() {
    let answer = solveNumbers(6, 3, 9, 2, 1, 7)
    XCTAssertEqual(3, answer)
}

この時点ではsolveNumbersは無いのでコンパイルは通りません。
どこかのクラスに属すべきかも、と考えがよぎりますがTDDなのでシンプルに行きます。

コンパイルを通す（RED）

ではプロダクトコードを実装します。

public func solveNumbers(_ n1: UInt, _ n2: UInt, _ n3: UInt, _ n4: UInt, _ n5: UInt, _ n6: UInt) -> UInt {
    return 0
}

少々不格好にも見えますが、TDDではシンプルを良しとします。

とりあえずダミー実装として0を返すようにしました。
まずはコンパイルが通るようにするのが目的です。

試しにこの状態でテストを実行してみます。

test failure: -[SwiftCheckMathMagicTests test_solveNumbers()] failed:
XCTAssertEqual failed: ("3") is not equal to ("0") - 

期待通りテストは失敗しました。

これがTDDで言うところの最初の段階「RED」です。
意図的にテストを失敗させることで、間違っているのにテストが通るという状況を無くすことが出来ます。

Fake-it でテストをパスさせる（GREEN）

さて次にテストがパスする最小限のコードを記述します。
最低限のコードとは何か、それはすなわち3を固定で返すことです。

public func solveNumbers(_ n1: UInt, _ n2: UInt, _ n3: UInt, _ n4: UInt, _ n5: UInt, _ n6: UInt) -> UInt {
    return 3
}

これは「Fake-it」といって、ダミー値を返すことでまずはテストを成功する状態にするというTDD技法（と呼ぶほどでもないかもですが）です。

この状態でテストを実行するとめでたく「GREEN」になります。

冗長に感じるかもしれませんが、こうして一歩ずつ確実に進めていくのがTDDです。

プロダクトコードを実装する（GREEN）

さてテストは通りましたが本体ロジックは正しくありません。
実装していきたいと思います。

public func solveNumbers(_ n1: Int, _ n2: Int, _ n3: Int, _ n4: Int, _ n5: Int, _ n6: Int) -> Int {
    var xs: [Int] = [n1, n2, n3, n4, n5, n6]
    while xs.count > 1 {
        xs = solve(xs)
    }
    return xs.first!
}

func solve(_ xs: [Int]) -> [Int] {
    var ys: [Int] = []
    for (i, _) in xs.enumerated() {
        guard i < xs.count - 1 else { break }
        var n = xs[i] + xs[i + 1]
        if n > 9 {
            n = n - 10
        }
        ys.append(n)
    }
    return ys
}

ループやIndexアクセスが多用されていて少し嫌な匂いがしますが、今目指しているのはテストをパスするコードを書くことです。
テストを実行してみると「GREEN」になるのが分かります。

テストケースの追加を検討する

さてテストはパスしましたが、さすがに1ケースだけでは答えがあっているのか不安です。

冒頭のTweetでもありましたが、6つの数字を「abcdef」で表した場合に、bとeが「偶数と奇数」の組み合わせなら「a + f + 5」の1桁目が答え。
そうでなければ、「a + f」の1桁目が答え、だそうです。

現状のテストは後者のものになっているので、後者のケースはテストできてそうです。
なので、不足している前者のケースをテストとして追加したいと思います。

手元で「4, 2, 8, 1, 5, 3」という数字で計算してみましたが、
確かに「a + f + 5」の1桁目、すなわち「4 + 3 + 5」＝12の1桁目である「2」が答えになることを確認しました。

テストケースを追加する（GREEN）

これはテストコードを追加するだけなので簡単です。

func test_solveNumbers() {
    let answer = solveNumbers(6, 3, 9, 2, 1, 7)
    XCTAssertEqual(3, answer)

    let answer2 = solveNumbers(4, 2, 8, 1, 5, 3)
    XCTAssertEqual(2, answer2)
}

answerとanswer2とあったりして、テストを追加する時に明らかに間違えそうですが一旦はこれで。

さてこれでテストを実行してみると、無事テストは「GREEN」になりました。
ロジックは恐らくあってそうですね。

Property-based Testing の導入を検討する

さて通常のテストであれば、境界値などを意識してテストを追加していくところです。
しかし、今回の場合の境界値とは何でしょうか？

法則にもあった「b」と「e」の組み合わせが偶数か奇数かでパターンは作れますが、
それ意外の入力値についてはどれだけテストすれば十分なのでしょうか？

そこで今回は無数のランダム値でテストを行える「Property-based Testing」でテストしてみたいと思います。

Property-based Testing でテストを書く

ではSwiftCheckを使ってコードを書いていきます。

失敗する雛形コードを書く（RED）

まずはTDDのセオリーに従って失敗する雛形コードを書いてみます。

func test_solveNumbers_property() {

    property("どんな数字に対しても「b + e」が偶数と奇数の組み合わせであれば「a + f + 5」の1桁目、そうでなければ「a + f」の1桁目になること")
        <- forAll { (a: UInt, b: UInt, c: UInt, d: UInt, e: UInt, f: UInt) in
        
        return false
    }
}

テストを実行すると当然のことながら失敗します。

テストコードを書く（RED）

今回は場合分けがあるので、偶数と奇数の判定や1桁目を取得といったロジックがテストコード内に入ることになります。
コードを単純化するためにIntのextensionを用意したいと思います。

extension UInt {
    var even: Bool { return self % 2 == 0 }
    var odd:  Bool { return !even }
    var oneDigit: UInt {
        return (self < 10)
            ? self
            : UInt(String("\(self)".characters.last!))!
    }
}

さてテストコード本体は以下のような感じになるでしょうか。

func test_solveNumbers_property() {

    property("どんな数字に対しても「b + e」が偶数と奇数の組み合わせであれば「a + f + 5」の1桁目、そうでなければ「a + f」の1桁目になること")
        <- forAll { (a: UInt, b: UInt, c: UInt, d: UInt, e: UInt, f: UInt) in
        
        let answer = solveNumbers(a, b, c, d, e, f)
            
        let isEvenAndOdd = (b.even && e.odd) || (b.odd && e.even)
        return isEvenAndOdd
            ? answer == (a + f + 5).oneDigit
            : answer == (a + f).oneDigit
    }
}

かなり愚直に書いていますが、まさにTweetの条件で示された性質（Property）を表したテストコードになっています。

さてこのテストを実行すると・・・なんと「RED」になってしまいました。

*** Failed! Proposition: どんな数字に対しても「b + e」が偶数と奇数の組み合わせであれば「a + f + 5」の1桁目、そうでなければ「a + f」の1桁目になること
Falsifiable (after 19 tests and 3 shrinks):
1
2
1
11
17
4
*** Passed 18 tests

失敗した原因を探る

さて何がマズかったのかExample-basedの方のテストを追加してみます。
さきほど失敗したと表示された「1, 2, 1, 11, 17, 4」の組み合わせを検証してみます。

let answer3 = solveNumbers(1, 2, 1, 11, 17, 4)
XCTAssertEqual(0, answer3)

b と e、すなわち 2 と 17 の組み合わせは偶数と奇数の組み合わせになるので、
「a + f + 5」、すなわち「1 + 4 + 5」＝10の1桁目である「0」が答えになるはずです。

テストを実行してみると、確かに失敗します。

test failure: -[SwiftCheckMathMagicTests test_solveNumbers()]
failed: XCTAssertEqual failed: ("0") is not equal to ("10") - 

そしてここで間違いに気づきます。
1桁目を求めるロジックが正しくないのです。

if n > 9 {
    n = n - 10
}

横着して書かれたこのコードが正しく動くのは「19以下の場合のみ」であり「20以上の場合」には正しい1桁目は求められません。

うーん、これはひどい。

修正してGREENにする

さて正しく直すのは簡単です。
なぜなら慎重に書いたテストコード側のextensionには正しく1桁目を求めるコードがあるからです（汗）

extension をプロダクトコードに移動する（Refactor）

さきほどのextensionは本体ロジックでも利用できそうですし、プロダクトコードに移しましょう。

UInt+extension.swift

public extension UInt {
    var even: Bool { return self % 2 == 0 }
    var odd:  Bool { return !even }
    var oneDigit: UInt {
        return (self < 10)
            ? self
            : UInt(String("\(self)".characters.last!))!
    }
}

また今回のようなことが起きないようにテストコードも書いておきます。

UInt+extensionTests.swift

func test_even_odd() {
    
    // 1
    XCTAssertTrue (UInt(1).odd)
    XCTAssertFalse(UInt(1).even)
    
    // 2
    XCTAssertTrue (UInt(2).even)
    XCTAssertFalse(UInt(2).odd)
}

func test_oneDigit() {
    
    // one-digit
    XCTAssertEqual(UInt(1).oneDigit, 1)
    XCTAssertEqual(UInt(3).oneDigit, 3)
    
    // two-digit
    XCTAssertEqual(UInt(21).oneDigit, 1)
    XCTAssertEqual(UInt(63).oneDigit, 3)
}

単純なテストで予想通りパスします。

プロダクトコードを修正する（GREEN）

ここまできたら、今度こそプロダクトコードを正しいものに修正します。
といっても簡単で、extensionのoneDigitを利用するように修正するだけです。

func solve(_ xs: [UInt]) -> [UInt] {
    var ys: [UInt] = []
    for (i, _) in xs.enumerated() {
        guard i < xs.count - 1 else { break }
        let n = (xs[i] + xs[i + 1]).oneDigit
        ys.append(n)
    }
    return ys
}

ごちゃっとした処理も減って、let宣言できるようになって良い感じです。

さて、まずはExample-basedのテストを実行すると・・・「GREEN」です！

では次にProperty-basedのテストも実行すると・・・こちらも「GREEN」になりました！

どんな値でテストされてる？

Property-basedはランダム値でテストされているということですが、どういった値がテストされているのか気になります。
試しにprintしてみると以下のように確かにいろんな値でテストが実行されています。

Test Case '-[SwiftCheckMathMagicTests.SwiftCheckMathMagicTests test_solveNumbers_property]' started.
0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 1
2, 1, 0, 0, 1, 2
0, 2, 2, 2, 0, 2
1, 4, 4, 4, 0, 1
4, 5, 3, 5, 1, 4
6, 2, 2, 3, 4, 6
1, 3, 6, 5, 6, 0
1, 4, 3, 6, 6, 2
2, 1, 6, 4, 2, 1
1, 5, 1, 4, 9, 1
7, 1, 4, 6, 11, 3
10, 6, 3, 0, 0, 8
7, 4, 3, 3, 2, 6
5, 11, 11, 1, 0, 3
15, 11, 12, 6, 15, 12
5, 8, 8, 13, 8, 13
8, 12, 15, 10, 5, 1
1, 15, 6, 1, 3, 6
6, 18, 13, 5, 9, 1
1, 10, 19, 14, 13, 0
6, 19, 9, 0, 6, 18
12, 7, 12, 5, 18, 18
11, 8, 15, 4, 19, 7
11, 22, 16, 8, 0, 13
10, 9, 15, 0, 11, 17
23, 6, 10, 16, 2, 26
4, 6, 14, 11, 11, 19
28, 7, 25, 27, 5, 12
8, 25, 6, 3, 14, 23
11, 4, 27, 5, 15, 12
4, 2, 1, 1, 15, 20
23, 32, 25, 31, 20, 12
16, 30, 30, 31, 22, 33
27, 16, 24, 4, 5, 26
30, 22, 35, 23, 26, 27
7, 30, 1, 22, 34, 27
31, 4, 11, 28, 3, 15
31, 11, 2, 14, 13, 5
33, 39, 11, 16, 13, 10
29, 0, 20, 33, 5, 15
11, 22, 24, 17, 6, 30
34, 27, 20, 15, 11, 21
10, 22, 3, 33, 27, 19
39, 19, 14, 11, 16, 5
9, 26, 24, 38, 21, 3
2, 14, 23, 36, 45, 31
33, 4, 27, 43, 3, 26
42, 10, 19, 18, 23, 27
25, 37, 21, 36, 15, 31
3, 7, 5, 22, 31, 19
4, 35, 22, 42, 23, 31
36, 26, 25, 22, 15, 10
48, 6, 21, 40, 5, 43
0, 32, 53, 50, 46, 37
29, 41, 5, 50, 42, 10
21, 23, 39, 29, 13, 20
11, 48, 37, 48, 12, 0
46, 41, 51, 32, 27, 45
5, 8, 2, 58, 12, 17
52, 41, 56, 23, 37, 27
0, 22, 23, 54, 21, 39
60, 51, 30, 20, 46, 35
27, 4, 52, 36, 6, 22
63, 64, 17, 46, 8, 59
26, 1, 60, 1, 47, 17
57, 1, 45, 10, 62, 21
20, 65, 46, 38, 3, 17
8, 12, 54, 38, 13, 65
51, 20, 13, 36, 4, 23
34, 27, 27, 11, 2, 15
40, 61, 62, 50, 19, 6
61, 11, 58, 35, 54, 27
1, 15, 57, 16, 48, 39
6, 35, 60, 31, 2, 62
27, 34, 9, 4, 33, 30
40, 5, 23, 44, 76, 7
24, 36, 57, 37, 7, 19
4, 32, 49, 8, 11, 25
74, 39, 19, 70, 16, 11
18, 25, 13, 52, 33, 15
50, 61, 60, 75, 74, 35
23, 82, 77, 65, 54, 27
26, 64, 40, 26, 68, 58
51, 60, 74, 56, 84, 76
64, 15, 81, 39, 84, 75
66, 86, 23, 34, 86, 17
19, 44, 15, 84, 23, 50
36, 40, 2, 7, 41, 66
33, 1, 82, 79, 16, 22
43, 33, 85, 6, 19, 79
37, 10, 6, 85, 64, 25
87, 92, 81, 11, 5, 7
0, 15, 31, 25, 39, 87
45, 61, 88, 38, 52, 25
61, 27, 18, 77, 40, 48
24, 36, 32, 63, 17, 8
48, 40, 4, 21, 63, 78
26, 95, 96, 46, 60, 1
64, 44, 2, 12, 29, 33
*** Passed 100 tests

これらすべての組み合わせに対して、テストはパスしたということになります！

リファクタリング（Refactor）

さて2種類の単体テストが出来たので、安心してリファクタリングに取り組めます。
そうです、TDDではリファクタリングという作業が最後に待っているのです。

テストコードのリファクタリング

前にも触れましたが、現状のExample-basedなテストは一時変数が多くてテスト追加時に明らかにミスをしそうです。

func test_solveNumbers() {
    let answer = solveNumbers(6, 3, 9, 2, 1, 7)
    XCTAssertEqual(3, answer)
    
    let answer2 = solveNumbers(4, 2, 8, 1, 5, 3)
    XCTAssertEqual(2, answer2)
    
    let answer3 = solveNumbers(1, 2, 1, 11, 17, 4)
    XCTAssertEqual(0, answer3)
}

ここではシンプルにインライン化してしまいたいと思います。

func test_solveNumbers() {
    XCTAssertEqual(3, solveNumbers(6, 3, 9,  2,  1, 7))
    XCTAssertEqual(2, solveNumbers(4, 2, 8,  1,  5, 3))
    XCTAssertEqual(0, solveNumbers(1, 2, 1, 11, 17, 4))
}

意図は十分伝わりますし、テストも追加しやすいですね。

もちろんテストは「GREEN」です。

プロダクトコードのリファクタリング

こちらも前に触れましたが、現状のループベースのコードは明らかに不吉な匂いがします。

public func solveNumbers(_ n1: UInt, _ n2: UInt, _ n3: UInt, _ n4: UInt, _ n5: UInt, _ n6: UInt) -> UInt {
    var xs: [UInt] = [n1, n2, n3, n4, n5, n6]
    while xs.count > 1 {
        xs = solve(xs)
    }
    return xs.first!
}

func solve(_ xs: [UInt]) -> [UInt] {
    var ys: [UInt] = []
    for (i, _) in xs.enumerated() {
        guard i < xs.count - 1 else { break }
        let n = (xs[i] + xs[i + 1]).oneDigit
        ys.append(n)
    }
    return ys
}

関数型プログラミングの力を借りて、宣言ベースのコードにします。

public func solveNumbers(_ n1: UInt, _ n2: UInt, _ n3: UInt, _ n4: UInt, _ n5: UInt, _ n6: UInt) -> UInt {
    return solve([n1, n2, n3, n4, n5, n6])
}

private func solve(_ xs: [UInt]) -> UInt {
    guard xs.count > 1 else { return xs.first! }
    let ys = zip(xs, xs.dropFirst()).map { ($0.0 + $0.1).oneDigit }
    return solve(ys)
}

ループ処理を追う必要もなくなりましたし、コードもだいぶ短くなりました。
Haskellで言うところのzipWithがあるとさらにスッキリしそうですが、TDDなのでYAGNIでいきましょう。

完成

といった感じで出来上がったコード全体は以下のとおりです。

MathMagic.swift

import Foundation

public func solveNumbers(_ n1: UInt, _ n2: UInt, _ n3: UInt, _ n4: UInt, _ n5: UInt, _ n6: UInt) -> UInt {
    return solve([n1, n2, n3, n4, n5, n6])
}

private func solve(_ xs: [UInt]) -> UInt {
    guard xs.count > 1 else { return xs.first! }
    let ys = zip(xs, xs.dropFirst()).map { ($0.0 + $0.1).oneDigit }
    return solve(ys)
}

UInt+extension.swift

import Foundation

public extension UInt {
    var even: Bool { return self % 2 == 0 }
    var odd:  Bool { return !even }
    var oneDigit: UInt {
        return (self < 10)
            ? self
            : UInt(String("\(self)".characters.last!))!
    }
}

SwiftCheckMathMagicTests.swift

import XCTest
import SwiftCheck
@testable import SwiftCheckMathMagic

class SwiftCheckMathMagicTests: XCTestCase {
    
    override func setUp() {
        super.setUp()
    }
    
    override func tearDown() {
        super.tearDown()
    }
    
    func test_solveNumbers() {
        XCTAssertEqual(3, solveNumbers(6, 3, 9,  2,  1, 7))
        XCTAssertEqual(2, solveNumbers(4, 2, 8,  1,  5, 3))
        XCTAssertEqual(0, solveNumbers(1, 2, 1, 11, 17, 4))
    }
    
    func test_solveNumbers_property() {

        property("どんな数字に対しても「b + e」が偶数と奇数の組み合わせであれば「a + f + 5」の1桁目、そうでなければ「a + f」の1桁目になること")
            <- forAll { (a: UInt, b: UInt, c: UInt, d: UInt, e: UInt, f: UInt) in
                
            let answer = solveNumbers(a, b, c, d, e, f)
                
            let isEvenAndOdd = (b.even && e.odd) || (b.odd && e.even)
            return isEvenAndOdd
                ? answer == (a + f + 5).oneDigit
                : answer == (a + f).oneDigit
        }
    }
}

UInt+extensionTests.swift

class UInt_extensionTests: XCTestCase {
    
    override func setUp() {
        super.setUp()
    }
    
    override func tearDown() {
        super.tearDown()
    }
    
    func test_even_odd() {
        
        // 1
        XCTAssertTrue (UInt(1).odd)
        XCTAssertFalse(UInt(1).even)
        
        // 2
        XCTAssertTrue (UInt(2).even)
        XCTAssertFalse(UInt(2).odd)
    }
    
    func test_oneDigit() {
        
        // one-digit
        XCTAssertEqual(UInt(1).oneDigit, 1)
        XCTAssertEqual(UInt(3).oneDigit, 3)
        
        // two-digit
        XCTAssertEqual(UInt(21).oneDigit, 1)
        XCTAssertEqual(UInt(63).oneDigit, 3)
    }
}

プロジェクトも含めたコード全体はGitHubにおいておきました。
https://github.com/YusukeHosonuma/SwiftCheckMathMagic

最後に

というわけでTwitterにあった数学パズルからインスピレーションを受けて、
TDDを用い、Example-based Testing と Property-based Testing を組み合わせながら問題が正しいことを検証してみました。

Property-based Testing は使いどころが難しい印象はありますが、
適材適所でうまいこと使うようにすれば、よりプロダクトコードの信頼性をあげられるのではないかと思いました。