Lab7

Introduksjon

I denne oppgaven skal vi lære hvordan vi genererer en QR-kode! Når vi er helt ferdige skal programmet vårt fungere som følger:

• Input: en nettadresse, for eksempel strengen 'https://inf100.ii.uib.no'
• Resultat: en QR-kode vises på skjermen. Om vi scanner QR-koden med mobilen kommer vi til nettadressen oppgitt som input.

Før du vi begynner, anbefaler vi sterkt at du ser igjennom denne videon som forklarer hvordan QR-koder fungerer (det er greit om du ikke klarer å følge med på de aller mest tekniske detaljene om Reed-Solomon -enkoding):

Prosessen med å lage en QR-kode går igjennom følgende steg:

Selv om prosessen begynner med å konvertere en streng til en liste med bits (1’ere og 0’ere), vil oppgavene i denne lab’en være organisert «baklengs», slik at vi begynner med å skrive funksjonen for å tegne QR-koden. Grunnen til dette er rett og slett at du får prøve at koden din fungerer etter hvert steg ved å scanne QR-kodene du produserer!

Kom i gang

Last ned disse filene til arbeidsmappen din:

Opprett også en fil qr0_main.py og lim inn følgende kode:

import json
from pathlib import Path
from qr1_draw import display

# from qr3_masking import get_refined_matrix
from qr_dummies import get_refined_matrix

# from qr4_zigzag import bit_list_to_raw_matrix
from qr_dummies import bit_list_to_raw_matrix

# from qr5_bit_list import string_to_bit_list
from qr_dummies import string_to_bit_list

def get_qr_matrix(content_string):
    qr_layout = json.loads(Path('qrv2_layout.json').read_text(encoding='utf-8'))
    bit_list, err_corr = string_to_bit_list(content_string, qr_layout)
    raw_matrix = bit_list_to_raw_matrix(bit_list, qr_layout)
    matrix = get_refined_matrix(raw_matrix, err_corr, qr_layout)
    return matrix

if __name__ == '__main__':
    url = 'https://inf100.ii.uib.no'
    qr_matrix = get_qr_matrix(url)
    display(qr_matrix)

Æsj, programmet krasjer allerede. Kan det være fordi vi ikke er ferdige med qr1_draw.py enda? Gjennomfør neste steg og finn ut!

1: Tegning

I denne oppgaven skal vi skrive et program som tegner en QR-kode til skjermen, gitt at vi får en matrise (2D-liste) med hvilke felter som skal være svarte og hvilke som skal være hvite i et rutenett. I denne deloppgaven skal vi opprette filen qr1_draw.py.

draw_qr

I filen qr1_draw.py skriven funksjon draw_qr med fem parametre:

• canvas: et lerret QR-koden skal tegnes på;
• x_left og y_top: koordinatene til hjørnet øverst til venstre;
• size: bredden og høyden til QR-koden som skal tegnes (tegningen skal være like høy som den er bred); og
• qr: en kvadratisk 2D-dimensjonell liste som inneholder 1’ere og 0’ere. En 1’er betyr at ruten skal være svart, mens en 0’er betyr at ruten skal være hvit.

For å teste programmet ditt kan du legge til disse linjene nederst i filen qr1_draw.py. Når du kjører programmet, skal bildet under vises.

def display(matrix):
    from uib_inf100_graphics.simple import canvas, display as dsp
    canvas.create_rectangle(0, 0, 400, 400, fill='white', outline='')
    draw_qr(canvas, 25, 25, 350, matrix)
    dsp(canvas)

if __name__ == '__main__':
    sample_grid = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1],
        [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0],
        [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0],
        [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1],
        [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0],
        [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0],
        [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    ]
    
    display(sample_grid)

Får du linjer mellom rutene? Det skal det ikke være. Angi outline='' som et av argumentene når du kaller på create_rectangle.

Sjekk deg selv

Gå tilbake til qr0_main.py fra introduksjonssteget og kjør den nå. Om du har gjort alt riktig, skal det vises en QR-kode. Scan QR-koden med mobilen og se hvor du kommer… forhåpentligvis fant du en spennende nettside. Dessverre er det ikke riktig nettside, siden vi ikke ender opp på hovedsiden til https://inf100.ii.uib.no/ slik vi forventer ut i fra å lese koden i qr0_main.py. Det viser seg nemlig at get_refined_matrix-funksjonen som ligger i qr_dummies.py ikke bryr seg om argumentene den får, men alltid gir samme matrise tilbake uansett. Dette skal vi rette opp i løpet av de neste to stegene i oppgaven.

2: Faste mønstre og meta-felter

Det finnes mange ulike typer QR-koder. Den mest fremtredende forskjellen er kanskje dimensjonen til QR-koden, som avgjør hvor mange piksler det er i den. Jo større QR-kode, jo mer informasjon (f. eks. lengre nettadresser) kan den inneholde. I denne oppgaven skal vi for enkelhets skyld begrense oss til å kun jobbe med versjon 2 (QRv2), noe som innebærer at rutenettet vi skal lage er en matrise (2D-liste) med størrelse 25x25.

Matrisen for en QRv2 -kode er delt inn i følgende hovedkomponenter:

• En fast komponent som er lik for alle QRv2 -koder (markert i blått/lyseblått under). Disse feltene hjelper en QR-scanner å finne i hvilken del av bildet QR-koden befinner seg og hvordan den er vinklet og orientert. For oss som ikke er i businessen av å scanne QR-koder men istedet bare produsere dem, er ikke dette noe vi graver oss videre ned i utover at vi selvfølgelig må følge reglene og alltid lage koder som følger dette faste mønsteret.
• En datakomponent som inneholder selve data’en som er lagret (i svart/hvitt under). Dette datafeltet inneholder også underkomponenter for feilretting (error correction), men det kommer vi tilbake til senere.
• En komponent for metadata som sier noe om hvordan datafeltet er «maskert» og hvilket feilrettingsnivå koden benytter seg av i datafeltet (i rødt/rosa under).

I filen qrv2_layout.json (som du allerede har lastet ned til arbeidsmappen din, se introduksjon) finner du en datastruktur som forteller oss hvilke posisjoner i matrisen som hører til den faste komponenten og hvilke verdier de skal ha, samt hvilke posisjoner i matrisen som hører til metadata og hvilke verdier disse posisjonene kan ha ved ulike konfigurasjoner. Ta en kikk på filen den og prøv å forstå hvilken informasjon den inneholder.

En QRv2 -kode kan variere på følgende måter:

• Selve dataen som er lagret i QR-koden kan selvfølgelig variere. Ofte er dette en nettadresse, men det kan i prinsippet være hvilken som helst data. I denne oppgaven begrenser vi oss til å kun jobbe med strenger som data. Nettadresser er en form for streng, så vi vil kunne bruke programmet vårt til å lage QR-koder som fører oss til en nettside.
• Alle QR-koder har en viss kapasitet til å rette opp feil i avlesningen på egen hånd; men hvor stor andel av QR-koden som er feilaktig tolket før lesingen feiler kan variere. Du kan velge mellom fire nivåer av feilretting: L, M, Q og H. Disse ulike nivåene gjør at du kan hente ut korrekt informasjon selv om respektivt 7%, 15%, 25% eller 30% av matrisen blir feiltolket av programmet som leser bildet fra kameraet.
• Alle QR-koder har gått igjennom en prosess som heter «maskering», slik at bildet får en jevn fordeling av svarte og hvite piksler uavhengig av hvilken data bildet representerer. Prosessen innebærer å «flippe» enkelte ruter i matrisen etter et bestemt mønster. Det finnes 8 ulike mønstre man kan velge mellom, og ideelt sett velger vi mønsteret som gir den jevnest mulige fordeling av hvite og svarte ruter.

Når vi oppretter matrisen for QR-koden, gjøres det i fire hovedsteg:

Råversjon	Maskering	Metadata	Faste komponenter

Vi skal nå fokusere på de to siste stegene i denne helheten, nemlig fra vi har en ferdig maskert matrise til vi får en komplett QR-kode. Vi begynner med det siste steget først: å lime inn de faste komponentene. Deretter lager vi en funksjon for å lime inn feltene for metadata.

Begge oppgavene på denne siden skal skrives i filen qr2_matrix_completion.py.

set_fixed_fields

Opprett funksjonen set_fixed_fields som har to parametere

• matrix en kvadratisk matrise (2D-liste), og
• qr_layout et oppslagsverk på samme format du ser i qrv2_layout.json.

Funksjonen skal (destruktivt) endre 2D-listen matrix slik at de faste feltene får riktig verdi i henhold til qr_layout.

def test_set_fixed_fields():
    print('Testing set_fixed_fields...', end='')
    matrix = [
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 1],
    ]
    sample_layout = {
        'about': 'A fake and incomplete QR layout for testing only',
        'side_length': 5,
        'fixed_positions': {
            'zeros': [
                [3, 2], [3, 3], [3, 4], [4, 2], [4, 3], [4, 4]
            ],
            'ones': [
                [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]
            ]
        }
        # skipping keys 'byte_capacity', 'meta_positions' and 'meta_patterns'
        # since they are irrelevant here 
    }
    set_fixed_fields(matrix, sample_layout)
    assert matrix == [
        [1, 1, 1, 0, 1],
        [1, 1, 1, 1, 0],
        [1, 0, 1, 0, 1],
        [0, 1, 0, 0, 0],
        [1, 0, 0, 0, 0],
    ]

    print(' OK')

set_meta_fields

Metadata-feltet varierer basert på to parametre:

• Feilrettingsnivå (L, M, Q eller H), og
• Maskenummer (angitt ved et tall mellom 0 og 7)

Opprett funksjonen set_meta_fields som har fire parametere:

• matrix en kvadratisk matrise (2D-liste),
• err_corr en streng på ett tegn som indikerer feilrettingsnivå (enten L, M, Q eller H),
• mask_no et tall 0-7 som angir hvilken maske som er benyttet, og
• qr_layout et oppslagsverk på samme format du ser i qrv2_layout.json.

Husk, vi skal ikke gjøre noe med feilrettingskoder eller maskering akkurat nå; vi kan anta at dette allerede er tatt hånd om. Vi skal bare gjøre informasjon om valgene som er gjort tilgjengelig i QR-kodens metafelter.

Funksjonen skal (destruktivt) endre 2D-listen matrix slik at metafeltene får riktig verdi i henhold til qr_layout. Merk at for å vite hvilket mønster som skal brukes, må du slå opp i «meta_patterns» i qr_layout i henhold til parametrene err_corr og mask_no; og for å vite posisjonene hvor dette mønsteret skal plasseres, må du slå opp i «meta_positions». Studer også testen for et forenklet eksempel.

def test_set_meta_fields():
    print('Testing set_meta_fields...', end='')
    # For easier visualization the test uses a matrix of strings rather
    # than 0's and 1's, but ultimately 1's and 0's should also work
    matrix = [
        ['-', '|', '-', '|', '-'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
    ]
    sample_layout = {
        'about': 'A fake and incomplete QR layout for testing only',
        'side_length': 5,
        # skipping key 'fixed_positions' since it is irrelevant here 
        'meta_positions': {
            'first': [
                [0, 0], [0, 1], [0, 2]
            ],
            'second': [
                [0, 4], [4, 4], [3, 1]
            ]
        },
        'meta_patterns': {
            'L': [
                ['A', 'B', 'C'], # mask_no = 0
                ['a', 'b', 'c']  # mask_no = 1
            ],
            'Q': [
                ['Q', 'R', 'S'], # mask_no = 0
                ['q', 'r', 's']  # mask_no = 1
            ],
        }
    }
    err_corr = 'L'
    mask_no = 0
    set_meta_fields(matrix, err_corr, mask_no, sample_layout)
    assert matrix == [
        ['A', 'B', 'C', '|', 'A'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
        ['|', 'C', '|', '-', '|'],
        ['-', '|', '-', '|', 'B'],
    ]

    err_corr = 'Q'
    mask_no = 1
    set_meta_fields(matrix, err_corr, mask_no, sample_layout)
    assert matrix == [
        ['q', 'r', 's', '|', 'q'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
        ['|', 's', '|', '-', '|'],
        ['-', '|', '-', '|', 'r'],
    ]

    print(' OK')

Sjekk deg selv

Legg til denne snutten nederst i qr2_matrix_completion.py. Om du har gjort alt rett skal du kunne besøke en nettside med en hyggelig melding når du scanner QR-koden som vises.

if __name__ == '__main__':
    from qr_dummies import sample_masked_matrix
    from qr1_draw import display
    from pathlib import Path
    import json

    # Retrieve sample of premasked matrix without meta/fixed fields
    # and getting the matching config for it.
    matrix, error_correction_level, mask_no = sample_masked_matrix()
    qr_layout = json.loads(Path('qrv2_layout.json').read_text(encoding='utf-8'))

    # Try the functions we have created here
    set_meta_fields(matrix, error_correction_level, mask_no, qr_layout)
    set_fixed_fields(matrix, qr_layout)

    # Draw the picture
    display(matrix)

3: Maskering

I dette steget skal vi maskere en matrise. Hensikten med å maskere matrisen er å få en jevn fordeling av svarte og hvite ruter i QR-koden, slik at den blir lettere å lese for en QR-scanner. Dette innebærer å «flippe» noen av verdiene i en matrise i henhold til et bestemt mønster. QR -standarden spesifiserer 8 ulike masker man kan velge mellom. Gitt et radnummer row og et kolonnenummer col så skal en posisjon i matrisen flippes dersom en gitt betingelse er oppfylt:

Maske nr	Betingelse for flipping	Illustrasjon
0	(row + col) % 2 == 0
1	row % 2 == 0
2	col % 3 == 0
3	(row + col) % 3 == 0
4	(row//2 + col//3) % 2 == 0
5	(row*col) % 2 + (row*col) % 3 == 0
6	((row*col) % 2 + (row*col) % 3) % 2 == 0
7	((row+col) % 2 + (row*col) % 3) % 2 == 0

I illustrasjonene er de svarte rutene posisjoner hvor betingelsen er oppfylt, og rutene skal flippes.

Funksjonen beskrevet på denne siden skal skrives i filen qr3_masking.py.

should_flip

En funksjon should_flip som skal avgjøre hvorvidt en posisjon skal flippes eller ikke. La funksjonen ha parametre:

• row hvilken rad posisjonen er i,
• col hvilken kolonne posisjonen er i, og
• mask_no hvilken maske som skal benyttes.

La funksjonen returnere True dersom verdien i cellen skal flippes i henhold til gitt maske, og False hvis ikke. Denne funksjonen kan du benytte som en hjelpefunksjon for get_masked_matrix.

get_masked_matrix

En ikke-destruktiv funksjon get_masked_matrix med parametre:

• matrix en matrise (2D-liste) hvor alle verdiene er 0 eller 1, og
• mask_no et nummer som indikerer hvilken maske som skal benyttes.

Funksjonen skal returnere en ny matrise (2D-liste) med samme dimensjoner som matrix. Verdiene skal også være de samme som i matrix, bortsett fra at alle 1’ere er omgjort til 0’ere og alle 0’ere er omgjort til 1’ere i de posisjonene hvor verdien skal flippes i henhold til maskenummeret.

Legg merke til: det er oppgitt at funksjonen skal være «ikke-destruktiv». Det betyr at funksjonen ikke skal mutere matrix.

def test_get_masked_matrix():
    print('Testing get_masked_matrix...', end='')
    blank_5x5_matrix = [[0] * 5 for _ in range(5)]

    actual = get_masked_matrix(blank_5x5_matrix, 0)
    expected = [
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 1],
    ]
    assert expected == actual
    assert blank_5x5_matrix == [[0] * 5 for _ in range(5)]

    actual = get_masked_matrix(expected, 1)
    expected = [
        [0, 1, 0, 1, 0],
        [0, 1, 0, 1, 0],
        [0, 1, 0, 1, 0],
        [0, 1, 0, 1, 0],
        [0, 1, 0, 1, 0],
    ]
    assert expected == actual
    print(' OK')

score_matrix

En ikke-destruktiv funksjon score_matrix med én parameter:

• matrix, en matrise (2D-liste) med 1’ere og 0’ere.

Funksjonen skal returnere absolutt-forskjellen på antall enere og nullere i matrisen.

PS: Dette er en forenkling; hvis du er interessert i å skrive en ordentlig score-funksjon, kan du lese deg opp hos Thonky sin QR-tutorial. Men: benytt forenklingen vår når du leverer på CodeGrade, siden testene våre forventer det slik.

def test_score_matrix():
    print('Testing test_score_matrix...', end='')
    arg = [
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
    ]
    assert 5 == score_matrix(arg)

    arg = [
        [1, 1, 0],
        [1, 1, 0],
        [0, 0, 1]
    ]
    assert 1 == score_matrix(arg)
    print(' OK')

get_refined_matrix

En ikke-destruktiv funksjon get_refined_matrix med tre parametere:

• raw_matrix, en matrise (2D-liste) med 1’ere og 0’ere som representerer en «rå» matrise med umaskert data;
• error_correction_level, enten L, M, Q eller H som indikerer hvilket nivå av feilretting som ligger i den rå matrisen;
• qr_layout et oppslagsverk på formatet gitt i qrv2_layout.json som angir detaljer om hvor de faste kompontentene og meta-komponentene i matrisen befinner seg og hvordan de skal fylles ut.

Funksjonen skal returnere en komplett ferdig matrise som er både maskert og fylt med riktige verdier i de faste komponentene og i meta-komponentene. Importer og benytt funksjoner fra tidligere steg som nødvendig. Funksjonen skal velge det maskenummeret som gir lavest score (og hvis det er to masker som gir samme score, skal den med lavest maskenummer blant dem velges). De faste komponentene og meta-feltene skal legges til matrisen før den scores.

Sjekk deg selv

Gå tilbake til qr0_main.py fra introduksjonssteget og endre importene slik at get_refined_matrix importeres fra qr3_masking og ikke fra qr_dummies. Kjør programmet og scan QR-koden som vises. Om du har gjort alt riktig, skal du kunne lese en hyggelig melding.

4: Sikksakk

Det neste steget er å skape en «råmatrise» fra en streng. Denne prosessen vil foregå i to hovedsteg:

• først konverteres strengen til en (1-dimensjonell) liste med «bits» (1’ere og 0’ere), og
• så plasseres den 1-dimensjonelle listen av bits som en slange gjennom en matrise.

Vi skal fokusere på det siste først.

Når vi skal legge listen med bits inn i slangen, følges det et spesielt mønster som slanger seg gjennom matrisen. Vi begynner nederst til høyre og legger bitene som en slange som går opp og ned gjennom matrisen mot venstre. Det som gjør det litt komplisert er at man går «to og to» kolonner om gangen i et sikksakk -mønster. Se illustrasjonen under.

Noen steder (i nærheten av de faste komponentene) ser det ut som mønster av og til avviker fra det vanlige; men det som er kult, er at vi faktisk kan følge det vanlige mønsteret hele tiden, bare at vi hopper over de posisjonene som tilhører faste komponententer og meta-komponentene.

get_next_pos

I filen qr4_zigzag.py skriv en funksjon get_next_pos med parametre:

• row og column, heltall som beskriver en posisjon i en matrise (2D-liste), og
• size et heltall som beskriver sidelengden i en kvadratisk matrise.

Funksjonen skal returnere en tuple (next_row, next_column) i henhold til slange-sikksakk-mønsteret illustrert over. Du skal ikke ta hensyn til at noen deler av matrisen er forbudt, men la mønsteret fylle hele matrisen.

Du kan anta at size én mer enn delelig på fire, altså at size % 4 er 1 (dette er sant for alle QR-størrelser).

def test_get_next_pos_basic():
    print('Testing get_next_pos (basic)...', end='')
    size = 25
    # De første flyttene
    assert (24, 23) == get_next_pos(24, 24, size)
    assert (23, 24) == get_next_pos(24, 23, size)
    assert (23, 23) == get_next_pos(23, 24, size)
    ...
    # Når vi har sikksakket helt til topps
    assert (0, 23) == get_next_pos(0, 24, size)
    assert (0, 22) == get_next_pos(0, 23, size)
    assert (0, 21) == get_next_pos(0, 22, size)
    assert (1, 22) == get_next_pos(0, 21, size)
    assert (1, 21) == get_next_pos(1, 22, size)
    assert (2, 22) == get_next_pos(1, 21, size)
    ...
    # Når vi har ned helt til bunns igjen
    assert (24, 20) == get_next_pos(24, 21, size)
    assert (24, 19) == get_next_pos(24, 20, size)
    ...
    # Siste kolonne
    assert (24, 0) == get_next_pos(24, 1, size)
    assert (23, 0) == get_next_pos(24, 0, size)
    assert (22, 0) == get_next_pos(23, 0, size)
    print(' OK')

def test_get_next_pos_5x5():
    print('Testing get_next_pos (5x5)...', end='')

    size = 5
    expected = [
        [24, 11, 10, 9, 8],
        [23, 13, 12, 7, 6],
        [22, 15, 14, 5, 4],
        [21, 17, 16, 3, 2],
        [20, 19, 18, 1, 0]
    ]
    actual = [[-1] * size for _ in range(size)]
    row, col = 4, 4
    for i in range(size * size):
        actual[row][col] = i
        row, col = get_next_pos(row, col, size)

    assert expected == actual
    print(' OK')

def test_get_next_pos_9x9():
    print('Testing get_next_pos (9x9)...', end='')
    size = 9
    expected = [
        [80, 55, 54, 53, 52, 19, 18, 17, 16],
        [79, 57, 56, 51, 50, 21, 20, 15, 14],
        [78, 59, 58, 49, 48, 23, 22, 13, 12],
        [77, 61, 60, 47, 46, 25, 24, 11, 10],
        [76, 63, 62, 45, 44, 27, 26, 9, 8],
        [75, 65, 64, 43, 42, 29, 28, 7, 6],
        [74, 67, 66, 41, 40, 31, 30, 5, 4],
        [73, 69, 68, 39, 38, 33, 32, 3, 2],
        [72, 71, 70, 37, 36, 35, 34, 1, 0]
    ]
    
    actual = [[-1] * size for _ in range(size)]
    row, col = 8, 8
    for i in range(size * size):
        actual[row][col] = i
        row, col = get_next_pos(row, col, size)

    assert expected == actual
    print(' OK')

bit_list_to_raw_matrix

I filen qr4_zigzag.py skriv en funksjon bit_list_to_raw_matrix med parametre:

• bit_list en liste med bits (1’ere og 0’ere) som skal limes inn i en matrise
• qr_layout et oppslagsverk med formatet du finner i qrv2_layout.json.

Funksjonen skal opprette en kvadratisk matrise som i utgangspunktet består av kun 0’ere (størrelsen på matrisen som opprettes er angitt i qr_layout). Du skal deretter legge inn elementene fra bit_list: begynn i hjørnet nederst til høyre og benytt get_next_pos -funksjonen for å finne neste posisjon. Hopp over alle posisjoner som er tilhører en fast komponent eller en meta-komponent (informasjon om hvilke posisjoner dette er finnes i qr_layout).

• Hvis det ikke er plass til alle elementene i bit_list, bør programmet krasje.
• Hvis det er plass til overs etter at bitene fra bit_list er plassert, bare la det være 0 i de siste posisjonene.

def test_bit_list_to_raw_matrix():
    print('Testing bit_list_to_raw_matrix...', end='')
    # To make the test easier to read, bit_list contain distinct elements here
    # (in actual applications, bit_list would only have 0's and 1's)
    arg_bit_list = list(range(1, 72))
    arg_qr_layout = {
        'about': 'A fake and incomplete QR layout for testing only',
        'side_length': 9,
        'fixed_positions': {
            'ones': [
                [1, 3], [1, 4], 
            ],
            'zeros': [
                [2, 3], [2, 4],
            ]
        },
        'meta_positions': {
            'first': [
                [5, 2], [5, 3]
            ],
            'second': [
                [6, 2], [6, 3]
            ]
        }
        # key 'meta_patterns' skipped, since it is irrelevant for this task
    }

    expected = [
        [ 0, 50, 49, 48, 47, 20, 19, 18, 17],
        [ 0, 52, 51,  0,  0, 22, 21, 16, 15],
        [71, 54, 53,  0,  0, 24, 23, 14, 13],
        [70, 56, 55, 46, 45, 26, 25, 12, 11],
        [69, 58, 57, 44, 43, 28, 27, 10,  9],
        [68, 59,  0,  0, 42, 30, 29,  8,  7],
        [67, 60,  0,  0, 41, 32, 31,  6,  5],
        [66, 62, 61, 40, 39, 34, 33,  4,  3],
        [65, 64, 63, 38, 37, 36, 35,  2,  1]
    ]
    actual = bit_list_to_raw_matrix(arg_bit_list, arg_qr_layout)
    assert expected == actual
    print(' OK')

Sjekk deg selv

Gå tilbake til qr0_main.py fra introduksjonssteget og endre importene slik at bit_list_to_raw_matrix importeres fra qr4_zigzag og ikke fra qr_dummies. Kjør programmet og scan QR-koden som vises. Om du har gjort alt riktig, skal du kunne lese en hyggelig melding.

5: Feilretting

I denne siste delen skal vi se nærmere på hvordan vi skal representere en streng som en liste av bits (1’ere og 0’ere). Du husker kanskje fra kursnotatene om unicode at en streng kan representeres som en sekvens av enere og nullere. Det skal vi ser nærmere på her.

Listen med bits i en QR-kode er delt inn i seks deler:

• Modus er fire bits som forteller hvordan resten av bit-listen skal tolkes. For våre formål skal denne verdien alltid være 0100, som betyr at data’en er lagret som «binær» data; de fleste QR-scannere tolker dette i praksis som at dataen representerer en streng i latin-1 (eller ASCII) enkoding (andre mulige verdier som vi altså ikke skal bruke er: 0001 numerisk modus, 0010 alfanumerisk modus, 1000 japansk kanji, og 0111 ECI-modus).
• Lengde er et tall (i totallsystemet) som indikerer hvor mange bytes dataen består av. Åtte bits utgjør én byte, så vi kan gange tallet med 8 for å finne ut for mange bits som befinner seg i data-seksjonen.
• Data er selve dataen. For våre formål et dette en ASCII-enkodet streng.
• Terminator er fire nuller som følger etter dataen (disse brukes egentlig ikke til noen ting i binærmodus, men må være til stede for å fylle opp plassen).
• Padding er noen faste mønstre som gjentar seg. Hensikten er å bruke opp resten av plassen før feilrettingen begynner. Hvor mye padding det er kommer an på hvor mye data det er og hvor mye plass feilrettingen tar (paddingen kan også være ingenting).
• Feilretting er spesielle bits som gjør det mulig å gjenopprette den originale dataen selv om noen bits av en eller annen grunn har blitt flippet. Denne delen regnes ut på bakgrunn av de foregående delene av bit-listen.

Funksjonene på denne siden skal opprettes i filen qr5_bit_list.py.

string_to_data

Opprett en funksjon string_to_data med én parameter:

• content_string en streng du kan anta består av ASCII -symboler.

Funksjonen skal returnere en liste av bits som representerer strengen i ASCII-enkoding.

def test_string_to_data():
    print('Testing string_to_data...', end='')
    assert [0,1,0,0,0,0,0,1] == string_to_data('A')
    assert [0,1,0,0,0,0,0,1,0,1,0,0,0,0,1,1] == string_to_data('AC')
    foo = [0,1,1,0,0,1,1,0,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1]
    assert foo == string_to_data('foo')
    print(' OK')

c = 'A'
bit_list = [int(x) for x in f'{ord(c):08b}'] 

# la 'result' være er en tom liste
# for hvert symbol i content_string:
#    finn bit-listen for symbolet
#    utvid (extend) 'result' med bit-listen
# returner resultatet

get_core_bit_list

Opprett en funksjon get_core_bit_list med én parameter:

• content_string en streng du kan anta består av ASCII -symboler.

Funksjonen skal returnere de fire første delene av en bit-liste: modus, lengde, data og terminator for den gitte strengen

def test_get_core_bit_list():
    print('Testing get_core_bit_list...', end='')
    arg = 'hei'
    expected_head = [0, 1, 0, 0]
    expected_len = [0, 0, 0, 0, 0, 0, 1, 1] # 3 in binary
    expected_data = [int(x) for x in '011010000110010101101001']
    expected_term = [0, 0, 0, 0]
    expected = expected_head + expected_len + expected_data + expected_term

    actual = get_core_bit_list(arg)
    assert expected == actual
    print(' OK')

my_len = 42
len_bit_list = [int(x) for x in f'{my_len:08b}'] 

pad_bit_list

Opprett en funksjon pad_bit_list med to parameter:

• core_bit_list en liste med bits
• pad_to_bytes et tall som sier hvor mange bytes den ferdig paddeded bit-listen skal inneholde

Funksjonen skal destruktivt legge til padding-mønstre på slutten av core_bit_list slik at den til sammen blir pad_to_bytes lang. Husk at én byte er åtte bit, så lengden på den endelige listen skal være 8 * pad_to_bytes.

Paddingen som legges til skal veksle mellom [1, 1, 1, 0, 1, 1, 0, 0] og [0, 0, 0, 1, 0, 0, 0, 1] annenhver gang helt til listen er tilstrekkelig lang.

def test_pad_bit_list():
    print('Testing pad_bit_list...', end='')
    PAD1 = (1, 1, 1, 0, 1, 1, 0, 0)
    PAD2 = (0, 0, 0, 1, 0, 0, 0, 1)
    
    arg = [1, 1, 1, 1, 1, 1, 1, 1]
    expected = arg + list(PAD1) + list(PAD2) + list(PAD1)
    pad_bit_list(arg, 4)
    assert expected == arg

    arg = [1, 1, 1, 1, 1, 1, 1, 1]
    expected = arg + list(PAD1) + list(PAD2) + list(PAD1) + list(PAD2)
    pad_bit_list(arg, 5)
    assert expected == arg

    arg = [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1]
    expected = arg + list(PAD1) + list(PAD2) + list(PAD1) + list(PAD2)
    pad_bit_list(arg, 6)
    assert expected == arg
    print(' OK')

string_to_bit_list

Opprett en funksjon string_to_bit_list med to parametere:

• content_string, en streng du kan anta består av ASCII -symboler, og
• qr_layout, et oppslagsverk på formatet du finner i qrv2_layout.json.

Funksjonen skal returnere to ting i en tuple:

• en komplett bit-liste, inkludert modus, lengde, data, terminator, padding, og feilretting, og
• en streng på ett tegn: ‘L’, ‘M’, ‘Q’ eller ‘H’ som indikerer hvilket feilrettingsnivå som brukes i bit-listen.

Før vi begynner:

En QRv2-kode har 25x25 piksler, og representerer dermed 625 bit med informasjon. Mye av dette brukes imidlertid til faste komponenter og meta-komponenter, så i praksis er det bare 352 bits (44 bytes) vi har til rådighet (nøkkelen ‘byte_capacity’ i qr_layout forteller oss dette). Denne plassen skal fordeles mellom feltene for modus, lengde, data, terminator, padding og feilrettingskode.

En QR-kode kan ha fire ulike nivåer av feilretting: L, M, Q eller H som gir bedre og bedre nivåer av feilretting. Disse nivåene krever henholdsvis 80, 128, 176 og 224 bits (eller 10, 16, 22 og 28 bytes om du vil). Jo bedre feilretting vi ønsker oss, jo mer plass krever altså feilrettings-komponenten. Konsekvensen av dette er at vi bare kan bruke et høyt nivå av feilretting dersom dataen vi lagrer er tilstrekkelig liten.

Når vi velger nivå av feilretting, gjør vi som følger:

• Vi finner først bit-listen for modus, lengde, data og terminator og ser hvor stor plass dette tar.
• Vi velger deretter nivå av feilretting L, M, Q eller H så høyt som mulig, men slik at det likevel er plass til begge deler (hvis det ikke er plass til laveste feilrettingsnivå, krasj programmet og gi en hensiktsmessig feilmelding).
• Hvis vi ser at det vil bli plass til overs, legger vi til padding før vi regner ut selve feilrettingsmønsteret.

Husk å holde tungen rett i munnen med tanke på bytes og bits. 1 byte = 8 bits.

Forresten, en funksjon for å regne ut selve feilrettingsmønsteret kan du laste ned her: qr6_error_correction.py (du må også installere den eksterne pakken reedsolo. Prøv å skrive python3 -m pip install reedsolo i terminalen eller se notatene om eksterne pakker for eksempler på hvordan man installerer eksterne pakker).

Vil du lære å regne ut feilrettingsmønsteret selv? Sjekk ut INF243.

Ferdigstilling

Gå tilbake til qr0_main.py fra introduksjonssteget og endre importene slik at string_to_bit_list importeres fra qr5_bit_list og ikke fra qr_dummies. Kjør programmet og scan QR-koden som vises. Om du har gjort alt riktig, programmet nå fungerer. Yay!

0: Introduksjon

Geofarer som jordskred, snøskred, flommer og lava beveger seg hovedsakelig etter en enkel regel: de trekkes nedover i terrenget av tyngdekraften.

I denne oppgaven skal du simulere et vulkanutbrudd og finne ut hvor man trygt kan bygge et hus nedenfor en vulkan.

Du skal altså simulere noe som ligner vulkanutbruddet under:

men i denne oppgaven holder vi oss til et 2D-fugleperspektiv, så simuleringene dine vil ligne denne:

Forenklinger

Vi gjør to forenklinger:

• Lava kan bevege seg til alle naboceller som ligger like høyt eller lavere.
• Det er en evig mengde lava som strømmer ut fra vulkanens krater.

Terrenget er altså det eneste som avgjør hvor lavaen ender opp.

Oversikt

Oppgaven er delt i åtte deler som bygger på hverandre:

1. Last inn og undersøk terrenget (3 poeng)
2. Innføring i matplotlib (0 poeng)
3. To tidssteg (8 poeng)
4. Simuler hele utbruddet (4 poeng)
5. Animasjon av vulkanen (0 poeng)
6. Tell hvor mange hus som blir tatt av lava (3 poeng)
7. Videreutvikling av koden (2 poeng)

All koden skal skrives i filen lavasimulering.py.

1: Last inn terrenget

Vi begynner med å laste inn dataen for vulkanterrenget.

Kom i gang

Last ned vulkan_terreng.csv og legg den i arbeidsmappen din.

Filen inneholder terrenghøyder i meter over havet: 800×800 tall skilt med komma. Filen har ingen overskriftsrad. Hver rad i filen er én rad i terrenget.

load_terrain

I filen lavasimulering.py, skriv en funksjon load_terrain(path) som leser CSV-filen med filsti path og returnerer en 2D-liste med flyttall. Hver indre liste er én rad i terrenget.

Test deg selv

def test_load_terrain():
    print('Tester load_terrain... ', end='')
    terrain = load_terrain('vulkan_terreng.csv')
    assert len(terrain) == 800
    assert len(terrain[0]) == 800
    assert type(terrain[0][0]) == float
    print('OK')

highest_point og lowest_point

Når du arbeider med et nytt datasett, er det lurt å gjøre seg kjent med hva slags verdier du skal arbeide med.

I filen lavasimulering.py, skriv to funksjoner:

• highest_point(terrain) som tar inn en 2D-liste terrain og returnerer den høyeste verdien i terrenget.
• lowest_point(terrain) som tar inn en 2D-liste terrain og returnerer den laveste verdien i terrenget.

Test deg selv

def test_highest_and_lowest_point():
    print('Tester highest_point og lowest_point... ', end='')
    terrain = [
        [3.0, 7.5, 2.0],
        [9.0, 1.5, 4.0],
    ]
    assert highest_point(terrain) == 9.0
    assert lowest_point(terrain) == 1.5
    print('OK')

Bruk funksjonene dine på vulkanterrenget. Hvor høyt er det høyeste punktet, og hvor høyt er det laveste?

2: Innføring i matplotlib

Før vi kan se vulkanen vår, trenger vi et verktøy for å lage figurer. I denne delen lærer du det grunnleggende i matplotlib. Dette biblioteket er et av de mest populære for å visualisere ulike typer data i Python.

Les mer om biblioteket her: https://matplotlib.org/

Denne delen er en gjennomgang (tutorial). Les gjennom, kjør eksemplene selv, og gjør oppgavene merket Prøv selv. Du trenger ikke levere noe fra denne delen.

Installasjon

Matplotlib er et bibliotek som kun trengs å installeres én gang på din lokale maskin.

Først, sjekk om du har matplotlib installert allerede:

import matplotlib
print(matplotlib.__version__)

Hvis du får et versjonsnummer (f.eks. 3.9.2), er du klar. Får du feilmeldingen ModuleNotFoundError: No module named 'matplotlib', må du installere det.

Da kan du installere det på én av to måter

1. Du kan installere biblioteket med pip install matplotlib i terminalen.

2. Du kan installere biblioteket med

import sys
from subprocess import run

package_name = 'matplotlib'  # <--- navnet på pakken du vil installere

run(f'{sys.executable} -m ensurepip'.split())
run(f'{sys.executable} -m pip install --upgrade pip'.split())
run(f'{sys.executable} -m pip install {package_name}'.split())

Ditt første plot: et linjeplot

Da er vi klare! Lag en ny fil matplotlib_intro.py som du kan prøve deg frem i. Øverst i filen importerer du matplotlib slik:

import matplotlib.pyplot as plt

matplotlib må importeres i toppen av alle filer hvor du vil bruke biblioteket.

pyplot er den delen av matplotlib vi bruker for å lage figurer, og plt er et kallenavn på den som “alle” bruker. Du vil se plt brukt i nesten alle eksempler på nettet.

Vi begynner helt klassisk med et linjeplot som trekker en linje mellom punkter. Vi har to lister av samme lengde: x-verdiene og y-verdiene. I dette eksempelet bruker vi omtrentlige månedlige middeltemperaturer i Bergen.

# Definer listene
months = ['jan', 'feb', 'mar', 'apr', 'mai', 'jun',
          'jul', 'aug', 'sep', 'okt', 'nov', 'des']
temperature = [1.5, 1.5, 3.0, 6.0, 9.5, 12.5, 14.5, 14.5, 11.5, 8.0, 4.5, 2.0]

# Visualiser dataen
plt.figure()
plt.plot(months, temperature)
plt.show()

Element nummer i i months hører sammen med element nummer i i temperature. Har listene ulik lengde, krasjer programmet med en ValueError.

Gjør plottet leselig

Et plot uten tittel og aksetitler er vanskelig å forstå for andre. Vi legger dem til slik:

plt.figure(figsize=(8, 4))
plt.plot(months, temperature, color='red', marker='o', label='Bergen')
plt.title('Månedlig middeltemperatur')
plt.xlabel('Måned')
plt.ylabel('Temperatur (°C)')
plt.legend()
plt.grid(alpha=0.3)
plt.show()

Prøv selv: Endre fargen til blå, og bytt marker='o' med marker='s'. Hva skjer hvis du legger til linestyle='--' som argument i plt.plot()?

Punktplot

Noen ganger gir det ikke mening å trekke en linje mellom punktene. Da bruker vi et punktplot (scatter plot) med plt.scatter.

Se for deg at du har vært ute i juli og målt temperaturen for forskjellige høyder på Galdhøpiggen.

Her plotter vi temperatur mot høyde i juli:

altitude_july = [10, 180, 390, 560, 790, 1010, 1240, 1430, 1680, 1890, 2150, 2469]
temperature_july = [16.3, 15.1, 14.1, 12.5, 11.4, 9.8, 8.1, 7.2, 5.2, 4.2, 2.2, 0.1]

plt.figure()
plt.scatter(altitude_july, temperature_july, color='red')
plt.title('Galdhøpiggen temperatur i juli')
plt.xlabel('Høyde over havet (m)')
plt.ylabel('Temperatur (°C)')
plt.show()

Du drar tilbake til Galdhøpiggen i oktober og tar nye målinger, men ikke på de samme stedene. Du kan plotte flere dataset i en figur som vist under:

altitude_october = [10, 270, 480, 700, 920, 1120, 1350, 1600, 1810, 2050, 2170, 2290, 2469]
temperature_october = [7.9, 6.6, 4.8, 3.6, 2.6, 1.6, 0.0, -1.7, -2.5, -4.7, -5.1, -5.5, -7.0]

plt.figure()
plt.scatter(altitude_july, temperature_july, color='red', label='Juli')
plt.scatter(altitude_october, temperature_october, color='blue', marker='^', label='Oktober')
plt.title('Galdhøpiggen temperatur')
plt.xlabel('Høyde over havet (m)')
plt.ylabel('Temperatur (°C)')
plt.legend()
plt.show()

Vis en 2D-liste som et bilde

Til nå har vi plottet lister. Men et terreng er en 2D-liste, der hver verdi er høyden i én celle. En 2D-liste kan vi vise som et bilde med plt.imshow. Hver celle blir én rute, og verdien bestemmer fargen.

small_terrain = [
    [9, 9, 9, 9, 9, 9, 9],
    [9, 9, 9, 8, 7, 5, 9],
    [9, 9, 5, 6, 4, 8, 9],
    [9, 8, 4, 3, 7, 4, 9],
    [9, 9, 3, 3, 8, 2, 9],
    [9, 9, 9, 8, 2, 1, 9],
    [9, 9, 9, 9, 9, 9, 9],
]

plt.figure()
plt.imshow(small_terrain, cmap='plasma')
plt.colorbar(label='Høyde (m)')
plt.title('Et lite terreng')
plt.show()

Dette er det samme lille terrenget som du skal teste lava-koden din på senere. Den gule kanten rundt er alle 9-erne.

Legg merke til at matplotlib godtar 2D-lister direkte.

Konturlinjer

På kart viser vi ofte høyde med høydekurver, linjer som går gjennom punkter med samme høyde. I matplotlib heter dette plt.contour. Det blir tydeligst på et terreng med mange celler, så her lager vi en kjegleformet fjelltopp på 50×50 celler:

import math

hill = []
for row in range(50):
    new_row = []
    for col in range(50):
        distance = math.sqrt((row - 25)**2 + (col - 25)**2)
        new_row.append(100 - 2 * distance)
    hill.append(new_row)

plt.figure()
plt.imshow(hill, cmap='terrain')
plt.colorbar(label='Høyde (m)')
plt.contour(hill, colors='black', linewidths=0.5, levels=range(30, 100, 10))
plt.title('En kjegleformet fjelltopp')
plt.show()

levels=range(30, 100, 10) betyr at matplotlib tegner en høydekurve for hver 10. meter, fra 30 til 90 m. Når vi tegner imshow og contour på den samme figuren, havner de oppå hverandre.

(rad, kolonne) eller (x, y)?

Dette er den vanligste feilen når man plotter 2D-lister, så den er verdt å stoppe opp ved.

• I en 2D-liste skriver vi small_terrain[rad][kolonne].
• I et plot er x den vannrette aksen og y den loddrette. En kolonne tilsvarer altså en x-verdi, og en rad tilsvarer en y-verdi.

Det betyr at plt.scatter(x, y) må få kolonnen først og raden etterpå:

plt.figure()
plt.imshow(small_terrain, cmap='plasma')
plt.scatter(1, 3, color='red', s=100)   # rad 3, kolonne 1
plt.title('small_terrain[3][1] markert med rødt')
plt.show()

s=100 bestemmer størrelsen på punktene.

Lagre og lukke figuren

Når du bruker plt.show() popper figuren opp i et eget vindu, som du lukker før koden kan fortsette.

Vil du bruke figuren i en rapport, kan du lagre den som en bildefil i stedet for (eller i tillegg til) å vise den. Kall plt.savefig før plt.show():

plt.savefig('temperatur.png', dpi=300)
plt.show()

dpi bestemmer oppløsningen. 300 er en god oppløsning for rapporter.

MEN dersom du ikke vil se og lukke figuren (ofte tilfellet hvis du produserer mange figurer), er det viktig å lukke figuren i koden før du starter en ny.

plt.savefig('temperatur.png', dpi=300)
plt.close()

Hvis du ikke lukker figuren før du starter på en ny kan du få problemer med at data plottes i feil figur eller at Pythons minne blir overveldet av for mange figurer og må avsluttes. Om du er usikker på om du har åpne figurer, kan du lukke alle for sikkerhets skyld ved å bruke plt.close('all')

Animasjon

Når vi simulerer noe som skjer over tid, vil vi gjerne se figuren endre seg mens koden kjører. Da tegner vi ikke en ny figur for hvert tidssteg. I stedet tegner vi figuren én gang, og bytter bare ut dataen som endrer seg.

Her lar vi fjelltoppen fra forrige avsnitt vokse frem, fra 0 til 100 meter. Funksjonen grow_hill lager den samme kjegleformede fjelltoppen, men med høyden max_height på toppen.

import math

def grow_hill(max_height):
    hill = []
    for row in range(50):
        new_row = []
        for col in range(50):
            distance = math.sqrt((row - 25)**2 + (col - 25)**2)
            new_row.append(max_height - 2 * distance)
        hill.append(new_row)
    return hill

# Tegn figuren én gang
hill = grow_hill(0)
plt.ion()
plt.figure(figsize=(6, 6))
im = plt.imshow(hill, cmap='terrain', vmin=0, vmax=100)
plt.colorbar(label='Høyde (m)')
plt.xticks([])
plt.yticks([])
plt.show(block=False)
plt.pause(0.001)

# Øk høyden på fjellet
for h in range(0, 101, 1):
    hill = grow_hill(h)
    im.set_data(hill)
    plt.pause(0.1)

plt.ioff()
plt.show()

Det er set_data som gjør animasjonen rask. Figuren, fargeskalaen og aksene tegnes bare én gang, og det er bare selve bildet som byttes ut. Dette blir viktig når vi senere animerer lava på et terreng med flere celler.

Prøv selv: Legg til plt.title(f'Høyde: {h} m') inne i løkken. Gjør plt.pause(0.1) større eller mindre. Hva skjer? Hva skjer hvis du fjerner vmin=0, vmax=100?

Oppsummering

Nå kan du nok matplotlib til å visualisere vulkanen. I neste del bruker vi imshow, contour og egne fargekart på det ekte terrenget.

Les mer

• Quick start guide på matplotlib.org: dette er utviklernes egen innføring som denne gjennomgangen bygger på.
• Cheatsheets: oversiktsark over plottyper, farger og markører.
• Farger: oversikt over alle innebygde farger.
• Fargekart: oversikt over alle innebygde fargekart, og hvilke som passer til hva.

3: To tidssteg

Nå er vi klare til å ta fatt på selve simuleringen. Vulkanterrenget har 800×800 = 640 000 celler, og da er det vanskelig å se om koden gjør det den skal. Vi utvikler og tester derfor koden på et lite terreng først, hvor vi kan ha god oversikt over at den gjør som den skal.

Vi bruker det samme lille terrenget som i innføringen i matplotlib. Legg det inn i en fil lavasimulering.py:

small_terrain = [
    [9, 9, 9, 9, 9, 9, 9],
    [9, 9, 9, 8, 7, 5, 9],
    [9, 9, 5, 6, 4, 8, 9],
    [9, 8, 4, 3, 7, 4, 9],
    [9, 9, 3, 3, 8, 2, 9],
    [9, 9, 9, 8, 2, 1, 9],
    [9, 9, 9, 9, 9, 9, 9],
]

create_lava_list

Vi holder styr på hvor det er lava i en egen 2D-liste lava med samme størrelse som terrenget. Foreløpig betyr 0 «ingen lava» og 1 «lava».

Lag en funksjon create_lava_list(terrain,start_row, start_col). Denne skal returnere en 2D-liste lava med samme antall rader og kolonner som terrenget den gis. Her er alle verdiene 0, bortsett fra lava[start_row][start_col] som er 1. Her sier vi at utbruddet begynner.

For å teste denne, kan du gjerne bruke small_terrain som terreng, og starte utbruddet i lava[2][3], altså start_row=2 og start_col=3.

def test_create_lava_list():
    print('Testing create_lava_list...', end=' ')
    small_terrain = [
        [9, 9, 9, 9, 9, 9, 9],
        [9, 9, 9, 8, 7, 5, 9],
        [9, 9, 5, 6, 4, 8, 9],
        [9, 8, 4, 3, 7, 4, 9],
        [9, 9, 3, 3, 8, 2, 9],
        [9, 9, 9, 8, 2, 1, 9],
        [9, 9, 9, 9, 9, 9, 9],
    ]
    expected = [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]
    actual = create_lava_list(small_terrain, 2, 3)
    assert expected == actual
    print('OK')

plot_lava

For å se hva lavaen gjør, er det nyttig å plotte terrenget med lava på topp. Koden for dette får du av oss og er basert på matplotlib. Kopier koden inn øverst i lavasimulering.py:

import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

# Vi lager vårt eget fargekart for lava.
# Alle celler med lava (høyere enn 0) blir røde.
# Celler uten lava (0) ligger under vmin og blir gjennomsiktige.
lava_cmap = ListedColormap(['red'])
lava_cmap.set_under((0, 0, 0, 0))

def plot_lava(terrain, lava):
    """Tegner terrenget med lava oppå."""
    plt.figure()
    plt.imshow(terrain, cmap='gist_earth')
    plt.colorbar(label='Høyde (m)')
    plt.imshow(lava, cmap=lava_cmap, vmin=1, vmax=2)
    plt.show()

Funksjonen tegner to bilder oppå hverandre i den samme figuren, slik du gjorde med imshow og contour i del 2. Vi har her gjort et triks hvor alle celler under vmin=1 blir gjennomsiktige, slik at du ser terrenget under.

vmin og vmax i plt.imshow() setter minimum og maksimumverdi av hva du vil fargekartet skal vise.

Kall funksjonen med plot_lava(small_terrain, lava). Du skal få opp et bilde av terrenget med én rød celle i krateret:

Hvor kan lavaen renne?

I terrenget over har vi lava i punktet A (se under). Denne lavaen kan renne til de åtte omkringliggende punktene (B–I), dersom disse ligger like høyt som, eller lavere enn, A.

I dette tilfellet ligger I, H, G og E lavere enn A, så lavaen kan renne dit.

Tegningen viser naboene rundt krateret i det lille terrenget. A er krateret i (2, 3) med høyde 6. I, H, G og E har høyde 5, 4, 3 og 4, mens B, C, D og F har høyde 9, 8, 7 og 7.

lava_flow

I filen lavasimulering.py, skriv en funksjon lava_flow(terrain, lava) som tar inn 2D-listene terrain og lava, og returnerer en ny 2D-liste new_lava der lavaen har rent fra cellen med lava til alle naboceller som ligger like høyt eller lavere. Nabocellene som får lava skal ha verdien 1.

Det er lurt å lage en ny 2D liste new_lava som er en kopi av lava. I den kan du legge til nye punkter med lava. Dersom du endrer direkte i lava og koden din samtidig looper over alle cellene i lava, mister vi oversikt over tidsstegene.

Test deg selv

def test_lava_flow_one_cell():
    print('Tester lava_flow med én celle... ', end='')
    small_terrain = [
        [9, 9, 9, 9, 9, 9, 9],
        [9, 9, 9, 8, 7, 5, 9],
        [9, 9, 5, 6, 4, 8, 9],
        [9, 8, 4, 3, 7, 4, 9],
        [9, 9, 3, 3, 8, 2, 9],
        [9, 9, 9, 8, 2, 1, 9],
        [9, 9, 9, 9, 9, 9, 9],
    ]
    lava = create_lava_list(small_terrain, 2, 3)
    new_lava = lava_flow(small_terrain, lava)

    # Lavere naboer får lava
    assert new_lava[2][2] == 1  # I
    assert new_lava[3][2] == 1  # H
    assert new_lava[3][3] == 1  # G
    assert new_lava[2][4] == 1  # E

    # Høyere naboer får ikke lava
    assert new_lava[1][2] == 0  # B
    assert new_lava[1][3] == 0  # C
    assert new_lava[1][4] == 0  # D
    assert new_lava[3][4] == 0  # F
    print('OK')

Når testen går gjennom, se på resultatet med plot_lava(small_terrain, lava_flow(small_terrain, lava)). Lavaen skal ha rent til de fire lavere naboene:

Alle celler med lava

Nå vet vi hvor lavaen kan renne fra én celle. Neste steg er å gjøre det samme for alle cellene som har lava.

I neste tidssteg må du sjekke hvor lavaen kan renne fra de nye punktene (I, H, G og E). I eksempelet under tester vi hvor lavaen kan flyte fra punktet “I”. De eneste mulighetene er a, b, c, d og e, siden de andre allerede er fylt av lava.

Tre verdier i lava

Hvis du sjekker alle celler med lava i hvert tidssteg, blir koden din treg. Du trenger heller ikke sjekke celler som lavaen allerede har rent fra (f.eks. A i eksempelet over). Vi innfører derfor en ny verdi i lava, 2, som betyr at cellen er ferdigsjekket:

lava_flow (utvidet)

Endre funksjonen lava_flow(terrain, lava) fra forrige del slik at

1. lava renner fra alle celler i lava som har verdien 1,
2. lava kan renne til alle celler som er like høye som eller lavere enn cellen som testes,
3. lava ikke renner til celler som allerede har lava (verdi 1 eller 2),
4. hver celle som lavaen har rent fra, får verdien 2 i listen som returneres.

Som i forrige steg, skal funksjonen være ikke-destruktiv. Det betyr at den ikke skal endre lava, men lage en kopi og gjøre endringene i kopien.

Test deg selv

def test_lava_flow_one_step():
    print('Tester lava_flow med ett tidssteg... ', end='')
    terrain = [
        [9, 9, 9, 9, 9, 9, 9],
        [9, 9, 9, 8, 7, 5, 9],
        [9, 9, 5, 6, 4, 8, 9],
        [9, 8, 4, 3, 7, 4, 9],
        [9, 9, 3, 3, 8, 2, 9],
        [9, 9, 9, 8, 2, 1, 9],
        [9, 9, 9, 9, 9, 9, 9],
    ]
    lava = create_lava_list(terrain, 2, 3)

    # Tidssteg 1
    lava_1 = lava_flow(terrain, lava)
    assert lava_1 == [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 2, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]

    # Tidssteg 2
    lava_2 = lava_flow(terrain, lava_1)
    assert lava_2 == [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 2, 2, 2, 0, 0],
        [0, 0, 2, 2, 0, 1, 0],
        [0, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0],
    ]

    # Den originale lava-listen skal ikke endre innhold
    assert lava[2][3] == 1
    assert lava_1[3][3] == 1
    print('OK')

Ikke la lava flyte utenfor kartet

I det lille terrenget har vi laget en kant med 9-ere som gir en høy barriere lavaen ikke kan flyte forbi. Dette er ikke nødvendigvis tilfellet for andre terreng.

Utvid lava_flow så lavaen ikke kan flyte forbi kanten, så du slipper indekseringsfeil.

Under er to forskjellige terreng du kan teste koden din med.

def test_lava_flow_edge():
    print('Tester lava_flow ved kanten... ', end='')
    # Lava i hjørnet øverst til venstre. Alle naboene er høyere,
    # så lavaen skal ikke renne noe sted.
    terrain = [
        [5, 9, 9],
        [9, 9, 9],
        [1, 1, 1],
    ]
    lava = [
        [1, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]
    assert lava_flow(terrain, lava) == [
        [2, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]

    # Lava i hjørnet nederst til høyre.
    terrain = [
        [1, 1, 1],
        [9, 9, 9],
        [9, 9, 5],
    ]
    lava = [
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 1],
    ]
    assert lava_flow(terrain, lava) == [
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 2],
    ]
    print('OK')

Indekseringsfeil er ikke noe gøy, men enda verre: lava[-1][-1] er lov i Python og betyr siste rad og siste kolonne, så lava i rad 0 kan plutselig dukke opp i bunnen av kartet uten at programmet krasjer. Dette er nyttig når du skal lage et snake-program, men ikke når man arbeider med kart.

4: Hele utbruddet

Nå har vi alt vi trenger for å la vulkanen få utbrudd. Som en siste test, gjentar vi lava_flow helt til det ikke finnes mer lava som kan renne videre, altså helt til det ikke er noen 1-ere igjen i lava.

has_active_lava

I filen lavasimulering.py, skriv en funksjon has_active_lava(lava) som returnerer True dersom det finnes minst én celle med verdien 1 i lava, og False ellers.

Skriv din egen test-funksjon test_has_active_lava() for å se om funksjonen din fungerer. Testen skal passere dersom has_active_lava er riktig implementert, og skal feile med en assert hvis ikke.

simulate_eruption

I filen lavasimulering.py, skriv en funksjon simulate_eruption(terrain, start_row, start_col) som

1. lager en ny lava-liste med samme størrelse som terrain, med 1 i startpunktet (start_row, start_col) og 0 ellers,
2. kaller lava_flow gjentatte ganger så lenge det finnes aktiv lava, og
3. returnerer den ferdige lava-listen.

Se resultatet

lava = simulate_eruption(small_terrain, 2, 3)
plot_lava(small_terrain, lava)

simulate_eruption gir oss bare den ferdige lava-listen. For å se hvordan lavaen sprer seg underveis, må du lage din egen løkke som tegner lavaen for hvert tidssteg. Får du de samme fem tidsstegene som under? Da er du klar for neste steg!

Legg merke til cellen (1, 5), den grønne ruten. Den har høyde 5 og ligger altså lavere enn krateret, men får likevel ikke lava. Lava renner aldri oppover, og den eneste lava-naboen til (1, 5) er E, som ligger lavere (4).

Prøv selv: Start utbruddet i (1, 4) i stedet, der høyden er 7. Prøv å forutsi hvilke celler som får lava før du kjører koden. Hvorfor får (1, 5) lava nå?

5: Vulkanen

Koden din virker på det lille terrenget. Nå er det tid for den ekte vulkanen!

I denne delen skal du sy sammen det du har gjort til nå, og du trenger også kode fra del 2 om matplotlib.

Kom i gang

Du trenger vulkan_terreng.csv fra del 1 i arbeidsmappen din. Last inn terrenget med load_terrain:

terrain = load_terrain('vulkan_terreng.csv')

Plot vulkanen

Det lille terrenget plottet vi med det innebygde fargekartet 'gist_earth'. Men vi kan faktisk lage våre helt egne fargekart. Under lager vi vårt eget fargekart og plotter konturlinjer for vulkanen. Du kan justere dette akkurat som du ønsker.

from matplotlib.colors import LinearSegmentedColormap

# Fargekart for vulkanen.
colors = [
    '#1d4d30',  # mørk grønn
    '#3a7a4a',  # grønn
    '#7aa86c',  # olivengrønn
    '#7a3d18',  # kobberbrun
    '#b96a2a',  # middels kobber
    '#e6a14a',  # varm oransje
    '#f7d29a',  # lys kobber
    '#fff1d6',  # nesten hvit
    '#f4d7a3',  # blek gull
    '#ffffff',  # hvit
]
volcano_cmap = LinearSegmentedColormap.from_list('volcano_cmap', colors)

plt.figure(figsize=(8, 8))
plt.imshow(terrain, cmap=volcano_cmap)
plt.contour(terrain, colors='black', linewidths=0.5, alpha=0.5, levels=15) # Her setter vi contour til å velge 15 nivået mellom laveste og høyeste punkt i dataen
plt.xticks([])  # fjern tallene på aksene
plt.yticks([])
plt.title('Vulkan')
plt.show()