Sist endret: 23.09.2016  
 

Praksisoppgave - Redd Ratatosk

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 23.10.2017 15:00

Denne øvingen er ikke laget ferdig ennå.

Velg språk:
- Python
- Java

Løsningsforslag

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

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
ratatosk.py Funksjonene dfs(node) og bfs(node)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 2

Redd Ratatosk

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

Algemannen ser på klokken. 11:25, snart lunsj. Bare fem minutter igjen nå. Kobra trommer utålmodig på skrivebordet sitt, som er betydelig mindre enn Algemannens. Slik må det være på en effektiv arbeidsplass. Plutselig kommer en melding opp på skjermen til Algemannen.

To: algemannen@superhelt.org
From: ffryd@wwf.org
Subject: Redd meg fra en skummel fyr

En skummel fyr har kommet til treet Yggdrasil. Han har børse, og ser ond ut!

Hjelp, hjelp! 

PS: Jeg er singel.

- Kobra, vi har en jobb å gjøre!
- Å, nei! Vi har et kjempeproblem! Det er lunsj snart. Vi rekker ikke en liten pause først?
- Jo, selvfølgelig. Det rekker vi, siden vi er super-raske.

Tredve små minutter senere suser heltene avgårde i Algobilen. Etter kun kort tid er de fremme ved Yggdrasil, og er hur klara som helst. Ved foten av treet står en dame i rød anorakk og fekter med armene.
- Den skumle mannen klatret akkurat opp i treet. Dere må stoppe han!
- Hvordan så han ut? spør Algemannen.
- Han hadde hvit frakk, tykke briller, og var lettere skallet. Han hadde også med seg et gevær.
- Det er dr. Gewalt, den gale vitenskapsmannen, utbryter Algemannen. Hva enn han skal i treet, er det med onde hensikter.
- Gewalt er en ivrig storviltjeger, skyter Kobra inn. Kanskje han vil ha et trofé?
- Bor det noen dyr i treet? spør Algemannen den forskrekkede dyreverneren.
- Ja! Ratatosk, det søte lille ekornet bor der. Dere må redde det!

Før Algemannen og Kobra kan klatre opp i treet for å redde Ratatosk, må de legge en strategi for hvordan de skal gjennomsøke treet. Algemannen har gått på superheltskolen, og forklarer at det finnes to metoder. De kan enten gå i dybden eller bredden først. Hvis de går dybde-først, følger de en sti helt til de kommer til første løvnode. Deretter tar de den neste løvnoden, osv. Hvis de går bredde-først, tar de først alle nodene på første nivå, deretter alle på andre nivå, osv.

Dybde først søk med stakk Bredde først søk

- Det kan da ikke være noen tvil om at dybde-først er best, hevder Kobra. Det kan umulig være effektivt å klatre opp og ned som en tulling.
- Jeg har da vel ikke tenkt å klatre opp og ned, din fjomp. Jeg kaster meg jo fra grein til grein som den Tarzan jeg er. Det blir nok du som klatrer opp og ned.
- Jeg kommer ihvertfall ikke til å falle ned, svarer Kobra.
- Nå må du ikke glemme at dette er ikke hvilket som helst tre, forklarer Algemannen. Dette treet er uendelig høyt, mens ekornet befinner seg på en endelig possisjon.
- For eksempel halveis? spør Kobra
- Ja, for eksempel. Hvis du går dybde først, skal du ha litt mer enn bare superflaks hvis du skal finne ekornet i dette uendelige treet.
- Er dere klare snart, eller? spør den utålmodige ekornelskeren.

- Jeg synes den teorien din høres litt drøy ut, sier Kobra til Algemannen. Hva om jeg går dybde først, du bredde-først, og så ser vi hvem som finner Ratatosk først. Den som taper må gå hjem.
- Det er en deal, sier Algemannen morskt.
- Har du tid til en kopp kaffe etterpå eller? spør kvinnen.
- Vi superhelter har alltid dårlig tid, men det må jeg klare å presse inn i tidsskjemaet, sier Algemannen. Kobra må uansett gå hjem.
- Bah!

Kobra tenker sitt og spretter opp i treet. Alltid er det Algemannen som får alle damene. Det er bare fordi han er slik en glatt superhelt med alltid perfekt frisyre og egen algobil.

Oppgave

Du skal implementere dybde- og bredde-først-søk (DFS og BFS) for å finne Ratatosk, som finnes i akkurat én av nodene i et tre. Du kan lese om DFS på side 604 og BFS på side 595 i Cormen. Nedenfor ser du et rammeverk for innlesing av data, og en klasse Node som brukes til å holde styr på treet. En Node har en attributt barn som er en liste med referanser til alle barna.

Du skal lage to funksjoner dfs og bfs som begge tar inn en rotnode som parameter, traverserer treet og returnerer dybden på noden Ratatosk befinner seg i. Rotnoden er på dybde 0. DFS kan enten implementeres ved hjelp av en stakk eller med rekursjon, men i denne øvingen skal du bruke en stakk. Dette er ikke forklart direkte i læreboken, men det står om DFS på side 605. BFS implementeres ved hjelp av en kø (Cormen side 595).

Input består av følgende linjer:

  1. Hvilken funksjon som skal brukes, 'dfs', 'bfs' eller 'velg'. Dersom første linje inneholder verdien 'velg', kan du finne Ratatosk på den måten du vil. Ellers skal du kalle tilsvarende funksjon, for å sjekke at den fungerer. (På tidstestene vil input alltid være 'velg'.)
  2. Antall noder i treet.
  3. Hvilken node som er rot-noden i treet.
  4. Hvilken node Ratatosk befinner seg i (0-indeksert).
  5. Resten av linjene inneholder først et nodenummer (0-indeksert) og så en liste med nummerne til barna til nodene, alt separert med mellomrom.

Hvis det er n noder i treet, vil alle nodene ha et nummer fra og med 0 opp til n, men ikke nødvendigvis i rekkefølge.

Det oppgis at det er like stor sannsynlighet for at ratatosk befinner seg på alle nivåer, og dermed ikke like stor sannsynlighet for at han befinner seg i alle noder.

I eksempelet under er det 10 noder. Node 0 har barna 1, 2 og 3. Rotnoten er node 0 og Ratatosk befinner seg i node 7.

PS: Det er en sterk relasjon mellom lenkede lister, trær og grafer. Et tre er et spesialtilfelle av en graf, og en lenket liste er et spesialtilfelle av et tre. DFS og BFS er generelle graftraverseringsalgoritmer. Hvis du modifiserer funksjonene dine til å merke hvilke noder de allerede har besøkt, fungerer de på generelle grafer.

Rammeverk

#!/usr/bin/python3

from sys import stdin


class Node:
    def __init__(self):
        self.child = []
        self.ratatosk = False
        self.next_child = 0


def dfs(root):
    # SKRIV DIN KODE HER


def bfs(root):
    # SKRIV DIN KODE HER

function = stdin.readline().strip()
number_of_nodes = int(stdin.readline())
nodes = []
for i in range(number_of_nodes):
    nodes.append(Node())
start_node = nodes[int(stdin.readline())]
ratatosk_node = nodes[int(stdin.readline())]
ratatosk_node.ratatosk = True
for line in stdin:
    number = line.split()
    temp_node = nodes[int(number.pop(0))]
    for child_number in number:
        temp_node.child.append(nodes[int(child_number)])

if function == 'dfs':
    print(dfs(start_node))
elif function == 'bfs':
    print(bfs(start_node))
elif function == 'velg':
    # SKRIV DIN KODE HER

Variabelbeskrivelse

Rammeverket oppretter en nodeklasse med folgende egenskaper: barn - en liste over alle nodebarna til noden (noder direkte underlagt noden du staar i) ratatosk - en boolsk variabel som er True om ratatosk finnes i noden nesteBarn - en variabel du kan sette til neste nodebarn naar du bruker dybde-forst-ok

Input-eksempel

dfs
10
0
7
7 8 9
1 4 5
3 6 7
0 1 2 3

Tilhørende output

2

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: Modifiser programmet ditt til å kunne takle generelle grafer i stedet for trær. Du må da merke nodene etter hvert som du besøker dem. Lag deg input-data som tester at programmet ditt fungerer.

Et generelt tre er ofte oppbygd slik at en node peker til alle barna sine, som vist i denne øvingen. En annen måte å representere et tre på, er at en node peker til sitt første barn, og sitt neste søsken (venstre eller høyre). Alle nodene peker da til 0, 1 eller 2 andre noder, og er da et binærtre. Du ser et eksempel på dette i figuren under.

tree_to_2tree.png

Bit 2: Lag en funksjon som transformerer et tre hvor nodene har pekere til alle barna, til et tre hvor nodene har pekere til første barn og neste søsken. Legg merke til at dette blir et binærtre.

Topologien i et binærtre har en enkel "en-til-en"-relasjon med de positive heltall, som gjør at nodene kan lagres i en array, uten at de trenger å ha pekere. Hvis en node har nummeret i, har venstre barn nummeret 2*i+1, og høyre barn nummeret 2*i+2.

tree_to_2tree.png

Bit 3: Lag en funksjon som putter et binærtre fra oppgaven over inn i en liste. Nodene kan da representeres kun ved sin vekt (altså en float, ikke et Node-objekt). Binærtreet fra Bit 1 er ikke komplett, hvilket betyr at noen av elementene i listen ikke skal være noder. Du kan representere disse med verdien None.