Lab8

Grunnleggende oppgaver (Nivå E):

Nivå A-D:

Nivå E
Handleliste

Denne oppgaven består av to deler. Skriv funksjoner til begge deloppgaver i én felles fil, shopping_list.py.

Del A

Skriv funksjonen shopping_list_to_dict med en parameter shopping_list som er en streng som innholder en handleliste. Funksjonen skal returnere et oppslagsverk med varer som nøkler og antall som verdier. Du kan anta at strengen består av flere linjer, hvor hver linje (som ikke er tom) består av først et heltall, deretter et mellomrom, og deretter navnet på varen (uten mellomrom).

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester shopping_list_to_dict... ", end="")
shopping_list = """\
2 brød
3 pizza
10 poteter
1 kaffe
1 ost
14 epler
"""
shopping_list_as_dict = shopping_list_to_dict(shopping_list)
assert({
    "brød": 2,
    "pizza": 3,
    "poteter": 10,
    "kaffe": 1,
    "ost": 1,
    "epler": 14,
} == shopping_list_as_dict)
print("OK")

  • Les kursnotater om oppslagsverk.
  • Begynn med å opprette et tomt oppslagsverk (som skal returneres på slutten av funksjonen).
  • Bruk en løkke over hver av linjene i strengen; les kursnotater om løkker over strenger for å finne en egnet måte å gå gjennom linjene i strengen på.
  • Inne i løkken, sjekk at linjen ikke er den tomme strengen (hvis den er det, bruk f. eks. continue for å hoppe over denne linjen og fortsette med neste).
  • Inne i løkken, bruk linjen num, food_name = line.split(" ") for å dele opp strengen i to biter; da blir num en variabel som holder en streng med antallet (f. eks. "2"), og food_name blir en streng som inneholder navnet på maten (f. eks. "brød").
  • I oppslagsverket, legg til food_name som en nøkkel med verdien int(num).

Del B

Skriv funksjonen shopping_list_file_to_dict med en parameter path som er en streng som representerer en filsti til en fil som inneholder en handleliste.

For å teste funksjonen, last ned filen handleliste.txt og legg den i samme mappe programmet kjøres fra (husk at dette ikke nødvendigvis er samme mappe hvor shopping_list.py ligger med mindre du har åpnet VSCode i den samme mappen).

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester shopping_list_file_to_dict... ", end="")
shopping_list_as_dict = shopping_list_file_to_dict("handleliste.txt")
assert({
    "brød": 2,
    "pizza": 3,
    "poteter": 10,
    "kaffe": 1,
    "ost": 1,
    "epler": 13,
} == shopping_list_as_dict)
print("OK")

Denne funksjonen består av 1-3 linjer med kode avhengig av hvor kompakt du skriver.

  • Begynn med å lese inn hele filen som en enkelt streng (du kan kopiere og kalle på funksjonen read_file fra kursnotater om lesing og skriving til fil).
  • Bruk denne strengen og kall på funksjonen du skrev i forrige deloppgave.
  • Returner resultatet.

Nivå E
Collatz-sekvensen

Collatz-sekvensen er definert som følger:

  1. Start med et tall \(n\)
  2. Hvis \(n\) er jevnt så er neste tall \(\frac{n}{2}\), ellers så er neste tall \(3n +1\)
  3. Repeter steg \(2\) med det nye tallet helt til du får \(1\). Da er du ferdig.

Her er en funksjon som beregner Collatz-sekvensen gitt en en startverdi \(n\):

def collatz_sequence(n):
    sequence = [n]
    while n > 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        sequence.append(n)
    return sequence

I filen collatz.py, skriv en funksjon som heter collect_collatz(a, b) som bruker collatz_sequence -funksjonen gitt over til å beregne Collatz-sekvensen for alle tall fra og med \(a\) og opp til (men ikke inkludert) \(b\). Sekvensene skal returneres i form av et oppslagsverk hvor startverdiene er nøkler.

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester collect_collatz... ", end="")
assert({
    1: [1],
    2: [2, 1], 
    3: [3, 10, 5, 16, 8, 4, 2, 1],
} == collect_collatz(1, 4))
assert({
    3: [3, 10, 5, 16, 8, 4, 2, 1],
    4: [4, 2, 1],
    5: [5, 16, 8, 4, 2, 1],
} == collect_collatz(3, 6))
print("OK")

  • Begynn med å opprette et tomt oppslagsverk (som du skal returnere på slutten av funksjonen, når det er ferdig fylt opp med nøkler og verdier).
  • Bruk en løkke for å gå gjennom alle tall fra og med \(a\) opp til men ikke inkludert \(b\) (se kursnotater om løkker).
  • Inne i løkken: gjør et kall til collatz_sequence -metoden med iteranden som argument. Oppdater oppslagsverket slik at iteranden blir en ny nøkkel med returverdien fra kallet til collatz_sequence som verdi.

Nivå E
Lister vs oppslagsverk

Denne oppgaven består av to deler. Skriv funksjoner til begge deloppgaver i én felles fil, list_vs_dictionary.py.

I denne oppgaven skal vi undersøke slektskapet mellom oppslagsverk og lister. En nøkkel spiller på mange måter samme rolle for et oppslagsverk som en indeks gjør for en liste.

Del A

Skriv funksjonen key_value_getter(d) som tar inn en dictionary d, og skriver ut til skjermen nøklene, verdiene og nøkkel/verdi-par. Eksempelkjøring:

key_value_getter({
  "monday": 0,
  "tuesday": 0.7,
  "wednesday": 0,
  "thursday": 4.7,
  "friday": 10
})

skal gi utskriften:

Dictionary keys:
monday
tuesday
wednesday
thursday
friday

Dictionary values:
0
0.7
0
4.7
10

Dictionary keys/value:
monday 0
tuesday 0.7
wednesday 0
thursday 4.7
friday 10

Del B

Skriv funksjonen index_value_getter(a) som tar inn en liste a og skriver ut til skjermen indeksene, verdiene og indeks/verdi -parene. Eksempelkjøring:

index_value_getter([7.0, 8.0, 10.0, 9.0, 10.0])

skal gi utskriften:

List indices:
0
1
2
3
4

List values:
7.0
8.0
10.0
9.0
10.0

List indices/value:
0 7.0
1 8.0
2 10.0
3 9.0
4 10.0
Nivå D
På lager

Vi ser for oss at følgende dictionary representerer varebeholdningen i en bokhandel. Nøklene er titler og verdiene er antall bøker:

in_storage = {
    "Ancillary Justice": 1_046, # vi kan bruke _ i tall, den blir ignorert
    "The Use of Weapons": 372,
    "1984": 5_332,
    "The Three-Body Problem": 523,
    "A Fisherman of the Inland Sea": 728,
}

I filen in_stock.py, skriv en funksjon søk_på_lager()som tar brukerinput en boktittel (bruk input() for dette) og bruker .get() i en løkke for å finne ut hvor mange eksemplarer av boken vi har. Funksjonen skriver ut strengen som sier hvor mange eksemplarer av boken vi har. Hvis boken ikke er på lager skal programmet skrive ut strengen Vi har 0 av [book_tittel]. Kjør løkken frem til vi får en tom streng som tittel. Da skal programmet skrive ut strengen «Ha det!».

Eksempelkjøring:

søk_på_lager()

Tittel?
1984   
Vi har 5332 av "1984"
Tittel?
A Fire Upon the Deep
Vi har 0 av "A Fire Upon the Deep"
Tittel?
Automate the Boring Stuff with Python
Vi har 0 av "Automate the Boring Stuff with Python"
Tittel?
 
Ha det!
Nivå C

Værmelding

I denne oppgaven skal vi bruke et oppslagsverk som igjen inneholder oppslagsverk med informasjon om værstasjoner:

weather_stations = {
    "Bergen": {
        "Wind speed": 3.6,
        "Wind direction": "northeast",
        "Precipitation": 5.2,
        "Device": "WeatherMaster500"
    },
    "Trondheim": {
        "Wind speed": 8.2,
        "Wind direction": "northwest",
        "Precipitation": 0.2,
        "Device": "ClimateDiscoverer3000"
    },
    "Svalbard": {
        "Wind speed": 7.5,
        "Wind direction": "southwest",
        "Precipitation": 1.1,
        "Device": "WeatherFinder5.0"
    },
}

I filen weather_report.py, lag et funksjonen weather_report(weather_stations, city) som tar in et bynavn og skriver ut værrapporten for denne byen.

Eksempelkjøring:

weather_report(weather_stations, "Bergen")

skal skrive ut:

The weather in Bergen:
The wind speed is 3.6m/s in the northeast direction and the precipitation is 5.2mm.
The measurement was done using the WeatherMaster500 weather station.
Nivå C
Ord sammenligning

I filen word_comparison.py skriv en funksjon som heter word_comparison() og som tar to ord (strenger) som argumenter. Funksjonen skal så sammenligne bokstavene i ordene og returnere en dictionary som sier hvilke bokstaver finnes i begge ordene, hvilke bokstaver som finnes i kun det første ordet og hvilke bokstaver som finnes i kun det andre ordet (som set). Husk at rekkefølgen ikke spiller noen rolle i mengder.

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester word_comparison... ", end="")
assert({
  "In common": {"e", "c"},
  "Unique to first word": {"r", "u", "t", "p", "o", "m"},
  "Unique to second word": {"s", "i", "n"},
} == word_comparison("computer", "science"))
print("OK")
Nivå B
Fantasy Game Inventory

Fantasy Game Inventory er tatt fra boken https://automatetheboringstuff.com/2e/chapter5/.

Du lager et fantasy-videospill. Datastrukturen for å modellere spillerens beholdning skal være en dictionary hvor nøklene er strings som beskriver tingene i beholdningen, og verdiene er integers som forteller hvor mange av hver ting spilleren har. For eksempel, verdiene i dictionary {'rope': 1, 'torch': 6, 'gold coin': 42, 'dagger': 1, 'arrow': 12} betyr at spilleren har 1 rope, 6 torches, 42 gold coins, osv.

I filen fantasy_game_inventory.py skriv funksjonen displayInventory(d) som tar inn en dictionary av beholdningen d. Funksjonen skal returnere en streng som beskriver hele innholdet i beholdningen samt den totale antall gjenstander i beholdningen i formatet vist i eksempelkjøringen nedenfor.

stuff = {"rope": 1, "torch": 6, "gold coin": 42, "dagger": 1, "arrow": 12}
print(displayInventory(stuff))

Inventory:
1 rope
6 torch
42 gold coin
1 dagger
12 arrow

Total number of items: 62
Nivå B
Dragon Hoard

Dragon Hoard er tatt fra boken https://automatetheboringstuff.com/2e/chapter5/.

Skatten til en beseiret drage er representert som en liste med strenger som dette: dragonLoot = ['gold coin', 'dagger', 'gold coin', 'gold coin', 'ruby']

I filen dragon_hoard.py skriv en funksjon som heter addToInventory(inventory, addedItems), hvor inventory parameteren er en dictionary av spillerens beholdning og addedItems parameteren er en liste som f.eks dragonLoot.

addToInventory() funksjonen skal returnere en dictionary som representerer den oppdaterte beholdningen. Merk at listen over tilleggsartikler kan inneholde flere av samme element.

Om du kaller displayInventory() etter å ha oppdatert beholdingen med addToInventory() funksjonen skal du få ut likt som nedenfor:

inv = {"gold coin": 42, "rope": 1}
dragonLoot = ["gold coin", "dagger", "gold coin", "gold coin", "ruby"]
updated_inv = addToInventory(inv, dragonLoot)
print(displayInventory(updated_inv))

Inventory:
45 gold coin
1 rope
1 dagger
1 ruby

Total number of items: 48
Nivå A
Pinlig party

Denne oppgaven er tatt fra https://open.kattis.com/problems/awkwardparty.

Martin har invitert alle han kjenner til å feire bursdagen hans, og hele \(n\) folk fra hele verden har takket ja til invitasjonen.

Martins mor Margrethe har bestemt seg for at alle gjestene skal sitte med maksimal klossethet; dette er for å sikre at ingen har noe meningsfullt å diskutere under middagen, og at alle i stillhet vil nyte den ganske smakfulle koriandersuppen hennes.

Margrethe vet at klossheten maksimeres hvis gjestene sitter på en lang rekke langs et enkelt bord, på en slik måte at ingen sitter ved siden av noen som snakker samme språk som dem selv. Enda bedre, hun har definert klosshetsnivået til en sittearrangement til å være minimum antall seter som skiller to gjester som snakker samme språk. Hvis ikke to personer snakker samme språk, er klosshetsnivået definert til å være \(n\) (antall gjester). To seter ved siden av hverandre sies å være adskilt med 1.

I filen awkward_party.py skriv en funksjon awkwardness_level(seating) som tar inn en filsti seating som input parameter. Filen seating skal bestå av to linjer. Den første linjen inneholder et heltall \(n\) som angir antall gjester. På den andre linjen følger \(n\) heltall separert med mellomrom, hvorav det \(i\)-te indikerer språket som snakkes av gjesten som sitter på posisjon \(i\) i den foreslåtte ordningen (hver gjest snakker nøyaktig ett språk). Funksjonen skal returnere ett enkelt heltall, klosshetsnivået til det foreslåtte sittearrangementet.

Kjør koden din på filene seating1.txt og seating2.txt.

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester awkwardness_level... ", end="")
assert(awkwardness_level("seating1.txt") == 3)
assert(awkwardness_level("seating2.txt") == 3)
print("OK")

  • Bruk et oppslagsverk

Nivå A
Marsboer-DNA

Denne oppgaven er tatt fra https://open.kattis.com/problems/martiandna.

Menneskelig DNA kan representeres som en lang streng over et alfabet av størrelse fire (A, C, G, T), der hvert symbol representerer en distinkt nukleobase (henholdsvis; adenin, cytosin, guanin og tymin).

For marsboere er ting imidlertid litt annerledes; forskning utført på den siste marsboeren fanget av NASA har vist at mars-DNA består av \(K\) forskjellige nukleobaser! Mars-DNA kan dermed representeres som en streng over et alfabet av størrelse \(K\).

En viss forskningsgruppe som er interessert i å utnytte marsboer-DNA (til videre forskning) har bedt om å få en enkelt kontinuerlig del av en mars-DNA-streng. For \(R\) \((R < K)\) av nukleobasene har de spesifisert en minimumsmengde av hvor mange de trenger av den aktuelle nukleobasen å være tilstede i prøven deres.

Vi er interessert i å finne den korteste delstrengen av DNA som tilfredsstiller deres krav.

I filen martian_dna.py skriv en funksjon martian_dna_subsequence(dna) som tar in en filsti dna som input parameter. Den første linjen i filen dna inneholder tre heltall \(N\), \(K\) og \(R\) \((R < K < N)\), som angir henholdsvis den totale lengden på mars-DNA, alfabetets størrelse og antall nukleobaser som forskerne har et minimumskrav på. Den andre linjen inneholder \(N\) mellomromseparerte heltall: den komplette DNA-strengen. Den \(i\)-te av disse heltallene, indikerer hvilken nukleobase som er i den \(i\)-te posisjonen av DNA-strengen. Hver nukleobase vil forekomme minst én gang i DNA-strengen. Hver av de følgende \(R\) linjene inneholder to heltall \(B\) og \(Q\) \((B < K, Q < N)\) som representerer henholdsvis en nukleobase og minimum ønsket antall forekomster av den neukleobasen. Ingen nukleobase vil bli oppført mer enn én gang i disse \(R\) linjene.

Funksjonen skal returnere et enkelt heltall, lengden på den korteste kontinuerlige delstrengen av DNA som tilfredsstiller forskernes krav. Hvis ingen slik delstreng eksisterer, skal programmet returnere “impossible”.

Kjør koden din på filene martian1.txt, martian2.txt og martian3.txt.

Test koden din ved å legge til disse linjene nederst i filen:

print("Tester martian_dna_subsequence... ", end="")
assert(martian_dna_subsequence("martian1.txt") == 2)
assert(martian_dna_subsequence("martian2.txt") == 7)
assert(martian_dna_subsequence("martian3.txt") == "impossible")
print("OK")