Maison développement back-end Tutoriel Python Comment coder un algorithme de tri pour l'avènement du code 4

Comment coder un algorithme de tri pour l'avènement du code 4

Dec 11, 2024 am 08:37 AM

Dans le post précédent, j'ai brièvement mentionné que je participais à l'Avent du Code de cette année. Par coïncidence, dans l'une des énigmes, en particulier celle publiée le cinquième jour, il s'agit de fixer l'ordre des pages dans une liste. Cela est arrivé peu de temps après avoir publié un article sur la mise en œuvre d'un algorithme de tri, alors je pense que je devrais écrire à ce sujet.

How to code a Sorting Algorithm for Advent of Code 4
Une jolie image représentant un algorithme de tri

Pour ceux qui n'ont pas entendu parler d'Advent of Code, c'est un événement annuel animé par Eric Wastl. Chaque année, il raconte une histoire qui se déroule pendant la période des fêtes. Cette année, il s'agit de rechercher l'historien en chef, peut-être un personnage important de chaque grand lancement de traîneau de Noël. Le défi se déroulera du 1er décembre de chaque année au 25. Chaque jour, l'intrigue progresse et contient un puzzle de programmation (et il est accompagné d'une entrée).

Dans la narration de l'histoire, le puzzle est généralement défini clairement et comprend des cas de test. Chaque puzzle est divisé en deux parties et la deuxième partie n'apparaît qu'après avoir soumis la première réponse.

Les participants peuvent implémenter n'importe quel algorithme, dans n'importe quel langage, ou même sauter complètement la programmation, à condition que la réponse dérivée corresponde. Cette année, j'essaie de coder les solutions en Python, et après 9 jours, j'ai l'impression d'avoir beaucoup appris tout au long du voyage.

Le jour 5, l'histoire a demandé de l'aide pour l'impression des manuels de sécurité. L'entrée contenait à la fois les règles de la page et les listes de pages que l'elfe essayait d'imprimer.

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
Copier après la connexion
Copier après la connexion
Copier après la connexion

Commençons par analyser l'entrée :

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()), ((), ())
    )
Copier après la connexion
Copier après la connexion

La fonction reçoit l'entrée sous forme de chaîne nommée input, la divise en lignes avec .splitlines(), à envoyer dans la fonction interne pour produire deux tuples, un pour les règles de page et un autre pour la séquence de pages. Le code différencie les deux types de définitions grâce au séparateur | pour les règles de page, et pour les pages.

Dans la première partie du puzzle, l'histoire demandait de vérifier si les pages étaient dans l'ordre. Commençons par implémenter une fonction qui fait le travail :

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules
Copier après la connexion
Copier après la connexion

Et puis une autre fonction qui envoie toutes les combinaisons de pages (combinations((1,2,3), 2) renvoie 1,2, 1,3 et 2,3) :

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)
    )
Copier après la connexion
Copier après la connexion

La principale raison pour laquelle j'ai séparé ces deux fonctions en fonctions individuelles est que je souhaite garder chaque partie aussi petite que possible. D'après mon expérience, garder les choses suffisamment petites les rend non seulement testables, mais cela aide généralement également au débogage de l'entrée finale (qui est généralement déraisonnablement grande).

Souvent, la partie 2 est une surprise, et il n'est pas rare de constater qu'elle nécessite une révision de la conception du code pour la partie 1. Il peut s'agir d'une petite variation par rapport à quelque chose que vous avez implémenté ou nécessiter une fonction différente. ordre d'invocation pour un objectif différent, etc. Je garde l'habitude d'écrire de courtes fonctions au travail (comme alternative aux commentaires).

Les petites fonctions comme celle-ci ne fonctionnent que si les noms sont bons, vous devez donc faire très attention à la dénomination. Cela demande de la pratique, mais une fois que vous y parvenez, cette approche peut rendre le code remarquablement auto-documenté. Les fonctions à plus grande échelle peuvent se lire comme une histoire, et le lecteur peut choisir dans quelles fonctions se plonger pour plus de détails selon ses besoins.

extrait de l'article intitulé Function length, rédigé par Martin Fowler

Retour au puzzle.

À la fin, le puzzle demandait la somme des numéros de page du milieu pour tous les cas où les pages étaient correctement ordonnées.

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
Copier après la connexion
Copier après la connexion
Copier après la connexion

Assez simple, si vous avez tout fait correctement, il suffit de comprendre une liste (car les développeurs Python préfèrent cela à la carte/filtre).

Ensuite, l'algorithme de tri :

Dans la continuité de la première partie, la deuxième partie souhaitait la somme des pages du milieu, mais pour les cas où les pages n'étaient pas correctement ordonnées. L'instruction demandait également de corriger la commande avant de récupérer le numéro de page du milieu.

Alors que mes pairs ont réussi à le résoudre sans un algorithme de tri complet, j'ai décidé de le faire exactement de la même manière que le puzzle décrit plus tôt, dans la section expliquant les règles de la page. J'ai déjà fait la partie comparaison (check_pair), maintenant j'ai besoin d'une fonction qui déplacerait les éléments.

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()), ((), ())
    )
Copier après la connexion
Copier après la connexion

Supposons que j'ai 1,2,3,4,5 et que la fonction déplace le numéro entrant juste avant le numéro actuel. En supposant que courant = 2 et entrant = 4, alors j'obtiendrai 1,4,2,3,5 en retour (en supposant que nous organisons en fonction de la valeur numérique croissante).

How to code a Sorting Algorithm for Advent of Code 4
Ma tentative infructueuse d'expliquer l'algorithme à un ami

Il s'agit ensuite de transformer l'algorithme, présenté dans mon brouillon manuscrit, en code réel.

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules
Copier après la connexion
Copier après la connexion

Ouais, malheureusement c'est dans une récursion. Je devrais poster la première version, cela pourrait être plus convivial à lire :

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)
    )
Copier après la connexion
Copier après la connexion

Les deux sont essentiellement les mêmes, la version fonctionnelle finale étant légèrement optimisée. En me référant au brouillon de capture d'écran, j'ai deux pointeurs, le soulignement jaune est nommé pointeur dans le code et le soulignement bleu entrant.

L'algorithme fonctionne comme suit :

  1. Cela commence par placer le pointeur sur le premier élément.
  2. Au départ, entrant est toujours l'élément à côté.
  3. Le pointeur entrant parcourra un élément à la fois et déplacera la valeur juste avant le courant s'il enfreint la règle.
  4. Une fois que cela se produit, le pointeur entrant se réinitialise et revient au suivant du courant.
  5. Le pointeur actuel ne change pas de position, mais il pointe maintenant vers le nouvel élément qui a été inséré à l'étape précédente.

Si le pointeur entrant parvient à parcourir le reste de la liste sans introduire de changement, nous avançons le pointeur actuel (et le pointeur entrant réinitialisé à la position à côté) et répétons le processus.

Le processus se termine une fois que l'algorithme a terminé de comparer les 2 derniers éléments, puis renvoie les pages triées comme résultat. Ensuite, nous pouvons procéder à l'assemblage de tout ce que nous avons pour la partie 2 :

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
Copier après la connexion
Copier après la connexion
Copier après la connexion

Le code des deux parties est similaire. Il s'agit juste d'une légère modification de part1, juste d'une variation dans la clause filter, et get_middle reçoit une liste triée à la place. Essentiellement, c'est comme si j'assemblais une réponse à partir de blocs de construction sous forme de fonctions, dans une combinaison légèrement différente.

Bien que ce ne soit toujours pas exactement un algorithme efficace, car la complexité temporelle est proche de O(n^2). Selon le compagnon d'IA en cascade en planche à voile, l'algorithme ressemble à certains égards au tri par insertion (oui, c'est à ce moment-là que l'outil d'IA est utile, fournissant des explications aux algorithmes).

C'est tout pour aujourd'hui, je suis content que l'algorithme fonctionne bien, même si ma vie est actuellement en désordre (je viens de me retirer d'un projet en raison de problèmes de financement). J'espère que les choses s'amélioreront avec le temps, et j'écrirai à nouveau la semaine prochaine.

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

<🎜>: Bubble Gum Simulator Infinity - Comment obtenir et utiliser les clés royales
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
<🎜>: Grow A Garden - Guide de mutation complet
3 Il y a quelques semaines By DDD
Nordhold: Système de fusion, expliqué
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Comment déverrouiller le grappin
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Tutoriel Java
1675
14
Tutoriel PHP
1278
29
Tutoriel C#
1257
24
Python vs C: courbes d'apprentissage et facilité d'utilisation Python vs C: courbes d'apprentissage et facilité d'utilisation Apr 19, 2025 am 12:20 AM

Python est plus facile à apprendre et à utiliser, tandis que C est plus puissant mais complexe. 1. La syntaxe Python est concise et adaptée aux débutants. Le typage dynamique et la gestion automatique de la mémoire le rendent facile à utiliser, mais peuvent entraîner des erreurs d'exécution. 2.C fournit des fonctionnalités de contrôle de bas niveau et avancées, adaptées aux applications haute performance, mais a un seuil d'apprentissage élevé et nécessite une gestion manuelle de la mémoire et de la sécurité.

Apprendre Python: 2 heures d'étude quotidienne est-elle suffisante? Apprendre Python: 2 heures d'étude quotidienne est-elle suffisante? Apr 18, 2025 am 12:22 AM

Est-ce suffisant pour apprendre Python pendant deux heures par jour? Cela dépend de vos objectifs et de vos méthodes d'apprentissage. 1) Élaborer un plan d'apprentissage clair, 2) Sélectionnez les ressources et méthodes d'apprentissage appropriées, 3) la pratique et l'examen et la consolidation de la pratique pratique et de l'examen et de la consolidation, et vous pouvez progressivement maîtriser les connaissances de base et les fonctions avancées de Python au cours de cette période.

Python vs. C: Explorer les performances et l'efficacité Python vs. C: Explorer les performances et l'efficacité Apr 18, 2025 am 12:20 AM

Python est meilleur que C dans l'efficacité du développement, mais C est plus élevé dans les performances d'exécution. 1. La syntaxe concise de Python et les bibliothèques riches améliorent l'efficacité du développement. Les caractéristiques de type compilation et le contrôle du matériel de CC améliorent les performances d'exécution. Lorsque vous faites un choix, vous devez peser la vitesse de développement et l'efficacité de l'exécution en fonction des besoins du projet.

Python vs C: Comprendre les principales différences Python vs C: Comprendre les principales différences Apr 21, 2025 am 12:18 AM

Python et C ont chacun leurs propres avantages, et le choix doit être basé sur les exigences du projet. 1) Python convient au développement rapide et au traitement des données en raison de sa syntaxe concise et de son typage dynamique. 2) C convient à des performances élevées et à une programmation système en raison de son typage statique et de sa gestion de la mémoire manuelle.

Quelle partie fait partie de la bibliothèque standard Python: listes ou tableaux? Quelle partie fait partie de la bibliothèque standard Python: listes ou tableaux? Apr 27, 2025 am 12:03 AM

PythonlistSaReparmentofthestandardLibrary, tandis que les coloccules de colocède, tandis que les colocculations pour la base de la Parlementaire, des coloments de forage polyvalent, tandis que la fonctionnalité de la fonctionnalité nettement adressée.

Python: automatisation, script et gestion des tâches Python: automatisation, script et gestion des tâches Apr 16, 2025 am 12:14 AM

Python excelle dans l'automatisation, les scripts et la gestion des tâches. 1) Automatisation: La sauvegarde du fichier est réalisée via des bibliothèques standard telles que le système d'exploitation et la fermeture. 2) Écriture de script: utilisez la bibliothèque PSUTIL pour surveiller les ressources système. 3) Gestion des tâches: utilisez la bibliothèque de planification pour planifier les tâches. La facilité d'utilisation de Python et la prise en charge de la bibliothèque riche en font l'outil préféré dans ces domaines.

Python pour l'informatique scientifique: un look détaillé Python pour l'informatique scientifique: un look détaillé Apr 19, 2025 am 12:15 AM

Les applications de Python en informatique scientifique comprennent l'analyse des données, l'apprentissage automatique, la simulation numérique et la visualisation. 1.Numpy fournit des tableaux multidimensionnels et des fonctions mathématiques efficaces. 2. Scipy étend la fonctionnalité Numpy et fournit des outils d'optimisation et d'algèbre linéaire. 3. Pandas est utilisé pour le traitement et l'analyse des données. 4.Matplotlib est utilisé pour générer divers graphiques et résultats visuels.

Python pour le développement Web: applications clés Python pour le développement Web: applications clés Apr 18, 2025 am 12:20 AM

Les applications clés de Python dans le développement Web incluent l'utilisation des cadres Django et Flask, le développement de l'API, l'analyse et la visualisation des données, l'apprentissage automatique et l'IA et l'optimisation des performances. 1. Framework Django et Flask: Django convient au développement rapide d'applications complexes, et Flask convient aux projets petits ou hautement personnalisés. 2. Développement de l'API: Utilisez Flask ou DjangorestFramework pour construire RestulAPI. 3. Analyse et visualisation des données: utilisez Python pour traiter les données et les afficher via l'interface Web. 4. Apprentissage automatique et AI: Python est utilisé pour créer des applications Web intelligentes. 5. Optimisation des performances: optimisée par la programmation, la mise en cache et le code asynchrones

See all articles