Boggle


Spelet boggle går ut på att bilda ord ur en slumpad bokstavsmatris av storlek 4x4. Ord bildas genom att starta på en godtycklig bokstav i matrisen, och sedan hela tiden gå till närliggande bokstäver, rakt eller diagonalt. Varje bokstav får användas högst en gång i varje ord, och orden måste vara minst tre bokstäver långa.

Ord som är tre eller fyra bokstäver långa ger en poäng, varje bokstav därutöver ger ytterligare en poäng. Ett ord med längden åtta ger sådeles fem poäng.

Exempel

    r    a    e    r
    i    e    l    k
    s    g    i    a
    e    p    n    n

Ur denna matris kan man bilda t.ex. följande ord: alger, ange, aning, gele, gles, kanin, kelig, klang, klia, leka, pina, psi, regler, regn, reling, segel, segla, spinnaker, signaler, spinna.

Uppgift

Skriv ett program som låter en person spela boggle. Låt programmet slumpa fram en bokstavsmatris, varefter spelaren får en minut på sig att skriva in så många ord som möjligt. Användaren ska hela tiden se hur lång tid som återstår av minuten. Efter att denna minut gått kontrolleras vilka av orden som verkligen gick att bilda samt vilka av dessa som fanns med i ordlistan över godkända ord. Bara de ord som blivit godkända räknas. Uppslagning i ordlistan ska gå på logaritmisk tid eller snabbare (alltså inte på linjär tid).

Resultatet av varje omgång ska presenteras på lämpligt sätt. Det ska framgå vilka ord som godkänts och vilka som underkänts, samt varför de underkänts. Det ska även finnas möjlighet att få en lista över alla ord i ordlistan som går att bilda för den givna matrisen. Spelarens skicklighet fås som kvoten mellan de poäng spelaren uppnått och det antal poäng som maximalt skulle kunna erhållas med den givna matrisen.

När bokstavsmatrisen slumpas bör sannolikheterna för olika bokstäver väljas på ett lämpligt sätt; t.ex. bör vokaler generellt ha högre sannolikhet än konsonanter.