Labb 2: Ordkedjor

Om du redovisar labben senast den 30 september får du en bonuspoäng på tentan. På övningen den 22 september har du dessutom möjlighet att redogöra för lösningen på teoriuppgifterna nedan. Korrekt lösning av dessa ger en bonuspoäng på tentan. Sen redovisning ger ingen bonus för labb eller teoriuppgifter.
Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

I katalogen /info/adk11/labb2 finns ett Javaprogram som löser nedanstående problem. Din uppgift är att snabba upp programmet så att det går ungefär 10000 gånger snabbare. Korrekthet och effektivitet testas genom att din lösning skickas till Kattis, se separata instruktioner. För att klara labben ska du bli godkänd av Kattis samt redovisa labben för en handledare.

Problem

Det ligger nära till hands att fråga sig hur man finner kortaste vägen från aula till labb genom att byta ut en bokstav i taget, till exempel så här:

aula -> gula -> gala -> gama -> jama -> jamb -> jabb -> labb

där alla mellanliggande ord måste finnas i ordlistan (se nedan).

För många ord i ordlistan existerar det en (kortaste) ordkedja från ordet själv till labb. Nu kan man fråga sig: vilket ord är det som har längst kortast ordkedja till labb och hur ser den kedjan ut? Det räcker att hitta och skriva ut en enda ordkedja av den maximala längden.

Specifikation

Indata består av två delar. Den första delen är ordlistan, som består av ett antal fyrbokstavsord, ett per rad. Denna del avslutas av en rad som bara innehåller ett '#'-tecken. Den andra delen är ett antal frågor, en per rad. En fråga är antingen på formen 'slutord' eller på formen 'startord slutord', där bägge orden förekommer i ordlistan.

Programmet ska, för varje fråga på formen 'slutord', räkna ut hur lång den längsta kortaste kedjan är från något ord i ordlistan till slutordet och även skriva ut en sådan kedja. För frågor på formen 'startord slutord' ska programmet räkna ut hur lång den kortaste kedjan är från startordet till slutordet, och även skriva ut en sådan kedja. Om det inte finns någon kedja från start- till slutord ska detta anges.

Exempel på körning

En ordlistefil finns i /info/adk11/labb2/word4. Du kan provköra ditt program genom att skriva in några testfrågor (t.ex. frågorna 'aula labb', 'sylt gelé', och 'idén') på varsin rad i en fil (t.ex. testord.txt) och sedan köra

spel01$ cat /info/adk11/labb2/word4 testord.txt | java Main
aula labb: 8 ord
aula -> gula -> gala -> gama -> jama -> jamb -> jabb -> labb
sylt gelé: ingen lösning
idén: 15 ord
romb -> bomb -> bobb -> jobb -> jabb -> jamb -> jams -> kams -> kaos -> klos -> klon -> klen -> ilen -> iden -> idén

Uppgift

Det givna Javaprogrammet löser visserligen ovanstående problem, men det tar timmar att få fram svaret. Du ska effektivisera programmet så att det hittar svaret inom den tidsgräns som Kattis ger.

Bra testfall att testa ditt program med finns på /info/adk11/labb2/testfall/

Teoriuppgifterna ger uppslag om olika sätt att effektivisera programmet. Ditt optimerade program ska ha samma in- och utmatning som det givna programmet (vilken av alla lika långa lösningar det skriver ut gör dock detsamma) och det måste fortfarande vara Java.

Kattis känner till problemet som oldkattis:adkwordchain

Teoriuppgifter

1. Sätt dig in i hur det givna programmet fungerar. Svara speciellt på följande frågor: Vad används datastrukturen used till i programmet? Varför används just breddenförstsökning och inte till exempel djupetförstsökning? När lösningen hittats, hur håller programmet reda på vilka ord som ingår i ordkedjan i lösningen?
2. Både ordlistan och datastrukturen used representeras med klassen Vector i Java och sökning görs med metoden contains. Hur fungerar contains? Vad är tidskomplexiteten? I vilka lägen används datastrukturerna i programmet? Hur borde dessa två datastrukturer representeras så att sökningen går så snabbt som möjligt?
3. I programmet lagras varje ord som en String. Hur många Stringobjekt skapas i ett anrop av MakeSons? Att det är så många beror på att Stringobjekt inte kan modifieras. Hur borde ord representeras i programmet för att inga nya ordobjekt ska behöva skapas under breddenförstsökningen?
4. Det givna programmet gör en breddenförstsökning från varje ord i ordlistan och letar efter den längsta kedjan. Visa att det räcker med en enda breddenförstsökning för att lösa problemet.