L'énigme du clavier de l'avènement du Code Day

Jour 21 : énigme du clavier

Repo GitHub - Solution

Le défi d'aujourd'hui était difficile et il m'a fallu 2 jours pour avoir un peu de temps pour le résoudre, ainsi que pour bien comprendre la logique. Quelque chose que j'ai découvert cette année, c'est que j'ai du mal à comprendre les intentions des instructions.

J'espère que, comme moi, vous avez appris quelque chose de ce défi et de cette solution. Je constate que chaque année je participe à Advent of Code, j'apprends beaucoup, c'est pourquoi j'aime essayer différentes langues ou sortir de ma zone de confort. Je considère Advent of Code comme une opportunité d'apprentissage/développement où les développeurs devraient partager leurs connaissances et leurs idées, plutôt que de le traiter comme une simple compétition.

Un autre essai sur Python aujourd'hui et je suis satisfait de la solution. Quelque chose que j'ai appris aujourd'hui était : Classes immuables utilisant l'annotation @dataclass(frozen=True) sur une déclaration de classe.

J'ai créé la classe Location en tant que classe d'assistance pour naviguer et mettre à jour les coordonnées (un peu comme je l'ai fait précédemment avec la classe Point dans certaines solutions C#.

En tant que personne venant d'un milieu fortement typé C# / .Net, j'ai essayé d'ajouter des types à mon code pour m'aider à visualiser avec quoi je travaillais pendant ce problème complexe. J'ai également l'habitude de faire cela en écrivant TypeScript, donc presque une seconde nature.

Le problème d'aujourd'hui

**La première partie **présente le problème de la navigation et du contrôle de plusieurs robots pour transmettre des instructions au robot suivant afin de saisir des codes sur un clavier numérique.

La deuxième partie s'appuie sur le problème en augmentant la complexité grâce à une chaîne de robots et de claviers directionnels, démontrant la nature exponentielle des dépendances à plusieurs niveaux.

Procédure pas à pas

Comme nous connaissons déjà la disposition des directions et du clavier, nous pouvons créer les dictionnaires de toutes les cartographies de localisation et directions dans lesquelles ils peuvent se déplacer.

Mise en cache (cache et move_cache)

cache : Stocke les séquences les plus courtes précédemment calculées pour éviter les calculs redondants et améliorer les performances.

moves_cache : Stocke toutes les séquences de mouvements valides entre deux boutons quelconques d'un clavier, précalculées pour une recherche rapide.

Calcul de la longueur la plus courte (shortest_length)

Calcule de manière récursive la séquence la plus courte d'appuis sur un bouton pour saisir un code donné.

Gère le chaînage à plusieurs niveaux de claviers en parcourant les niveaux (cur_degree) jusqu'à la limite (deep_limit).

*Se déplace entre les positions (moves_between_positions)
*

Calcule toutes les séquences de mouvements valides entre deux boutons d'un clavier, garantissant que les robots ne paniquent en pointant vers des positions invalides (les espaces).

Initialisation du cache (create_cache_moves)

Précalcule les séquences de mouvements valides pour toutes les paires de boutons sur les claviers numériques et directionnels, économisant ainsi le calcul à l'exécution.

Les fonctions de résolution parcourent ensuite l'entrée en calculant sa complexité en multipliant la longueur de la séquence par la partie numérique du code, puis résument simplement les complexités de tous les codes selon les exigences du puzzle.

Permutations

À quoi servent les permutations ?

La fonction de permutations en Python (du module itertools) génère tous les arrangements ordonnés possibles d'une collection d'éléments.

Par exemple :

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

Cela produira :

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

Chaque permutation est une séquence unique contenant tous les éléments de la collection originale, mais dans un ordre différent.

Pourquoi utiliser des permutations et non des combinaisons ?

permutations :

Génère tous les arrangements ordonnés possibles d'une collection d'articles.
L'ordre des articles compte.

attendu,
combinaisons :

Génère toutes les sélections non ordonnées possibles d'une collection d'éléments.

L'ordre des articles n'a pas d'importance.

Pourquoi l’ordre est-il important dans ce scénario ?

Navigation au clavier : La position du robot sur le clavier change après chaque mouvement, de sorte que la séquence dans laquelle les mouvements sont effectués a un impact direct sur le résultat.

Vérification des mouvements valides : La fonction vérifie la validité des positions intermédiaires pendant la navigation. Changer l'ordre des mouvements peut conduire à un chemin invalide.

Quand les combinaisons seraient-elles utiles à la place ?

Les combinaisons pourraient être utiles dans des scénarios où l'ordre des mouvements n'a pas d'importance ou où vous sélectionnez un sous-ensemble de mouvements ou de boutons sans vous soucier de leur séquence.

L'utilisation actuelle des permutations est nécessaire car l'ordre des mouvements est important pour la navigation au clavier. Le remplacer par des combinaisons briserait la logique du programme. Si la tâche nécessitait de trouver tous les groupes uniques de mouvements ou de touches, quelle que soit la séquence, alors les combinaisons seraient plus appropriées.

La partie la plus difficile du puzzle a été de trouver un moyen propre et agréable de suivre le niveau de profondeur (début) des instructions du robot -- cela m'a pris un peu de temps pour y accorder toute mon attention.

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!