Introduction

C'est le cinquième jour de l'avènement du code, et aujourd'hui nous avons un problème intéressant d'ordre des pages. Examinons le problème et comment je l'ai abordé. C'était un problème assez simple si on le pensait pacifiquement, sinon cela se retrouverait dans un désordre de cartes, de listes et d'index.

Vous pouvez consulter mes solutions ici sur GitHub.

Saisir

Dans l'entrée du jour 5, nous avons deux sections, la première définit les règles d'ordre des pages, plus précisément quelle page doit précéder laquelle et la seconde contient l'ordre réel des pages.

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

Ainsi, la première section contient les règles définies, l'autre l'ordre des pages et chaque ligne est une requête ou une liste de pages en tant que données réelles à traiter. Nous devons l'utiliser dans le traitement des parties 1 et 2.

Sections de lecture

Nous devons donc analyser ces sections et les lire dans une structure de données qui pourrait être plus facile d'accès.

Une fa?on de le faire serait

• Une liste avec deux sections

• La première section sera une liste

  • La liste sera une liste d'entiers pour contenir les deux entiers, c'est-à-dire pour les règles

• La deuxième section sera une liste

  • La liste sera une liste d'entiers pour contenir la liste des pages

Ainsi, la structure des données ressemblerait à une liste de liste de liste d'entiers.

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
}

La fonction ci-dessus appelée ReadFileSections prend un chemin vers le fichier d'entrée et renvoie une tranche/un tableau) de la liste de la liste d'entiers comme indiqué. Nous lisons d'abord le fichier et divisons les octets en deux caractères de nouvelle ligne qui seront le séparateur des sections, nous stockerons les lignes sous forme de liste de cha?nes, la première contiendra les lignes de règle et la seconde contiendra les lignes de liste de pages.

Ensuite, nous parcourons la section et divisons les lignes individuelles pour les sections séparément avec le séparateur respectif, c'est-à-dire | pour la première section et (espace) pour la deuxième section. Nous analysons chaque ligne pour obtenir une liste d'entiers et les ajoutons aux sections respectives.

Nous disposons donc désormais de données que nous pouvons utiliser pour construire les règles et les pages permettant de traiter le problème.

Construire des règles

Maintenant, nous devons traiter la liste de règles pour un accès pratique, nous devons obtenir le numéro de page qui doit appara?tre après une page donnée, nous allons donc utiliser une carte d'entiers avec une liste d'entiers, où la clé sera le premier chiffre et celui de la valeur seront le deuxième chiffre (le chiffre qui doit appara?tre après dans l'ordre des pages).

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
}

Nous parcourons simplement la liste des entiers et mappons le premier élément comme clé et la valeur comme deuxième élément de la liste, afin de visualiser?:

FROM

[][]int

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

TO

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

Alors, ayez maintenant les règles sous forme de carte d'entiers avec des entiers.

Construire des indices

Maintenant, pour faciliter la première et la deuxième parties, nous devons créer une carte pour chaque numéro dans la section des règles avec les indices qui apparaissent dans la liste des pages.

Donc, nous allons parcourir les règles, qui est une carte d'entiers et d'entiers, nous allons créer une carte d'entiers qui nous aidera à créer une liste unique d'entiers à partir des règles.

Maintenant, une fois que nous avons la liste des entiers des règles, nous allons parcourir tous les nombres et sur chaque ligne de page, vérifier sur quel index il appara?t, pour créer une liste d'entiers(indices).

Donc, nous parcourons tous les nombres de la ligne de pages, si nous trouvons ce numéro dans la liste des pages, nous ajoutons l'index, cependant, si nous ne le faisons pas, nous ajoutons -1, donc pour chaque ligne nous besoin d'avoir un index ajouté pour ce numéro comme ceci?:

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

Donc, dans l'exemple ci-dessus, nous avons pris 75 comme référence, nous obtiendrons l'index pour chaque liste de numéros de page, et nous obtiendrons la liste des index où 75 appara?t.

Maintenant, cela peut être fait avec la fonction suivante?:

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
}

Donc, nous avons maintenant l'index mappé à chaque liste de numéros de page à partir des règles.

Partie 1

Maintenant, pour la première partie, nous devons parcourir chaque mise à jour de page (ligne), puis nous devons vérifier si les numéros de page suivent les règles, chaque numéro doit suivre les règles. Cela signifie que si un numéro se trouve après un certain numéro mais que la règle dit qu'il devrait être avant, alors il a violé la règle de numérotation des pages dans cette mise à jour, nous ne pouvons donc pas le considérer comme la page correctement ordonnée, nous devons ajouter la page du milieu. numéro de chaque mise à jour qui est correctement ordonné comme réponse pour la première partie.

Pour ce faire, nous parcourons chaque mise à jour de page, puis nous devons parcourir chacun des numéros de cette mise à jour de page, nous obtenons toutes les règles associées à ce numéro (appelons-le le numéro actuel) puisque nous avons un carte d'entiers avec une liste d'entiers. Maintenant, nous devons vérifier si le numéro dans lequel nous nous trouvons actuellement est avant les chiffres dans ses règles. Ainsi, nous vérifions avec l'index du nombre actuel en utilisant les indices numériques que nous avons créés qui sont une carte du nombre avec une liste d'entiers comme indices. Ainsi, nous obtenons la liste des indices de la carte avec le numéro actuel comme clé de la carte et l'index dans la liste comme nombre de mises à jour de ligne/page dans lesquelles nous nous trouvons actuellement.

Ensuite, une fois que nous avons obtenu l'index du numéro actuel, nous obtenons la même chose pour le deuxième numéro qui est tous les nombres de sa règle, et si ce numéro dans sa règle est présent dans cette ligne/mise à jour de page, c'est-à-dire qu'il est pas -1 et si tel est le cas, nous obtenons son index de la même manière et vérifions s'il appara?t après le numéro actuel suivant la règle. Et donc, si un numéro enfreint la règle, nous devons marquer la mise à jour de la page comme n'étant pas correcte. commande.

Comme nous constatons que la règle d'indexation pour cette mise à jour de page n'est pas respectée, nous marquons l'ordre comme faux. Si nous constatons que l'indicateur ordonné est toujours vrai, nous mettons à jour le score avec l'élément central de cette mise à jour de page.

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
}

Donc, pour réitérer, nous créons une fonction appelée GetOrderedPage avec des indices de règles et de nombres comme une carte d'entiers avec une liste d'entiers et les pages qui sont une liste d'entiers lors de la mise à jour de la page. Nous renvoyons le score en sortie de cette fonction.

Nous parcourons chacune des mises à jour de page, puis à travers chaque numéro de page de la mise à jour, nous vérifions la règle de ce numéro et si l'index de celui-ci est inférieur au numéro actuel, nous le marquons comme non ordonné, et donc à la fin de chaque mise à jour de page nous mettons à jour le score avec l'élément central de la mise à jour de page, si l'ordre est correct.

Donc, cela sera résumé dans la première partie, il nous suffit d'obtenir le score des mises à jour de pages correctement ordonnées.

Partie 2

Dans la partie 2 cependant, nous devons vérifier si la mise à jour de la page est en ordre, si ce n'est pas le cas, nous devons la mettre en ordre.

Nous faisons la même chose pour la partie 2, nous devons parcourir chacune des mises à jour de page, et pour chaque numéro de cette mise à jour de page, nous devons vérifier si la règle est violée ou non, si nous rencontrons un cas où la règle est violée pour n'importe quel numéro, nous marquons le drapeau ordonné comme faux, nous l'utiliserons pour corriger l'ordre des mises à jour de la page. Après avoir mis à jour les pages dans cette ligne/mise à jour de page, nous devons ajouter le score avec l'élément central de l'ordre corrigé de mise à jour de la page.

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

Nous devons implémenter la fonction CorrectPageOrder qui prend en compte la ligne de page ou la mise à jour de la page et les règles, nous devons créer une nouvelle mise à jour de page, qui remplira la page qui suit toutes les règles.

Donc, nous gardons d'abord une trace de l'index des éléments initialisés et mettons à jour l'index si nous devons déplacer l'élément avant lui.

Donc, nous parcourons tous les nombres dans la mise à jour de la page et définissons l'index avant tout nombre dans la règle, si nous rencontrons un tel nombre dans la carte des règles, nous devons mettre à jour l'index avec l'index de ce numéro.

Et une fois que nous avons l'index vers lequel nous voulons échanger l'élément, nous créons une tranche avant cet index et y ajoutons ce numéro, et ajoutons tout après cet index.

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
}

Ainsi, cette fonction trouvera l'index d'un nombre pour le placer à l'extrême gauche (début de la liste) afin que nous ne violions aucune règle pour ce nombre, puis nous créons une tranche pour ajouter ce nombre avant cet index et ajoutez tout après cet index.

C'est tout pour la deuxième partie, nous avons mis à jour l'ordre des pages s'il y avait des écarts dans l'ordre des pages.

Vous pouvez consulter mes solutions ici sur GitHub.

Conclusion

Donc, ?a y est depuis le jour 5 de Advent of Code in Golang, faites-moi savoir si vous avez des suggestions et comment vous l'avez abordé. de meilleures solutions ?

Joyeux codage?:)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!