一筆書きは、とけまぁす！
有名な話だが。一筆書きは、非常に簡単なルールで、解けるか解けないかの判定ができる。
いわゆるオイラーグラフってやつ。
- 連結グラフであること。すなわち、ひとかたまりであること。(漢字の「回」は、一筆書きできないですよね。外の四角と中の四角を結ぶ辺がないので、どうがんばっても無理です)
- 以下のいずれかであること。
2-1: すべての点は、偶数本の辺を持っている(この場合、どの点から始めても構わない。最後は始点に戻ってくる)
2-2: ちょうど2点のみが奇数本の辺を持ち、他の点が持つ辺の数は偶数である。(この場合、どちらか、奇数本の辺を持った点が始点になり、もう片方の奇数本の辺を持った点が終点になる)
……相当デカい一筆書きでもない限りは、始点を決めて、何も考えずに適当にバックトラックすりゃ解けそうだな。
再帰しない、という選択肢
ならば、と、書き始めたはいいが。再帰関数を作ろうとしたとき、面倒なことに気づいた。
返す値は、線をどの順でたどるか、というリストになるはず。
再帰関数を呼び出すたびに、新しいリストを作るか？
再帰関数の末端が長さ1のリストを返して、値を返すたびにリストを長くするか？
……とか考えてたら、もう、自前でスタック持って、ループで回せばいいじゃんって思った。
イテレータをスタックにぶち込む
そしたら、ループの途中で再帰関数を呼び出すのはどうすんだよ？ 途中から再開できるのか？
できる。イテレータオブジェクトを残しとけば、次は続きからループが始められる。
forループだとイテレータを途中で入れ替えることができない(できるかもしれないが、やり方を知らない)ので、
whileループを使いながら、イテレータから要素を取り出してみた。
基礎知識として、Pythonでは、
for x in iterable:
foo(x)
は、以下とだいたい等価である。
_it = iter(iterable)
while 1:
try:
x = next(_it) # Python3
# x = _it.next() # Python2
except StopIteration:
break
else:
foo(x)
要するに、イテレータはnextを呼び出すと次の要素を返し、次の要素がなければStopIteration例外を投げる。
forループは裏でnextを呼び出してくれて、StopIterationがきたらループを終了してくれる。
一筆書きコード
結果、こんなのができた。
from collections import Counter
# Edges := [Edge*]
# Edge := (Vertex, Vertex)
# Vertex := Hashable except None
def solve_hitofude(edges):
def _make_vertexcounter(edges):
'各頂点ごとに、辺の数を数える'
c = Counter()
for x, y in edges:
c[x] += 1
c[y] += 1
return c
def _make_edgeflag(edges, value=True):
'通った辺を管理するための辞書を作る'
d = dict()
for edge in edges:
d[edge] = value
return d
def _get_head_tail(counter):
'始点・終点を決める'
odd = []
for k,v in counter.items():
if v&1: odd.append(k)
if len(odd) == 2:
return tuple(odd)
elif len(odd) == 0:
t = c.most_common(1)[0][0]
return t, t
else:
return None, None
def _edge_selector(pos, edgeflag):
'ジェネレータ関数。ある点につながっていて、まだ通ってない辺をyieldするジェネレータを作る。'
for edge in edgeflag:
if edgeflag[edge]:
a, b = edge
if a == pos:
yield edge, b
if edgeflag[edge] and b == pos:
yield edge, a
stack_pos = [] # 通った点を順に入れていく
stack_edge = [] # 通った辺を入れていく
stack_selector = [] # _edge_selectorジェネレータを入れていく
c = _make_vertexcounter(edges)
remain = _make_edgeflag(edges)
pos, tail = _get_head_tail(c)
if pos is None:
return None
n = len(edges)
selector = _edge_selector(pos, remain)
while n: # 全部の辺をたどったら終了
try:
edge, nextpos = next(selector)
except StopIteration: # 辿れる辺がなくなったら戻る。これ以上戻れない場合はNoneを返す。
if stack_pos:
pos = stack_pos.pop()
remain[stack_edge.pop()] = True
selector = stack_selector.pop()
n += 1
else:
return None
else: # 辿れる場合の処理。
stack_pos.append(pos)
stack_edge.append(edge)
stack_selector.append(selector)
pos = nextpos
remain[edge] = False
selector = _edge_selector(pos, remain)
n -= 1
if pos == tail:
return stack_pos, stack_edge
assert False
辺を辿る/戻るたびに、イテレータであるselector変数がころころと入れ替わっている。
試してみよう
PyQt4でサクサクっとGUI化してみた。
(サクサクっと、のはずが、いろいろとハマってめっちゃ時間がかかったのは内緒。Qt/PyQt関連もそのうち記事書きたい)
コードはすべて、Githubで公開している。