한 필기 쓰기는, 어쩌다!

유명한 이야기지만. 한 글은 매우 간단한 규칙으로 풀 수 있는지 풀 수 있는지를 결정할 수 있습니다.
이른바 오일러 그래프는 녀석.

1) 연결 그래프일 것. 즉, 한 덩어리인 것. (한자의 「회」는, 일필 쓸 수 없네요. 밖의 사각과 안의 사각을 연결하는 변이 없기 때문에, 어떻게 노력해도 무리입니다)
2) 다음 중 하나여야 한다.
2-1: 모든 점은 짝수 개의 변을 가지고 있다(이 경우, 어느 점으로부터 시작해도 상관없다. 마지막은 시작점으로 돌아온다)
2-2: 단지 2점만이 홀수개의 변을 가지며, 다른 점이 가지는 변의 수는 짝수이다. (이 경우, 어느 쪽인가, 홀수개의 변을 가진 점이 시작점이 되고, 다른 한쪽의 홀수개의 변을 가진 점이 종점이 된다)

......상당히 큰 필기도 아닌 한, 시작점을 결정하고, 아무것도 생각하지 않고 적당하게 백 트랙하면 풀릴 것 같다.

재귀하지 않는 옵션

그렇다면 , 쓰기 시작한 것은 좋지만. 재귀 함수를 만들려고 했을 때, 귀찮은 것을 깨달았다.
돌려주는 값은, 선을 어느 순서로 따르는지, 라고 하는 리스트가 될 것.
재귀 함수를 호출 할 때마다 새 목록을 만들까요?
재귀 함수의 끝이 길이 1의 목록을 반환하고 값을 반환 할 때마다 목록을 길게합니까?
…

반복자를 스택에 뿌리기

그렇다면 루프 중간에 재귀 함수를 호출하는 것은 어떨까요? 도중부터 재개할 수 있을까?
할 수 있다. 반복자 객체를 남겨두면, 다음은 계속부터 루프가 시작된다.

for 루프라면 반복자를 도중에 바꿀 수 없다 (할 수 있을지도 모르지만, 방법을 모른다) 때문에,
while 루프를 사용하면서 이터레이터로부터 요소를 꺼내 보았다.

기본 지식으로서 파이썬에서는

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에서 공개 있습니다.