Sist endret: 23.09.2016  
 

Praksisoppgave - Kortstokker

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 11.09.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
kortstokker.py, kortstokker_tweak.py, kortstokker_tweak2.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
kortstokker.py Funksjonen flett(stokker)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt initiativ

Kortstokker

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

Algemannen står på toppen av en skyskraper. I hendene har han en liten dings som sier "Tikk, takk. Tikk, takk." På bakken ved siden av ham ligger det noen kortstokker og en konvolutt.
- Kobra, tar du og åpner den konvolutten som ligger på bakken der?
Kobra tar opp konvolutten, og åpner den nervøst. Han skummer gjennom brevet før han leser det høyt.
- "Ha, ha! For siste gang har dere stukket kjepper i hjulene mine. Dette er slutten på deres karrierer og liv! Den eneste sjansen dere har til å overleve, er å løse gåten og taste inn den hemmelige koden på bomben. Med vennlig hilsen dr. Gewalt." Å, nei! Vi har et kjempeproblem! Jeg hater gåter.
- Ta det med ro, Kobra. Dette ordner seg. Står det ikke noe mer i brevet, kanskje med liten skrift eller noe?
- Hmm. Jo, her står det noe. "Hint: Ha, ha. Dere får ikke noe hint!".
- Dette blir for dumt, sier Algemannen. Dette bryter liksom med en eller annen uskreven kodeks eller noe. Men som de joviale karene vi er, får vi bare gjøre det beste ut av situasjonen. Hva er det med de kortstokkene?
Kobra bøyer seg ned og undersøker.
- Hmm, det er skrevet noen tall og bokstaver på dem. Hva skal det bety mon tro?

Oppgave

I denne øvingen skal du flette sammen et sett med kortstokker. På hvert av disse kortene står det ett tall og en bokstav. Hver enkelt stokk er allerede sortert på tall. Oppgaven din er å flette stokkene sammen slik at resultatet fremdeles er riktig sortert. Det er mange forskjellige måter å løse dette problemet på, men det enkleste er nok å flette sammen stokkene som du gjør i merge-sort. Se Cormen side 32.

Input til programmet er en stokk på hver linje. Kortene i hver stokk har alltid samme bokstav. Hver linje begynner med bokstaven til stokken etterfulgt av kolon. Deretter kommer verdien til kortene, separert med komma, i sortert rekkefølge. Det vil aldri finnes to kort med samme verdi. Du skal skrive ut ordet som bokstavene til de sorterte kortene danner (uten mellomrom).

Hvis du implementerer fornuftig, blir kjøretiden O(n log k), hvor k er antall stokker. Men mergingen av disses stokkene kan til og med bli mer enn O(n log n) hvis du merger dem i på en dum måte. Den kan bli så mye som O(n2). Hvordan det? Spør en studass hvis du ikke finner det ut.

I denne øvingen er det ikke tillatt å bruke den innebygde list.sort(). Ikke levér slike løsninger på øvingssystemet. Det er også juks å bruke modulen heapq og lignende. Moral: Alt som har med selve sorteringen å gjøre må du gjøre selv.

Rammeverk

#!/usr/bin/python3

from sys import stdin
from itertools import repeat


def merge(decks):
    # SKRIV DIN KODE HER


def main():
    # Read input.
    decks = []
    for line in stdin:
        (index, csv) = line.strip().split(':')
        deck = list(zip(map(int, csv.split(',')), repeat(index)))
        decks.append(deck)
    # Merge the decks and print result.
    print(merge(decks))


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Rammeverket lagrer en liste bestaaende av lister til variabelen 'decks'. De interne listene representerer en kortstokk hver. Hvert enkelt kort er representert som et tuppel paa formen (tall, bokstav) f.eks. (1, 'i'). Ved bruk av eksempelinputet vil 'decks' se ut som: [[(1,'i'),(3,'i'),(5,'i'),(8,'i')], [(2,'n')], [(4,'t'),(7,'t')], [(6,'a')], [(9,'v')]]

Input-eksempel

i:1,3,5,8
n:2
t:4,7
a:6
v:9

Tilhørende output

initiativ

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

I stedet for å flette stokkene sammen to og to, kan du flette alle på en gang. Du ønsker da å finne stokken med det minste kortet, ta dette ut, og sette det inn i restultatstokken. Det er mange forskjellige måter å finne denne stokken på.

Bit 1: En måte å raskt finne frem til stokken med det laveste kortet på er å holde alle stokkene i en min-heap. Du kan ta ut det minste kortet fra stokken på toppen, og så la denne stokken synke til riktig sted i heapen. Kjøretiden for hele algoritmen blir da O(n log k). Implementer denne kortstokkflettingen.