Courtoisie photo :jimray
Nous avons vu dans un précédent article d'introduction d'awk qu'awk peut être un outil efficace pour tout, des petites lignes simples à certaines applications intéressantes. Il existe certainement des langages plus complexes à notre disposition si une situation l'exige; perl et python me viennent à l'esprit. Les applications nécessitant une prise en charge réseau, un accès à une base de données, des interfaces utilisateur, des données binaires ou une prise en charge et une complexité de bibliothèque plus étendues sont mieux laissées à d'autres langages avec une meilleure prise en charge dans ces domaines.
Néanmoins, awk est un superbe langage pour tester des algorithmes et des applications avec une certaine complexité , en particulier lorsque le problème peut être divisé en morceaux qui peuvent être diffusés dans le cadre d'un tuyau. C'est un outil idéal pour augmenter les fonctionnalités de la programmation shell car il est omniprésent; trouvé sous une forme ou une autre sur presque tous les systèmes Unix/Linux/BSD. De nombreux problèmes liés au texte, aux lignes de journal ou aux tables de symboles sont facilement résolus ou à tout le moins prototypés avec awk avec les autres outils trouvés sur les systèmes Unix/Linux.
Alors que awk se prête bien à fonctionner sur l'entrée une ligne à la fois, en traitant puis en envoyant une sortie pour chaque ligne, il peut également être utilisé dans une application de style batch plus traditionnelle où il lit toutes les entrées, traite puis envoie le sortie traitée.
Encore un autre résolveur de puzzle Sudoku - YASPS pour Awk
L'application que j'ai choisi d'utiliser comme exemple est "encore un autre solutionneur de sudoku". Je dois avouer d'emblée que je ne me suis jamais assis pour résoudre l'un de ces casse-tête moi-même, mais que j'ai esquissé cela en quelques jours tout en me déplaçant dans un train et en regardant d'autres personnes y travailler. C'était beaucoup plus amusant, je pense, que de faire n'importe lequel des puzzles...
Télécharger le programme YASPS pour Awk :solve.awk
Le format d'entrée que j'ai choisi est facile à analyser dans awk et assez traditionnel dans l'environnement Unix. Les lignes vides et celles commençant par un caractère dièse (#) sont ignorées, ce qui facilite l'insertion de commentaires. Des espaces supplémentaires peuvent être utilisés entre les colonnes pour plus de lisibilité. Un exemple est illustré dans la figure suivante :
------------------------------------------------------------------------------- # I forget where I got this.. # this is one of the hardest ones I've found for this algorithm, although # after transposing the matrix it can be solved in a fraction of the time 2 0 0 6 7 0 0 0 0 0 0 6 0 0 0 2 0 1 4 0 0 0 0 0 8 0 0 5 0 0 0 0 9 3 0 0 0 3 0 0 0 0 0 5 0 0 0 2 8 0 0 0 0 7 0 0 1 0 0 0 0 0 4 7 0 8 0 0 0 6 0 0 0 0 0 0 5 3 0 0 8 -------------------------------------------------------------------------------
Il n'y a presque pas de vérification d'erreur dans ce programme, mais il serait facile de l'ajouter devant ou dans le cadre d'un script wrapper. Je vais laisser cela comme un exercice pour le lecteur.
Ce programme utilise un algorithme très simple de backtracking récursif en profondeur d'abord avec élimination initiale et continue des entrées invalides. Awk n'a peut-être pas le pouvoir expressif de représenter des données complexes comme perl ou d'autres langages, mais avec précaution, de nombreux problèmes et ensembles de données de taille moyenne peuvent être utilisés. Cet algorithme n'est peut-être pas le meilleur, mais il est certainement assez rapide pour la plupart des problèmes et facile à mettre en œuvre.
Quel que soit le problème, la représentation efficace des données rend la tâche de conception d'un programme beaucoup plus facile. J'ai représenté l'état complet du puzzle dans une matrice appelée "maître". Ceci n'est guère utilisé pour beaucoup, sauf pour garder une trace de ce qui est où et pour faire la sortie finale.
Les principales variables de cheval de bataille sont trois autres tableaux. Intuitivement, nous savons grâce à la méthode récursive d'essais et d'erreurs que nous avons choisie que nous devrons vérifier assez souvent la validité des numéros d'essai. Pour accélérer ce processus, nous maintenons des tableaux associatifs pour stocker l'état actuel des lignes, des colonnes et de chaque région (qui, bien que techniquement incorrect, nous l'appellerons un "quadrant"). Ce sont les tableaux R, C et Q. (Notez que awk est sensible à la casse.)
Parfois, cela aide lorsque vous essayez de factoriser des calculs courants à partir de boucles for imbriquées ou d'appels de fonctions récursifs pour pré-calculer des valeurs qui sont souvent utilisées. J'avais essayé cela avec la matrice "regmap" qui stockait un numéro de quadrant compte tenu des valeurs de ligne et de colonne, mais j'ai trouvé que le gain de temps dans ce cas était ambigu. Je l'ai laissé en commentaire, mais votre kilométrage peut varier et la technique est souvent très utile.
Les algorithmes récursifs sont souvent mieux conçus et donc décrits de manière descendante. La fonction supérieure de ce programme s'appelle "search()" et est appelée à partir du modèle "END" après que les données problématiques ont été lues dans les tableaux.
À un niveau élevé, search() commence par les paramètres de ligne et de colonne fournis et recherche le prochain espace vide à vérifier. S'il n'y en a pas, le problème a été résolu et il revient avec la solution. S'il y a un espace vide (représenté par zéro), il teste les nombres disponibles (avec la fonction inuse(), pour les nombres non utilisés dans cette ligne, colonne ou quadrant) en insérant un nombre dans les tableaux à l'aide de mark() et en appelant lui-même récursivement. Si la fonction search() récursive renvoie un zéro, cela signifie qu'elle a échoué, donc la fonction mark() est à nouveau appelée pour décocher le numéro d'essai. Il boucle ensuite jusqu'à ce que les possibilités soient épuisées ou que l'appel search() renvoie un succès.
La beauté de nombreux algorithmes récursifs réside dans l'élégance et la simplicité inhérentes des solutions. Bien qu'ils ne soient parfois pas les algorithmes les plus rapides, ils sont souvent "suffisamment rapides" et plus faciles à concevoir. Ce programme résout la plupart des énigmes en moins de quelques secondes. Une chose que j'ai remarquée en essayant ce programme sur différents puzzles est que si un problème prenait plus de temps à résoudre (en dizaines de secondes), la simple transposition de la matrice donnerait souvent la même solution en une fraction de seconde. Avec les processeurs multicœurs d'aujourd'hui, cela suggère une possibilité pour l'accélérer :écrire un script wrapper qui démarre plusieurs instances du programme avec différentes transpositions de la matrice. Un exemple est montré avec le puzzle précédent montré ci-dessus et la version transposée dans la figure suivante où le problème transposé a été résolu quatre fois plus vite.
------------------------------------------------------------------------------- marion:~/sudoku$ time awk -f solve.awk THE-HARDEST-SO-FAR.dat # Searches=134214 2 8 3 6 7 1 9 4 5 9 7 6 5 4 8 2 3 1 4 1 5 3 9 2 8 7 6 5 6 7 4 1 9 3 8 2 8 3 4 2 6 7 1 5 9 1 9 2 8 3 5 4 6 7 3 2 1 7 8 6 5 9 4 7 5 8 9 2 4 6 1 3 6 4 9 1 5 3 7 2 8 real 0m10.009s user 0m9.889s sys 0m0.024s marion:~/sudoku$ time awk -f solve.awk /tmp/transposed.dat # Searches=32253 8 3 4 7 9 2 6 1 5 2 1 9 6 5 8 7 3 4 7 6 5 4 1 3 8 2 9 3 4 6 5 7 9 2 8 1 5 2 8 3 6 1 9 4 7 1 9 7 8 2 4 3 5 6 9 8 1 2 4 7 5 6 3 4 5 2 9 3 6 1 7 8 6 7 3 1 8 5 4 9 2 real 0m2.487s user 0m2.456s sys 0m0.008s -------------------------------------------------------------------------------
Lorsque quelque chose d'encore plus rapide est requis, cela peut souvent être accompli en traduisant l'algorithme dans un autre langage avec une représentation plus directe des ensembles de données. J'ai fait une fois une traduction de ce programme en C avec une tournure intéressante sur l'indexation des données. Cette version s'exécute probablement quelques ordres de grandeur plus rapidement, principalement en raison de la manière dont les données sont représentées. Nous publierons probablement "Yet Another Sudoku Puzzle Solver Using C" dans un autre article plus tard.
Je crois que awk mérite une place dans la boîte à outils de chacun. Sa simplicité par rapport aux autres langues est peut-être vue comme une faiblesse, mais je la vois comme une de ses forces. La langue peut être apprise en un après-midi et utilisée sans avoir recours à des ouvrages de référence pour résoudre de nombreux problèmes quotidiens. Je l'utilise régulièrement depuis la ligne de commande, jusqu'à l'implémentation d'éléments tels que des compilateurs pour DSL (Domain Specific Languages).
Livres Awk recommandés
- Le langage de programmation AWK par Alfred V. Aho, Brian W. Kernighan et Peter J. Weinberger. Le livre original des auteurs du langage contient d'excellents exemples de programmes modérément complexes et reste mon livre préféré sur awk. Publié par Addison-Wesley, 1988. ISBN 020107981X.
- Plus de perles de programmation :Confessions d'un codeur par Jon Bentley, AT&T Bell Labs, Murray Hill, NJ. Un autre livre sur l'utilisation d'awk comme outil de prototypage d'algorithmes peut être trouvé dans More Pearls. Excellente lecture. Année de publication :1988. ISBN :0201118890