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

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.