[GO] Solve the one-stroke writing (backtrack without recursion in Python)

One-stroke writing is melty!

It's a famous story. One-stroke writing is a very simple rule that allows you to judge whether you can solve or not. The so-called Euler graph.

1. It must be a connected graph. That is, it is a group. (You can't write the kanji "times" with a single stroke. There is no side connecting the outer square and the inner square, so you can't do your best.)
2. Must be one of the following. 2-1: Every point has an even number of edges (in this case, you can start from any point, and finally return to the starting point) 2-2: Only two points have an odd number of sides, and the other points have an even number of sides. (In this case, the point with odd-numbered sides is the start point, and the point with the other odd-numbered sides is the end point.)

...... Unless it's a fairly big one-stroke writing, it seems that you can solve it by deciding the starting point and properly backtracking without thinking about anything.

The option of not recursion

Then, I should start writing. When I tried to create a recursive function, I found it annoying. The value returned should be a list of the order in which the line should be followed. Do you create a new list each time you call a recursive function? Does the recursive function return a list of length 1 and lengthen the list each time it returns a value? When I thought about it, I thought that I should have my own stack and spin it in a loop.

Push the iterator onto the stack

Then how about calling a recursive function in the middle of the loop? Is it possible to resume from the middle? it can. If you leave the iterator object, the loop will start from the next.

With a for loop, iterators cannot be replaced in the middle (maybe, but I don't know how to do it), so I tried to extract the element from the iterator while using the while loop.

As a basic knowledge, in Python,

for x in iterable:
    foo(x)

Is roughly equivalent to:

_it = iter(iterable)
while 1:
    try:
        x = next(_it)  # Python3
        # x = _it.next()  # Python2
    except StopIteration:
        break
    else:
        foo(x)

In short, when the iterator calls next, it returns the next element and throws a StopIteration exception if there is no next element. The for loop calls next behind the scenes and ends the loop when Stop Iteration comes.

One-stroke code

As a result, I was able to do something like this.

from collections import Counter

# Edges := [Edge*]
# Edge := (Vertex, Vertex)
# Vertex := Hashable except None

def solve_hitofude(edges):
    def _make_vertexcounter(edges):
        'Count the number of edges for each vertex'
        c = Counter()
        for x, y in edges:
            c[x] += 1
            c[y] += 1
        return c

    def _make_edgeflag(edges, value=True):
        'Make a dictionary to manage the side you passed'
        d = dict()
        for edge in edges:
            d[edge] = value
        return d

    def _get_head_tail(counter):
        'Determine the start and end points'
        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):
        'Generator function. Create a generator that yields edges that are connected to a point and haven't passed yet.'
        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 = []  #Put the points you passed in order
    stack_edge = []  #I will put in the side that passed
    stack_selector = []  # _edge_Insert the selector generator

    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:  #Finish when you follow all the sides
        try:
            edge, nextpos = next(selector)
        except StopIteration:  #Return when there are no more traceable sides. If it cannot return any more, it returns None.
            if stack_pos:
                pos = stack_pos.pop()
                remain[stack_edge.pop()] = True
                selector = stack_selector.pop()
                n += 1
            else:
                return None
        else:  #Processing when it can be traced.
            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

Every time I follow / return an edge, the iterator selector variable is swapped around.

Let's try

I tried to make it a GUI with PyQt4. (It was supposed to be crispy, but it was a secret that it took a lot of time to get hooked on various things. I would like to write an article about Qt / PyQt soon)

All the code is [published] on Github (https://github.com/gyu-don/hitofude).