Lab6

Filtrer ordliste

I en fil wordlist.py, lag en funksjon filter_wordlist som har parametre

• path, en streng som angir et filnavn, og
• search_string, en streng vi søker etter.

Funksjonen skal returnere en liste med alle ord fra filen som inneholder search_string. Anta at filen inneholder ett ord på hver linje, og at den er lagret i UTF-8.

For eksempel, hvis filen angitt av path inneholder teksten

data
datasett
database
baser
syrer
bås

og search_string har verdien 'base': da skal funksjonene returnere en liste ['database', 'baser'] fordi dette er ordene i filen som inneholder «base».

print('Tester filter_wordlist... ', end='')

# Test 1
expected = ['database', 'baser']
actual = filter_wordlist('sample.txt', 'base')
assert expected == actual

# Test 2
expected = [
  'småstad', 'småstaden', 'småstas', 'småstasen', 'småstat', 'småstaten',
  'småstatene', 'småstater',
]
actual = filter_wordlist('nsf2022.txt', 'småsta')
assert expected == actual

# Test 3
expected = [
  'stjerneskudd', 'stjerneskudda', 'stjerneskuddene', 'stjerneskuddet', 
]
actual = filter_wordlist('nsf2022.txt', 'stjerneskudd')
assert expected == actual

print('OK')

Rettskriving

Intro for mengder og hastighet

Les gjerne om mengder i kursnotatene før du begynner. Forklaringen under forklarer det viktigste for akkurat denne oppgaven.

Før vi begynner på oppgaven skal vi forklare litt mer om mengder enn det vi har sett på i forelesning. En mengde er en samling av elementer der alle elementene er unike. Dette betyr at det ikke kan være to like elementer i en mengde. I motsetning til en liste har ikke en mengde egentlig noen orden, så det er ikke mulig å hente ut elementer fra en mengde ved å bruke indeksering. Dette er en konsekvens av måten mengder lagres i minne, som vi ikke skal gå inn på her.

Likevel, grunnet denne måten å lagre elementer på, er det mye raskere å sjekke om et element finnes i en mengde enn i en liste (for store datasett). Se for deg at du har en liste med alle studentene på UiB, og vil sjekke om en person er student. Bruker du en liste og sjekker if maybe_student in students, vil programmet gå gjennom og utføre en sammenligning for hvert element i listen students. Se koden under for hva dette betyr:

students = ["Bob", "Charlie", "David", "Eve", "Alice"]
maybe_student = "Alice"

# Dette:
if maybe_student in students:
    print(f"{maybe_student} is a student")

# Er omtrent ekvivalent med dette (som er treigt):
for student in students:
    if student == maybe_student:
        print(f"{maybe_student} is a student")

Hvis listen er lang (la oss si over 1000 elementer), vil det ta lang tid å finne ut om en person er student. Dersom vi gjør listen om til en mengde i stedet, vil det gå mye raskere:

students = ["Bob", "Charlie", "David", "Eve", "Alice"]
students = set(students)
maybe_student = "Alice"
if maybe_student in students:
    print(f"{maybe_student} is a student")

Forskjellen merker vi ikke ved små datamengder som dette på grunn av tiden det tar å gjøre listen om til en mengde, men med flere tusen verdier i datasettet vi ønsker å søke i, vil vi merke en stor forskjell.

Oppgave

Del A - Rettskriving

I filen spellcheck.py skal du først lage to funksjoner spelling_errors_slow og spelling_errors_fast. Disse funksjonene vil gjøre akkurat det samme, men den ene tar i bruk bare lister og den andre bruker også mengder. Du kan gjerne skrive den treige versjonen først også kopiere og lime inn koden og gjøre den om til den raske versjonen.

Funksjonene tar inn to filstier, en for en tekst og en for en ordbok. Teksten vil kun ha bokstaver, mellomrom og enkle linjeskifte, og ingen komma, punktum osv. Ordboken vil være en tekstfil med ett ord per linje.

Funksjonene skal lese inn filene og returnere hvor mange ord i teksten som ikke finnes i ordboken, altså hvor mange ord som sannsynligvis er skrevet feil. I den treige versjonen skal du lagre både ordene fra teksten og ordboken i 2 forskjellige lister, mens i den raske versjonen skal du lagre ordene fra teksten som en liste og ordboken som en mengde. I begge tilfeller itererer du over ordene i teksten og teller opp hvor mange av ordene som ikke finnes i ordboken.

print('Tester spelling_errors_*... ', end='')
assert 5 == spelling_errors_slow('tekst1.txt', 'nsf2022.txt')
assert 5 == spelling_errors_fast('tekst1.txt', 'nsf2022.txt')
print("OK")

Del B - Sjekk hastigheten

Skriv en funksjon speed_test som tar inn de samme filstiene som de forrige funksjonene. Funksjonen skal returnere forholdet av hvor mye treigere den treige versjonen er enn den raske. Dette er altså slow_time / fast_time. Dette kan du finne ut ved å bruke biblioteket time og funksjonen time.time() til å måle hvor lang tid hver av funksjonene tar å kjøre, og så sammenligne disse tidene. Her er starten på funksjonen:

import time

def speed_test(text_path, dict_file):
    start = time.time()
    spelling_errors_slow(text_path, dict_file)
    end = time.time()
    slow_time = end - start
    ... # Din kode her:
    # Gjør det samme for den raske versjonen og returner forholdet

print('Tester speed_test... ', end='')
assert speed_test('tekst2.txt', 'nsf2022.txt') > 3
print("OK")

Bibliotek

Les om oppslagsverk i kursnotatene før du begynner. Denne oppgaven gir deg anledning til å bli kjent med dem i praksis.

Vi skal lage noen små funksjoner for å håndtere et bibliotek med bøker. Vi skal lage en funksjon som legger til bøker i biblioteket, en funksjon som fjerner bøker fra biblioteket, og en funksjon som sjekker hvor mange bøker som totalt finnes i biblioteket. Vi skal gjøre alt dette i en fil library.py.

Del A: Legg til bøker

I library.py, skriv en destruktiv funksjon add_book som tar inn et oppslagsverk library og en streng book. Hvis boken allerde finnes i biblioteket, skal funksjonen øke antallet av boken med 1. Hvis boken ikke finnes i biblioteket, skal funksjonen legge til boken i biblioteket med antallet 1.

print('Tester add_book... ', end='')
my_library = {
    'The Little Prince': 4,
    'The Hobbit': 2,
    'Norwegian Wood': 1
}
add_book(my_library, 'The Hobbit')
add_book(my_library, 'Peter Pan')

assert 3 == my_library['The Hobbit'], (
    f"Forventet 3 kopier av 'The Hobbit' men fant {my_library['The Hobbit']}"
)
assert 'Peter Pan' in my_library, "'Peter Pan' mangler i biblioteket"
assert 1 == my_library['Peter Pan'], (
    f"Forventet 1 kopi av 'Peter Pan' men fant {my_library['Peter Pan']}"
)
print('OK')

Del B: Fjern bøker

I library.py, skriv en destruktiv funksjon remove_book som tar inn et oppslagsverk library og en streng book. Hvis boken ikke finnes i oppslagsverket skal funksjonen returnere og gjøre ingenting. Ellers (hvis boken finnes i biblioteket) skal funksjonen redusere antallet av boken med 1. Hvis antallet av boken blir 0, skal funksjonen fjerne boken fra biblioteket.

print('Tester remove_book... ', end='')
my_library = {
	'Black Beauty': 1,
	'The Train': 5,
	'Fireworks in Winter': 3
}
remove_book(my_library, 'The Train')
remove_book(my_library, 'The Train')
remove_book(my_library, 'Black Beauty')

assert 'The Train' in my_library, (
    "Forventet ikke at 'The Train' skulle forsvinne fra biblioteket"
)
assert 3 == my_library["The Train"], (
    f"Forventet 3 kopier av 'The Train' men fant {my_library['The Train']}"
)
assert 'Black Beauty' not in my_library, (
    "Forventet ikke at 'Black Beauty' fortsatt er i biblioteket"
)
# Sjekker at programmet ikke krasjer hvis vi prøver å fjerne en bok 
# som ikke finnes i biblioteket
remove_book(my_library, 'Black Beauty')
print('OK')

Del C: Totalt antall bøker

I library.py, skriv en funksjon total_books som tar inn et oppslagsverk library og returnerer den totale mengden av bøker i biblioteket.

print("Tester total_books... ", end="")
my_library = {
    "Apothecary Diaries Volume 1": 3,
    "Apothecary Diaries Volume 2": 200,
    "Apothecary Diaries Volume 3": 1,
    "Apothecary Diaries Volume 4": 0,
}

expected = 204
actual = total_books(my_library)
assert expected == actual, f"{expected=},  {actual=}"
my_library["Apothecary Diaries Volume 4"] += 10

expected = 214
actual = total_books(my_library)
assert expected == actual, f"{expected=},  {actual=}"

print("OK")

Personlig postkort

Du er en kreativ sjel som elsker å lage personlige og unike postkort til venner og familie ved å bruke bokstaver og bilder klippet ut fra aviser og ukeblader. For å lage et spesielt postkort til en venn, har du bestemt deg for å skrive en hilsen som bruker bokstaver og tegn fra favorittmagasinet deres. For å sikre at du har nok og at du ikke kaster bort tid på å klippe for mye, trenger du å lage en oversikt over nøyaktig hvor mange av hver bokstav og tegn du trenger.

I en fil postcard.py, skriv en funksjon symbol_count som tar inn et filnavn path og returnerer et oppslagsverk som teller hvor mange ganger hvert tegn forekommer i filen. Mellomrom og linjeskift (såkalt whitespace) skal ikke telles. Du kan anta at filen er lagret i UTF-8.

def remove_whitespace(s):
    return ''.join(s.split())

print('Tester count_letters... ', end='')
expected = {
    'K': 2, 'j': 1, 'æ': 1, 'r': 10, 'e': 15, 'v': 3, 'n': 10, ',': 2,
    'S': 2, 'a': 3, 't': 2, 'y': 3, '.': 2, '"': 2, 'F': 2, 'i': 3, ':': 1,
    'B': 1, 'o': 2, 'd': 2, 'J': 1, 'u': 1, "'": 1, 's': 4, 'E': 1, 'p': 1,
    '!': 1, 'l': 2, 'm': 3,
}
actual = symbol_count('postcard.txt')
assert 'æ' in actual, 'æ er ikke i resultatet, har du husket utf-8 encoding?'
assert expected == actual
print('OK')

Gallius' varer

Trollmannen Gallius har bestemt seg for å åpne en butikk i landsbyen sin. Han har samlet sammen en mengde varer, og har så laget en csv-fil med varene, prisen av å lage varen, antall solgte varer og hva han selger dem for. Siden du enda ikke har sluttet som hans lærling, har han bestemt seg for å gi deg i oppgave å finne ut hvor mye han har tjent på varene sine.

Når skal han lære deg magi, egentlig?

I en fil sales.py, skriv en funksjon total_income som tar inn en filsti path og returnerer total inntekt fra varene opplistet i filen. Anta at filen er kodet i UTF-8 og har følgende format:

name,production_cost,price,sold
Potion of Healing,10,50,100
Potion of Strength,20,100,50
Crystal Ball,50,500,10
Cloak,100,1000,5
Rose of Versailles,500,10000,2

print('Tester total_income... ', end='')
expected = (
    (50 - 10) * 100
    + (100 - 20) * 50
    + (500 - 50) * 10
    + (1000 - 100) * 5
    + (10000 - 500) * 2
)
actual = total_income('sales.csv')
assert expected == actual, f'{expected=}, {actual=}'
print('OK')

Genetisk overlapp

Du jobber som forsker ved et biologisk institutt som studerer genetisk mangfold blant ulike arter. Instituttet har samlet DNA-prøver fra et bredt spekter av organismer, fra mikrober til planter, insekter og større dyr, inkludert mennesker. Prøvene har blitt analysert og lagret i filer som inneholder DNA-sekvenser, som er korte biter av DNA som kan brukes til å identifisere en spesifikk egenskap eller markør i organismen.

Din oppgave er å utvikle en funksjon som kan sammenligne to slike filer for å finne ut hvor mye genetikk de har til felles. Dette vil gi innsikt i det genetiske slektskapet mellom de to organismene, og kan hjelpe forskere med å forstå evolusjonære forhold og artenes opprinnelse.

I en fil genetics.py, skriv en funksjon count_overlap som tar inn to filnavn path1 og path2 som begge viser til filer med genetisk data for hver sin organisme. Hver linje i filene inneholder en DNA-sekvens, og ingen sekvens forekommer mer enn én gang i samme fil. Funksjonen count_overlap skal returnere antall sekvenser som er inkludert i begge datasettene. Husk at filene kan ha newline på slutten, og denne telles ikke som en DNA-sekvens.

Et utdrag av filene path1 eller path2 kan se for eksempel slik ut:

CGAAGAGTGTATGACTAGGC
TATTAGGTGCATGTCTCCTA
CTTTCGCCATTTATTTAAAA
GAGGGGTTAGAGTGCCTAGT

print('Tester count_overlap... ', end='')
# Tester funksjonalitet:
# Se gjerne på sample filene direkte, det er enkelt å se hvor mange sekvenser som er i begge filene
expected = 2
actual = count_overlap('sample1.txt', 'sample2.txt')
assert expected == actual, 'sample\'ene har ' + ('mer' if actual > expected else 'mindre') + ' felles enn forventet'

# Tester hastighet (testen tar veldig lang tid ved feil løsning):
expected = 100001 # Det er antatt at du fjerner newline fra slutten av filen, ellers er svaret 100002
actual = count_overlap('id1.txt', 'id2.txt')
assert expected == actual, 'id\'ene har ' + ('mer' if actual > expected else 'mindre') + ' felles enn forventet'
print("OK")

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")

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")

Kraftige jordskjelv

Denne oppgaven består av tre deler. Skriv funksjoner til alle deloppgaver i én felles fil, high_impact.py.

Eksempelet under er en forkortet og forenklet oversikt over registrerte jordskjelv i CSV format hentet fra CORGIS.

id;location;impact;time
nc72666881;California;1.43;2016-07-27 00:19:43
us20006i0y;Burma;4.9;2016-07-27 00:20:28
nc72666891;California;0.06;2016-07-27 00:31:37

I dennne oppgaven skal vi skrive et program som leser inn en CSV-fil med formatet over, og produserer en ny fil som inneholder alle de rekkene i den første filen hvor impact er større enn en gitt verdi.

Det finnes biblioteker som gjør håndtering av CSV-filer enklere, og det skal vi se mer på senere i kurset. I denne oppgaven skal vi derimot ikke importere biblioteker for CSV-håndtering, men kun bruke standard streng-metoder og kode vi har skrevet selv.

Del A

Skriv en funksjon get_impact(line) som får én enkelt linje (en streng) som input, og som returnerer impact-kolonnen i den linjen som et flyttall. Dersom det er noe feil med input som gjør at det ikke er mulig å se hvilken styrke jordskjelvet har, skal funksjonen returnere None, men ikke krasje.

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

print("Tester get_impact... ", end="")
assert 1.43 == get_impact("nc72666881;California;1.43;2016-07-27 00:19:43")
assert 4.9 == get_impact("us20006i0y;Burma;4.9;2016-07-27 00:20:28")
assert None is get_impact("us20006i0y;Burma;not_a_number;2016-07-27 00:20:28")
print("OK")

Del B

Skriv en funksjon filter_earthquakes(earthquake_csv_string, threshold) som tar inn en streng earthquake_csv_string med CSV-data på formatet vist over, samt et flyttall threshold. Funksjonen skal returnere en streng på samme format, men hvor linjer med impact strengt lavere enn threshold -verdien og linjer hvor det ikke er gyldig impact-verdi ikke er inkludert.

Test koden din ved å legge til følgende linjer nederst i filen:

print("Tester filter_earthquakes... ", end="")
input_string = """\
id;location;impact;time
nc72666881;California;1.43;2016-07-27 00:19:43
us20006i0y;Burma;4.9;2016-07-27 00:20:28
nc72666891;California;0.06;2016-07-27 00:31:37
nc72666892;California;not_a_number;2016-08-23 03:21:18
"""
# Test 1
expected_value = """\
id;location;impact;time
nc72666881;California;1.43;2016-07-27 00:19:43
us20006i0y;Burma;4.9;2016-07-27 00:20:28
"""
actual_value = filter_earthquakes(input_string, 1.1)
assert expected_value.strip() == actual_value.strip()

# Test 2
expected_value = """\
id;location;impact;time
us20006i0y;Burma;4.9;2016-07-27 00:20:28
""" 
actual_value = filter_earthquakes(input_string, 3.0)
assert expected_value.strip() == actual_value.strip()

# Test 3
expected_value = """\
id;location;impact;time
"""
actual_value = filter_earthquakes(input_string, 5.0)
assert expected_value.strip() == actual_value.strip()
print("OK")

Del C

Skriv en funksjon filter_earthquakes_file(source_filename, target_filename, threshold) som tar inn navnet på to filer, samt en grenseverdi. Funksjonen skal gjøre det samme som i forrige deloppgave, men leser inn data fra source_filename, og skriver ut data til target_filename.

For å teste funksjonen, last ned earthquakes_simple.csv og legg den i mappen hvor du kjører programmet fra. Legg deretter til koden under nederst i filen:

print('Tester filter_earthquakes_file... ', end='')

def read_file(path):
    with open(path, 'rt', encoding='utf-8') as f:
        return f.read()

filter_earthquakes_file('earthquakes_simple.csv',
                        'earthquakes_above_7.csv', 7.0)
expected_value = '''\
id;location;impact;time
us100068jg;Northern Mariana Islands;7.7;2016-07-29 17:18:26
us10006d5h;New Caledonia;7.2;2016-08-11 21:26:35
us10006exl;South Georgia Island region;7.4;2016-08-19 03:32:22
'''
actual_value = read_file('earthquakes_above_7.csv')
assert expected_value.strip() == actual_value.strip()
print('OK')

# Manuell test: Finn earthquakes_above_7.csv, åpne og se at innholdet stemmer