CP2012 – Dogson Game

by Mithrandir

A doua problemă din cadrul concursului de programare, ediția 2012, trackul normal este inspirată dintr-un joc propus de Caroll Lewis.

Ideea e simplă: pornind de la un singur cuvânt, schimbând o singură literă pentru a ajunge la alt cuvânt real și repetând procedeul de câteva ori se ajunge la alt cuvânt, de cele mai multe ori în așa fel încât să poți construi o propoziție interesantă.

De exemplu «The CAT was afraid of the DOG» se bazează pe existența unei transformări CAT – COT – DOT – DOG. Alte exemple ar fi «APE evolved into MAN» sau «It was COLD but now it’s WARM».

Cerința e simplă: pornind de la o listă de propoziții cu 2 cuvinte CAPS-LOCK să se găsească cea mai scurtă secvență de transformare de la un cuvânt la următorul.

Ca input veți avea o listă de propoziții, fiecare pe câte un rând. Cele 2 cuvinte vor fi cu litere mari. Propozițiile se termină cu . și linie nouă.

Outputul trebuie sa contina fiecare lant pe o linie, cuvintele separate prin spatiu. De exemplu, pentru inputul

The CAT was afraid of the DOG

outputul corespunzator trebuie sa fie

CAT COT DOT DOG

(nu conteaza case-ul, puteti scrie si mixt in output)

Ca dicționar se va folosi acest fișier care va mai apărea la câteva probleme viitoare. Puteți să-l prelucrați înainte dacă vreți, nu-l includeti în soluție. Se va afla în același director cu executabilul în momentul testării.

Timpul de rulare nu contează, cât timp este sub 30 minute. Contează doar lungimea cumulată a tuturor lanțurilor găsite.

Scoringul este astfel: sunt 100 de fraze. Notând cu \eta proporția de propoziții pentru care se găsește un lanț valid de transformări pentru cele 2 cuvinte în intervalul de timp precizat (30 de minute pentru toate cele 100 de propoziții în total) și cu \lambda suma cumulată a lanțurilor obținute de program și presupunând \lambda^* lungimea cumulată cea mai mică, scorul este dat de \eta * \frac{\lambda^*}{\lambda}. Scorul poate deci varia între 0 și 100. În plus, pentru a evita corner-case, un test eșuat se consideră că a produs un lanț de lungime 10

Ponderea acestei probe este 1.1, cu 10% mai mare față de problema anterioară.

Spor.

PS: ca istorie, problema m-a pasionat puțin prin anul 1. Lista de cuvinte este luată din alt challenge, acum încerc să scriu o soluție în Haskell care să meargă cât mai rapid posibil — încă n-am început să lucrez la ea.