Advent of Code ay n Golang: Bestellseiten

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.

Herr-Destruktiv / Advent_of_code

Aufkommen des Codes

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.

Herr-Destruktiv / Advent_of_code

Aufkommen des Codes

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!