Einführung

Es ist Tag 5 des Aufkommens des Codes und heute haben wir ein interessantes Problem beim Ordnen von Seiten. Lassen Sie uns auf das Problem eingehen und wie ich es angegangen bin. Es war ein ziemlich einfaches Problem, wenn man es friedlich betrachtete, andernfalls würde es zu einem Karten-, Listen- und Index-Durcheinander kommen.

Sie k?nnen meine L?sungen hier auf GitHub ansehen.

Eingang

In der Eingabe für Tag 5 haben wir zwei Abschnitte. Der erste definiert die Regeln für die Reihenfolge der Seiten, insbesondere welche Seite vor welcher stehen soll, und der zweite enth?lt die tats?chliche Reihenfolge der Seiten.

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 erste Abschnitt enth?lt also die Regeln, der andere die Reihenfolge der Seiten und jede Zeile ist eine Abfrage oder eine Liste von Seiten als unsere eigentlichen Daten, die verarbeitet werden sollen. Wir müssen es bei der Verarbeitung der Teile 1 und 2 verwenden.

Leseabschnitte

Also müssen wir diese Abschnitte analysieren und sie in einer Datenstruktur lesen, die leichter zug?nglich sein k?nnte.

Eine M?glichkeit, das zu tun w?re

• Eine Liste mit zwei Abschnitten

• Der erste Abschnitt wird eine Liste sein

  • Die Liste ist eine Liste von Ganzzahlen, die die beiden Ganzzahlen enthalten, d. h. für Regeln

• Der zweite Abschnitt wird eine Liste sein

  • Die Liste ist eine Liste von Ganzzahlen, die die Seitenliste enthalten sollen

Die Datenstruktur würde also wie eine Liste oder eine Liste mit ganzen Zahlen aussehen.

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    for _, line := range bytes.Split(fileBytes, separator) {
        if string(line) != "" {
            lines = append(lines, string(line))
        }
    }

    sections := [][][]int{}
    for i, section := range lines {
        nums := [][]int{}
        lineStrs := strings.Split(section, "\n")
        separator := ","
        if i == 0 {
            separator = "|"
        }
        for _, lineStr := range lineStrs {
            if lineStr == "" {
                continue
            }
            numL := []int{}
            for _, numStr := range strings.Split(lineStr, separator) {
                num, _ := strconv.Atoi(numStr)
                numL = append(numL, num)
            }
            nums = append(nums, numL)
        }
        sections = append(sections, nums)
    }
    return sections
}

Die obige Funktion namens ReadFileSections übernimmt einen Pfad zur Eingabedatei und gibt ein Slice/Array der Liste der Ganzzahlen zurück, wie besprochen. Wir lesen zuerst die Datei und teilen die Bytes in zwei neue Zeilen auf, die als Trennzeichen für die Abschnitte dienen. Wir speichern die Zeilen als Liste von Zeichenfolgen, das erste enth?lt die Regelzeilen und das zweite die Seitenlistenzeilen.

Dann iterieren wir über den Abschnitt und teilen die einzelnen Zeilen für Abschnitte separat mit dem jeweiligen Trennzeichen auf, z. B. | für den ersten Abschnitt und (Leerzeichen) für den zweiten Abschnitt. Wir analysieren jede Zeile, um eine Liste von Ganzzahlen zu erhalten und h?ngen sie an die jeweiligen Abschnitte an.

Wir verfügen nun über Daten, mit denen wir die Regeln und Seiten erstellen k?nnen, die bei der Bearbeitung des Problems helfen.

Regeln konstruieren

Jetzt müssen wir die Regelliste für einen bequemen Zugriff verarbeiten. Wir müssen die Seitenzahl ermitteln, die nach einer bestimmten Seite erscheinen soll. Daher verwenden wir eine Zuordnung von Ganzzahlen mit einer Liste von Ganzzahlen, in der sich der Schlüssel befindet Die erste Zahl und der Wert sind die zweite Zahl (die Zahl, die in der Reihenfolge der Seiten danach erscheinen sollte).

func ConstructRules(rulesList [][]int) map[int][]int {
    rules := make(map[int][]int)
    for _, rule := range rulesList {
        rules[rule[0]] = append(rules[rule[0]], rule[1])
    }
    return rules
}

Wir durchlaufen einfach die Liste der Ganzzahlen und ordnen das erste Element als Schlüssel und den Wert als zweites Element in der Liste zu, um Folgendes zu visualisieren:

FROM

[][]int

[
    [47,53]
    [97,13]
    [97,61]
]

TO

map[int][]int
{
    47: [53]
    97: [13,61]
}

Also, jetzt haben Sie die Regeln als eine Karte von ganzen Zahlen mit ganzen Zahlen.

Erstellen von Indizes

Um den ersten und zweiten Teil einfacher zu machen, müssen wir nun für jede Zahl im Regelabschnitt eine Karte mit den Indizes erstellen, die in der Seitenliste angezeigt werden.

Also werden wir über die Regeln iterieren, die eine Karte von Ganzzahlen sind. Wir werden eine Karte von Ganzzahlen erstellen, die uns hilft, aus den Regeln eine eindeutige Liste von Ganzzahlen zu erstellen.

Sobald wir nun die Liste der Ganzzahlen aus den Regeln haben, werden wir alle Zahlen durchlaufen und in jeder Seitenzeile prüfen, welcher Index angezeigt wird, um eine Liste von Ganzzahlen (Indizes) zu erstellen.

Also iterieren wir über alle Zahlen in der Seitenzeile. Wenn wir diese Zahl in der Seitenliste finden, h?ngen wir den Index an. Wenn wir dies jedoch nicht tun, h?ngen wir -1 an, also für jede Zeile Für diese Nummer muss ein Index wie folgt angeh?ngt werden:

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

Im obigen Beispiel haben wir also 75 als Referenz genommen, wir erhalten den Index für jede Liste mit Seitenzahlen und wir erhalten die Liste der Indizes, in denen 75 vorkommt.

Dies kann nun mit der folgenden Funktion erfolgen:

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    for _, line := range bytes.Split(fileBytes, separator) {
        if string(line) != "" {
            lines = append(lines, string(line))
        }
    }

    sections := [][][]int{}
    for i, section := range lines {
        nums := [][]int{}
        lineStrs := strings.Split(section, "\n")
        separator := ","
        if i == 0 {
            separator = "|"
        }
        for _, lineStr := range lineStrs {
            if lineStr == "" {
                continue
            }
            numL := []int{}
            for _, numStr := range strings.Split(lineStr, separator) {
                num, _ := strconv.Atoi(numStr)
                numL = append(numL, num)
            }
            nums = append(nums, numL)
        }
        sections = append(sections, nums)
    }
    return sections
}

Also haben wir jetzt den Index jeder Seitennummernliste aus den Regeln zugeordnet.

Teil 1

Jetzt müssen wir für Teil eins jede Seitenaktualisierung (Zeile) durchlaufen und dann überprüfen, ob die Seitenzahlen den Regeln entsprechen. Jede Zahl sollte den Regeln folgen. Das hei?t, wenn eine Nummer nach einer bestimmten Nummer steht, die Regel jedoch vorgibt, dass sie davor stehen sollte, dann hat sie in diesem Update gegen die Seitennummerierungsregel versto?en, sodass wir sie nicht als die richtig geordnete Seite betrachten k?nnen, sondern die mittlere Seite hinzufügen müssen Nummer jedes Updates, das als Antwort für den ersten Teil richtig geordnet ist.

Dazu iterieren wir über jede Seitenaktualisierung, dann müssen wir über jede der Zahlen in dieser Seitenaktualisierung iterieren. Wir erhalten alle Regeln, die dieser Nummer zugeordnet sind (nennen wir sie die aktuelle Nummer), da wir eine haben Karte von ganzen Zahlen mit einer Liste von ganzen Zahlen. Jetzt müssen wir prüfen, ob die Zahl, in der wir uns gerade befinden, vor den Zahlen in ihren Regeln liegt. Wir überprüfen also den Index der aktuellen Zahl mithilfe der von uns erstellten Zahlenindizes, bei denen es sich um eine Abbildung der Zahl mit einer Liste von Ganzzahlen als Indizes handelt. Wir erhalten also die Liste der Indizes der Karte mit der aktuellen Nummer als Schlüssel für die Karte und dem Index in der Liste als Anzahl der Zeilen-/Seitenaktualisierungen, in denen wir uns gerade befinden.

Sobald wir dann den Index für die aktuelle Zahl haben, erhalten wir denselben für die zweite Zahl, die alle Zahlen in ihrer Regel umfasst, und wenn diese Zahl in ihrer Regel in dieser Seitenzeile/Aktualisierung vorhanden ist, d. h., sie ist es nicht -1 und wenn das der Fall ist, erhalten wir auf ?hnliche Weise den Index davon und prüfen, ob er nach der aktuellen Zahl gem?? der Regel erscheint. Wenn also eine Zahl gegen die Regel verst??t, müssen wir die Seitenaktualisierung als nicht korrekt markieren bestellen.

Da wir feststellen, dass gegen die Indexregel für diese Seitenaktualisierung versto?en wird, markieren wir die Bestellung als falsch. Wenn wir sehen, dass die geordnete Flagge immer noch wahr ist, aktualisieren wir die Punktzahl mit dem mittleren Element dieser Seitenaktualisierung.

func ConstructRules(rulesList [][]int) map[int][]int {
    rules := make(map[int][]int)
    for _, rule := range rulesList {
        rules[rule[0]] = append(rules[rule[0]], rule[1])
    }
    return rules
}

Also, um es noch einmal zu wiederholen: Wir erstellen eine Funktion namens GetOrderedPage mit Regel- und Zahlenindizes als Karte von Ganzzahlen mit einer Liste von Ganzzahlen und den Seiten, die eine Liste von Ganzzahlen sind, als Seitenaktualisierung. Wir geben die Punktzahl als Ausgabe dieser Funktion zurück.

Wir durchlaufen jede Seitenaktualisierung, dann prüfen wir jede Seitennummer in der Aktualisierung, ob die Regel dieser Nummer vorliegt, und wenn der Index dieser Nummer niedriger als die aktuelle Nummer ist, markieren wir sie als nicht geordnet und daher Am Ende jeder Seitenaktualisierung aktualisieren wir die Partitur mit dem mittleren Element der Seitenaktualisierung, sofern die Reihenfolge korrekt ist.

Das wird Teil eins zusammengefasst sein, wir müssen nur noch die Punktzahl der korrekt geordneten Seitenaktualisierungen ermitteln.

Teil 2

In Teil 2 müssen wir jedoch prüfen, ob die Seitenaktualisierung in Ordnung ist. Ist dies nicht der Fall, müssen wir sie in Ordnung bringen.

Wir machen dasselbe für Teil 2, wir müssen jede Seitenaktualisierung durchlaufen und für jede Nummer in dieser Seitenaktualisierung müssen wir prüfen, ob gegen die Regel versto?en wird oder nicht, falls wir auf einen Fall sto?en, in dem dies der Fall ist Wenn die Regel für eine beliebige Zahl verletzt wird, markieren wir die bestellte Flagge als falsch. Dies verwenden wir, um die Reihenfolge der Seitenaktualisierungen zu korrigieren. Nachdem wir die Seiten in dieser Seitenzeile/Aktualisierung aktualisiert haben, müssen wir die Partitur mit dem mittleren Element der korrigierten Reihenfolge der Seitenaktualisierung hinzufügen.

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

Wir müssen die CorrectPageOrder-Funktion implementieren, die die Seitenzeile oder Seitenaktualisierung und die Regeln berücksichtigt. Wir müssen eine neue Seitenaktualisierung erstellen, die die Seite füllt, die allen Regeln folgt.

Also verfolgen wir zun?chst den Index der initialisierten Elemente und aktualisieren den Index, wenn wir das Element davor verschieben müssen.

Also durchlaufen wir alle Zahlen in der Seitenaktualisierung und setzen den Index vor einer beliebigen Zahl in der Regel. Wenn wir in der Regelzuordnung auf eine solche Zahl sto?en, müssen wir den Index mit dem Index dieser Zahl aktualisieren.

Und sobald wir den Index haben, zu dem wir das Element austauschen m?chten, erstellen wir einen Slice vor diesem Index und h?ngen diese Zahl daran an und h?ngen alles nach diesem Index an.

func ReadFileSections(path string) [][][]int {

    fileBytes := ReadFileBytes(path)
    lines := []string{}
    separator := []byte("\n\n")
    for _, line := range bytes.Split(fileBytes, separator) {
        if string(line) != "" {
            lines = append(lines, string(line))
        }
    }

    sections := [][][]int{}
    for i, section := range lines {
        nums := [][]int{}
        lineStrs := strings.Split(section, "\n")
        separator := ","
        if i == 0 {
            separator = "|"
        }
        for _, lineStr := range lineStrs {
            if lineStr == "" {
                continue
            }
            numL := []int{}
            for _, numStr := range strings.Split(lineStr, separator) {
                num, _ := strconv.Atoi(numStr)
                numL = append(numL, num)
            }
            nums = append(nums, numL)
        }
        sections = append(sections, nums)
    }
    return sections
}

Diese Funktion findet also den Index einer Zahl, um ihn ganz links (am Anfang der Liste) zu platzieren, sodass wir keine Regeln für diese Zahl verletzen. Anschlie?end erstellen wir einen Slice, um diese Zahl vorher anzuh?ngen diesen Index und h?nge alles nach diesem Index an.

Das war's mit Teil zwei, wir haben die Seitenreihenfolge aktualisiert, falls es Unstimmigkeiten in der Seitenreihenfolge gab.

Sie k?nnen meine L?sungen hier auf GitHub ansehen.

Abschluss

Das war's ab Tag 5 von Advent of Code in Golang. Lassen Sie mich wissen, ob Sie Vorschl?ge haben und wie Sie daran vorgegangen sind. Gibt es bessere L?sungen?

Viel Spa? beim Programmieren :)

Das obige ist der detaillierte Inhalt vonAdvent of Code ay n Golang: Bestellseiten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!