Vallende korrels¶
Canonieke uitwerking van het werkcollege. De cellen hieronder draaien in volgorde; samen vormen ze het algoritme dat in de bijeenkomst wordt opgebouwd.
Voorgedaan: kan deze korrel zakken?¶
Drie voorwaarden, in deze volgorde: er ligt een korrel, hij ligt niet op de bodem, en de cel eronder is leeg. De functie kijkt alleen naar het bord zoals het op dat moment is.
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¶
Verplaatsen is twee toewijzingen. De functie controleert niets: can_fall heeft
dat al gedaan, en die verantwoordelijkheid twee keer beleggen maakt beide
functies minder duidelijk.
def drop_grain(board, row, col):
"""Verplaatst de korrel op (row, col) één rij omlaag."""
board[row][col] = 0
board[row + 1][col] = 1
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¶
Van de onderste rij naar de bovenste. Dat is de hele ontwerpkeuze: een korrel zakt naar een rij die al is afgehandeld, en kan in dezelfde tijdstap dus niet opnieuw zakken. Loop je van boven naar beneden, dan valt één korrel in één tijdstap door tot de bodem en breekt een stapel van twee uit elkaar.
def fall_once(board):
"""Laat elke korrel die kan zakken precies één rij zakken."""
for row in range(len(board) - 1, -1, -1):
for col in range(len(board[0])):
if can_fall(board, row, col):
drop_grain(board, row, col)
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]]
De fout die de testcel vangt¶
Deze variant loopt van boven naar beneden en is daarmee fout. Ze staat hier omdat die fout het onderwerp van stap 2 is: de assertions leggen vast wát er misgaat. Eén korrel belandt meteen op de bodem, en de stapel van twee laat een gat vallen.
def fall_once_top_down(board):
"""Foute variant: doorloopt het bord van boven naar beneden."""
for row in range(len(board)):
for col in range(len(board[0])):
if can_fall(board, row, col):
drop_grain(board, row, col)
bord = [[1, 0], [0, 0], [0, 0], [0, 0]]
fall_once_top_down(bord)
assert bord == [[0, 0], [0, 0], [0, 0], [1, 0]] # door tot de bodem
stapel = [[1, 0], [1, 0], [0, 0]]
fall_once_top_down(stapel)
assert stapel == [[1, 0], [0, 0], [1, 0]] # de stapel breekt
Stap 3: doorgaan tot er niets meer beweegt¶
Het aantal tijdstappen staat niet van tevoren vast, dus de lus stopt op een
voorwaarde en niet op een teller. Om te zien of er nog iets veranderde is een
onafhankelijke kopie nodig: previous = board zou een tweede naam voor hetzelfde
bord geven en altijd gelijk blijven. De lege lijst als startwaarde is zeker
ongelijk aan het bord, zodat de lus minstens één keer draait.
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
def settle(board):
"""Laat korrels zakken tot er geen enkele meer kan zakken."""
previous = []
while board != previous:
previous = copy_board(board)
fall_once(board)
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]]