Nous avons discuté des solutions aux problèmes sur les chaînes de caractères, puis une nouvelle série de problèmes sur les graphes a été annoncée.
Au cours des deux dernières semaines, nous nous sommes consacrés à des problèmes sur les chaînes de caractères. Nous avons consacré cette rencontre à une discussion sur les solutions à ces problèmes.
Pour résoudre le problème “Avion”, il suffisait d’analyser chaque ligne de l’entrée à la recherche d’un motif fixé, et de noter les lignes contenant une occurrence. Certains se sont essayés au code golfing sur ce problème: pour le moment, la plus courte solution trouvée est longue de 62 octets et programmée en Python 3.
Le problème “Pebble Solitaire” peut être résolu par une recherche exhaustive (backtracking) qui essaie tous les coups possibles et retient le minimum de pions qu’on peut ainsi atteindre. La plus courte solution trouvée pour ce problème est longue de 155 octets et programmée en Python 3. Certains ont proposé des solutions en Prolog, en tirant parti du backtracking intégré au langage.
La variante “Pebble Solitaire 2” complique le problème en faisant passer la taille des configurations de 12 positions à 23 positions. Ici encore, une recherche exhaustive est suffisante, quoiqu’il soit en plus nécessaire de retenir les configurations déjà rencontrées pour sauver du temps de calcul. Le passage à la deuxième dimension avec “Peg Solitaire” se traite également par recherche exhaustive, la difficulté ici étant dans la représentation et la manipulation des configurations.
Certains se sont interrogés sur la possibilité de résoudre ces problèmes sans avoir recours à la recherche exhaustive. Il s’est avéré que d’autres se sont posés la question avant nous. En deux dimensions, le problème a été montré NP-complet par Ryuhei Uehara et Shigeki Iwata en 1990 dans “Generalized Hi-Q is NP-Complete”. En une dimension, l’article “One-Dimensional Peg Solitaire, and Duotaire” par Cristopher Moore et David Eppstein (2002) détaille une solution en temps linéaire!
Malheureusement, une tentative d’implémentation de ce dernier algorithme s’est soldée par un échec. Nous avons émis des doutes sur la validité d’une des affirmations de l’article, selon laquelle toute configuration réductible à
Une approche naïve pour résoudre “Bing It On” consiste à conserver la liste des mots vus précédemment, et à parcourir cette liste à chaque nouveau mot
Une façon d’en améliorer l’efficacité consiste à construire une table de hachage dans laquelle on sauve le nombre de fois que chaque préfixe de chaque mot précédent a été vu. Cette construction se fait en
Une autre approche consiste à construire un trie contenant tous les mots rencontrés au fur et à mesure. Chaque nœud du trie est annoté avec le nombre de mots qui commencent avec le préfixe correspondant. À l’aide de cette structure, on peut répondre en temps constant à la question du nombre de mots précédents dont le mot actuel est un préfixe.
Dans le problème “String Factoring”, l’objectif est de trouver la factorisation la plus courte d’une chaîne de caractères. Les opérations autorisées sont la concaténation de deux factorisations et la répétition d’un sous-mot un nombre arbitraire de fois. Par exemple,
Une approche vorace, qui consisterait à factoriser itérativement la plus courte sous-période du mot, n’est pas optimale. Cela conduirait par exemple à factoriser d’abord
Cette remarque nous conduit à considérer une approche en programmation dynamique. Supposons qu’on veuille factoriser un mot
Le premier cas de cette équation correspond à la concaténation de deux factorisations, tandis que le second cas correspond à la factorisation d’une période. Cette approche donne un algorithme en
Dans “Automatic Trading”, l’objectif est de calculer le plus long préfixe commun à 100 000 paires de suffixes piochées dans un même mot de 100 000 caractères. Le fait que les suffixes soient tous choisis dans le même mot pourrait nous orienter vers une solution à base de table des suffixes. Une approche naïve suffit cependant, en particulier parce que le nombre de paires données en entrée est largement inférieur au nombre total de paires possibles. Il faut toutefois prendre garde à la lecture de l’entrée qui est de grande taille: utilisez C ou C++ avec des fonctions efficaces de lecture de l’entrée.
Nous nous intéressons désormais à une série de problèmes portant sur des graphes, ou pouvant être modélisés avec des graphes. Les problèmes ci-dessous sont en ordre croissant de difficulté.