Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

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

課題

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

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

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

    • つまり、盤上の一番左上のセルの左上のセルは、盤上の一番右下のセルになる。
  • Coderetreatだと使用言語は自由

制約

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

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

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

まずは普通に実装

まずは制約を考えずに普通にライフゲームを実装してみる。
言語は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]],"初期生成エラー"
        #1世代進めて結果をテスト
        lg.next_generation()
        assert lg.board == [[1,1,0,1],[0,0,1,1],[1,1,0,0],[0,0,0,1]],"世代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()

普通の実装コード:hatching_chick:

制約を考えずに実装した場合のコード。
やはり普通に考えると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()

出力結果
lifegame.gif

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

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

ここから本番。
先ほどのコードを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つも使ってしまっている。
まずは判定は1つにまとまれるのでまとめる。
加えて、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を使わない方が、ライン数が少なくて見やすいコードになった:sunny:

制約を守った実装コード:rooster:

同じようにして全体を修正して、最終的に制約(条件分岐禁止、ループ禁止、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が壊れても実装できる(嬉しいか?)

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

sionn
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away