Vallende korrels¶

Deze pagina bevat uitvoerbare code.

Zand valt. Denk aan een raster waarin sommige cellen een zandkorrel bevatten: elke korrel zakt omlaag tot hij op de bodem ligt of op een andere korrel. Je weet meteen wat er hoort te gebeuren. Hoe je dat opschrijft is een tweede vraag, en daar gaat deze bijeenkomst over.

In dit werkcollege bouw je dat algoritme met de klas op. Je begint niet met code maar met een plan: je knipt het probleem in deelproblemen, geeft elk deelprobleem een naam, een invoer en een uitvoer, en schrijft ze pas daarna één voor één uit. Het bord verandert daarbij op zijn plek, met bord[rij][kolom] = waarde.

De regel, met een voorbeeld¶

Een bord is een rechthoekige lijst van lijsten. 0 is lege ruimte en 1 is een korrel. bord[rij][kolom] is één cel. Rij 0 is boven, de laatste rij is de bodem. Buiten het bord bestaat niets: daar wordt nooit gelezen of geschreven.

De regel voor één tijdstap:

Een korrel blijft liggen als hij op de bodem ligt, of als de korrel onder hem blijft liggen. Alle andere korrels zakken precies één rij.

Geen korrel zakt dus meer dan één rij per tijdstap. Een hele kolom zand schuift wel in één keer een rij omlaag, want zodra de onderste korrel zakt, komt de plek boven hem vrij.

Dit is het bord waar we mee werken:

101
001
010

Per cel levert de regel dit op:

positie	waarde	wat er onder ligt	zakt?
`(0, 0)`	`1`	een lege cel	ja
`(0, 1)`	`0`	-	nee, hier ligt geen korrel
`(0, 2)`	`1`	een korrel die zelf zakt	ja
`(1, 2)`	`1`	een lege cel	ja
`(2, 1)`	`1`	de bodem	nee

Eén tijdstap op dit bord geeft dus:

      000
 ->   101
      011

Het plan: vier deelproblemen¶

Voordat er één regel code staat, knippen we het probleem op. Een deelprobleem is pas af beschreven als het een naam heeft, een invoer en een uitvoer.

Noem eerst zelf drie deelproblemen die je hiervoor nodig denkt te hebben, met van elk een naam, een invoer en een uitvoer. Vergelijk ze daarna met het plan hieronder: welke had je ook, welke miste je, en waar knipte je het anders?

#	Deelprobleem	Naam	Invoer	Uitvoer
1	Kan deze korrel zakken?	`can_fall`	bord, rij, kolom	`True` of `False`
2	Laat deze korrel één rij zakken	`drop_grain`	bord, rij, kolom	niets; het bord verandert
3	Voer één tijdstap uit op het hele bord	`fall_once`	bord	niets; het bord verandert
4	Laat alles vallen tot het stil ligt	`settle`	bord	niets; het bord verandert

Let op de uitvoerkolom. Deelprobleem 1 geeft een antwoord terug; de andere drie geven niets terug maar veranderen het bord dat ze meekrijgen. Dat verschil is geen detail: het bepaalt hoe je de functies straks test.

Deelprobleem 1 doen we hieronder samen voor. Daarna schrijf je 2, 3 en 4 zelf, in die volgorde, want elke stap gebruikt de vorige. De koppen hieronder nummeren die drie opnieuw: deelprobleem 2 is stap 1, deelprobleem 3 is stap 2 en deelprobleem 4 is stap 3.

Voorgedaan: kan deze korrel zakken?¶

Drie dingen moeten kloppen voordat een korrel kan zakken: er ligt een korrel, hij ligt niet op de bodem, en de cel eronder is leeg. Elk van die drie is één regel code. De functie kijkt naar het bord zoals het op dat moment is; ze houdt geen rekening met korrels die straks nog gaan zakken.

Voer de cel uit en controleer dat de vier assertions slagen. De vier gevallen zijn met opzet gekozen: een korrel met ruimte, een lege cel, een korrel op een korrel, en een korrel op de bodem.

def can_fall(board, row, col):
    """Geeft True als de korrel op (row, col) één rij omlaag kan."""
    if board[row][col] == 0:
        return False
    if row == len(board) - 1:
        return False
    return board[row + 1][col] == 0


bord = [[1, 0, 1], [0, 0, 1], [0, 1, 0]]
assert can_fall(bord, 0, 0)  # korrel met een lege cel eronder
assert not can_fall(bord, 0, 1)  # hier ligt geen korrel
assert not can_fall(bord, 0, 2)  # de plek eronder is bezet
assert not can_fall(bord, 2, 1)  # de bodem

Stap 1: laat één korrel zakken¶

Schrijf drop_grain(board, row, col), die de korrel op die positie één rij omlaag verplaatst.

voor	aanroep	na
`[[0, 1, 0], [0, 0, 0]]`	`drop_grain(bord, 0, 1)`	`[[0, 0, 0], [0, 1, 0]]`

Hint. Verplaatsen is twee toewijzingen: de oude plek wordt 0 en de plek eronder wordt 1. Je hoeft hier niet te controleren of het mag: dat doet straks de aanroeper, met can_fall. Een functie die niets teruggeeft heeft ook geen return nodig.

# schrijf hier drop_grain, met een docstring van één regel

bord = [[0, 1, 0], [0, 0, 0]]
drop_grain(bord, 0, 1)
assert bord == [[0, 0, 0], [0, 1, 0]]

Stap 2: één tijdstap over het hele bord¶

Schrijf fall_once(board), die elke korrel die kan zakken precies één rij laat zakken. Gebruik can_fall en drop_grain; samen zijn ze de tijdstap.

Hier zit de ontwerpvraag van vandaag. can_fall kijkt naar het bord zoals het op dat moment is, en jij verandert dat bord terwijl je erdoorheen loopt. De volgorde waarin je de rijen doorloopt bepaalt dus de uitkomst. Probeer het eerst van boven naar beneden en kijk wat de testcel zegt.

Hint. Loop met twee geneste lussen over rijen en kolommen. Wil je een lus die achteruit loopt, dan geeft range je die met een negatieve stap: range(start, stop, stap). Let op de ondergrens: stop doet zelf niet mee, dus wil je rij 0 ook langs, dan moet stop op -1 staan en niet op 0.

De testcel controleert drie dingen: één losse korrel zakt één rij en niet meteen naar de bodem, een stapel van twee korrels schuift als geheel omlaag, en het bord uit de tabel hierboven wordt precies de tijdstap die daar staat.

# schrijf hier fall_once, met een docstring van één regel

bord = [[1, 0], [0, 0], [0, 0], [0, 0]]
fall_once(bord)
assert bord == [[0, 0], [1, 0], [0, 0], [0, 0]]

stapel = [[1, 0], [1, 0], [0, 0]]
fall_once(stapel)
assert stapel == [[0, 0], [1, 0], [1, 0]]

voorbeeld = [[1, 0, 1], [0, 0, 1], [0, 1, 0]]
fall_once(voorbeeld)
assert voorbeeld == [[0, 0, 0], [1, 0, 1], [0, 1, 1]]

Stap 3: doorgaan tot er niets meer beweegt¶

Schrijf settle(board), die tijdstappen blijft uitvoeren tot geen enkele korrel meer kan zakken.

Je weet niet van tevoren hoeveel tijdstappen dat zijn, dus een for-lus met een vast aantal werkt niet. Je moet na elke tijdstap kunnen zien of er nog iets is veranderd, en daarvoor heb je het bord van vóór die tijdstap nodig. board verandert op zijn plek, dus een tweede naam voor hetzelfde bord helpt je niet: je hebt een onafhankelijke kopie nodig. Die krijg je van copy_board hieronder, die je overneemt zoals ze er staat. Je kent haar al: het is de kopie die je in opdracht 3 van de opstap hebt gemaakt, nu met een naam eromheen.

Hint. Bewaar vóór elke tijdstap een kopie in previous en herhaal zolang board != previous. Begin met een previous die zeker niet gelijk is aan het bord, bijvoorbeeld de lege lijst.

def copy_board(board):
    """Geeft een nieuw bord terug met voor elke rij een nieuwe lijst."""
    result = []
    for row in board:
        result = result + [row[:]]
    return result


# schrijf hier settle, met een docstring van één regel

bord = [[1, 0, 1], [0, 0, 0], [1, 0, 0]]
settle(bord)
assert bord == [[0, 0, 0], [1, 0, 0], [1, 0, 1]]

settle(bord)
assert bord == [[0, 0, 0], [1, 0, 0], [1, 0, 1]]

Wat je hier hebt gedaan¶

Je hebt een probleem opgeknipt voordat je code schreef. Elk deelprobleem kreeg eerst een naam, een invoer en een uitvoer, en pas daarna een functie. Je hield daardoor vier kleine functies over in plaats van één grote, en je kon ze afzonderlijk testen.

Twee dingen om mee te nemen. Het eerste: de volgorde waarin je een bord doorloopt is onderdeel van het algoritme. can_fall en drop_grain waren allebei goed, en tóch was de tijdstap fout zolang je van boven naar beneden liep. Van onder naar boven klopt het wél, en dat is geen toeval: de rij onder een korrel is dan al afgehandeld, dus de korrel die daar lag is al gezakt als hij kon zakken. De cel onder hem is op dat moment dus leeg in precies de gevallen waarin de regel zegt dat hij mag zakken, en can_fall geeft dan het antwoord dat de regel bedoelt.

Het tweede: een functie die het bord verandert, test je anders dan een functie die iets teruggeeft. Je kijkt na afloop naar het bord zelf.

In de basis van deze week doe je het omgekeerde. Daar bereken je een volgende rastertoestand in een nieuw bord en laat je het invoerbord met rust, en een assertion bewaakt dat. Wanneer je muteert en wanneer je iets nieuws opbouwt is de keuze die deze week draagt; hier heb je de ene kant gezien, in de basis de andere.