Uke 6

Innlevering, Krav for å bestå og viktigheten av bonusoppgaver

Du kan levere så mange ganger du vil. Siste innlevering telles.
For å få bestått, må du få 100% riktig av CodeGrade på alle oppgaver som ikke er merket som bonus.
Oppgavene som er merket som bonus er frivillige. Imidlertid er det verdt å bruke tid på disse oppgavene da de kan gi deg verdifull erfaring med å løse liknende problemer som kan dukke opp på eksamen.

Oppgave 1a

I filen uke_06_oppg_1.py skriv en destruktiv funksjon remove_ones(a) som har en liste a som parameter. Funksjonen skal mutere listen slik at alle forekomster av tallet 1 blir borte.

print("Tester remove_ones... ", end="")
# Test 1
a = [1, 2, 3, 4]
remove_ones(a)
assert(a == [2, 3, 4])

# Test 2
a = [1, 1, 2, 3]
remove_ones(a)
assert(a == [2, 3])

# Test 3
a = [1, 1, 3, 1, 2, 4, 1, 1, 1]
remove_ones(a)
assert(a == [3, 2, 4])

# Test 4
a = [1, 1]
remove_ones(a)
assert(a == [])
print("OK")

Så lenge det finnes en 1’er i listen: fjern en 1’er fra listen.

Oppgave 1b

I filen uke_06_oppg_1.py skriv en ikke-destruktiv funksjon every_fourth(a) med en liste a som input. Funksjonen skal returnere en ny liste som inneholder hvert fjerde element fra a (begynn med det første elementet, altså elementet på indeks 0).

print("Tester every_fourth... ", end="")
# Test 1
a = ["a", "b", "c", "d", "e"]
assert(["a", "e"] == every_fourth(a))
assert(["a", "b", "c", "d", "e"] == a)

# Test 2
a = list(range(10))
assert([0, 4, 8] == every_fourth(a))
assert(list(range(10)) == a)

# Test 3
a = list(range(20, 1000))
assert(list(range(20, 1000, 4)) == every_fourth(a))
assert(list(range(20, 1000)) == a)
print("OK")

Opprett en resultatliste (som i utgangspunktet er tom)
Gå gjennom listen a med en indeksert løkke. Dersom indeks er delelig med 4, legg til elementet i resultatlisten.

Oppgave 1c

I filen uke_06_oppg_1.py skriv en destruktiv funksjon double_values(a) som tar en liste a med tall og muterer listen slik at alle tallene i listen dobles.

print("Tester double_values... ", end="")
a = [1, 2, 3]
double_values(a)
assert([2, 4, 6] == a)
print("OK")

Gå gjennom listen a med en indeksert løkke. Inne i løkken muterer vi listen i den posisjonen indeks refererer til.

Oppgave 1d

I filen uke_06_oppg_1.py skriv en ikke-destruktiv funksjon unique_values(a) tar en liste a og returnerer en ny liste lik som a men hvor alle gjentagende forekomster av verdier er fjernet. Det vil si, de unike verdiene skal ligge i samme rekkefølge som de først opprådte i a.

print("Tester unique_values... ", end="")
# Test 1
a = [1, 1, 2, 1, 3, 3, 3, 2]
assert([1, 2, 3] == unique_values(a))
assert([1, 1, 2, 1, 3, 3, 3, 2] == a)

# Test 2
a = ["a", "b", "c"]
assert(["a", "b", "c"] == unique_values(a))
assert(["a", "b", "c"] == a)
print("OK")

Opprett en resultatliste (som i utgangspunktet er tom)
Gå gjennom listen a med en løkke, og legg elementet fra a til i resultatlisten dersom det ikke finnes der fra før.

Oppgave 1e

I filen uke_06_oppg_1.py skriv en destruktiv funksjon add_list(a, b) som tar to like lange lister av tall a og b som input. Funksjonen skal mutere listen a slik at verdiene i listen a økes med verdiene i listen b på tilsvarende posisjoner.

print("Tester add_list... ", end="")
a = [1, 2, 3]
b = [4, 2, -3]
add_list(a, b)
assert([5, 4, 0] == a)
assert([4, 2, -3] == b)
print("OK")

Gå gjennom listen a med en indeksert løkke
For hver indeks, regn ut summen av verdiene fra a og b med den gitte indeksen.

Oppgave 2

En DNA-sekvens (f.eks ATAGCAGT) er satt sammen av fire forskjellige baser: A, T, G og C. Et nyttig konsept som ofte brukes i sammenheng med DNA-sekvenser er “k-mers”.

K-mer er delstrenger av lengde k som finnes innenfor en DNA-sekvens. For eksempel, hvis \(k = 5\), så inneholder DNA-sekvensen TCGATCACA følgende k-mere : TCGAT, CGATC, GATCA, ATCAC og TCACA. En sekvens med lengde \(L\) vil ha \(L-k+1\) k-mere.

I filen uke_06_oppg_2.py lag en funksion som heter kmers(seq,k) som returnerer en liste av alle k-mers i en DNA-sekvens seq i den samme rekkefølgen de har i sekvensen.

print("Tester kmers... ", end="")
k3=['ACT', 'CTG', 'TGC', 'GCT', 'CTA', 'TAT']
assert k3 == kmers("ACTGCTAT",3)

k5 = ['ACTAG', 'CTAGA', 'TAGAT', 'AGATA', 'GATAC', 'ATACT', 'TACTA']
assert k5 == kmers("ACTAGATACTA",5)

k12 = ['ATGCAGCTGTGT']
assert k12 == kmers("ATGCAGCTGTGT",12)

k0 = []
assert k0 == kmers("ATGCAGCTGTGT",13)
print("OK")

Oppgave 3

I filen uke_06_oppg_3.py skriv funksjonen dot_product(a, b) som regner ut prikk-produkuktet av to like lange lister a og b (a[0] * b[0] + a[1] * b[1] + …)

print("Tester dot_product... ", end="")

assert(32 == dot_product([1, 2, 3], [4, 5, 6]))
assert(12 == dot_product([0, 6, 1], [400, 1, 6]))
assert(657 == dot_product([43, 6, 1], [15, 1, 6]))

print("OK")

Oppgave 4

I filen uke_06_oppg_4.py, lag en funksjon som heter render_histogram(). Funksjonen skal ta inn en liste med positive heltall og returnere et histogram ved å bruke stjernestapler for å representere verdien til hvert element i listen. For eksempel, print(render_histogram([5, 4, 2, 7, 0, 3, 10])) skal gi følgende output.

      *
      *
      *
   *  *
   *  *
*  *  *
** *  *
** * **
**** **
**** **

Test om funksjonen din fungerer som den skal ved å inkludere følgende følgende kode.

pattern1 = """\  
   *  
   *  
*  *  
** *  
** *
****
****
"""
assert pattern1 == render_histogram([5, 4, 2, 7])

pattern2 = """\
 *   
 *  *
**  *
** **
"""
assert pattern2 == render_histogram([2, 4, 0, 1, 3])

Bonus 1

Lag en ikke-destruktiv funksjon sort_by_sign(a) som tar inn en liste a med helltall og returnerer en ny liste som består av

først, alle de negative tallene i samme rekkefølgen de opptrådte i a;
deretter, alle 0 -verdiene; og
til slutt, alle de positive tallene i samme rekkefølge de opptrådte i a.

For eksempel, hvis a er [3, -4, 1, 0, -1, 0, -2], skal funksjonen returnere listen [-4, -1, -2, 0, 0, 3, 1].

print("Tester sort_by_sign... ", end="")
# Test 1
a = [3, -4, 1, 0, -1, 0, -2]
assert([-4, -1, -2, 0, 0, 3, 1] == sort_by_sign(a))

# Test 2
a = [10, -10, -2, 0, 0, 30, 10]
assert([-10, -2, 0, 0, 10, 30, 10] ==  sort_by_sign(a))

# Test 3
a = [100, -10, -20, 1000, -1000, 10]
assert([-10, -20, -1000, 100, 1000, 10] == sort_by_sign(a))
print("OK")

Bonus 2

Lag en funksjon read_and_sort uten parametre som leser ett og ett heltall fra brukeren og lagrer dem i en liste. Funksjonen skal fortsette å lese verdier helt til brukeren skriver inn 0. Programmet skal ikke skrive ut noe så lenge det leser input.

Når programmet har lest 0, er lesefasen ferdig. Programmet skal nå skrive ut alle verdiene som er lest inn (unntatt 0) i rekkefølge fra minst til størst. For eksempel:

Input (skrevet av bruker)

Output (utskrift)

I denne oppgaven er det viktig at du lar det være et kall til read_and_sort() på slutten av filen, slik at CodeGrade klarer å teste programmet ditt.

Bonus 3

En streng sub er en ikke-kontinuerlig substreng av strengen s dersom alle tegnene i sub opptrer i samme rekkefølge i s. For eksempel er "foo" en ikke-kontinuerlig substreng av "good for nothing":

good for nothing
     ||   |
     fo   o

Skriv en funksjon non_contiguous_substrings(s) som tar inn en streng s og returnerer en liste med alle ikke-kontinurelige substrenger av s.

print("Tester non_contiguous_substrings... ", end="")
# Test 1
# Merk: rekkefølgen på elementene i listen betyr ingenting,
# siden begge listene sorteres før de sammenlignes
assert(sorted([
  "", # Den tomme strengen er alltid en substreng
  "a", "b", "c", "d",
  "ab", "ac", "ad", "bc", "bd", "cd",
  "abc", "abd", "acd", "bcd",
  "abcd",
]) == sorted(non_contiguous_substrings("abcd")))

# Test 2
assert(sorted([
  "",
  "f", "o",  # Merk: "o" opptrer bare én gang
  "fo", "oo",
  "foo",
]) == sorted(non_contiguous_substrings("foo")))
print("OK")

For å se løsningen på denne oppgaven, hjelper det å observere følgende:

Dersom vi på magisk vis vet løsningen for problemet når strengen vi jobber med er ett symbol kortere, kan vi utnytte den: alle substrenger for den ett symbol kortere strengen, er også substrenger for den lengre strengen. De eneste substrengene som da “mangler” er de som slutter på det siste tegnet i strengen.

Begynn med å opprette en resultatliste som inneholder kun den tomme strengen (den tomme strengen er alltid en substreng).
Gå gjennom tegnene i s med en løkke; én iterasjon av løkken er ansvarlig for å legge til alle ikke-kontinuerlige substrenger som slutter på dette tegnet.
Hvilke valg finnes det for begynnelsen på de substrengene vi nå skal legge til? Det er nettopp de strengene som finnes i resultatlisten fra før.
Å utvide en liste samtidig som man løkker over listen krever at man holder tungen beint i munnen. Det kan være lettere å opprette en hjelpeliste substrings_ending_at_c hvor man legger til bare dem som slutter på gitte tegn, og så utvide resultatlisten med denne listen når den er ferdig utregnet.
Benytt funksjonen unique_values du skrev i oppgave 1 for å fjerne duplikater.

Hvor mange ikke-kontinuerlige substrenger finnes det for strengen "good for nothing"?