TILDA, ÖVNING 3
   
______________________________________________________________________
**********************************************************************

Problemträd, breddenförst, djupetförst, hashning

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.

# coding:iso-8859-1

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ö.

# coding:iso-8859-1

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())


Om man ska skriva ut lösningen:

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

from queue import Queue
from sys import exit

q=Queue() 

def insert(tal,far):
    nod=Node(tal, 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)
        print p.tal

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




______________________________________________________________________
**********************************************************************
3 PERFEKT HASHFUNKTION 

Hitta på en perfekt hashfunktion för atomer. Hur stor blir
hashtabellen?

______________________________________________________________________

Låt a=1, b=2, ..., z=26 och A=0, B=27, ..., Z=675 (25*27)
Då blir hash("A")=0 och hash("Zz")=701, så det behövs
702 platser i hashtabellen (dvs ca sex gånger mer än antalet element).

Ingen extra luft - det blir inga krockar!

I labb 5 ska ni inte göra en så här stor tabell utan istället
använda kvadratisk probning.




______________________________________________________________________
**********************************************************************
4 HÅLL REDA PÅ MEDIA (Tildatenta 030308)

Under gulfkriget var det väldigt svårt för armestaben att hålla reda 
på alla TV-bolag som for omkring och rapporterade i öknen. För att 
hålla reda på dem användes en hashvektor. Koden fungerade inte som 
avsett och man har nu gett i uppdrag åt en f.d. tildastudent att 
titta på en misstänkt del av koden:

from string import find

p = 100;
hashvektor = [0]*p
alfabet = "abcdefghijklmnopqrstuvxyz"

def put(tvbolagsnamn, tvbolag):
    hashcode = 0
    for i in range(len(tvbolagsnamn)):
        alfanum = find(alfabet, tvbolagsnamn[i])+1
        hashcode += alfanum
    hashcode = hashcode % p
    hashvektor[hashcode] = tvbolag

Vad är det för fel på koden? Beskriv hur man kan förbättra den. 
Namnen på TV-bolagen kan antas bestå av högst tre bokstäver. 
Det kommer inte att förekomma mer än 75 TV-bolag.



______________________________________________________________________

Det som gör att koden inte fungerar är att det inte finns någon 
krockhantering.
	 hashvektor[hashcode] = tvbolag;
För att lösa det kan man använda t.ex. krocklistor eller linjär 
probning. Linjär probning fungerar så att om det är upptaget på 
den givna positionen så söker man tills man antingen hittar 
nyckeln (den var redan instoppad sedan tidigare) eller tills  
man hittar ett tomt element i vektorn.

Hashkoden är ganska korkat implementerad. Strängarna "AB" och 
"BA" får samma värde. 
        alfanum = find(alfabet, tvbolagsnamn[i])+1
        hashcode += alfanum
För att lösa det kan man vikta genom att multiplicera med 
t.ex. 1, 100 och 10000.

Längden på hashvektorn är lite för liten och dessutom inget 
primtal. Välj istället hashvektorns storlek till exempelvis 151 
(dubbelt så stor som förväntade antalet element). 

______________________________________________________________________
**********************************************************************
5 Nix till telefonförsäljning (TILDA-tenta 000603)

Föreningen för konsumentskydd vid marknadsföring per telefon
har startat ett register dit den som inte vill bli uppringd av
telefonförsäljare kan anmäla sig.

Till att börja kommer kontrollen att ske genom att företaget sänder 
sin telefonlista till nix och får tillbaka en lista där de nixade
numren markerats.

Vilka av följande metoder kan föreningen använda sig av? 
Vilken är bäst?
Binärträd, bloomfilter, hashtabell.

Ett framtida mål är att kontroll också skall kunna ske över internet.
Då måste kontrollen ske snabbt men man vill också försäkra sig om att 
ingen ska kunna få ut en lista över alla nixade telefonnummer.

Vilken metod passar bäst för internet-kontrollen?


______________________________________________________________________


Just nu ringer många och anmäler sig till NIX-registret så det måste 
gå lätt att lägga till nya.

Binärträd går snabbt att söka i men man måste se till att 
det inte blir obalanserat när nya telefonnummer läggs till.

Bloomfilter är besvärligt att stoppa in nya nummer i.

Hashtabell se bloomfilter ovan.


Bloomfilter är det bästa alternativet för den framtida internet-
kontrollen. Man kan räkna med att många har registrerat sig så 
snabb sökning är nödvändig. 
Dessutom har bloomfilter fördelen att ingen användare kan få ut 
telefonnummerlistan.