ペアプロでTDDやってみよう(ライフゲーム) その3

その1、その2と続いて、今回はライフゲームTDDその3です。なかなか完了しない、誕生の処理を完成させたいと思っておりますが、どうなることやら。

前回はスパイクをへてCellクラスを抽出し、TDDで実装しました。このあたりのコーディング、本来はTODOリストに積みながらやったほうがよかった気がします。後知恵は正しいものなので、いまさらですがTODOリストに(もう終わった)タスクを書いておきます。

  1. 初期パターンを渡せる
  2. グリッドのデータ構造をスパイクする
  3. Cellを実装する
  4. 死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。 <- いまここ
  5. 生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
  6. 生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
  7. 生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。
  8. テストをわかりやすく修正する。

さて、Cellクラスを書く前にスパイクしたコードを見直しておきます。うまくいけば、これが誕生の実装に使えるはずです。

life.py

class GameOfLife(object):
    ...

    def prepare_next_generation(self, cells):
        for cell in cells:
            if self.will_born(cell.neighbours):
                cell.born()

    def will_born(self, neighbours):
        alive_cells = 0
        for cell in neighbours:
            if cell.is_alive():
                alive_cells += 1
        return alive_cells == 3

なんとなく良さそうな気がしますが、テストがないので不安ですね。後付けではありますが、テストを書きます。

life_test.py

    def test_will_born_true(self):
        game = GameOfLife(pattern='')

        cells = [Cell() for i in range(8)]
        cells[0].live()
        cells[1].live()
        cells[2].live()
        self.assertTrue(game.will_born(cells))

    def test_will_born_false(self):
        game = GameOfLife(pattern='')

        cells = [Cell() for i in range(8)]
        cells[0].live()
        cells[1].live()
        cells[2].live()
        cells[3].live()
        self.assertFalse(game.will_born(cells))

cells = [Cell() for i in range(8)]というのは内包表記という記法で、ここでは8個のCellオブジェクトをリストにしています。続く行で、そのうちいくつかを生きている状態にして、セルの状態が生死正しく切り替わるかテストしています。

こうしてテストを書いてみると、will_born()はCellを相手にしているので、GameOfLifeクラスにいるのは不適当ですね。リファクタリングでCellクラスに移動します。

life.py

class Cell(object):
    ....

    def will_born(self):
        alive_cells = 0
        for cell in self.neighbours:
            if cell.is_alive():
                alive_cells += 1
        return alive_cells == 3

life_test.py

class CellTest(unittest.TestCase):
    ....

    def test_will_born_true(self):
        cell = Cell()
        cell.neighbours = [Cell() for i in range(8)]
        cell.neighbours[0].live()
        cell.neighbours[1].live()
        cell.neighbours[2].live()
        self.assertTrue(cell.will_born())

    def test_will_born_false(self):
        cell = Cell()
        cell.neighbours = [Cell() for i in range(8)]
        cell.neighbours[0].live()
        cell.neighbours[1].live()
        cell.neighbours[2].live()
        cell.neighbours[3].live()
        self.assertFalse(cell.will_born())

cell.neighboursを作る処理が冗長ですが、これもあとで整理しましょう。それにこの形式だと、誕生に続く他のルールもうまいぐあいに表現できそうな気がします。

GameOfLifeクラスに残ったprepare_next_generation()、リファクタリングの影響も受けているので、これもテストしておきたいところです。乱暴ですが、1セルだけ渡してもメソッドは動くはずなのでその方法でテストします。


life_test.py

class GameOfLifeTest(unittest.TestCase):
    ....

    def test_prepare_next_generation(self):
        game = GameOfLife(pattern=None)
        cell = Cell()
        cell.neighbours = [Cell() for i in range(8)]
        cell.neighbours[0].live()
        cell.neighbours[1].live()
        cell.neighbours[2].live()
        game.prepare_next_generation([cell])

        cell.tick()
        self.assertTrue(cell.is_alive())

life.py

    def prepare_next_generation(self, cells):
        for cell in cells:
            if cell.will_born():
                cell.born()

なお、簡単なモックを自分で書いてテストする手もあります。こんなふうに書けば、CellStubを使ってprepare_next_generation()をテストすることもできます。もちろんモックライブラリを使ってもいいでしょう。

life_test.py

    def test_prepare_next_generation(self):
        game = GameOfLife(pattern=None)
        class CellStub(object):
            born_is_called = False
            def will_born(self): return True
            def born(self): self.born_is_called = True

        cells = [CellStub()]
        game.prepare_next_generation(cells)
        self.assertTrue(cells[0].born_is_called)

ここまで来れば、あとはCellを使って実際のグリッドを構築すれば、誕生のテストが通るようになるはずです。文字列で渡されるグリッドの情報をCellに変換してやる必要があります。Cellの構築ではneighboursを作ってやるところがキモになりそうです。

構築の部分もTODOリストに積んでおきましょう。すでに終わったつもりだった「初期パターンを渡せる」の再来です。文字列からCellを構築するところと、各Cellにneighboursを設定するところに分けていきます。

  1. 初期パターンを渡せる
  2. グリッドのデータ構造をスパイクする
  3. Cellを実装する
  4. 初期パターンのCellを構築する <- 追加 いまここ
  5. Cellのneighboursを設定する <- 追加
  6. 死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
  7. 生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
  8. 生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
  9. 生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。
  10. テストをわかりやすく修正する。

まずは文字列からCellを構築する部分です。アサートする部分は、あとで各セルの周囲のセルをアクセスする処理をイメージして、dict(Pythonの連想配列)から座標(x, y)をキーとしてCellオブジェクトを取り出せるという構造を書きました。(今まで逃げ回っていましたが、とうとう座標が出てきました。)

life_test.py

class GameOfLifeTest(unittest.TestCase):
    ....
    def test_build_cells(self):
        initial = '''
oo.
o..
...
'''
        cells = GameOfLife.build_cells(initial)
        self.assertEqual(cells[(0, 0)].is_alive(), True)
        self.assertEqual(cells[(1, 0)].is_alive(), True)
        self.assertEqual(cells[(2, 0)].is_alive(), False)
        self.assertEqual(cells[(0, 1)].is_alive(), True)
        self.assertEqual(cells[(1, 1)].is_alive(), False)
        self.assertEqual(cells[(2, 1)].is_alive(), False)
        self.assertEqual(cells[(0, 2)].is_alive(), False)
        self.assertEqual(cells[(1, 2)].is_alive(), False)
        self.assertEqual(cells[(2, 2)].is_alive(), False)

実装はこうです。

life.py

class GameOfLife(object):
    ....

    @staticmethod
    def build_cells(pattern):
        cells = {}
        for y, line in enumerate(pattern.strip().split("\n")):
            for x, c in enumerate(line.strip()):
                if c == 'o':   state = Cell.ALIVE
                elif c == '.': state = Cell.DEAD
                cells[(x, y)] = Cell(state)
        return cells

....

class Cell(object):
    ....

    def __init__(self, state=DEAD):
        self.state = state
        self.neighbours = []

ネストが深いのが気になりますが、あまり効果的なリファクタリングが思いつかないのでこのままにしておきます。Cellクラスも、コンストラクタで初期状態を渡せるよう変更しています。

続いて、build_cells()で構築したCellのneighboursを設定する処理です。これはみっちりテストを書くと面倒なので、角のセル(周囲は3つだけ)と中央のセル(周囲は8つ)だけ確認しています。テストデータ(フィクスチャ)を作るのが面倒な感じです。手抜きで、build_cells()を使ってテストデータ(フィクスチャ)を作る手もありますが、あとでなにか起きたとき原因箇所が見つかりにくくなるので、ちゃんと書きました。

    def test_connect_neighbours(self):
        cells = {
            (0, 0): Cell(), (1, 0): Cell(), (2, 0): Cell(),
            (0, 1): Cell(), (1, 1): Cell(), (2, 1): Cell(),
            (0, 2): Cell(), (1, 2): Cell(), (2, 2): Cell(),
        }
        GameOfLife.connect_neighbours(cells)
        self.assertEqual(sorted(cells[(0, 0)].neighbours),
            sorted([cells[(1, 0)], cells[(0, 1)], cells[(1, 1)]]))

        self.assertEqual(sorted(cells[(1, 1)].neighbours),
            sorted([
                cells[(0, 0)], cells[(1, 0)], cells[(2, 0)],
                cells[(0, 1)],                cells[(2, 1)],
                cells[(0, 2)], cells[(1, 2)], cells[(2, 2)],
            ]))

cellsを作るところやアサートのところは、多少なりともセルの配列がイメージしやすいように書いて、整形しています。

このテストを通すための実装は、ぐっと力を込めて書き上げました。

life.py

    @staticmethod
    def connect_neighbours(cells):
        for x, y in cells.keys():
            cell = cells[(x, y)]
            for dx, dy in [(dx, dy) for dx in range(-1, 2) for dy in range(-1, 2)]:
                if dx == dy == 0: continue
                if (x + dx, y + dy) in cells:
                    cell.neighbours.append(cells[(x + dx, y + dy)])

座標の数字とfor文が絡むと、どうしても読みにくくなるようです。もっとスマートな方法があるといいのですが、今回は諦めます。少しでもリファクタリングして可読性をあげておきます。

life.py

    NEIGHBOUR_POSITIONS = [(dx, dy) for dx in range(-1, 2) for dy in range(-1, 2) if not dx == dy == 0]
    @staticmethod
    def connect_neighbours(cells):
        for x, y in cells.keys():
            GameOfLife.connect_neighbour(cells[(x, y)], x, y, cells)

    @staticmethod
    def connect_neighbour(cell, x, y, cells):
        for dx, dy in GameOfLife.NEIGHBOUR_POSITIONS:
            if (x + dx, y + dy) not in cells: continue
            cell.neighbours.append(cells[(x + dx, y + dy)])

最後に、いままで書いた処理をコンストラクタおよびtick()から呼び出すようにします。これで完成!

life.py

class GameOfLife(object):
    def __init__(self, pattern=''):
        self.pattern = pattern
        self.cells = GameOfLife.build_cells(pattern)
        GameOfLife.connect_neighbours(self.cells)

    def dump(self):
        return self.pattern

    def tick(self):
        self.prepare_next_generation(self.cells.values())
        for cell in self.cells.values(): cell.tick()

class Cell(object):
    ....

    def __init__(self, state=DEAD):
        self.next_state = self.state = state
        self.neighbours = []

...と思ったのですが、ツメが甘かった。dump()で文字列に戻す処理も必要でした。一気に書きたくなりますがぐっとこらえて、まずテストから。

life_test.py

    def test_dump_cells(self):
        cells = {
            (0, 0): Cell(), (1, 0): Cell(), (2, 0): Cell(),
            (0, 1): Cell(), (1, 1): Cell(), (2, 1): Cell(),
            (0, 2): Cell(), (1, 2): Cell(), (2, 2): Cell(),
        }
        cells[(0, 0)].live()
        cells[(0, 2)].live()
        cells[(2, 1)].live()
        expected = '''
o..
..o
o..
'''
        actual = GameOfLife.dump_cells(cells)
        self.assertEqual(actual, expected)

一部のセルを生きている状態に書き換えてからdump_cells()に渡す形にしました。x軸とy軸を取り違えるというバグがいかにもありそうなので、非対称な形にしています。実装はそんなに難しくないはずです。

life.py

    @staticmethod
    def dump_cells(cells):
        grid_max = max(cells.keys())
        dump = [[''] * (grid_max[0] + 1) for i in range(grid_max[1] + 1)]
        for x, y in cells.keys():
            if cells[(x, y)].is_alive(): c = 'o'
            else: c = '.'
            dump[y][x] = c
        return '\n' + '\n'.join([''.join(line) for line in dump])

...そんなに易しくもないですね。グリッドの大きさを先に調べないといけないのが少々わずらわしい。仮想2次元バッファもどきを作っているので、文字列からの変換も合わせて別クラスにするのがいいかもしれません。その方向であれば、画面表示も効率よくできるかもしれません。TODOに積んで今はこのまま進めます。最後にdump()からdump_cells()を呼ぶように直します。

life.py

class GameOfLife(object):
    def dump(self):
        return GameOfLife.dump_cells(self.cells)

これですべてのテストが通るようになりました! TODOリストから気合いを込めて消しておきましょう。

  1. 初期パターンを渡せる
  2. グリッドのデータ構造をスパイクする
  3. Cellを実装する
  4. 初期パターンのCellを構築する
  5. Cellのneighboursを設定する
  6. 死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
  7. 生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
  8. 生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
  9. 生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。
  10. テストをわかりやすく修正する。
  11. 文字列のI/Oを別クラスにする。

残りのルールを実装するのは、今回までの成果があればかなり簡単にいけそうです。続きはまたこんど。コードはこちら https://github.com/yattom/tdd-life です。