Python code bij Chomp
Je kunt de code ook hier vinden als Jupyter notebook.
"""Python programma bij "Een wiskundige doet de afwas 18 -- Chocolade eten: analyse"
Pythagoras, 63ste jaargang, nummer 6, juni 2024
Auteur: Tom Verhoeff, TU Eindhoven
In Python >= 3.9 kan `@lru_cache(maxsize=None)` vervangen worden door `@cache`.
in Python >= 3.9 kunnen de type hints in de functie aanhef opgenomen worden.
"""
from functools import lru_cache # vanaf Python 3.2
# from functools import cache # vereist Python >=3.9
from typing import Any, Union, Optional, Iterator
import doctest
# types
SpelToestand = tuple[int, ...] # for blok: SpelToestand: all(row > 0 for row in blok)
Zet = Union[tuple[()], tuple[int, int]]
def is_blok_legaal(blok):
# type: (SpelToestand) -> bool
"""Bepaal of blok een legale Chomp speltoestand is.
>>> is_blok_legaal(())
True
>>> is_blok_legaal((1,))
True
>>> is_blok_legaal((0,))
False
>>> is_blok_legaal((1, 0))
False
>>> is_blok_legaal((1, 2))
False
"""
return (all(n > 0 for n in blok) and
all(a >= b for a, b in zip(blok, blok[1:])))
def start_blok(m, n):
# type: (int, int) -> SpelToestand
"""Construeer een vol m x n blok.
>>> start_blok(0, 0)
()
>>> start_blok(1, 1)
(1,)
>>> start_blok(2, 3)
(3, 3)
"""
return m * (n,)
def str_blok(blok):
# type: (SpelToestand) -> str
"""Converteer blok naar een string.
>>> print(str_blok(start_blok(1, 1)))
##
>>> print(str_blok(start_blok(2, 3)))
##[][]
[][][]
>>> print(str_blok((5, 3, 1, 1)))
##[][][][]
[][][]
[]
[]
>>> print(str_blok(()))
.
"""
if blok:
return '\n'.join(
('[]' if index else '##') + (n - 1) * '[]'
for index, n in enumerate(blok)
if n > 0
)
else:
return '.'
def is_legale_zet(blok, zet):
# type: (SpelToestand, Zet) -> bool
"""Bepaal of zet een legale zet is voor blok.
>>> is_legale_zet(start_blok(1, 1), (-1, 0))
False
>>> is_legale_zet(start_blok(1, 1), (0, -1))
False
>>> is_legale_zet(start_blok(1, 1), (0, 1))
False
>>> is_legale_zet(start_blok(1, 1), (1, 0))
False
>>> is_legale_zet(start_blok(1, 1), (0, 0))
True
>>> is_legale_zet(start_blok(2, 3), (1, 2))
True
>>> is_legale_zet((), ())
True
>>> is_legale_zet(start_blok(1, 1), ())
False
"""
if not zet: # zet == ()
return not bool(blok) # blok == ()
m, n = zet
return 0 <= m < len(blok) and 0 <= n < blok[m]
def alle_zetten(blok):
# type: (SpelToestand) -> Iterator[Zet]
"""Lever 1-voor-1 alle zetten voor blok.
>>> print(*alle_zetten(()))
<BLANKLINE>
>>> print(*alle_zetten(start_blok(1, 1)))
(0, 0)
>>> print(*alle_zetten(start_blok(2, 3)))
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2)
>>> print(*alle_zetten((3, 2)))
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1)
"""
for rij, n in enumerate(blok): # n > 0
for kolom in range(n):
yield rij, kolom
def chomp(blok, zet):
# type: (SpelToestand, Zet) -> SpelToestand
"""Neem hap uit blok.
Aanname: is_legale_zet(blok, zet)
>>> chomp(start_blok(1, 1), (0, 0))
()
>>> chomp(start_blok(2, 2), (1, 1))
(2, 1)
>>> chomp(start_blok(2, 2), (1, 0))
(2,)
"""
rij, kolom = zet
return tuple(n if r < rij or n < kolom else kolom
for r, n in enumerate(blok)
if r < rij or 0 < kolom
)
@lru_cache(maxsize=None) # onthoud vorige resultaten; gaat sneller maar kost meer geheugen
def winnende_zet(blok):
# type: (SpelToestand) -> Optional[Zet]
"""Bepaal een winnende zet, indien mogelijk, en anders retourneer None.
>>> print(winnende_zet(()))
()
>>> print(winnende_zet(start_blok(1, 1)))
None
>>> print(winnende_zet(start_blok(1, 2)))
(0, 1)
>>> print(winnende_zet(start_blok(2, 3)))
(1, 2)
>>> print(winnende_zet((2, 1)))
None
"""
# print(sum(blok) * ' ', repr(str_blok(blok)))
if not blok: # leeg blok
return () # reeds gewonnen door niets te doen
for zet in alle_zetten(blok):
nieuw_blok = chomp(blok, zet)
# print(sum(blok) * ' ', 'beschouw', zet, '->', repr(str_blok(nieuw_blok)))
# print(winnende_zet(nieuw_blok))
if winnende_zet(nieuw_blok) is None:
return zet
return None
def alle_winnende_zetten(blok):
# type: (SpelToestand) -> Iterator[Zet]
"""Lever 1-voor-1 alle winnende zetten.
>>> print(*alle_winnende_zetten(start_blok(1, 1)))
<BLANKLINE>
>>> print(*alle_winnende_zetten(start_blok(2, 2)))
(1, 1)
>>> print(*alle_winnende_zetten(start_blok(8, 10)))
(3, 8) (4, 5)
"""
if not blok:
yield ()
for zet in alle_zetten(blok):
nieuw_blok = chomp(blok, zet)
if winnende_zet(nieuw_blok) is None:
yield zet
def main():
# Kies via "uitcommentariëren" welke functie je wilt aanroepen
# 1
print("Voer alle doctests in de docstrings uit.")
doctest.testmod(verbose=True)
print()
# 2
print("Analyseer wat kleine blokken, met visuele uitvoer.")
for m in range(1, 5 + 1):
for n in range(m, 6 + 1):
blok = start_blok(m, n)
winner = winnende_zet(blok)
print()
print(m, 'x', n, winner)
if winner:
print(str_blok(chomp(blok, winner)))
print()
# 3
print("Bepaal alle winnende zetten voor blokken tot 12x12.")
print("(Dit duurt wat langer.)")
for m in range(1, 12 + 1):
for n in range(m, 12 + 1):
print(f"{m:2} x {n:2}", *alle_winnende_zetten(start_blok(m, n)))
print("Bij de blokken 8x10 en 9x10 is er meer dan één winnende zet.")
print()
# 4
print("Bepaal alle winnende zetten voor blokken 3 x n t/m n = 30.")
for m in range(3, 3 + 1):
for n in range(1, 30 + 1):
print(f"{m:2} x {n:2}", *alle_winnende_zetten(start_blok(m, n)))
print("Ze zijn allemaal uniek.")
print("Kun je hier een patroon in vinden?")
print()
# 5
print("Bepaal afmeting van winnende zet voor blokken 3 x n t/m n = 30.")
for m in range(3, 3+1):
for n in range(1, 30+1):
blok = start_blok(m, n)
winner = winnende_zet(blok)
print(m, 'x', n, winner)
print(f"afmeting van winnende zet: {m - winner[0]}x{n - winner[1]}")
# print(str_blok(chomp(blok, winner)))
if __name__ == '__main__':
main()