Laboration 4 - Från fan till gud

Det gäller att finna kortaste vägen från fan till gud genom att byta ut en bokstav i taget, till exempel så här:
fan -> man -> mun -> tun -> tur -> hur -> hud -> gud
Alla mellanliggande ord måste finnas i ordlistan word3.txt från förra laborationen.

Ditt program ska finna en kortare väg till gud än den här föreslagna. Lösningsprincipen gås igenom nedan och den beskrivs ofta i läroböcker för det analoga problemet att finna kortaste väg i en graf.

Breddenförstsökning

Problemträdets urmoder/stamfar fan har barnen fin, man, far med flera, barnbarnen hin, mun, får osv. Enligt kedjan ovan är gud barnbarnbarnbarnbarnbarnbarn till fan, men gud finns säkert redan tidigare i problemträdet. För att finna den första förekomsten gör man en breddenförstsökning enligt följande.

Lägg urmodern/stamfadern som första och enda post i en kö. Gör sedan följande om och om igen: Plocka ut den första ur kön, skapa alla barn till den och lägg in dom sist i kön. Första förekomsten av det sökta ordet ger kortaste lösningen.

Man kan spara in både tid och utrymme om man undviker att skapa barn som är kopior av tidigare släktingar (t ex mans barn fan), så kallade dumbarn.

Första versionen

Uppgiften är så komplicerad att det är lämpligt att lösa den stegvis. Låt filen fan.py utgå från förra labben, som ju har två binärträd. Nu kallar vi dom svenska och gamla. Huvudprogrammet ska läsa in ordlistan, fråga efter startord och slutord, och göra anropet makechildren(startord). Denna funktion går systematiskt igenom alla sätt att byta ut en bokstav i startordet, kollar att det nya ordet finns i ordlistan men inte finns i gamla och skriver i så fall ut det nya ordet på skärmen.

Om du gjort rätt ska fan få sjutton barn.

Andra versionen

För fortsatt genomgång av fans barnbarn osv behövs den köklass som du använde i kortkonstlabben. Importera den och skapa kön q. I stället för att skriva ut barnen på skärmen lägger makechildren in dom i kön. Huvudprogrammet lägger in startordet i kön och går sedan i en slinga

    while not q.isempty(): 
        makechildren(q.get())

När makechildren() stöter på slutordet gör den utskriften

    print "Det finns en väg till", slutord

Provkör med lite olika start- och slutord, bland annat ful - gud och ute - hit.

Tredje versionen

Det tråkiga med programmet är att det bara talar om att det finns en lösning. För att programmet ska kunna veta hur det har funnit gud måste varje ord kunna peka på sin förälder. Det är alltså inte typen string man ska arbeta med utan typen node som ser ut så här.

    class node:
        word = None
        parent = None

Huvudprogrammet skapar ett sådant objekt och lägger in startordet. Det som sätts in i kön och plockas ut ur kön är nu inte längre ord utan node, och det medför några ändringar i makechildren. När makechildren finner slutordet vill den skriva ut hela kedjan genom ett anrop writechain(child). Metoden writechain() ska skrivas rekursivt, så att man får ut kedjan med slutordet sist.

Om kön töms utan att någon lösning påträffats bör programmet meddela att det är omöjligt. Och när en lösning skrivits ut bör programmet avbryta körningen. Ett sätt att göra det är sys.exit() om man importerar modulen sys.

Frivilliga extrauppgifter

Längst från gud: Undersök vilket trebokstavsord som har längst väg till gud. Du måste då skriva en rekursiv countchain(child) som returnerar kedjans längd. Ledning: Om startord och slutord byter roller ändrar det inte kedjans längd.