「え!? ifもforも使わずにライフゲームの実装を!? 」「できらぁ!!」

この前Coderetreatというイベントに参加してライフゲームを実装した際、チャレンジ目標に「条件分岐禁止」や「ループ禁止」があった。
イベント中はやれなかったので、今回挑戦してみる。

ライフゲームってのはこんな感じのやつ。

課題

• ライフゲームを実装する
  (ルールの詳細はリンク先参照、一部抜粋)

ライフゲームのルール
ライフゲームでは初期状態のみでその後の状態が決定される。碁盤のような格子があり、一つの格子はセル（細胞）と呼ばれる。各セルには8つの近傍のセルがある (ムーア近傍) 。各セルには「生」と「死」の2つの状態があり、あるセルの次のステップ（世代）の状態は周囲の8つのセルの今の世代における状態により決定される。
セルの生死は次のルールに従う。
誕生　死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生存　生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
過疎　生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
過密　生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

• 今回は、ライフゲームにおける盤上の左右と上下はつながっている仕様とした。

  • つまり、盤上の一番左上のセルの左上のセルは、盤上の一番右下のセルになる。

• Coderetreatだと使用言語は自由

制約

実装する上での制約事項。Coderetreatのアクティビティより。

• ループ禁止
  • for,while等による繰り返し構文を使わない
  • (独自追加)pythonのmapも禁止
• 条件分岐禁止
  • if,while,switch、三項演算子等による分岐を使わない
  • (独自追加)pythonのfilterも禁止
• 1メソッド４行以下

※他に「不変オブジェクトしか使ってはならない」の制約もあったけど、今回は見送り。

まずは普通に実装

まずは制約を考えずに普通にライフゲームを実装してみる。
言語はpythonを選択。

ライフゲームクラスは以下のメソッドを持つ。

• コンストラクタ - 盤面の縦と横の長さを受け取り盤面を初期生成する。初期状態ではすべてのセルは死亡とする。
• set_alive(x,y) - x,yで指定されたセルを生存に設定する
• board - 現在の盤面のセルの状態を二次元配列で返す。セルの状態は、生存している場合は1、死亡している場合は0。
• next_generation() - 盤面のすべてのセルの状態を変化させ、次の世代に進める。

テストコード

Coderetreatの趣旨に従って、最初にテストコードを作成。
ライフゲームクラスを生成し、世代を進めたときに、生成された盤面が期待値と一致していることをテストする。

import unittest
from lifegame import LifeGame

class LifeGameTest(unittest.TestCase):
    def test_lifeGame(self):
        #初期状態生成
        lg =LifeGame(4,4)
        for p in [[0,1],[0,3],[1,2],[2,0],[2,1],[3,2],[3,3]]:
            lg.set_alive(p[0],p[1]);
        assert lg.board == [[0,1,0,1],[0,0,1,0],[1,1,0,0],[0,0,1,1]],"初期生成エラー"
        #１世代進めて結果をテスト
        lg.next_generation()
        assert lg.board == [[1,1,0,1],[0,0,1,1],[1,1,0,0],[0,0,0,1]],"世代1エラー"
        #もう１世代進めて結果をテスト
        lg.next_generation()
        assert lg.board == [[0,1,0,0],[0,0,0,0],[1,1,0,0],[0,0,0,1]],"世代2エラー"

if __name__ == "__main__":
    unittest.main()

普通の実装コード

制約を考えずに実装した場合のコード。
やはり普通に考えるとif/forは使ってしまう。

ALIVE = 1 #生存
DEAD = 0 #死亡

class LifeGame():
    # セルを初期化
    def __init__(self, x_len,y_len):
        self.x_len = x_len
        self.y_len = y_len
        self.board = [[DEAD for x in range(x_len)] for y in range(y_len)]

    # セルに生存を設定
    def set_alive(self,y,x):
        self.board[y][x] = ALIVE

    # 次の世代に進める
    def next_generation(self):
        new_board = []
        for y in range(len(self.board)):
            row = []
            for x in range(len(self.board[y])):
                row.append(self.judge_status(y,x))
            new_board.append(row)
        self.board = new_board

    # セルの次の世代の状態を判定して返す
    def judge_status(self,y,x):
        around_alive = self.count_alive(y,x);
        if self.board[y][x] == ALIVE:
            if 1 < around_alive < 4:
                return 1
            else:
                return 0
        else:
            if around_alive == 3:
                return 1
            else:
                return 0

    # 周囲の生存セルを返す
    def count_alive(self,y,x):
        around = []
        for dy in range(-1,2):
             for dx in range(-1,2):
                if not (dy ==0 and dx == 0):
                     cell = self.board[(y+dy)%self.y_len][(x+dx)%self.x_len]
                     around.append(cell)
        return sum(around)

出力例

テストケースが無事通ったので、適当なメイン処理を作って標準出力に表示してみる。

import random
import os
import time
import sys
from lifegame import LifeGame

def main():
    # 25×25の盤を生成
    lg =LifeGame(25,25)
    # ランダムに生存セルを設定
    for p in range(80):
        x = int((random.random()*100) %25)
        y = int((random.random()*100) %25)
        lg.set_alive(x,y);

    for cycle in range(100):
        print_board(lg)
        lg.next_generation()
        time.sleep(0.3)

def print_board(lg):
    board_str = "" 
    for y in lg.board:
        for x in y:
           # 生存なら■、死亡なら□で表示
           board_str += "■" if x == 1 else "□"
        board_str +="\n"
    os.system('cls')
    print(board_str)

if __name__ == "__main__":
    main()

出力結果

標準出力しているだけなので、コンソールの表示更新のタイミングによってはチラついてしまう。
まぁこれでテストコードと動作確認用のメインが作れた。

制約を守ったコードへの修正

ここから本番。
先ほどのコードをif/forを使わない形に修正していく。

1.初期化部分

self.board = [[DEAD for x in range(x_len)] for y in range(y_len)]

指定されたサイズの二次元配列を生成する処理だが、二重forループを使ってしまっているため、別の方法を考える。
まず、繰り返し処理については関数の再帰呼び出しを使えばforを使わずに実現できると気づく。

ただし、普通に再帰呼び出しを行ってしまうと、ifが使えないため無限ループとなってしまう。
そこでifについては、辞書型とラムダ式の組み合わせに置き換えることにする。
例をあげると

if a > 0:
    print("case 1")
else:
    print("case 2")

上記は、以下のように変えることでifを使わずに同じことができる。

# 辞書にBooleanキーに対応する関数を登録
dic = {True:lambda:print("case 1"),False:lambda:print("case 2")}
# 条件式の結果(Boolean)で辞書から関数を取得
func = dic[a > 0]
# 関数を呼び出し
func()

よって、初期化部分のコードは以下のようにすることで、if/forを使わないで実現が可能。

self.board = self.create_board([])
#再帰でボード初期化
def create_board(self,l):
    l.append([DEAD] * self.x_len)
    return {True:self.create_board,False:lambda x:x}[len(l) < self.y_len](l)

• 余談：最初は[[0]*x_len]*y_lenで簡単じゃーんと思ってたけどそんなことなかった。 いい勉強になった。

2.状態判定部分

def judge_status(self,y,x):
    around_alive = self.count_alive(y,x);
    if self.board[y][x] == ALIVE:
        if 1 < around_alive < 4:
            return 1
        else:
            return 0
    else:
        if around_alive == 3:
            return 1
        else:
            return 0

ifを4つも使ってしまっている。
まずは判定は１つにまとまれるのでまとめる。
加えて、int(<Boolean>)で0/1に変換できることを利用すると、以下のように変えられる。

def judge_status(self,y,x):
    around_alive = self.count_alive(y,x);
    return int((self.board[y][x] == ALIVE and 1 < around_alive < 4 ) 
               or (self.board[y][x] == DEAD and around_alive == 3))

ifを使わない方が、ライン数が少なくて見やすいコードになった

制約を守った実装コード

同じようにして全体を修正して、最終的に制約(条件分岐禁止、ループ禁止、1メソッド4行以下)をすべて守ったコードを作ることができた。

ALIVE = 1 #生存
DEAD = 0 #死滅

class LifeGame():
    # セルの初期化
    def __init__(self, x_len,y_len):
        self.x_len,self.y_len,self.size = x_len,y_len,x_len*y_len
        self.board = self.create_board([])

    #再帰でボード初期化
    def create_board(self,l):
        l.append([DEAD] * self.x_len)
        return {True:self.create_board,False:lambda x:x}[len(l) < self.y_len](l)

    # セルに生存を設定
    def set_alive(self,y,x):
        self.board[y][x] = ALIVE

    # 次の世代に進める
    def next_generation(self):
        self.board = self.next(0,self.create_board([]))

    # 再帰で次世代の各セルを更新
    def next(self,i,next_board):
        x,y = i%self.x_len,int(i/self.y_len)
        next_board[y][x] = self.judge_status(y,x)
        return {True:self.next,False:lambda *x:x[1]}[i+1 < self.size](i+1,next_board)

    # セルの次の状態を判定して返す
    def judge_status(self,y,x):
        num = self.count_alive(y,x,0,0) - self.board[y][x];
        return int((self.board[y][x] == ALIVE and 1 < num < 4 ) 
                   or (self.board[y][x] == DEAD and num == 3))

    # 再帰で3×3の範囲の生存セルの数を返す
    def count_alive(self,y,x,i,num):
        ty = (y+int(i/3)-1)%self.y_len
        tx = (x+i%3-1)%self.x_len
        num += self.board[ty][tx]
        return {True:self.count_alive,False:lambda *x:x[3]}[i+1 < 9](y,x,i+1,num)

まとめ

• 感想として、if/forを使わなくても、それほど可読性が落ちないことに驚いた。
  • むしろ使わないほうが、インデントがないので全体がスッキリしている。
  • 全体のコード量も47行から40行に減っている。
  • ただまぁ再帰を多用しているのでパフォーマンス的には悪いかもしれない…
• 制約を課してコーディングすることで自分の引き出しが増えるのを感じた。
  • 普段は脳死でif/forを使ってしまっているため、他の方法がないかを調べることで、言語についての知識が増えた。
  • これでキーボードのfが壊れても実装できる（嬉しいか？）

もし他にもこんな方法もあるよってのをご存知の方は、ぜひコメントで教えて頂ければ幸いです