Lab7

Forberedelser
Innlevering og automatisk retting
Oppgave 1

I denne oppgaven skal vi tegne et rutenett med farger. Funksjonen draw_grid har følgende parametre:

from uib_inf100_graphics import *

def draw_grid(canvas, x1, y1, x2, y2, color_grid):
    """ Tegner et rutenett med farger. Rutenettet er avgrenset av (x1, y1)
    i hjørnet til venstre oppe, og av (x2, y2) til høyre nede. Listen
    color_grid er en 2D-liste med strenger som representerer farger."""
    ...

def redraw_all(app, canvas):
    # Et 3x3 rutenett med innebygde farger
    draw_grid(canvas, 50, 20, 130, 100, [
        ["red", "green", "blue"],
        ["yellow", "pink", "cyan"],
        ["black", "gray", "orange"],
    ])

    # Et sjakkbrett
    draw_grid(canvas, 150, 20, 350, 100, [
        ["white", "black"] * 4,
        ["black", "white"] * 4,
    ] * 4)

    # En 2D-liste med kun én rad
    draw_grid(canvas, 50, 120, 350, 180, [
        ['#00c', '#01c', '#02c', '#03c', '#04c', '#05c', '#06c', '#07c',
         '#08c', '#09c', '#0ac', '#0bc', '#0cc', '#0dc', '#0ec', '#0fc']
    ])

run_app(width=400, height=200)

Illustrasjon av hva programmet over skal tegne

  • Begynn med å definere to variabler rows og cols som representere antall rader og antall kolonner i rutenettet. Antall rader er lengden på den ytre listen (len(color_grid)) mens antall kolonner er lengden på den første indre listen (len(color_grid[0])). Vi antar at det er like mange kolonner i hver rad, slik at vi ikke trenger å sjekke alle.

  • Definer to variabler cell_width og cell_height som representerer henholdsvis bredden og høyden på en celle i rutenettet. Bredden til en celle vil være differansen mellom x-koordinatene delt på antall kolonner, mens høyden til en celle vil være differansen mellom y-koordinatene delt på antall rader.

  • La oss gå gjennom hver eneste mulige kombinasjon av en rad og en kolonne. La row og col være iterandene i to nøstede for-løkker; la row gå fra 0 opp til (ikke inkludert) rows, og la col gå fra 0 og opp til (men ikke inkludert) cols.

  • Inne i den nøstede løkken skal vi tegne cellen i rad row og kolonne col. For å tegne cellen, må vi regne ut koordinatene (cell_x1, cell_y1) som er punktet til venstre øverst i cellen, og punktet (cell_x2, cell_y2) som er punktet til høyre nederst.

    • For å regne ut cell_x1, begynner vi på koordinatet x1 og flytter oss cell_width piksler til høyre col ganger.
    • For å regne ut cell_y1, begynner vi på koordinatet y1 og flytter oss cell_height piksler nedover row ganger.
    • For å regne ut cell_x2, begynn på cell_x1 og flytt deg cell_width piksler til høyre.
    • For å regne ut cell_y2, begynn på cell_y1 og flytt deg cell_height piksler nedover.

  • Etter at du har regnet ut koordinatene til cellen, kall create_rectangle på canvas. Etter de posisjonelle argumentene vi regnet ut over, bruk fill=color_grid[row][col] for å sette fargen.

Oppgave 2

Denne oppgaven består av fire deler. Funksjonene vi skriver i denne oppgaven har alle en 2D-liste som input og skal fjerne en rad destruktivt og ikke-destruktivt, og fjerne en kolonne destruktivt og ikke-destruktivt.

Del A

I filen uke_07_oppg_2.py skriv en destruktiv funksjon remove_row(grid, row) som har en 2D-liste grid og et radnummer row som parametre. Funksjonen skal mutere grid slik at rad row blir fjernet.

print("Tester remove_row... ", end="")
# Test 1
grid = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33],
    ]
remove_row(grid, 0)
assert([
        [21, 22, 23],
        [31, 32, 33],
    ] == grid)

# Test 2
grid2 = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ]
remove_row(grid2, 1)
assert([
        [11, 12, 13],
        [31, 32, 33],
    ] == grid2)
print("OK")

Tenk på grid som en 1-dimensjonell liste og bruk metoder fra kursnotatere om vanlige lister for å destruktivt fjerne raden.

Del B

I filen uke_07_oppg_2.py skriv en ikke-destruktiv funksjon row_removed(grid, row) som har en 2D-liste grid og et radnummer row som parametre. Funksjonen skal returnere en ny liste med alle radene i grid bortsett fra raden row.

print("Tester row_removed... ", end="")
grid = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ]

grid_without_row1 = row_removed(grid, 1)
assert([
        [11, 12, 13],
        [31, 32, 33],
    ] == grid_without_row1)
    
# Sjekk at vi ikke har mutert grid
assert([
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ] == grid)

# Sjekk at grid_without_row1 ikke inneholder aliaser til grid
grid_without_row1[0][1] = 1212 # Muterer grid_without_row1
assert([
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ] == grid)
print("OK")

I denne oppgaven kan det være lurt å bryte aliaset ved å lage en kopi, og deretter benytte funksjonen fra deloppgave A på kopien. Husk å bruke en dyp kopi (se kursnotater om grunne og dype kopier)

Del C

I filen uke_07_oppg_2.py skriv en destruktiv funksjon remove_col(grid, col) som har en 2D-liste grid og et kolonnenummer col som parametre. Funksjonen skal mutere grid slik at kolonnen col blir fjernet.

print("Tester remove_col... ", end="")
# Test 1
grid1 = [
        [16, 8, 3],
        [2, 10, 15],
    ]
remove_col(grid1, 0)
assert([
        [8, 3],
        [10, 15],
    ] == grid1)

# Test 2
grid2 = [
        [3, 0, 9],
        [4, 5, 3],
        [6, 8, 1],
    ]
remove_col(grid2, 1)
assert ([
        [3, 9],
        [4, 3],
        [6, 1],
    ] == grid2)
print("OK")

Benytt en løkke som går gjennom hver rad, og der muterer hver av radene (de innerste listene i 2D-listen). For selve mutasjonen av en rad, bruk metoder fra kursnotatere om vanlige lister for å destruktivt fjerne elementer.

Del D

I filen uke_07_oppg_2.py skriv en ikke-destruktiv funksjon col_removed(grid, col) som har en 2D-liste grid og et kolonnenummer col som parametre. Funksjonen skal returnere en ny 2D-liste med alle kolonnene i grid bortsett fra kolonne col.

print("Tester col_removed... ", end="")
# Test 1
grid = [
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33]
    ]
assert ([
        [12, 13],
        [22, 23],
        [32, 33],
    ] == col_removed(grid, 0))
# Sjekk at grid ikke ble mutert
assert([
        [11, 12, 13],
        [21, 22, 23],
        [31, 32, 33],
    ] == grid)

# Test 2
assert ([
        [11, 12],
        [21, 22],
        [31, 32],
    ]== col_removed(grid, 2))
print("OK")

  • Begynn med å opprette en tom liste result = [], som vi skal mutere for å opprette resultatet vårt. Merk at selv om vi muterer result, vil ikke metoden være destruktiv, siden result er en liste vi selv har opprettet inne i funksjonen.

  • For hver rad i grid, bruk metoder fra kursnotatere om vanlige lister for å ikke-destruktivt opprette en ny liste som ikke inkluderer kolonnen som skal fjernes. Legg den nye raden inn i result-listen.

Oppgave 3

I filen uke_07_oppg_3.py skriv funksjonen all_rows_and_cols_equal_sum(grid) som har en en 2D-liste med tall grid som parameter. Funksjonen skal returnere True dersom listen har samme sum langs alle rader, og samme sum langs alle kolonner, og returnerer False hvis ikke.

print("Tester all_rows_and_cols_equal_sum... ", end="")
# Test 1
assert(all_rows_and_cols_equal_sum([
        [16, 8, 3],     # begge rader summerer til 27
        [2, 10, 15],    # alle kolonner summerer til 18
    ]))
    
# Test 2
assert(not all_rows_and_cols_equal_sum([
        [3, 0, 9],   # rad0 summerer til 12, col0 summerer til 13
        [4, 5, 3],   # rad1 summerer til 12, col1 summerer til 13
        [6, 8, 1],   # rad2 summerer til 15, col2 summerer til 13
    ]))

# Test 3
assert(not all_rows_and_cols_equal_sum([
        [3, 4, 6],   # rad0 summerer til 13, col0 summerer til 12
        [0, 5, 8],   # rad1 summerer til 13, col1 summerer til 12
        [9, 3, 1],   # rad2 summerer til 13, col2 summerer til 15
    ]))

# Test 3
assert (all_rows_and_cols_equal_sum([
        [1, 2, 3, 4], # alle rader og kolonner summerer til 10
        [2, 3, 4, 1],
        [3, 4, 1, 2],
        [4, 1, 2, 3],
    ]))
print("OK")

Del opp problemet i mindre biter:

  • Skriv en hjelpemetode som finner summen av tallene i en gitt kolonne

  • Skriv en hjelpemetode som sjekker om en kolonne har samme sum som sin nabokolonne

  • Skriv en hjelpemetode som sjekker at alle kolonnene har samme sum som sin nabokolonne

  • Tilsvarende for rader

  • Bruk hjelpemetodene for løse problemet.

Oppgave 4

I filen uke_07_oppg_4.py skriv funksjonen find_words_in_character_grid(char_grid, words) som tar inn en 2D-liste med bokstaver char_grid og en ordliste words. Funksjonene skal søke i 2D-listen både fra venstre mot høyre og fra toppen og ned, og returnere en liste over alle ord fra ordlisten som finnes i char_grid.

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

glossary = ["dikt", "hus", "lese", "by", "elev",
            "smart", "helt", "mål", "yr", "lære"]
char_grid= [
        ['d','s','h','s','s','y'],
        ['l','æ','r','e','s','å'],
        ['k','a','l','a','m','e'],
        ['t','h','e','r','a','q'],
        ['e','t','s','t','r','z'],
        ['e','t','e','r','t','p'],
        ['e','m','å','l','v','w'],
    ]
found_words = find_words_in_character_grid(char_grid, glossary)
assert(sorted(['lese', 'smart', 'mål', 'lære']) == sorted(found_words))
print("OK")

  • Opprett en hjelpefunksjon som sjekker om et gitt ord finnes i char_grid vertikalt og begynner på en bestemt posisjon (row, col).

    • Begynn med å sjekke om det gitte ordet er for langt, og hvis det er det, returner False. Et ord er for langt dersom høyden på rutenettet (antall rader) er mindre enn startradens indeks (row) + ordets lengde.
    • Benytt løkke over ordet som sjekkes, og sjekk inni løkken at tegnet på denne posisjonen i ordet er den samme som posisjonen i rutenettet. Øk indeks til raden i rutenettet med én for hver iterasjon.
    • Dersom du finner en forskjell, returner False
    • Dersom du ikke fant en forskjell etter at du er ferdig med hele løkken, returner True

  • Skriv en funksjon tilsvarende den i kulepunktet over, men som sjekker horisontalt.

  • Opprett en funksjon som sjekker om et gitt ord finnes i char_grid: bruk en nøstet for-løkke for å gå gjennom alle mulige start-posisjoner, og bruk deretter hjelpemetodene fra forrige kulepunkter.

  • For hvert ord: sjekk om ordet finnes i char_grid med bruk av hjelpemetoden i forrige kulepunkt.

Oppgave 5

I filen uke_07_oppg_5.py, løs oppgaven EpigDanceOff på Kattis.

  • Merk at det er tilstrekkelig å telle antall kolonner som kun inneholder _-symboler, og skrive ut dette + 1.
  • For å lese første linje:
first_line = input()
rows, cols = first_line.split() # Deler opp på mellomrom
rows = int(rows) # Konverterer fra str til int
cols = int(cols)

  • Opprett en liste som skal inneholde “bildet” gitt som input. Bruk input() en gang for hver rad som skal leses (vi vet på forhånd hvor mange rader som kommer, ref. forrige kulepunkt). Legg den resulterende strengen fra input() -kallet inn i listen.

  • Opprett en hjelpefunksjon som returnerer True dersom en gitt kolonne kun inneholder _

  • Tell opp med en løkke hvor mange kolonner som kun inneholder _

  • Skriv ut svaret (husk + 1)

Oppgave 6

I filen uke_07_oppg_6.py, løs oppgaven Flow Shop på Kattis.

Oppgave 7

I filen uke_07_oppg_7.py, løs oppgaven Flag Quiz på Kattis.

  • Opprett en hjelpefunksjon som kan regne ut avstanden mellom to svar-alternativer. Funksjonene kan dele et svar inn i del-svar med .split(", ") og telle hvor mange ulike del-svar det er i de to alternativene.

  • Opprett en hjelpefunksjon som regner ut incongruousity for et gitt svaralternativ. Funksjonen finner maksimum-verdien for avstanden fra det gitte alternativet til et av de andre alternativene.

  • Regn ut incongruousity for alle alternativene, og finn minste verdi

  • Gå gjennom svaralternativene på nytt, og skriv ut dem som har minste incongruousity.

Oppgave 8

I filen uke_07_oppg_8.py, løs oppgaven Rings på Kattis.

Denne oppgaven er en utfordring! Noen hint:

  • Opprett en 2D -liste som skal holde på ring-dypdene som int. La verdiene i utgangspunktet være et alt for stort tall (f. eks 1000)
  • Sett alle 0-verdiene i 2D-listen basert på hvor det er . i input
  • Sett alle 1’er-verdiene langs kanten (der input er T langs kanten)
  • Utfør følgende så lenge som nødvendig:
    • Gå gjennom alle koordinater som ikke er ytterst langs kanten med en nøstet for-løkke
    • Dersom en rute har en nabo-rute som har en verdi lavere enn sin egen verdi minus 1, oppdater verdien i ruten slik at den får verdien til naboruten + 1.
    • Hvis du gikk igjennom alle koordinatene uten å endre noen ting, er du ferdig. Det kan være greit å ha en variabel did_make_change som oppdateres inne i den nøstede løkken, og som sjekkes etter at de nøstede løkkene er ferdige.
  • Det gjenstår å skrive ut svaret. Her kan det være nyttig med en hjelpemetode get_cell_string(cellwidth, num) som oppretter en liten streng basert på innholdet i en gitt celle. For eksempel, get_cell_string(3, 9) kan returnere ..9 og get_cell_string(3, 0) kan returnere ...