Python code bij Schildpadden redden
Je kunt de code ook als Jupyter notebook downloaden
"""Python programma bij "Een wiskundige doet de afwas 16 -- Schildpadden redden: analyse"
Pythagoras, 63ste jaargang, nummer 4, februari 2023
Auteur: Tom Verhoeff, TU Eindhoven
In Python >= 3.9, `@lru_cache(maxsize=None)` kan vervangen worden door `@cache`.
De type hints kunnen in Python >= 3.9 in de functie aanhef opgenomen worden.
"""
from functools import lru_cache # vanaf Python 3.2
# from functools import cache # vereist Python 3.9
import datetime as dt
from collections import Counter
@lru_cache(maxsize=None) # onthoud vorige resultaten; gaat sneller maar kost meer geheugen
def analyseer_1(bord):
# type: (str) -> tuple[str, str]
"""Bepaal uitslag voor eerste speler wanneer die begint met `bord`,
door alle mogelijkheden na te gaan. Dit is niet efficiënt
In geval van winst 'W', geef ook een zet die dat bereikt.
Verlies wordt aangegeven met 'X'.
De aanname is dat beide spelers optimaal spelen.
"""
if 'X' not in bord:
return 'X', ''
beste_uitslag, beste_zet = 'X', '' # voor als we niets beters vinden
mutable_bord = list(bord)
for i, schildpad in enumerate(bord):
if schildpad == 'X':
mutable_bord[i] = 'O'
for j in range(-1, i):
if j >= 0:
mutable_bord[j] = 'O' if bord[j] == 'X' else 'X'
uitslag, zet = analyseer_1(''.join(mutable_bord))
if j >= 0:
mutable_bord[j] = bord[j]
if uitslag == 'X': # 2e speler verliest, hoe dan ook; 1e speler kan dus winnen
return 'W', f"{i + 1} {j + 1 if j >= 0 else ''}"
mutable_bord[i] = 'X'
return beste_uitslag, beste_zet
def maak_tabel(n_max, analyseer):
# type: (int, Callable[[str], tuple[str, str]]) -> None
""""Druk tabel af met uitslagen voor borden met alleen X t/m n_max.
"""
start_alle = dt.datetime.now()
for n in range(n_max+1):
print(f"{n:2}", end=': ')
if hasattr(analyseer, 'cache_clear'):
analyseer.cache_clear() # type: ignore
start = dt.datetime.now()
print(analyseer(n * 'X'), dt.datetime.now() - start, end=' ')
if hasattr(analyseer, 'cache_info'):
print(analyseer.cache_info()) # type: ignore
else:
print()
print("Totale looptijd:", dt.datetime.now() - start_alle)
HARD_OP = True # Laat wel/niet extra informatie afdrukken
def analyseer_2(bord):
# type: (list[int]) -> tuple[str, str]
"""Bepaal uitslag voor eerste speler wanneer die begint met `bord`,
via het algoritme van Pi, door Schildpadden redden te zien als Nim spel.
In geval van winst 'W', geef ook een zet die dat bereikt.
Verlies wordt aangegeven met 'X'.
De aanname is dat beide spelers optimaal spelen.
"""
def splits(n):
# type: (int) -> list[int]
"""Splits getal in verschillende groepjes via herhaald samenvoegen van gelijke.
"""
g = 1 # grootte van de n nog losse groepjes
groepjes = [] # bekende groepjes die uniek zijn
# invariant: oorspronkelijke n == sum(groepjes) + n * g
while n > 0:
if n % 2 == 1: # dan is er een groepje dat niet meer samengevoegd kan worden
groepjes.append(g)
n = n - 1
g, n = 2 * g, n // 2
return groepjes
def splits_alle(bord):
# type: (list[int]) -> list[list[int]]
"""Splits alle posities van schildpadden die op hun rug liggen.
"""
result = [] # type: list[list[int]]
for i, schildpad in enumerate(bord, 1):
if schildpad == 'X':
result.append(splits(i))
return result
def nim_som(alle_groepjes):
# type: (list[list[int]]) -> list[int]
"""Bepaal alle groepjes die een oneven aantal keer voorkomen.
"""
counts = Counter(groepje for groepjes in alle_groepjes for groepje in groepjes)
return [groepje for groepje, count in counts.items() if count % 2 == 1]
alle_groepjes = splits_alle(bord)
ns = nim_som(alle_groepjes)
if HARD_OP:
print("bord:", bord)
print("gesplitst:", alle_groepjes)
print("nim som (groepjes die oneven aantal keer voorkomen):", ns)
if not ns:
if HARD_OP:
print("elk groepje komt even aantal keer voor")
return 'X', ''
m = max(ns)
# vind schildpadden waar m als groepje in voorkomt
grootste = [sum(groepjes) for groepjes in alle_groepjes if m in groepjes]
if HARD_OP:
print("grootste groepje dat oneven aantal keer voorkomt:", m)
print("posities van schildpadden met grootste oneven groepje:", grootste)
eerste = grootste[0]
tweede = sum(nim_som([ns, splits(eerste)]))
return 'W', f"{grootste[0]} {tweede if tweede > 0 else ''}"
def winnende_zet(stapels):
# type: (list[int]) -> tuple[int, int]
"""Bepaal zet om te winnen bij Nim spel, indien mogelijk, en anders None,
via het algoritme van Phi.
Een zet is een tupel van een stapelnummer en aantal achtergelaten
"""
s = sum(stapels)
if s == 0:
return None
else:
halve_stapels = [stapel // 2 for stapel in stapels]
halve_zet = winnende_zet(halve_stapels)
if halve_zet: # niet None
i, a = halve_zet
# verdubbel deze zet en maak som even
return i, 2 * a + (s - stapels[i - 1]) % 2
else:
if s % 2: # oneven som: kies oneven stapel
for i, stapel in enumerate(stapels, 1):
if stapel % 2:
# neem 1; dat maakt de som even en laat halve_stapels invariant
return i, stapels[i - 1] - 1
else:
return None # label D
def analyseer_3(bord):
# type: (str) -> typle[str, str]
"""Bepaal uitslag voor eerste speler wanneer die begint met `bord`,
via het recursieve algoritme van Phi (zie functie `winnende_zet`).
In geval van winst 'W', geef ook een zet die dat bereikt.
Verlies wordt aangegeven met 'X'.
De aanname is dat beide spelers optimaal spelen.
"""
# Bepaal Nim spel bij het bord voor Schildpadden redden
stapels = [positie
for positie, schildpad in enumerate(bord, 1)
if schildpad == 'X'
]
zet = winnende_zet(stapels)
if zet: # niet None
i, a = zet
return 'W', f"{stapels[i - 1]} {a if a > 0 else ''}"
else:
return 'X'
def interactief(n, analyseer):
# type: (int, Callable[[str], tuple[str, str]]) -> None
"""Laat interactief een spel spelen via een opgegeven analyse functie.
Toon ook analyse resultaat (best haalbare uitslag).
"""
assert 1 <= n <= 16, f"Aantal {n} ligt niet tussen 1 en 16"
mutable_bord = n * ['X']
zet_nr = 0
bord = ''.join(mutable_bord)
print(f"zet_nr: zet | analyseer({bord!r}) -> {analyseer(bord)}")
while True:
zet_nr += 1
while True:
zet = input(f"Zet {zet_nr} (index [index])? ")
posities = zet.split()
if not (1 <= len(posities) <= 2):
print(f"Een of twee posities nodig, gescheiden door spatie")
continue
try:
posities = [int(positie) for positie in posities]
except ValueError:
print(f"Posities moeten getallen zijn")
continue
i = posities[0] - 1
if len(posities) == 2:
j = posities[1] - 1
if not (0 <= i < len(bord)):
print(f"Eerste positie {posities[0]} valt buiten het bord")
continue
if bord[i] != 'X':
print(f"Schildpad op eerste positie ligt niet op zijn rug")
continue
if len(posities) == 2 and not (0 <= j < i):
print(f"Tweede positie ligt niet op het bord links van eerste positie")
continue
break
mutable_bord[i] = 'O'
if len(posities) == 2:
mutable_bord[j] = 'O' if mutable_bord[j] == 'X' else 'X'
bord = ''.join(mutable_bord)
print(f"{zet_nr:6}: {zet:3} | analyseer({bord!r}) -> {analyseer(bord)}")
if "X" not in bord:
print(f"{2 - zet_nr % 2}e speler wint")
break
if __name__ == '__main__':
# Kies via "uitcommentariëren" welke functie je wilt aanroepen
# 1
# maak_tabel(16, analyseer_1) # kost ca. 2 seconde (op mijn laptop)
# 2
# print(analyseer_2("XXXXXX"))
# 3
# HARD_OP = False
maak_tabel(16, analyseer_2) # kost fractie van seconde (op mijn laptop)
maak_tabel(16, analyseer_3) # kost fractie van seconde (op mijn laptop)
# 4
HARD_OP = False
interactief(8, analyseer_3)