泥庭

2012年12月20日

LINQ で LifeGame

Filed under: .NET — タグ: — yone64 @ 12:50 AM

この記事は、C#AdventCalendar2012の参加記事(20日目)です。

20121220ってことで、数字的に遊べたら面白いかな?と思って20日を希望してはみたものの、特に何も思いつかず、しかも覆面算の解があるわけでもないので(いや、あるかないか調べてないし、あってもネタにはできないんですけどね…)普通に進めます。

ところで、先日「Global Day of Coderetreat 2012 in Osaka」なるものに参加してきました。簡単に言うと、TDDでペアプロでひたすらLifeGameを作る会でした。詳細なルール等は適当にググれば出てくるので割愛しますが、1クールが45分と大変短いので大体時間切れになり完成しません。完成が目的ではないんですが、せっかくの面白テーマなので帰宅後追加実装してみました。(もちろんLINQで)
#あっそうそう、「ライフゲーム」ってググれば、ライフゲームが表示されるんですね。知らんかった。

LINQで物を考えるときは、とある集合から別の集合への変換を想定し、その変換ルールを定義するのが基本(?)です。
今回の場合は、ある世代の生命の集合から次の世代の生命の集合への変換を定義したいと思います。登場クラスは、生命を表すLifeクラス・世界を表すWorldクラス・この世の理を定義するGameMasterクラスといったところでしょうか?とりあえず、外枠だけ生成したのが、下記コードになります。

class Life
{
    public int X { get; set; }
    public int Y { get; set; }
}

class World : IEnumerable<Life>
{
    private List<Life> _lifes;

    public World(IEnumerable<Life> lifes)
    {
        this._lifes = lifes.ToList();
    }
    public IEnumerator<Life> GetEnumerator()
    {
        return this._lifes.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

static class GameMaster
{
    static World NextGeneration(this World world)
    {
        throw new NotImplementedException();
    }
}

WorldクラスにIEnumerable<T>を実装させていたり、NextGenerationメソッドが拡張メソッドになっていたりするあたりは、いろいろ議論の分かれるところだとは思いますが、素直でLINQっぽい気がしています。

で、肝心の変換ルールですが、次のような表を作ってみました。

今世代に生命が存在する場合に0.5pt、周囲に生命が存在する場合に生命数×1ptの重みづけを行い、列を足しています。この表より、次世代に生命が存在するかどうかは重みづけが2.5~3.5の範囲に収まることと同値であることがわかります。

生命の

有無
周囲の

次世代の

生命の有無
重みづけ
× 0.5
1 × 1.5
2 2.5
3 3.5
4 × 4.5
5 × 5.5
6 × 6.5
7 × 7.5
8 × 8.5
× ×
× 1 × 1
× 2 × 2
× 3 3
× 4 × 4
× 5 × 5
× 6 × 6
× 7 × 7
× 8 × 8

上記表のとおり実装したところ、NextGenerationメソッド内部ですが、こんな感じになりました。
うん、LINQっぽい。

public static World NextGeneration(this World world)
{
    var lifes = world.SelectMany(life => from x in Enumerable.Range(-1, 3)
                                            from y in Enumerable.Range(-1, 3)
                                            select new
                                            {
                                                X = life.X + x,
                                                Y = life.Y + y,
                                                Score = x == 0 && y == 0 ? 0.5 : 1
                                            })
                        .GroupBy(s => new { s.X, s.Y })
                        .Select(g => new { X = g.Key.X, Y = g.Key.Y, Score = g.Sum(a => a.Score) })
                        .Where(a => a.Score > 2 && a.Score < 4)
                        .Select(a => new Life { X = a.X, Y = a.Y });

    return new World(lifes);
}

…ますか…きこえますか…
…今…あなたの…心に…直接…呼びかけています…
レガシーコードを…生産…している場合では…ありません……
テストを…書くのです……
テストのない…コードは…レガシーコード…です…

ちょっと、流行に乗ってみましたが、そうですね、coderetreatですものテストが必須ですよね。
では、さっそくテストをば、とりあえず3ケースぐらいあればいいよね。

image

まず、1ケース目。

/// <summary>
/// NextGeneration のテスト
/// ケース1
/// ・周りに1つしかない生命は死ぬ
/// ・周りに2つしかない場合、誕生しない
/// <summary>
[TestMethod()]
public void NextGenerationTest1()
{
    World source = new World(new List<Life>
        {
            new Life{X = 1, Y = 1},
            new Life{X = 1, Y = 2},
        });
    World actual = source.NextGeneration();
    Assert.IsFalse(actual.Any());
}

楽勝。続いて2ケース目

/// <summary>
/// NextGeneration のテスト
/// ケース2
/// ・周りに生命が2つある生命は生きのこる
/// ・周りに生命が3つある生命は生きのこる
/// ・周りに生命が3つある場合、新しく生命が誕生する
/// </summary>
[TestMethod()]
public void NextGenerationTest2()
{
    World source = new World(new List<Life>
        {
            new Life{X = 1, Y = 1},
            new Life{X = 2, Y = 1},
            new Life{X = 1, Y = 2},
        });
    var expected = new List<Life>
        {
            new Life{X = 1, Y = 1},
            new Life{X = 2, Y = 1},
            new Life{X = 1, Y = 2},
            new Life{X = 2, Y = 2},
        };
    World actual = source.NextGeneration();
    CollectionAssert.AreEquivalent(expected, actual.ToList());
    CollectionAssert.AreEquivalent(expected, actual.NextGeneration().ToList());
}

これも楽勝?あれ、失敗した。
Lifeクラスが、EqualsとGetHashCodeを実装してないからですね。残念。
テストのために実装するのか?面倒だな。まぁ、とりあえず実装するか…

public override bool Equals(object obj)
{
    var life = obj as Life;
    return life != null &amp;&amp; this.X == life.X && this.Y == life.Y;
}

public override int GetHashCode()
{
    return this.X.GetHashCode() ^ this.Y.GetHashCode();
} 

ということで、再テスト。
今度はGreenを確認です。

/// <summary>
/// NextGeneration のテスト
/// ケース3
/// ・周りに生命が4つある生命は死ぬ
/// ・周りに生命が4つある場合、新しく生命は誕生しない
/// </summary>
[TestMethod()]
public void NextGenerationTest3()
{
    World source = new World(new List<Life>
        {
            new Life{X = 1, Y = 2},
            new Life{X = 2, Y = 1},
            new Life{X = 2, Y = 2},
            new Life{X = 2, Y = 3},
            new Life{X = 3, Y = 1},
        });
    var expected = new List<Life>
        {
            new Life{X = 1, Y = 1},
            new Life{X = 1, Y = 2},
            new Life{X = 1, Y = 3},
            new Life{X = 2, Y = 1},
            new Life{X = 2, Y = 3},
            new Life{X = 3, Y = 1},
        };
    World actual = source.NextGeneration();
    CollectionAssert.AreEquivalent(expected, actual.ToList());
}

これもさくっと通過。C0もC1も100%だし完璧。
(※注 LINQでロジックを書くと、いとも簡単に100%のカバレッジが得られます。100%のカバレッジが求められる現場に遭遇した際ご検討下さい。(滅))

…ますか…きこえますか…
そうでは…ありません……TDDです…テストファーストです。

誰か:え~い、まどろっこしい。ペアプロするよ。

(ここからは1人2役ペアプログラミングをやります。おつきあい下さい。)

誰か:まず、テストから書きましょう。テスト対象は?
よね:NextGenerationメソッドですね。
誰か:では、その責務は?
よね:当世代の生命一覧を受け取って、次世代の生命の一覧を返します。
誰か:ちょっとテスト対象としては仕事が多すぎる感じがしますね。ちょっと細かく分けてみましょう。ちなみにどんな感じの処理を行う予定?
よね:えっと、現世代の生命をベースにScoreを生成し、それをセル毎に集計し、判定する感じですかね?
誰か:じゃ、その単位でやってみますか?
よね:でも、メソッド分けると匿名型が使えないので…
誰か:つべこべ言わない。必要なクラスは定義する。とりあえず、集計用のセルをクラスにして、そこに判定メソッドを持たせましょうか。
よね:え~そこからですか?当日飽きるほどやりましたが…
誰か:仕方がない、ちょっと、はしょりましょうか。どうせ、詳しくやると長くなりすぎるし。とりあえずIFはこんな感じにして、あっScoreは無視しましたよ。

class Cell
{
    public int Around { get; set; }
    public bool IsAlive { get; set; }

    public bool NextGenerationIsAlive();
}

誰か:テストは、死→死、死→生、生→生、生→死の4パターンとそれぞれのエッジケースを含めて、これぐらいあれば十分ね。

[TestMethod()]
public void 誕生テスト()
{
    var cell = new Cell { Around = 3, IsAlive = false };
    Assert.IsTrue(cell.NextGenerationIsAlive());
}

[TestMethod()]
public void 誕生しないテスト()
{
    var cell = new Cell { Around = 2, IsAlive = false };
    Assert.IsFalse(cell.NextGenerationIsAlive());

    cell = new Cell { Around = 4, IsAlive = false };
    Assert.IsFalse(cell.NextGenerationIsAlive());
}

[TestMethod()]
public void 生きのこるテスト()
{
    var cell = new Cell { Around = 2, IsAlive = true };
    Assert.IsTrue(cell.NextGenerationIsAlive());

    cell = new Cell { Around = 3, IsAlive = true };
    Assert.IsTrue(cell.NextGenerationIsAlive());
}

[TestMethod()]
public void 死ぬテスト()
{
    var cell = new Cell { Around = 1, IsAlive = true };
    Assert.IsFalse(cell.NextGenerationIsAlive());

    cell = new Cell { Around = 4, IsAlive = true };
    Assert.IsFalse(cell.NextGenerationIsAlive());
}

誰か:そして、ここにすべてのテストをパスする、リファクタリング済のメソッドがあります。
よね:を~

public bool NextGenerationIsAlive()
{
    return this.Around == 3 || this.IsAlive &amp;&amp; this.Around == 2;
}

誰か:じゃ、次は集計箇所をやってみますか。キーボードどうぞ。

よね:集計を考えるのであれば座業を表すクラスが欲しいですね。あ、でもどうせXYだからSystem.Drawing.Pointで代用しちゃえばいいか。
誰か:クラス作ろうよ。ボソッ
よね:へい。クラスっと。

struct Coordinate
{
    public int X { get; set; }
    public int Y { get; set; }
}

よね:こっそりstructで。しかし、Lifeとほとんど同じだな。それとテスト対象のIFは、これで、いいか。めっちゃ、LINQっぽいIFだけど。

public static Cell CreateCell(this IGrouping<Coordinate, Coordinate> group);

誰か:ちなみに、グループ化のKeyとValueは?
よね:キーがセルの座標で、値はそのセルを中心とした3×3に含まれる生命の座標という感じです。
誰か:なるほど。
よね:で、テストは、っと。あら、IGroupingの実装クラスって提供されてないんだっけ?モックから作らねば。

class MockGroup<TKey, TElement> : IGrouping<TKey, TElement>
{
    private TKey _key;
    private IEnumerable<TElement> _value;

    public MockGroup(TKey key, IEnumerable<TElement> value)
    {
        this._key = key;
        this._value = value;
    }

    public TKey Key
    {
        get 
        {
            return this._key;
        }
    }

    public IEnumerator<TElement> GetEnumerator()
    {
        return this._value.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

よね:これで、ようやくテストができる。
誰か:とりあえず、中心に有りパターンとなしパターンで、2ケース用意しておけばいいんじゃないかな?
よね:ほい

[TestMethod()]
public void 中心に生命が存在するパターン()
{
    var groupInfo = new MockGroup<Coordinate, Coordinate>(
        new Coordinate { X = 1, Y = 1 },
        new List<Coordinate>()
        {
            new Coordinate { X = 1, Y = 1 },
            new Coordinate { X = 1, Y = 2 },
        });

    var cell = groupInfo.CreateCell();

    Assert.IsTrue(cell.IsAlive);
    Assert.AreEqual(1, cell.Around);
}

[TestMethod()]
public void 中心に生命が存在しないパターン()
{
    var groupInfo = new MockGroup<Coordinate, Coordinate>(
        new Coordinate { X = 1, Y = 1 },
        new List<Coordinate>()
        {
            new Coordinate { X = 2, Y = 1 },
            new Coordinate { X = 1, Y = 2 },
            new Coordinate { X = 0, Y = 2 },
        });

    var cell = groupInfo.CreateCell();
    Assert.IsFalse(cell.IsAlive);
    Assert.AreEqual(3, cell.Around);
}

よね:そしてテストをパスするメソッドがこちら。

public static Cell CreateCell(this IGrouping<Coordinate, Coordinate> group)
{
    return new Cell
    {
        Around = group.Count(c => !group.Key.Equals(c)),
        IsAlive = group.Any(c => group.Key.Equals(c))
    };
}

誰か:いいねぇ。どんどん行っちゃいましょう。
よね:あとは、集計元を生成するロジックぐらいですかね。座標クラスが3×3を返すのが自然っぽいですよね?まずIF。

public IEnumerable&lt;Coordinate&gt; AroundAndSelf();

よね:で、テスト

[TestMethod]
public void AroundAndSelfTest()
{
    var coordinate = new Coordinate { X = 1, Y = 1 };

    var expect = new List&lt;Coordinate&gt;
    {
        new Coordinate { X = 0, Y = 0 },
        new Coordinate { X = 0, Y = 1 },
        new Coordinate { X = 0, Y = 2 },
        new Coordinate { X = 1, Y = 0 },
        new Coordinate { X = 1, Y = 1 },
        new Coordinate { X = 1, Y = 2 },
        new Coordinate { X = 2, Y = 0 },
        new Coordinate { X = 2, Y = 1 },
        new Coordinate { X = 2, Y = 2 },
    };

    var actual = coordinate.AroundAndSelf();
    CollectionAssert.AreEquivalent(expect, actual.ToList());
}

よね:ほい。次、実装
誰か:とばすわね。
よね:そろそろ疲れてきたので、ポンポン行きます。

public IEnumerable<Coordinate> AroundAndSelf()
{
    var self = this;
    return from x in Enumerable.Range(-1, 3)
           from y in Enumerable.Range(-1, 3)
           select new Coordinate { X = self.X + x, Y = self.Y + y };
}

よね:あっそうそう、Lifeのメンバも変更しといて、それに対するリファクタもっと。

class Life
{
    public Coordinate Coordinate { get; set; }
}

よね:そうすると、NextGenerationメソッドの最終形はこんな感じかぁ。

public static World NextGeneration(this World source)
{
    var query = source.SelectMany(life => life.Coordinate.AroundAndSelf(), (x, y) => new { Target = y, Source = x.Coordinate })
                .GroupBy(a => a.Target, a => a.Source)
                .Where(g => g.CreateCell().IsAlive)
                .Select(g => new Life { Coordinate = g.Key });

    return new World(query);
}

誰か:後半かなり強引にLINQの形に持って行ったけど、一応用意したテストはすべて通るからいいんじゃない?
よね:なんかLifeいらない子になっちゃいましたね。
(小芝居終わり)

————————-

さてライフゲームを2パターンで作ってみたんですが、とりあえずで書いてみたLINQと、TDDで育てたLINQどちらが好きですか?
私は前者です。(をぃ)

なんていうか、TDDでLINQ書くと、処理を「.」で流しながら書く気持ちよさというか、ああやって、こうやって、それをこうするみたいに、考えながらその通りにかけるというのが損なわれる気がするんですよね。単にTDD力不足な感じもしますが。
#テスト可能な単位に処理を分割すると、匿名型が使えなくなるし、
#型定義するとEqualsとかGetHashCodeとか実装しないといけなくなるし、
それとは別に、拡張メソッドに当たる部分も切り分けてテストした方がいいんですかね?とか

今後の検討内容です。

そうそう、去年の記事を見つけたのですが、「LINQかわいいよう」とか「LINQえぐい」とかいう感想が書いてあって、どんなコードが書かれていたのかすごく気になります。

広告

コメントする »

まだコメントはありません。

RSS feed for comments on this post. TrackBack URI

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

WordPress.com Blog.