Im vorherigen Beitrag habe ich kurz erw?hnt, dass ich am diesj?hrigen Advent of Code teilnehme. Zuf?lligerweise geht es bei einem der R?tsel, insbesondere dem am 5. Tag ver?ffentlichten, darum, die Reihenfolge der Seiten in einer Liste festzulegen. Dies geschah nicht lange, nachdem ich über die Implementierung eines Sortieralgorithmus gepostet hatte, also denke ich, ich sollte darüber schreiben.

Ein sü?es Bild, das einen Sortieralgorithmus darstellt

Für diejenigen, die noch nichts von Advent of Code geh?rt haben: Es handelt sich um eine j?hrliche Veranstaltung, die von Eric Wastl moderiert wird. Jedes Jahr wird eine Geschichte erz?hlt, die in der Weihnachtszeit spielt. In diesem Jahr geht es um die Suche nach dem Chefhistoriker, m?glicherweise einer wichtigen Figur bei jedem gro?en Weihnachtsschlittenstart. Die Challenge l?uft jedes Jahr vom 1. Dezember bis zum 25. Dezember. Die Handlung schreitet jeden Tag voran und enth?lt ein Programmierr?tsel (und eine Eingabe).

Innerhalb der Erz?hlung der Geschichte wird das R?tsel normalerweise klar definiert und enth?lt Testf?lle. Jedes R?tsel ist in zwei Teile geteilt und der zweite Teil erscheint erst nach dem Absenden der ersten Antwort.

Teilnehmer k?nnen jeden Algorithmus in jeder Sprache implementieren oder sogar ganz auf die Programmierung verzichten, solange die abgeleitete Antwort übereinstimmt. Dieses Jahr versuche ich, die L?sungen in Python zu programmieren, und nach 9 Tagen habe ich das Gefühl, dass ich w?hrend der Reise ziemlich viel gelernt habe.

Am fünften Tag bat die Geschichte darum, beim Drucken von Sicherheitshandbüchern zu helfen. Die Eingabe enthielt sowohl die Seitenregeln als auch die Listen der Seiten, die der Elf zu drucken versuchte.

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

Beginnen wir mit dem Parsen der Eingabe:

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

Die Funktion empf?ngt die Eingabe als Zeichenfolge mit dem Namen ?input“, teilt sie mit .splitlines() in Zeilen auf, um sie an die innere Funktion zu senden, um zwei Tupel zu erzeugen, eines für Seitenregeln und eines für die Seitensequenz. Der Code unterscheidet die beiden Arten von Definitionen durch das Trennzeichen | für Seitenregeln und , für Seiten.

Im ersten Teil des R?tsels wurde die Geschichte gebeten, zu überprüfen, ob die Seiten in Ordnung sind. Beginnen wir mit der Implementierung einer Funktion, die diese Aufgabe erledigt:

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

Und dann eine weitere Funktion, die alle Seitenkombinationen sendet (combinations((1,2,3), 2) gibt 1,2, 1,3 und 2,3 zurück):

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

Der Hauptgrund, warum ich diese beiden in einzelne Funktionen unterteilt habe, ist, dass ich jeden Teil so klein wie m?glich halten m?chte. Meiner Erfahrung nach macht es nicht nur testbar, wenn man die Dinge klein genug h?lt, sondern es hilft normalerweise auch beim Debuggen der endgültigen Eingabe (die normalerweise unangemessen gro? ist).

Teil 2 kommt oft überraschend und es ist nicht ungew?hnlich, dass eine überarbeitung des Codedesigns für Teil 1 erforderlich ist. Es kann sich um eine kleine Variation von etwas handeln, das Sie implementiert haben, oder um eine andere Funktion Aufrufreihenfolge für unterschiedliche Ziele usw. Ich habe die Angewohnheit, bei der Arbeit kurze Funktionen zu schreiben (als Alternative zu Kommentaren).

Kleine Funktionen wie diese funktionieren nur, wenn die Namen gut sind, daher müssen Sie der Benennung gro?e Aufmerksamkeit schenken. Dies erfordert übung, aber wenn Sie erst einmal gut darin sind, kann dieser Ansatz den Code bemerkenswert selbstdokumentierend machen. Gr??ere Funktionen k?nnen sich wie eine Geschichte lesen, und der Leser kann je nach Bedarf ausw?hlen, in welche Funktionen er tiefer eintauchen m?chte.

zitiert aus dem Artikel mit dem Titel ?Funktionsl?nge“, verfasst von Martin Fowler

Zurück zum R?tsel.

Am Ende des R?tsels wurde nach der Summe der mittleren Seitenzahlen für alle F?lle gefragt, in denen die Seiten richtig geordnet waren.

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

Ganz einfach, wenn Sie alles richtig gemacht haben, ist es nur noch ein Listenverst?ndnis entfernt (weil Python-Entwickler dies gegenüber Karte/Filter bevorzugen).

Als n?chstes kommt der Sortieralgorithmus:

Als Fortsetzung von Teil 1 wollte der zweite Teil die Summe der mittleren Seiten, allerdings für F?lle, in denen die Seiten nicht richtig angeordnet waren. In der Anweisung wurde au?erdem dazu aufgefordert, die Reihenfolge zu korrigieren, bevor die mittlere Seitenzahl abgerufen wird.

W?hrend es meinen Kollegen gelang, das Problem ohne einen vollwertigen Sortieralgorithmus zu l?sen, habe ich beschlossen, es genau so zu machen, wie das R?tsel zuvor im Abschnitt zur Erl?uterung der Seitenregeln beschrieben wurde. Ich hatte den Vergleichsteil bereits erledigt (check_pair), jetzt brauche ich eine Funktion, die Elemente verschieben würde.

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

Angenommen, ich habe 1,2,3,4,5 und die Funktion verschiebt die eingehende Zahl direkt vor die aktuelle Zahl. Angenommen, Strom = 2 und Eingang = 4, dann erhalte ich als Gegenleistung 1,4,2,3,5 (vorausgesetzt, wir ordnen nach dem steigenden Zahlenwert).

Mein erfolgloser Versuch, einem Freund den Algorithmus zu erkl?ren

Als n?chstes wird der Algorithmus, der in meinem handgeschriebenen Entwurf gezeigt wird, in tats?chlichen Code umgewandelt.

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

Ja, leider handelt es sich um eine Rekursion. Ich sollte die erste Version posten, die k?nnte freundlicher zu lesen sein:

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

Beide sind im Wesentlichen gleich, wobei die endgültige Funktionsversion leicht optimiert ist. Wenn ich mich auf den Entwurfs-Screenshot beziehe, habe ich zwei Zeiger, die gelbe Unterstreichung ist der benannte Zeiger im Code und die eingehende Unterstreichung ist die blaue Unterstreichung.

Der Algorithmus funktioniert wie folgt:

1. Es beginnt damit, dass der Zeiger auf das erste Element gesetzt wird.
2. Anfangs ist immer das Element daneben.
3. Der eingehende Zeiger durchl?uft jeweils ein Element und verschiebt den Wert nach rechts vor den aktuellen, wenn er gegen die Regel verst??t.
4. Sobald dies geschieht, wird der eingehende Zeiger zurückgesetzt und zum n?chsten aktuellen Zeiger zurückgeleitet.
5. Der aktuelle Zeiger ?ndert seine Position nicht, zeigt aber jetzt auf das neue Element, das im vorherigen Schritt eingefügt wurde.

Wenn es dem eingehenden Zeiger gelingt, den Rest der Liste zu durchlaufen, ohne eine ?nderung herbeizuführen, verschieben wir den aktuellen Zeiger (und den neu initialisierten eingehenden Zeiger an die Position daneben) und wiederholen den Vorgang erneut.

Der Prozess endet, nachdem der Algorithmus den Vergleich der letzten beiden Elemente abgeschlossen hat, und gibt dann die sortierten Seiten als Ergebnis zurück. Dann k?nnen wir damit fortfahren, alles zusammenzustellen, was wir für Teil 2 haben:

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

Der Code für beide Teile ist ?hnlich. Es handelt sich lediglich um eine geringfügige ?nderung an Teil1, lediglich um eine Variation in der Filterklausel, und get_middle erh?lt stattdessen eine sortierte Liste. Im Wesentlichen ist es so, als würde ich eine Antwort aus Bausteinen in Form von Funktionen zusammensetzen, in einer etwas anderen Kombination.

Obwohl dies immer noch nicht gerade ein effizienter Algorithmus ist, liegt die Zeitkomplexit?t nahe bei O(n^2). Laut dem Kaskaden-KI-Begleiter im Windsurfen ?hnelt der Algorithmus in gewisser Weise der Einfügesortierung (ja, dann ist das KI-Tool nützlich, um Algorithmen zu erkl?ren).

Das war's für heute. Ich bin froh, dass der Algorithmus einwandfrei funktioniert, obwohl mein Leben derzeit ein Chaos ist (habe mich gerade wegen Finanzierungsproblemen aus einem Projekt zurückgezogen). Hoffentlich wird es mit der Zeit besser und ich werde n?chste Woche wieder schreiben.

Das obige ist der detaillierte Inhalt vonSo codieren Sie einen Sortieralgorithmus für die Einführung von Code 4. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!