So codieren Sie einen Sortieralgorithmus für die Einführung von Code 4

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!