Programmation Avancée
Devoir Maison: Boggle
Le devoir est à rendre strictement avant le mardi 2 avril,
par mail à baelde@lsv.ens-cachan.fr sous la forme d'une
archive se décompressant en un répertoire au nom de l'élève.
L'archive devra contenir uniquement votre code source commenté, accompagné
éventuellement d'un petit rapport, et les fichiers nécessaires à la
compilation, Makefile ou autre.
Le code devra compiler avec OCaml 3.12 sous un environnement linux standard.
Pour chacun des trois problèmes à traiter, vous devrez produire un exécutable
dont le nom est indiqué dans le problème. Ces exécutables implémenteront
différents algorithmes mais partageront certainement du code.
Vous serez notés sur l'organisation de votre code. Factorisez ce qui est factorisable, utilisez des interfaces pour clarifier le rôle des différents modules et garantir leur bonne utilisation, et commentez pour rendre le tout lisible. Les algorithmes complexes devront être expliqués et justifiés; réfléchissez aux différents styles de programmation, aux compromis entre efficacité et clarté du code. Enfin, vous serez aussi bien sûr jugés sur le choix de structures de données adéquates, et la conception d'algorithmes raisonnablement efficaces.
A titre indicatif, le devoir peut se résoudre avec quelques modules utilitaires de moins de cent lignes chacuns, plus un fichier de moins de cent lignes par problème; les fichiers mentionnés ne sont par contre pas beaucoup commentés.
Règle du jeu
Le Boggle se joue sur une grille carrée de caractères alphabétiques. On peut se déplacer verticalement, horizontalement ou en diagonale sur cette grille, formant ainsi des chemins et des mots. Le but du jeu est de trouver un maximum de mots distincts écrits sur des chemins ne visitant jamais deux fois la même case.
Par exemple, on trouve le mot exemple sur exactement deux chemins
de la grille suivante:
xexe xmxx pxxx lexx
Chaque mot rapporte un certain nombre de points en fonction de sa longueur, 0 pour un mot de deux lettres ou moins, 1 pour un mot de 3 ou 4 lettres, 2 pour 5 lettres, 3 pour 6 lettres, 5 pour 7 et 11 pour 8 lettres ou plus.
Pour générer des grilles de test nous ne simulerons pas les dés du jeu
original mais utiliserons un tirage aléatoire plus simple basé sur les
fréquences des lettres au Scrabble. Pour cela, récupérez les modules
Scrabble et Generator.
Le générateur prend plusieurs arguments qui seront détaillés ci-dessous.
Il permet aussi de fixer la graine du générateur aléatoire via la
variable d'environnement SEED: à moins que vous ayez une version de
OCaml très différente de la mienne, cela devrait vous permettre de
reproduire à l'identique les tests ci-dessous.
Vos algorithmes devront être indépendant du dictionnaire choisi,
mais nous n'utiliserons que sur cette liste de mots français.
La liste ne contient que des mots d'au moins deux lettres sur l'alphabet
[a-z] et ne contient aucun doublon.
(Crédits: notre dictionnaire a été composé de façon ad-hoc à partir du
morphalou et du
dictionnaire
Gutenberg.)
Problème 1: Trouver tous les mots
Etant donnée une grille, le but est de calculer tous les mots possibles
sur la grille. Plus précisemment, programmez une application solutions
qui lit une grille sur son entrée standard et affiche:
- le nombre total de mots du dictionnaire trouvés, en comptant autant de fois un mot qu'il y a de chemins Hamiltoniens qui donnent ce mot;
- le nombre de mots uniques trouvés, sans compter les différents chemins donnant un même mot;
- le score, c'est à dire la somme des scores des mots uniques;
- les dix mots (au plus) donnant les scores les plus élevés, avec leurs scores.
Exemple
Le générateur prend en premier argument (optionnel) la taille de la grille:
$ SEED=6 ./generator 4 | ./solutions Board: mqrt ldre eeat luer Searching... Found 252 words, 110 unique words. Score: 193 Best words: 11 points: retardee 5 points: derater 5 points: arretee 5 points: arreter 5 points: treteau 5 points: terreau 5 points: tetrade 5 points: retarde 3 points: dartre 3 points: derate
Un bon code devra être instantané en taille 4 (~1s) et monter sans
trop de problèmes jusqu'à la taille 40 (~10s). Aucune optimisation de bas
niveau n'est nécessaire pour atteindre ces temps, mais il peut être utile
(et agréable) d'économiser de potentiels coûts d'initialisation: on pourra
notamment pré-compiler le dictionnaire en une structure de données adaptée,
sauvée dans un fichier et chargée grâce au module Marshal.
Problème 2: Trouver un mot, avec des variables
On considère maintenant des grilles de Boggle avec inconnues. Les lettres en minuscules ont le même sens qu'auparavant, mais les majuscules correspondent à des variables qu'on peut instantier. Un variable peut apparaître à plusieurs positions sur une grille, et son instantiation modifiera toutes ces positions.
Ecrire un programme xfind qui prend une grille avec inconnues sur son entrée
standard, une liste de mots sur la ligne de commande, et cherche une
instantiation des variables qui permette de trouver tous les mots de la liste
dans la grille.
On pourra commencer par écrire l'algorithme de recherche d'un mot dans une grille, avant de l'adapter pour gérer les variables, et enfin itérer cet algorithme de façon adéquate pour traiter une liste de mots.
Exemple
On utilise les deux arguments supplémentaires du générateur, pour indiquer
respectivement le nombre maximal de variables (éviter d'en mettre plus que
26...) et la densité des variables dans la grille.
On note que la variable B apparaît deux fois sur la première ligne,
et que la variable F n'a pas eu besoin d'être instantiée pour avoir
une solution:
$ SEED=2013 ./generator 6 15 0.8 | ./xfind programmation continuation Board: FBGKMB jHIBrO LrCuBN kHCLDA NJhCae isIrrK [...] Assignment: C=n,B=a,A=t,O=m,N=i,M=m,L=p,K=g,J=i,I=o,H=t,G=c,D=o Board: Facgma jtoarm prnuai ktnpot iihnae isorrg
Ici, l'algorithme a trouvé cette première solution en quelques secondes. Cependant, le temps de calcul peut être nettement plus long, notamment quand il n'y a pas de solution.
Problème 3: Vérifier la Boggle-équivalence
Pour un dictionnaire fixé, le langage d'une grille de Boggle est l'ensemble des mots du dictionnaire contenus dans cette grille, et deux grilles sont dites Boggle-équivalentes si elles ont le même langage.
Ecrire un programme equivalence qui prend deux grilles de Boggle sur son
entrée standard, et indique en sortie si elles sont équivalentes, ou bien
donne un mot qui est dans l'une et pas dans l'autre. (Dans cette partie, on
ne considère plus de variables.)
Exemple
L'objectif est de faire mieux que de calculer les deux langages avant de les
comparer. Ainsi, on devrait en général distinguer instantanément deux grilles
aléatoires de taille 40:
$ (SEED=1234 ./generator 40 ; SEED=4321 ./generator 40) | ./equivalence Board A: eidqhpeflsirethaolwnrnstonbqzkpoxjuobten etieagasntinetfedettuiiacrtsictroaaokoeo dieuunezaerneeolzhenteuaoiarynuoaueefeul noerseerbeuvltahdqtlncamraietutsqeeezzbe snngntaweiwiressltpnzlrfraeteixmgeteabge yacdreneieutaeeneeeapgopnvrtaamaemobpalu zwntstthevinrqsevaioedroeiqiesaddraeaelr ytehtutehnizgqrilfasoeyeaelsmlahiunuheit vteiraonlokdapwreoibaaiedmenulonideeatnf tnihryweuehdbmeneiaoohnrednlltufibpnizee slmiqdseeakmineuraoqnhoneeacnndsuakesswo asrasetomnuoitcysurioaawraecrsoelaimsuib froszioesnitnfafnurreuoeauenaaiaeesilveh eiengagnsatitnagxftfpkkolliintcrvrejjiiu rldeisarbugntsjtiarrngfaeoremlewpuubroeo anryefateeteeqpuirddkuulthyualerhgdnehpe uxrgetenltapeuhriduysrsancoevrprsrisgmfb nennewsrbssrneaieuelgareiednaiexnioltrhs eexuliipisrzofieueeeepismeiomopxifuruoel rraotipeadrrtgksisuudekfoatemeitaeanaueu rmtitzlezleizitrizueygwirsaeeaivfeofelvt oeutfavyogugedeegizyhuogletmywoyloiaujoz ahsleokrieauriofrreayesoapevtshlslnteian necarsrnlnfniasrsbmetsmarasruioetntnyutp aurinziofoezinlriqbieeahrzrnuqiarihxsilr tyspduieudeeymjzereectyesaepktosefsteeex unircueeejlnjrnptylsaenuiangonetiveeoloi vkvekheneusxtldlhinpcbgwmzdemepaucamlula seateaeemenpocilnpazesspbzcaiselmtaddcog behieboemtoeeiaatdrioasralhaeaoryfeodsua pelngfalpolernuueetgkntftruurnerauutlama iereguriritmsawnooittisueovogkuoerrtersu auartknuittonrlauieuuaebauaaaeecruaeuiuo ugabtieaerngalimmproeeeqccdtcnrghanjloie aeeaciiipneattaelaozaattuousjemreneaedkp pvlnodsreeeatxllehoazkoilaetgfmajcwelete oisgeesinsplesdefieuvnseeamaerlrpensinst xegwnarklisnoaxauwteienseefoiteroaaeuueg prlxarioumirelubtlntetyevmuhfmgatsttaepr ejarofelnseuneaeujdstsdrteatdlxgieoesnoe Board B: rzhlfiljenatefeitrdekrinnirfiarevsnmeieu nrixelhejhfvtieindlzfaqeinegquamtirotrer dujvuwdeueaiodalmrznlficlwmlueoonenahhie nzysiuivsrmsfmmuufrvnnsdbaaouoryoneinnos eanaalimevrfcixnctniltosippuuflalingassb oemutequeeamseeiancndbphictntxrntihhsogv tuegoietnfiafwzgevoaezvtdutormntodesbeae isaalgdafqeuiolareesdaskaikabaeciwehnnon nexeeuviooptdieifafsxourelwtteuerstobtfz bubpwrnaaamxjggseieryibehtiaobtuinrccznh tkebefxasesnaaneojacseizoaevnwploihfkias hetteeneeeatllpsiaievloseefssoaieutadasn enrtlrjteeuveabensqrmaeaemmxsiuangtlntru atsbzxttnazujnosjoraqkretsetdeaemaxoaiae uoiubnuoaoseitcnrtklngnosjehnsesteaieoiu uehuethevhnknduysanoodloemeoaunaepiiiipg eaurefjromiivqerfnlnjbinudeleoepcfsnsemt deiwelpllepjdgbaheerresiedrkozsjenmepuea gontcetamssletdnitrlseunnisnneigensrunxb wvanllinuenclgvoeletdlpofpisgatikmslimwe ntirsuetflznsrbugiurugmvnbeeesiioauopcda uqiotlsieunefowtaauouavttnharrorupleiaaa ncuspovtuelegohtjeaitvbaonetedwonieeohre utlpsaengocirmzzlrorcnrgaoeneletdaueeeea aslblacitnouytbmotneoeeovertsoasneomifkn winegjcleuvndeaaeariuvottiogesesubreglgt uasummhuiagxvenifrgnupgataeeefetaesalrab nleidsjeagooiwinemweseezbzolyprzeauiuuei bseuuaiewuadcilzbqniekiaumuccafdsrneaera uaeemaorsirlietieiosierakdenvpiaraijvsda eddnrtcahfoaaaoubueagefeoryeeawmjaeewqsl tnmeoiprwrreeixveooneuruptemdrlsaxemieio ofedoieoalermzauvczaitquenesolvaiscunais dhgrniteseeilxrufulldentiansipuennmtsefi aaileuluuilsonglsnrgeizyeexmngareumytwbi gdehmndbwxbneofarneqxuelzxuaodeaincutarv eeeealotehbognurrbdsroukimfovalueosdeira uuuifryzuatoewaedesqtnoxratmscauittjdswt ieezeeosetogasrdreceaereacuarpoesusthseh iuekpykelanleceevriionehlnesooorvbotzpvt Word "zouave" found only in A.