TILDA, ÖVNING 3

    Problemträd, breddenförst, djupetförst

  1. STRYKORD

    Ordet orkan är ett strykord eftersom man kan stryka sista bokstaven om och om igen och bara få riktiga ord. orkan - orka - ork - or - o Uppgiften är att finna det längsta strykordet i svenska språket. Ordlistan finns på fil. Rita problemträdet och jämför olika tänkbara algoritmer.
    Tomt ord är stamfar, barnen får man genom att lägga på en bokstav och kolla i ordlistan. Eftersom man inte är ute efter kortaste strykord utan tvärtom längsta är breddenförst inte nödvändigt. Rekursiv djupetförst som går igenom hela trädet och noterar längdrekord är kanske bäst, särskilt eftersom letandet i ordlistan då hela tiden går framåt! Här har jag lagt alla svenska ord i ett binärträd - det tar förstås mycket minne och är onödigt. Man kan i stället läsa filen ord för ord eftersom man aldrig behöver backa. 

    def byggut(ord):
    """ Rekursiv djupetförst"""
    global rekord
    if len(ord) > len(rekord): 
       rekord = ord
    for tkn in alfabet:
      if svenska.exists(ord+tkn):
          byggut(ord+tkn)

    
from bintree import Bintree
alfabet="abcdefghijklmnopqrstuvwxyzåäö"
rekord=""

svenska=Bintree()
svenskfil = open("words.txt")
for rad in svenskfil.readlines():
    svenska.put(rad.strip())     #Ta bort returtecknet

byggut("")
print "Längsta strykord: ", rekord


  2. SJUOR TILL HUNDRA

    Det gäller att skriva talet 100 med enbart sjuor och dom fyra räknesätten, till exempel så här. 7 +7 /7 *7 *7 =98 Det var ett gott försök som inte nådde ända fram. För att man ska få använda / måste divisionen gå jämnt ut. Rita problemträdet och diskutera bästa algoritm för att avgöra OM problemet är lösbart. Om man dessutom vill veta hur lösningen ser ut krävs en mer komplicerad datastruktur. Beskriv den och skissa ett program.
    Som gjort för breddenförst med heltalskö. 

    from queue import Queue

q = Queue() 

def makesons(tal):
    if tal==100: '
       print "Hundra!"
    q.put(tal+7)
    q.put(tal-7)
    q.put(tal*7)
    if(tal%7==0): 
       q.put(tal/7)

q.put(0)             
while not q.isempty():
    makesons(q.get())


    Hoppsan, det här programmet håller på länge. Vi inför en boolesk variabel funnen som blir True när vi hittat en lösning, och låter den ingå i slingans villkor. 

    from queue import Queue

def makesons(tal):
    if tal==100:
       print "Hundra!"
       return True

    q.put(tal+7)
    q.put(tal-7)
    q.put(tal*7)
    if(tal%7==0): 
       q.put(tal/7)
    return False

q = Queue() 
q.put(0)             
funnen = False
while not q.isEmpty() and not funnen:
    funnen = makesons(q.get())


    Ett annat sätt att avbryta programmet är att definiera en egen klass Klar som ärver från Exception. 

    from queue import Queue

class Klar(Exception):
    pass

def makesons(tal):
    if tal==100:
       print "Hundra!"
       raise Klar

    q.put(tal+7)
    q.put(tal-7)
    q.put(tal*7)
    if(tal%7==0): 
       q.put(tal/7)

q = Queue() 
q.put(0)             
try:
    while not q.isEmpty():
        makesons(q.get())
except Klar:
    print "Lösning funnen."


    Om man ska skriva ut lösningen: 

    from queue import Queue
from sys import exit

class Node:
    def __init__(self, tal = 0, op = "", far = None):
        self.tal = tal
        self.op = op
        self.far = far


def insert(tal, op, far):
    nod=Node(tal, op, far)
    q.put(nod)

def makesons(far):
    tal = far.tal
    if tal == 100:
        writechain(far)
        exit()
    insert(tal+7, "+", far)
    insert(tal-7, "-", far)
    insert(tal*7, "*", far)
    if(tal%7==0): 
        insert(tal/7, "/", far)

def writechain(p):
    if p != None: 
        writechain(p.far)
        if p.far != None:
            print p.op, "7 =",  p.tal
        else:
            print p.tal

q=Queue()
q.put(Node())             
while not q.isEmpty():
    makesons(q.get())


    Utskrift: 

     0
 + 7 = 7
 + 7 = 14
 * 7 = 98
 * 7 = 686
 + 7 = 693
 + 7 = 700
 / 7 = 100

    Fråga: Kan man snabba upp programmet ytterligare genom att slopa dumbarn? Hur många gånger kommer 0 att läggas in i kön?

  3. Labyrint

    Tilda går ensam omkring i en labyrint, hennes kompisar har redan hittat ut. Det finns gångar och korsningar. En del gångar är blindgångar. Vid varje korsning kan man gå åt höger eller vänster alternativt gå tillbaka dit man kom ifrån. Tilda bestämmer sig för att hålla till höger i varje korsning tills hon hittar utgången. Vad kallas en sådan sökalgoritm? Väl hemma bestämmer sig Tilda för att skriva ett program som hittar vägen genom en labyrint. Vad behöver man för datastrukturer för att implementera en sådan algoritm?

  4. Taltävling

    Under sommaren har det gått en tävling i radio där det gäller att så snabbt som möjligt hitta ett tal som uppfyller två villkor. Första villkoret, som gäller hela tävlingen, är att siffrorna i talet måste vara strikt stigande (23578 är OK men inte 235578 eller 23587). Andra villkoret är nytt för varje dag och kan t ex vara att talet ska vara ett primtal, jämnt delbart med 599 eller en tvåpotens. Beskriv utförligt en breddenförst- eller djupetförstsökning (effektivare metod ger fler poäng) som hittar det minsta talet som uppfyller villkoren. Vilka klasser och metoder behövs?

  5. Patiens

    I patiensen "Rutan" använder man bara ess, kungar, damer och knektar, alltså sexton kort. Det gäller att lägga ut korten i en 4x4-matris så att två kort av samma färg eller valör aldrig finns i samma rad, kolumn eller någon av de båda diagonalerna. Man vill att ett program ska skriva ut alla lösningar till patiensen på nedanstående sätt. 
          hj E   sp D   kl Kn  ru K
      kl K   ru Kn  hj D   sp E
      ru D   kl E   sp K   hj Kn
      sp Kn  hj K   ru E   kl D
    Du behöver inte skriva programkod, men du ska förklara algoritmen utförligt och beskriva datastrukturer, metoder och klasser.

  6. Sudoku

    Sudoku är ett spel som består av ett rutnät på 9x9 rutor, uppdelat i nio 3x3-rutor. Rutnätet har n siffror ifyllda från början och det gäller att fylla varje rad, varje kolumn och varje 3x3-ruta med siffrorna 1-9. En siffra får aldrig förekomma mer än en gång per rad, kolumn och 3x3-ruta. Beskriv en algoritm som hittar en lösning till ett givet Sudoku-problem, och tala om hur algoritmen skulle kunna implementeras.

  7. Pokémontränaren

    Du är så uppskattad i ditt arbete som pokémontränare att du kan välja och vraka bland erbjudandena. Givet ett antal förslag (anbudsgivare, startdag, slutdag, arvode) vill du planera nästa månad så att den blir så lönsam som möjligt. Rita först upp problemträdet (roten och några noder i de första två nivåerna räcker). Föreslå en algoritm som finner det schema som ger störst inkomster. Motivera ditt val av algoritm och beskriv hur du skulle implementera algoritmen.