[GO] Résoudre un coup (retour en arrière sans récursivité en Python)

L'écriture en un seul coup, c'est melty

C'est une histoire célèbre. L'écriture en un seul trait est une règle très simple qui vous permet de juger si vous pouvez résoudre ou non. Le graphe dit du graisseur.

1. Il doit s'agir d'un graphe concaténé. Autrement dit, c'est un groupe. (Vous ne pouvez pas écrire les «temps» des kanji en un seul trait. Il n'y a pas de côté reliant le carré extérieur et le carré intérieur, vous ne pouvez donc pas faire de votre mieux.)
2. Doit être l'un des suivants. 2-1: Chaque point a un nombre pair de côtés (dans ce cas, vous pouvez commencer à partir de n'importe quel point, et enfin revenir au point de départ) 2-2: Seuls deux points ont un nombre impair de côtés, et les autres points ont un nombre pair de côtés. (Dans ce cas, le point avec le nombre impair de côtés est le point de départ, et le point avec l'autre côté impair est le point final.)

...... À moins que ce ne soit une grosse écriture en un seul coup, il semble que vous puissiez le résoudre en décidant du point de départ et en revenant correctement sans penser à rien.

L'option de ne pas se reproduire

Ensuite, je devrais commencer à écrire. Quand j'ai essayé de créer une fonction récursive, je l'ai trouvé ennuyeux. La valeur renvoyée doit être une liste de l'ordre dans lequel la ligne doit être suivie. Créez-vous une nouvelle liste chaque fois que vous appelez une fonction récursive? La fonction récursive renvoie-t-elle une liste de longueur 1 et allonge-t-elle la liste à chaque fois qu'elle renvoie une valeur? Quand j'y ai pensé, j'ai pensé que je devrais avoir ma propre pile et la faire tourner en boucle.

Poussez l'itérateur dans la pile

Alors que diriez-vous d'appeler une fonction récursive au milieu de la boucle? Est-il possible de reprendre à partir du milieu? ça peut. Si vous quittez l'objet itérateur, la boucle commencera à partir du suivant.

S'il s'agit d'une boucle for, il n'est pas possible de remplacer l'itérateur au milieu (c'est peut-être possible, mais je ne sais pas comment faire), donc J'ai essayé d'extraire l'élément de l'itérateur en utilisant la boucle while.

En tant que connaissance de base, en Python,

for x in iterable:
    foo(x)

Est à peu près équivalent à:

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

En bref, l'itérateur renvoie l'élément suivant lors de l'appel de next et lève une exception StopIteration s'il n'y a pas d'élément suivant. La boucle for appelle ensuite dans les coulisses et termine la boucle lorsque Arrêter l'itération arrive.

Code à un coup

En conséquence, j'ai pu faire quelque chose comme ça.

from collections import Counter

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

def solve_hitofude(edges):
    def _make_vertexcounter(edges):
        'Comptez le nombre de côtés pour chaque sommet'
        c = Counter()
        for x, y in edges:
            c[x] += 1
            c[y] += 1
        return c

    def _make_edgeflag(edges, value=True):
        'Faites un dictionnaire pour gérer le côté que vous avez passé'
        d = dict()
        for edge in edges:
            d[edge] = value
        return d

    def _get_head_tail(counter):
        'Déterminez les points de départ et d'arrivée'
        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):
        'Fonction générateur. Créez un générateur qui donne des côtés qui sont connectés à un certain point et qui ne sont pas encore passés.'
        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 = []  #Mettez les points que vous avez passés dans l'ordre
    stack_edge = []  #Je mettrai du côté qui est passé
    stack_selector = []  # _edge_Insérer le générateur de sélecteur

    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:  #Si vous suivez tous les côtés, vous avez terminé
        try:
            edge, nextpos = next(selector)
        except StopIteration:  #Revenez quand il n'y a plus de côtés traçables. S'il ne peut plus retourner, il renvoie None.
            if stack_pos:
                pos = stack_pos.pop()
                remain[stack_edge.pop()] = True
                selector = stack_selector.pop()
                n += 1
            else:
                return None
        else:  #Traitement lorsqu'il peut être retracé.
            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

Chaque fois que je suis / retourne un côté, la variable de sélection, qui est un itérateur, est permutée.

Essayons

J'ai essayé d'en faire une interface graphique avec PyQt4. (Cela aurait dû être croustillant, mais c'est un secret qu'il a fallu beaucoup de temps pour devenir accro à diverses choses. J'aimerais bientôt écrire un article sur Qt / PyQt)

Tout le code est public sur Github.