Inledning

Uppgiften består i att skriva ett program med webbgränssnitt som kan lösa "kryptokorsord". Kryptokorsord är ett slags korsord som inte bygger på att man ska hitta ord som är lösningar till gåtor som vanliga korsord. Istället finns det i varje ruta i korsordet ett tal. I varje korsord motsvarar ett tal alltid en bestämd bokstav, och två tal kan aldrig motsvara samma bokstav. Det gäller alltså att lista ut vilken bokstav varje tal motsvarar.

Inlämningsuppgiften skall lösas individuellt! Du får givetvis diskutera uppgiften och olika lösningsmetoder med kurskamrater, men du skall själv ha konstruerat din lösning. Uppgiften skall lämnas in i två etapper, vilka beskrivs närmare nedan.

Denna uppgift kan verka stor, men tänk på att du har till mitten av mars på dig att lösa den. För att göra uppgiften mera hanterlig så kan den delas upp i två delar: En del som handlar om att lösa ett kryptokorsord och en del som handlar om att hantera webbgränssnittet.

Uppgiften skall lämnas in i två etapper. I den första etappen skall du lämna in en beskrivning av de algoritmer och datastrukturer som du tänker använda. I den andra etappen skall du lämna in själva programkoden. Du skall också lämna in dokumentation. Detta beskrivs närmare nedan.

Exempel

Ett kryptokorsord kan se ut så här:

En lösning på korsordet får man om man parar ihop tal och bokstäver på följande sätt: 1-S, 2-T, 3-A, 4-K, 5-E:

Lösning av kryptokorsordet

Lösningar till kryptokorsord kan man hitta med gissningar och god ordkunskap, men det går också att göra genom att med hjälp av en ordlista systematiskt räkna igenom vilka möjligheter som finns.

Först några definitioner för att det ska vara tydligt vad vi pratar om i fortsättningen:

Ett krypto-ord är en sekvens av tal. Om man byter ut varje tal mot rätt bokstav ska detta bilda ett giltigt ord. I korsordet ovan finns kryptoorden 1-2-3-1-1, 3-1-4-5-2, 2-3-1-4-3, 1-4-3-2-2, 3-1-4-5-1 samt 1-3-2-1-3.

En matchning kan sägas vara en dellösning till korsordet -- en gissning. Den består av en hopparning av tal med bokstäver. Inget tal får vara hopparat med mer än en bokstav och ingen bokstav får vara hopparad med mer än ett tal.

Om man har en gissning för alla tal så är matchningen en komplett lösning och gissningen är egentligen ingen gissning.

När man börjar lösa korsordet så har man en matchning som inte innehåller några hopparningar:

(tomt)

Det första vågräta kryptoordet 1-2-3-1-1 skall bilda ett riktigt ord. Med hjälp av en ordlista letar vi efter ett fem bokstäver långt ord där varje bokstav motsvarar precis ett tal i kryptoordet. Vi hittar fem olika sådana ord: SKISS, SLUSS, STASS, STUSS och TRATT. För varje ord parar vi ihop tal med bokstäver och får då fem olika matchningar:

1-S	2-K	3-I
1-S	2-L	3-U
1-S	2-T	3-A
1-S	2-T	3-U
1-T	2-R	3-A

Därefter tittar vi på ett annat kryptoord ur korsordet, t.ex. 1-4-3-2-2 och försöker utvidga var och en av de fem matchningarna ovan. Återigen tar vi hjälp av en ordlista för att hitta ett fem bokstäver långt ord där varje bokstav precis motsvarar ett tal i kryptoordet, men nu räcker inte det - dessutom måste varje bokstav stämma överens med den hopparning som gjorts tidigare. Vi undersöker detta för var och en av de fem matchningarna.

1. Skall vi utvidga första matchningen så måste ordet ha formen S?IKK, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.
2. Skall vi utvidga andra matchningen så måste ordet ha formen S?ULL, där ? är en oanvänd bokstav. Tänkbara ord: SKULL.
3. Skall vi utvidga tredje matchningen så måste ordet ha formen S?ATT, där ? är en oanvänd bokstav. Tänkbara ord: SKATT, SLATT, SMATT, SPATT.
4. Skall vi utvidga fjärde matchningen så måste ordet ha formen S?UTT, där ? är en oanvänd bokstav. Tänkbara ord: SKUTT, SMUTT.
5. Skall vi utvidga femte matchningen så måste ordet ha formen T?ARR, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.

Den andra matchningen kan alltså utvidgas på ett sätt, den tredje på fyra sätt, den fjärde på två sätt och de första och femte inte alls. Gör vi alla utvidningar som är möjliga och stryker de matchningar som inte går att utvidga så får vi sju nya alternativa matchningar:

1-S	2-L	3-U	4-K
1-S	2-T	3-A	4-K
1-S	2-T	3-A	4-L
1-S	2-T	3-A	4-M
1-S	2-T	3-A	4-P
1-S	2-T	3-U	4-K
1-S	2-T	3-U	4-M

Därefter tittar vi på ett annat kryptoord, t.ex. 3-1-4-5-1 och försöker utvidga var och en av de nya sju matchningarna.

1. Skall vi utvidga första matchningen så måste ordet ha formen USK?S, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.
2. Skall vi utvidga andra matchningen så måste ordet ha formen ASK?S där ? är en oanvänd bokstav. Tänkbara ord: ASKES.
3. Skall vi utvidga tredje matchningen så måste ordet ha formen ASL?S, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.
4. Skall vi utvidga fjärde matchningen så måste ordet ha formen ASM?S, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.
5. Skall vi utvidga femte matchningen så måste ordet ha formen ASP?S, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.
6. Skall vi utvidga sjätte matchningen så måste ordet ha formen USK?S, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.
7. Skall vi utvidga sjunde matchningen så måste ordet ha formen USM?S, där ? är en oanvänd bokstav. Inga tänkbara ord i ordlistan.

Denna gång gick bara en matchning att utvidga och det bara på ett sätt. Vi får:

1-S	2-T	3-A	4-K	5-E

Nu har alla tal blivit ihopparade med en bokstav, men korsordet är inte löst för det! Först måste vi kontrollera att alla de återstående tre kryptoorden ger riktiga ord (enligt ordlistan) om man byter ut talen mot bokstäver. I detta exempel blir det SATSA för 1-3-2-1-3, ASKET för 3-1-4-5-2, och TASKA för 2-3-1-4-3. Den sista matchningen är alltså en riktig lösning. ("Taska" är ett äldre ord för "väska". Se SAOB. Tack till Tobias Fendin för upplysningen!)

I just detta fall hittade vi precis en matchning, men det kan också finnas flera olika lösningar vilket ger flera olika matchningar. Alternativt saknas lösningar och då får vi inte kvar några matchningar alls när alla kryptoord är genomgångna.

Ordlistor

Det finns två färdiga ordlistor som ditt program kan använda. De ligger i filerna /it/kurs/pk/public_html/ht09/labs/inlupp/long.txt respektive /it/kurs/pk/public_html/ht09/labs/inlupp/short.txt. Filerna innehåller ett ord per rad. Inga ord är längre än sju tecken. De är konstruerade för att prova denna uppgift och gör inga anspråk på att vara fullständiga! long.txt är en större ordlista med drygt 8000 ord, short.txt är en kortare ordlista med knappt 1600 ord. Den kortare ordlistan innehåller dessutom bara ord med bokstäverna AEIKLPRSTU. Normalt skall du använda den långa ordlistan men t.ex. för testning kan det vara bra att använda den korta ordlistan eller någon helt annan ordlista som du konstruerar själv.

Om du arbetar med uppgiften på institutionens datorer, var snäll och undvik att kopiera ordlistefilerna för att inte slösa med skivminnesutrymme i onödan. (Om du använder egen dator så måste du naturligtvis ladda hem en kopia av filen.)

Webbgränssnittet

Man skall kunna skriva in ett kryptokortsord på en webbsida och få det löst. Du skall alltså dels konstruera en webbsida där man kan fylla i ett kryptokorsord och dels ett ML-program som gör själva lösningen.

Webbsidan skall visa ett rutnät där man kan skriva in tal i varje ruta, precis som i exemplen på kryptokorsord ovan. Rutor som lämnas blanka skall inte ingå i några ord -- dvs de motsvarar de överkryssade rutorna i exemplen. Rutnätet skall vara åtminstonde så stort att alla exempel ryms -- dvs minst 5 rader och 7 kolumner.

Ett enkelt sätt att skapa ett sådant rutnät är med en HTML-tabell där varje cell innehåller ett kort INPUT-fält.

ML-programmet skall läggas upp som ett cgi-program och genom att klicka på en "lösningsknapp" skall webbsidan anropa det. Programmet skall då lösa korsordet och skapa en nya webbsida med lösningen (eller lösningarna). Det är också bra om webbsidan har en knapp som kan rensa korsordet.

Lösningswebbsidan skall visa de matchningar som korsordslösningaren hittar. Om programmet inte kunde lösa korsordet skall webbsidan tala om det. Eftersom det kan finnas väldigt många olika lösningar på enkla korsord så skall du sätta en gräns för hur många olika matchningar som visas -- t.ex. maximalt 10 stycken.

Ett enkelt sätt att visa en lösning är med en HTML-tabell där varje ruta innehåller den bokstav som motsvarar siffran i korsordet (eller blankt om motsvarande korsordsruta inte innehåller några siffror).

Utförande av korsordslösaren

Både för att det skall vara lättare för dig att lösa uppgiften och att rätta den så måste det finnas en tydlig gräns mellan de delar av programmet som löser korsordet och de delar som sköter webbgränssnittet.
För själva lösningen skall du skriva en funktion solve. solve skall ha följande funktionsspecifikation:

solve(crypto,words)
TYPE: int list list * string list list -> match list
PRE: words uppfyller kraven på en ordlista
POST: En lista med alla lösningar till kryptokorsordet crypto med ord tagna från ordlistan words
EXAMPLE: solve([[1,2],[2,1,3]],[["I"],["IS","NI"],["NIX","SIL","SAV"],["TOMT"]]) = [matchningen 1-I 2-S 3-L]

Första argumentet till solve är alltså en representation av kryptokorsordet. Varje kryptoord i korsordet representeras som en lista av heltal. Hela kryptokorsordet representeras som en lista av kryptoord. Korsordet i exemplet ovan kan alltså representeras som

[[1,2,3,1,1],[3,1,4,5,2],[2,3,1,4,3],[1,4,3,2,2],[3,1,4,5,1],[1,3,2,1,3]]

Andra representationer är också tänkbara eftersom kryptoordens inbördes ordning inte spelar någon roll. Det finns några exempelkorsord som du kan prova med.

Andra argumentet till solve är en ordlista. Ordlistan representeras som en lista av delordlistor för olika ordlängder. Första elementet skall vara en lista av ord (strängar) med längden 1, andra elementet skall vara en lista av ord (strängar) med längden 2 etc.

Resultatet från solve skall vara en lista med alla möjliga matchningar som löser korsordet. Om korsordet inte gick att lösa skall listan vara tom. Du skall representera matchningar som en abstrakt datatyp match. Bestäm själv hur gränsytan till match skall se ut, men tänk på att enbart funktioner som behövs för att hantera själva matchningarna skall finnas mellan with och end. Funktioner som har att göra med lösningen av kryptokorsordet i övrigt får inte finnas inne i deklarationen av den abstrakta datatypen. (Not: Match är ett möjligt men olämpligt namn på konstruktorn för datatypen eftersom ML har en inbyggd felkod (exception) som heter Match.

Den abstrakta datatypen skall innehålla en funktion fromMatch: match -> (int*char) list som tar en matchning och beräknar en lista av heltal-teckenpar som beskriver matchningen. Syftet är att få matchningen i en form som kan användas t.ex. för utskrift. När vi rättar uppgifter skall vi kunna anropa fromMatch på de matchningar som solve producerar för att lätt kunna se vilken lösning som ditt program gjort.

Jag rekommenderar starkt att du testar ut solve interaktivt i ML-systemet så att du säkert vet att den fungerar innan du börjar arbeta med "webbdelen" av programmet. Börja med att prova små kryptokorsord och ordlistor ungefär som i exemplet i funktionsspecifikationen och fortsätt sedan med de riktiga exemplen och ordlistorna.

Inläsning av data

Kryptokorsordet och ordlistan är inte tillgängliga för ditt program i en form som direkt går att skicka till funktionen solve. Detta är en mycket vanlig situation i databehandling. Ditt program måste alltså hämta information dels från webbsidan och dels från ordlistefilen och göra om den till den form som argumenten till funktionen solve har.

För korsordet så innebär det att du måste läsa in alla korsordsrutorna -- t.ex. som en lista av korsordsrader där varje rad i sin tur är en lista av innehållet i rutorna i just den raden -- och sedan plocka ut själva kryptoorden ur korsordet eftersom solve vill ha en lista av kryptoord. Du måste också göra felkontroll på indata. Har t.ex. användaren stoppat in något annat än ett tal i en korsordsruta så skall ditt program svara med en webbsida med felmeddelande.

För att kunna skicka ordlistan till solve så måste du läsa in dem från filen och sortera upp dem efter storlek eftersom solve vill ha en ordlista där ord av olika längd ligger i separata listor. Skriv funktionen som läser in ordlistor först eftersom du kommer att behöva dem när du testar solve!

Dokumentation

Du skall skriva dokumentation till ditt program. Förutom de vanliga specifikationerna till varje funktion som skall finnas i programkoden, så innebär det att du skall skriva ett separat dokument som beskriver hur ditt program fungerar och hur man skall använda det. Dokumentet skall lämnas in som en pdf-fil (helst) eller en textfil. Inte som en Microsoft Word .doc-fil, TeX-källkod eller liknande.

Dokumentationen skall innehålla:

1. Titel, författarnamn, uppgift om att detta är inlämningsuppgiften på denna kurs detta år, innehållsförteckning, inledning med sammanfattning av vad programmet gör.
2. En "användarbeskrivning": en anvisning för hur man praktiskt använder ditt program för att lösa kryptokorsord, inklusive körexempel.
3. En "programdokumentation": en beskrivning av hur ditt program egentligen fungerar:
   • Beskrivning av din abstrakta datatyp för matchningar -- hur gränssnittet till den abstrakta datatypen ser ut och hur du har representerat matchningarna.
   • Beskrivning av algoritmerna som du använder.
   • Beskrivning av hur de olika delfunktionerna hos programmet: inläsning av korsordet, inläsning av ordlista, lösning av kryptokorsord och presentation av lösningarna. Beskriv algoritmerna och ge funktionsspecifikationer för de viktigaste delfunktionerna. Tala om hur programflödet ser ut (alltså hur funktionerna anropar varandra).
4. Beskrivning av kända brister hos programmet. Det kan vara sådant som du själv tycker är mindre lyckat gjort, funktioner enligt uppgiften som du trots tappra försök inte lyckats få till ordentligt eller saker som du tycker programmet borde göra fastän det inte krävs i uppgiften.

Det skall räcka att läsa dokumentationen för att förstå ditt program. Du kan inte utgå ifrån att läsaren också läst denna uppgiftsbeskrivning. Du kan alltså inte utlämna information från dokumentationen bara för att den finns i uppgiftsbeskrivningen. Å andra sidan behöver du inte ta med allt som finns i uppgiftsbeskrivningen. Instruktionerna för hur uppgiften skall genomföras behöver förstås inte finnas i programdokumentationen.

Observera att praktiskt taget hela dokumentationen kan skrivas innan du börjar koda!!

Dokumentationen är lika viktig som själva programmet. Är dokumentationen dålig så kommer du att få komplettering på uppgiften även om ditt program fungerar. Det är svårt att skriva en godkänd dokumentation som är kortare än fyra sidor.

Det finns ett exempel på hur dokumentationen kan se ut. I exemplet så beskriver användardokumentationen hur man skall använda programmet från ML-tolken. Eftersom den uppgift du skall göra har ett webbgränssnitt så skall din användardokumentation beskriva hur man använder ditt program i en webbläsare.

Inlämning

Lösningen skall lämnas in i två etapper. I den första etappen skall du bestämma hur det skall gå till att använda ditt program, konstruera den abstrakta datatypen match samt de algoritmer som programmet skall använda. Du skall också konstruera webbsidan där man fyller i kryptokorsordet. Inlämningen skall bestå dels av dokumentation av de saker om du har gjort (utformat enligt mallen ovan i tillämpliga delar) dels av HTML-koden för webbsidan. Det är inte meningen att du skall skriva någon programkod ännu. Tvärtom kan det vara olämpligt eftersom du kan få kommentarer till din inlämning som är bra att ha när du kodar.

Den första etappen skall vara inlämnad enligt anvisningarna senast den 15/2 klockan 08:00!

I den andra etappen skall du lämna in en ML-fil med ditt program. Överst i ML-filen skall du lägga en kommentar med kursens namn, texten "Inlämningsuppgift", datum och ditt namn. Eftersom du kan ha gjort ändringar och tillägg till programdokumentation och HTML-kod så skall du lämna in dessa igen. Du skall installera webbsidan och kompilerat program i din egen webkatalog på institutionens datorsystem så att man direkt kan provköra den. Hur detta går till skall framgå av dokumentationen!

Den andra etappen skall vara inlämnad enligt anvisningarna senast den 19/3 klockan 08:00!

Som vanligt skall du följa kodstandarden, bl.a. skall du skriva funktionsdeklarationer för alla funktioner du definierar och varianter för alla rekursiva funktioner. Detta är ännu viktigare än för labbarna! Eftersom du har nästan full frihet att utforma din lösning som du vill -- t.ex. beträffande vilka hjälpfunktioner du inför -- så är det mycket viktigt att assistenterna snabbt kan sätta sig in i vad din kod gör. Där spelar bra funktionsspecifikationer en viktig roll.

Några tips:

Några praktiska tips som kommer att underlätta utförandet av uppgiften.

• Själva korsordslösaren (solve med hjälpfunktioner) behöver inte bli jättestor. Jag har själv skrivit en sådan med 47 rader ren kod (alltså exklusive tomrader och kommentarer men i övrigt utformad efter kodningsstandarden) och det utan att använda några speciella trick eller ens högre ordningens funktioner.
• Tänk på att en matchning har många likheter med en tabell och sådana har vi ju talat en hel del om på kursen. Återanvänd gärna idéer och kod från föreläsningarna.
• Skriv dokumentationen -- både funktionsspecifikationerna och den externa dokumentationen -- innan du börjar skriva programmet. Det vill säga: Tänk igenom hur du skall lösa uppgiften, skriv sedan dokumentationen och sist programmet.
• Använd datatype för matchningar vid felsökning. Det underlättar eftersom du får datastrukturerna utskrivna av ML. Göm bara inte att ändra tillbaka till abstype! Se till att ingenting som är beroende av datatypens utseende -- konstruktorer ("taggar") till exempel -- finns i de funktioner som ligger utanför den abstrakta datatypen. Hela den egentliga lösningen av kryptokorsordet ska ligga utanför datatypsdefinitionen -- denna ska enbart hantera matchningar.
• Starta om ML då och då så att du är säker på att du inte av misstag använder gamla definitioner. Antag att du i funktionen foo anropar funktionen bar. Sedan bestämmer du dig för att ta bort bar och ändrar på alla ställen där bar används, utom just i foo som du glömmer att ändra. Så länge du inte startar om ML kommer bar att finnas kvar och foo fungerar fortfarande. När du startar om ML så försvinner definitionen av bar och foo slutar att fungera. Ju förr du upptäcker det, dess bättre.
• Be om hjälp när du kör fast. Antingen via mail eller genom att söka upp din assistent eller föreläsare. Det är inte meningen att ni ska sitta i timtal och jaga en och samma bugg. Om du å andra sidan inte skrivit ner hur du tänkt göra, typ, etc, så är det det första du kommer att bli ombedd att göra, så det är ingen mening att fråga om kodhjälp om du inte gjort det (annat än väldigt specifika frågor förstås).