Sist endret: 23.09.2016  
 

Praksisoppgave - Kobra lærer å stave

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 02.10.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
ordbok.py, ordbok_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
ordbok.py Funksjonene bygg(ordliste) og posisjoner(ord, strukt)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt output_eksempel_01.txt

Kobra lærer å stave

Det er ikke nødvendig å lese historien for å løse oppgaven.

- Men hva er dette da, Kobra? Kanskje ett av tre ord er stavet riktig i dette notatet. Hvor var det egentlig du gikk på skole?

Algemannen og Kobra er på kontoret, og Algemannen ser over et notat han akkurat dikterte. Etter at Gewalt kjøpte opp et multinasjonalt advokatfirma forrige uke, har våre helter måttet jobbe overtid hver dag. Gewalt er en mann som prøver å følge med i tiden, og ukens strategi er er å kjøpe opp små firmaer i besittelse av patenter. De siste dagene har han saksøkt alle som kan krype og gå.
- Hva kan du vente da, når jeg skal være god hjelper, personlig tjener og sekretær. Jeg kan jo ikke klare alt perfekt.
- Skal ikke du liksom være en superhelt da?
- Tror du for eksempel at Wolverine er flink i bøying av sterke verb eller? Ble ikke noe lettere av at Gewalt fikk tak i den patenten på avlange skriveredskaper heller. Prøv å skrive med en potet dyppet i saft selv du.

Stillheten legger seg over kontoret. Begge to har skjønt at de nærmet seg farlige eksistensielle spørsmål.
- Fikk ikke du penger til å kjøpe en ordbok, da? spør Algemannen forsiktig.
- Tja, jo. Jeg brukte vel pengene på den siste Fantonald-pocketen.
- Det var penger vel brukt, da.
- Men har du tenkt over hvor ubrukelige de ordbøkene er eller? Hvis jeg slår opp i en ordbok, hva er det jeg lurer på da? Jo, jeg lurer på hvordan ordet staves. Men hvis jeg ikke vet hvordan ordet staves, hvordan i bestefars lange skjegg skal jeg kunne finne det i ordboken da?
- Du har jo et poeng, erkjenner Algemannen.
- Og vi har et middels stort problem!

Oppgave

Du skal lage et program for å finne ord i en tekst. For å gjøre dette, kan du lage en funksjon som bygger et tre og en funksjon som bruker treet til å søke. Første linje av input til programmet er en streng som består av tegnene [a-z] og mellomrom. Dette representerer dokumentet det skal søkes i. De neste linjene i input er spørringer etter ord. Programmet skal søke etter disse ordene i teksten, og returnere hvilke posisjoner ordet finnes på. Tegnet ? brukes til å angi at her kan det stå en hvilket som helst bokstav fra alfabetet [a-z].

En måte å løse denne oppgaven på er å putte ordene inn i et tre, hvor hver bokstav i ordet tilsvarer en peker til neste node. Nedenfor ser du treet for setningen ha ha mons har en hund med moms hun er en hunn. Legg merke til at noen av nodene inne i treet tilsvarer slutten på ord, mens andre ikke gjør det. Legg også merke til at noen ord finnes på flere steder i dokumentet.

Funksjonen posisjoner(ord, indeks, node) som skal returnerer posisjonene til alle treff på ord i trestrukturen med rot node. indeks sier hvor langt i ordet vi har kommet. For å finne disse posisjonene kan den bruke rekursjon. Å bruke rekursjon vil si å utføre rekursive kall. Et kall til funksjonen selv er et rekursivt kall. Rekursjon brukes som regel til å dele opp et problem i mindre deler, for deretter å sette sammen løsningene. I dette problemet er det ordene som inneholder ? som kan gi flere delproblemer. Når du ser ? skal du kalle posisjoner én gang for alle mulige erstatninger for ? med de tilhørende delene av treet.

ordtre.png

Output fra programmet ditt skal være søkeuttrykk: pos1 pos2 ... posN, som vist i eksempel-output. Posisjonene skal være sortert stigende. Dette gjøres allerede i den utdelte koden.

I rammeverket er det brukt dictionaries. En dict i Python er omtrent det samme som en HashMap Java, man kan lagre verdier assosiert med nøkler, og hente dem ut igjen, i konstant tid Θ(1) (i gjennomsnitt). Forskjellen fra vanlige arrays, hvor nøklene er indekser, kan nøklene i en dict være hva som helst, og du er ikke avhengig av at de er i et lite verdiområde.

Eksempel på bruk av dict:

>>> d = {} 
>>> d['a'] = 1
>>> d['b'] = 2
>>> if 'b' in d:
...     print d['b']
... 
2
>>> d[42] = 'mjau'
>>> print d.keys()
['a', 42, 'b']
>>> print d.values()
[1, 'mjau', 2]
>>> print d.items()
[('a', 1), (42, 'mjau'), ('b', 2)]

Rammeverk

#!/usr/bin/python3

from sys import stdin, stderr
import traceback


class Node:
    def __init__(self):
        self.barn = {}
        self.posi = []


def bygg(ordliste):
    # SKRIV DIN KODE HER


def posisjoner(ord, indeks, node):
    # SKRIV DIN KODE HER


def main():
    try:
        ord = stdin.readline().split()
        ordliste = []
        pos = 0
        for o in ord:
            ordliste.append((o, pos))
            pos += len(o) + 1
        toppnode = bygg(ordliste)
        for sokeord in stdin:
            sokeord = sokeord.strip()
            print("%s:" % sokeord, end='')
            posi = posisjoner(sokeord, 0, toppnode)
            posi.sort()
            for p in posi:
                print(" %s" % p, end='')
            print()
    except:
        traceback.print_exc(file=stderr)


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Rammeverket oppretter en nodeklasse for deg med folgende egenskaper:
barn - en liste med alle nodebarna til noden (noder direkte underlagt noden du staar i)
posi - en liste over indeksene hvor ordet begynner i tekststrengen (inputet)

Andre variable:
'ordliste' - en liste med tupler. Tuplene er paa folgende form: (ord, posisj), og det er et tuppel for hvert ord i input. Merk at for ord som forekommer flere ganger vil det vaere flere tupler, et tuppel for hver forekomst. For eksempel baade ("ha", 0) og ("ha", 3) for eksempel-input.
'ord' - et enkelt ord, for eksempel "ha".
'indeks' - sier hvor langt i ordet vi har kommet i soket, og er altsaa et tall.
'node' - er rotnoden til treet du skal soke gjennom.

Dersom du fortsatt er usikker paa de ulike variablene, kan det vaere greit aa printe de og se hva de faktisk inneholder.

Input-eksempel

ha ha mons har en hund med moms hun er en hunn
ha
mjau
m?d
e?

Tilhørende output

ha: 0 3
mjau:
m?d: 23
e?: 15 36 39

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit

Bit 1: Ofte er du interessert i å søke etter uttrykk med ukjente delstrenger, hvor du ikke vet lengden på delstrengen. La * representere fra 0 til uendelig mange bokstaver. En spørring som *e* i eksemplet skal da gi treff på ordene en, er og med. Modifiser søkefunksjonen din til å kunne søke etter slike uttrykk.