CheckIO というプログラミングサイトで2年以上前にPythonで書いたコードが久々に見返したらリファクタリングの提案がされてて少し感動したので解説を兼ねて共有する。
問題の回答とそこから伸びているスレッドは問題を解いた人にしか見えないらしいのでここにコピーする。以下の引用は全てこの問題やスレッドが出典である。
問題
0と1の二次元配列で迷路を渡すので、その迷路の (1, 1) の座標から初めて(10, 10) まで辿り着く経路を N,S, E, Wからなる文字列で返却せよ。
0は床、1は壁を表す。Nは上、Sは下、Eは右、Wは左を表す。およそこの図が全てである。経路は複数ありうるが最終的にゴールにたどり着ける経路を1つ返却すればよい。
僕の(いまいちな)回答
とにかくタイピングしたくなかったので回答を短く収めた。
def checkio(data):
result = []
dirs = [[-1, 0, "W"], [+1, 0, "E"], [0, -1, "N"], [0, +1, "S"]]
def move(path, x, y, field):
field[y][x] = 1
if x == 10 and y == 10:
result.append(path)
for d in dirs:
if field[y + d[1]][x + d[0]] == 0:
move(path + d[2], x + d[0], y + d[1], field)
move("", 1, 1, data)
return result[0]
解説
典型的な再帰による塗りつぶし探索。
move関数は引数として これまでに歩いてきた経路と探索起点とフィールドを受け取り、上下左右すべての床へmove関数を再帰的に呼び出す。
move関数は歩いた道を「壁」へと塗り替える(field[x][y] = 1)事で、来た道を引き返さないようにできている。
ゴールに辿り着いたらそれをゴール候補としてresult配列に追加する。これによってゴールに辿り着きうる全ての道順が配列に入るので最後にその先頭を返却してフィニッシュ。
本来であればダイクストラなりA*なりで無駄なく探索する事が常套だが、とにかく短く書いたため12行で収まった。
貰ったレビュー
この回答自体はツッコミどころはあれど、ぱっと見面倒臭そうな問題を短く解いたのは一部の人に響いたらしくこの回答に対する解のうち一番多いvoteをいただいた。
そのスレッドが盛り上がったのも一因か、vekyさんという方が丁寧なレビューとリファクタリングを提供してくれた。ここからが本題。
回答は英語でそれなりに長文なので回答の大事な部分のみを抜粋して解説する。
彼の提供した回答は以下である。
def checkio(data):
def move(path="", x=1, y=1):
data[y][x] = 1
if x == y == 10:
yield path
for x, y, way in (x-1,y,"W"), (x+1,y,"E"), (x,y-1,"N"), (x,y+1,"S"):
if not data[y][x]:
yield from move(path + way, x, y)
return next(move())
9行まで減っている。改良されている点は以下。
デフォルト引数の使用
Pythonは関数の仮引数リストに =と右辺をつける事でその引数が省略された場合の引数値を指定することができる。
多項比較の利用
Pythonの場合、複数の項を一気に比較できるので
x == 10 and y == 10という文は機械的に x == y == 10 と書き換えれる。
ジェネレータの利用
Pythonでのジェネレータ文は乱暴に説明するとreturnの代わりにyieldが使われている、関数の変種である。
関数の中でyieldと書くと、yieldに与えられた引数を返すジェネレータ生成関数として関数が解釈される。その関数に値を与えて呼び出すとジェネレータが生成される。
そのジェネレータはnext()関数が呼ばれるたびに、次のyieldに至るまで関数内部が続きから実行される。
next()関数を呼び出してStopIteration例外が投げられたところで打ち切る、というのはよくやるのでPythonではfor文にジェネレータを与える事で簡単に全要素を舐めさせる事ができる。
def fruit_generator(num):
yield "apple: " + str(num)
yield "banana: " + str(num)
yield "orange: " + str(num)
for fruit in fruit_generator(3):
print(fruit)
apple: 3
banana: 3
orange: 3
何らかの処理を繰り返し行う際に、その関数に個々の状態を持たせたいけど外から渡したりするのは嫌だという事は良くある。
典型的にはクラスを定義してメンバとして持たせるのが正直だが、ジェネレータで表現しても同様のことができて更にスッキリ短く書けるというケースも良くある。
タプルの利用
Pythonでは配列のような振る舞いをする物として list と tuple がある。
どちらも添字でアクセスできる点は一緒だが、listは [] で表し、tupleは()で表す。
listはappendなどを用いて要素を追加・削除したり添字参照に対して値を書き換えたりできる。配列としてプログラマが期待するものである。
a = []
a.append(2) # a == [2]
a.append(3) # a == [2, 3]
a[1] = 10 # a == [10, 3]
tupleはappendなどの変更も添字参照への書き換えもできない。
a = (2,3,4)
a[2] # 4
a.append(5) # AttributeError: 'tuple' object has no attribute 'append'
a[1] = 3 #TypeError: 'tuple' object does not support item assignment
なのでプログラムする際に「これは実行中に書き換わることを期待しない値だぞ」というのを明白なメッセージとして表現できる。
タプルアンパッキング
タプルの値を複数の変数に代入し直す事は良くある。
代入文の左辺値にコンマで複数の変数を書く事で一気に代入できる。
tup = (1,2,3)
a, b, c = tup
print(a) # 1
print(b) # 2
print(c) # 3
これはfor文の先頭でも使う事ができる。
x = 0
y = 0
for x, y, way in (x-1,y,"W"), (x+1,y,"E"), (x,y-1,"N"), (x,y+1,"S"):
print("x={x} y={y} way={w}".format(x=x, y=y, w=way))
x=-1 y=0 way=W
x=1 y=0 way=E
x=0 y=-1 way=N
x=0 y=1 way=S
僕の初めのコードでは「長さ3の配列のうち、1つめがx座標、2つめがy座標、3つめが方向」という暗黙の仕様がありそれに合わせた添字アクセスをしていたが本来こういう自明でない数字と意味の対応付け(通称マジックナンバー)は使うべきでない。アンパックして個々の変数名を名づけてしまったほうが意味が伝わりやすい。
yield from文の利用
Python3.3から追加されたの yield from を使う事で再帰ありのジェネレータを簡潔に表現している。
yield fromは馴染みのない人が多いと思うので少しまともに解説すると、ジェネレータの移譲をうまくやるための文である。
def foo():
yield 1
yield 2
def gen():
for x in range(5):
yield from foo() # yield fromをここで使う
d = gen()
for x in d:
print(x)
1
2
1
2
1
2
1
2
1
2
移譲と言ってもピンと来ないがgen()関数を以下のように書き換えても同じ結果が返る。
def gen():
for x in range(5):
for f in foo():
yield f
ジェネレータの中で他(もしくは再帰的に自分自身)のジェネレータの結果を代わりに返して欲しい場合に有効な記法である。
まとめ
- 微妙なコードでも晒しておくと有用な知見が得られることもあるのでどんどん晒そう
- CheckIOはフォーラムから知見が得られる良いところ