Ga naar hoofdinhoud

Zelf bouwen — speel de zetten na

Hier bouw je op verder

Leerdoel: je gebruikt de zettenlijst om de toestand van de drie palen bij te houden, en controleert dat de toren echt op doel belandt.

De uitdaging​

Je hanoi-functie geeft een lijst zetten, maar klopt die ook? Speel de zetten na en kijk waar de schijven eindigen.

Elke paal is een lijst van schijfgroottes, met de grootste onderaan (index 0) en de bovenste schijf achteraan:

# 3 schijven, alles op paal A:
{"A": [3, 2, 1], "B": [], "C": []}

Schrijf speel(n): begin met alle schijven op A, loop door de zetten van hanoi(n, "A", "C", "B"), en verplaats telkens de bovenste schijf van de bron-paal naar de doel-paal. Geef de eindtoestand terug.

Tip

"De bovenste schijf van een lijst pakken en op een andere leggen" is precies wat .pop() en .append(...) doen.

Bouw en test​

Python
Code-omgeving wordt voorbereid…
Antwoord
def speel(n):
    palen = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    for bron, doel in hanoi(n, "A", "C", "B"):
        schijf = palen[bron].pop()      # bovenste schijf van bron
        palen[doel].append(schijf)      # bovenop doel
    return palen

Omdat hanoi klopt, ligt aan het eind alles op C in de juiste volgorde, en heb je onderweg nooit een grotere schijf op een kleinere gelegd.

Uitdaging (optioneel)​

Bij welke zet komt de grootste schijf op doel? Schrijf grootste_op_doel(n) die het nummer van die zet teruggeeft, en print het voor 1 tot en met 5 schijven naast het totale aantal zetten. Zie je een patroon?

Tip

De grootste schijf is schijf n. In de lus van speel weet je na de .pop() welke schijf je net hebt opgepakt. Een nummer voor elke zet krijg je van enumerate(..., start=1), zoals op de compleet-pagina.

Antwoord
def hanoi(n, bron, doel, hulp):
    if n == 0:
        return []
    zetten = []
    zetten += hanoi(n - 1, bron, hulp, doel)
    zetten.append((bron, doel))
    zetten += hanoi(n - 1, hulp, doel, bron)
    return zetten


def grootste_op_doel(n):
    palen = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    for nummer, (bron, doel) in enumerate(hanoi(n, "A", "C", "B"), start=1):
        schijf = palen[bron].pop()
        palen[doel].append(schijf)
        if schijf == n:
            return nummer


for n in range(1, 6):
    print(f"n={n}: zet {grootste_op_doel(n)} van de {2 ** n - 1}")
n=1: zet 1 van de 1
n=2: zet 2 van de 3
n=3: zet 4 van de 7
n=4: zet 8 van de 15
n=5: zet 16 van de 31

Zodra je schijf n oppakt, is dat de zet die hem op doel legt; de functie stopt daar met return. De grootste schijf gaat steeds precies in het midden, bij zet 2ⁿ⁻¹ van de 2ⁿ − 1: eerst de 2ⁿ⁻¹ − 1 zetten voor de toren erboven, dan de grootste.

Door naar fouten →.