一筆書きを解こう (Pythonで再帰せずにバックトラック)

#一筆書きは、とけまぁす！

有名な話だが。一筆書きは、非常に簡単なルールで、解けるか解けないかの判定ができる。
いわゆるオイラーグラフってやつ。

1) 連結グラフであること。すなわち、ひとかたまりであること。(漢字の「回」は、一筆書きできないですよね。外の四角と中の四角を結ぶ辺がないので、どうがんばっても無理です)
2) 以下のいずれかであること。
2-1: すべての点は、偶数本の辺を持っている(この場合、どの点から始めても構わない。最後は始点に戻ってくる)
2-2: ちょうど2点のみが奇数本の辺を持ち、他の点が持つ辺の数は偶数である。(この場合、どちらか、奇数本の辺を持った点が始点になり、もう片方の奇数本の辺を持った点が終点になる)

……相当デカい一筆書きでもない限りは、始点を決めて、何も考えずに適当にバックトラックすりゃ解けそうだな。

#再帰しない、という選択肢

ならば、と、書き始めたはいいが。再帰関数を作ろうとしたとき、面倒なことに気づいた。
返す値は、線をどの順でたどるか、というリストになるはず。
再帰関数を呼び出すたびに、新しいリストを作るか？
再帰関数の末端が長さ1のリストを返して、値を返すたびにリストを長くするか？
……とか考えてたら、もう、自前でスタック持って、ループで回せばいいじゃんって思った。

#イテレータをスタックにぶち込む

そしたら、ループの途中で再帰関数を呼び出すのはどうすんだよ？　途中から再開できるのか？
できる。イテレータオブジェクトを残しとけば、次は続きからループが始められる。

forループだとイテレータを途中で入れ替えることができない(できるかもしれないが、やり方を知らない)ので、
whileループを使いながら、イテレータから要素を取り出してみた。

基礎知識として、Pythonでは、

```py3
for x in iterable:
    foo(x)
```

は、以下とだいたい等価である。

```py3
_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がきたらループを終了してくれる。

#一筆書きコード
結果、こんなのができた。

```py3
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化してみた。
![demo.gif](https://qiita-image-store.s3.amazonaws.com/0/88256/63448f41-154a-e627-e5ab-2bc2ec5bb37c.gif)
(サクサクっと、のはずが、いろいろとハマってめっちゃ時間がかかったのは内緒。Qt/PyQt関連もそのうち記事書きたい)

コードはすべて、Githubで[公開](https://github.com/gyu-don/hitofude)している。