Mudcraft is een vrij verslavend computerspel dat gespeeld wordt op een kaart met 19 zeshoekige gebieden. Aanvankelijk zijn alle gebieden "modder" (bruin).

De spelregels zijn zeer eenvoudig:

• Als je op een moddergebied klikt, dan wordt het "bos" (groen), en worden alle aangrenzende gebieden omgedraaid (dat wil zeggen: modder wordt bos en omgekeerd).

• Als je op een bosgebied klikt, dan blijft het bos, en worden alle aangrenzende gebieden omgedraaid (dat wil zeggen: modder wordt bos en omgekeerd).

Als je bijvoorbeeld vanaf de startkaart op het middelste gebied klikt, dan krijg je een kaart met 7 bosgebieden en 12 moddergebieden. Als je vervolgens op een gebied in een hoek klikt — bijvoorbeeld linksboven — dan krijg je een kaart met 9 bosgebieden en 10 moddergebieden, omdat bij de tweede klik drie moddergebieden in bos veranderen en één bosgebied weer modder wordt.

Wat is het minimaal aantal keer dat je moet klikken om de startkaart (waarop alle gebieden modder zijn) om te zetten naar deze kerstboom-kaart?

Is het mogelijk om de kerstboom-kaart terug om te zetten naar de startkaart met hetzelfde aantal keer klikken?

 Antwoord weergeven

Zes keer klikken is voldoende (en nodig) om de startkaart met alleen maar moddergebieden om te zetten naar de kerstboom-kaart. Het is echter niet mogelijk om terug te keren naar de kaart met alleen maar moddergebieden, ongeacht het aantal keer dat je klikt.

Hieronder beschrijven we een mogelijke denkpiste die je kunt volgen om een oplossing met zes keer klikken te vinden. Daarvoor helpt het om de gebieden in de leesrichting (van links naar rechts, en van boven naar beneden) te nummeren van 1 tot en met 19.

Eerst en vooral is het belangrijk om te onderstrepen dat het zeker mogelijk is om de kaart met alleen maar moddergebieden om te zetten naar de kerstboom-kaart. Twee keer na elkaar klikken op een moddergebied heeft immers als netto-effect dat enkel dat gebied verandert in een bosgebied, omdat alle aangrenzende gebieden twee keer omgedraaid worden. De kerstboom-kaart kan dus met 22 keer klikken gegenereerd worden uit de startkaart, door eenvoudigweg twee keer te klikken op elke van de 11 gewenste bosgebieden. Deze strategie is natuurlijk verre van optimaal, maar ze laat wel zien dat er een oplossing mogelijk is.

Deze strategie kan onmiddellijk verbeterd worden tot slechts negen keer klikken, door op te merken dat de zeven centrale gebieden van de kaart (zijnde 5, 6, 9, 10, 11, 14 en 15 volgens het voorgestelde nummeringsschema) allemaal deel uitmaken van de "kerstboom". Ze kunnen dus allemaal tegelijkertijd van modder naar bos omgezet worden door één klik op het centrale gebied (10). De volledige transformatie kan dus bekomen worden door negen keer te klikken (bijvoorbeeld 2, 2, 13, 13, 16, 16, 18, 18, 10). Deze volgorde zorgt ervoor dat vier gebieden (2, 13, 16 en 18) één voor één in bos veranderen, waarna de zeven resterende bosgebieden bekomen worden door een laatste klik op het centrale gebied (10).

Deze strategie kan nog verder geoptimaliseerd worden als we bedenken dat vanaf de startpositie met alleen maar moddergebieden, de gebieden 13, 16 en 18 naar bos kunnen omgezet worden (terwijl alle andere gebieden modder blijven) door achtereenvolgens de volgende drie klikken uit te voeren: 17, 19 en 18. Deze truc bespaart drie klikken ten opzichte van de negen-keer-klikken strategie die we in de vorige paragraaf hebben besproken, en ze geeft ons de volgende zes-keer-klikken oplossing voor de puzzel: 2, 2, 17, 19, 18, 10. Net als bij de negen-keer-klikken oplossing hierboven, zorgt deze oplossing ervoor dat enkel de gebieden 2, 13, 16 en 18 naar bos omgezet worden, voordat de resterende zeven gebieden in één keer naar bos omgezet worden.

Er zijn meerdere alternatieve oplossingen om in zes keer klikken de kerstboom-kaart te vormen: 120 om precies te zijn. Door met een computer exhaustief alle mogelijkheden te proberen of aan de hand van een ingewikkeld wiskundig bewijs kan aangetoond worden dat er geen oplossingen zijn met minder dan zes keer klikken.

We beantwoorden ten slotte ook nog naar de tweede vraag die gesteld werd: het is niet mogelijk om de kerstboom-kaart terug om te zetten naar de oorspronkelijke kaart met alleen maar moddergebieden. Niet in zes keer klikken en ook niet in om het even hoeveel keer klikken. Volgens de spelregels is het laatste gebied waarop geklikt wordt automatisch een bosgbied, of het nu modder of bos was voor er op geklikt werd.

Als we deze observatie combineren met de eerder genoemde "dubbelklik" eigenschap, dan zien we dat Mudcraft de verrassende eigenschap heeft dat het mogelijk is om een kaart met alleen maar moddergebieden te transformeren naar elke andere kaart die je maar wil, maar dat het onmogelijk is om terug te keren.

Opgave

We nummeren de 19 gebieden van Mudcraft in de leesrichting (van links naar rechts, en van boven naar beneden) van 1 tot en met 19.

Definieer een klasse Mudcraft waarmee we Mudcraft-kaarten kunnen voorstellen en manipuleren. Bij het aanmaken van een nieuwe kaart (Mudcraft) moeten nul of meer gehele getallen (int) tussen 1 en 19 (grenzen inbegrepen) doorgegeven worden. Dit zijn de nummers van de bosgebieden op de kaart bij aanvang van het spel. De andere gebieden zijn modder bij aanvang van het spel. Als er geen argumenten doorgegeven worden, dan bevat de startkaart dus enkel moddergebieden. Het is toegelaten dat hetzelfde nummer meerdere keren doorgegeven wordt, maar dat heeft geen effect.

Als er een kaart $$k$$ (Mudcraft) wordt doorgegeven aan de ingebouwde functie repr, dan moet die een beschrijving (str) van kaart $$k$$ teruggeven die leest als een Python expressie om een nieuwe kaart (Mudcraft) aan te maken met bij aanvang dezelfde modder- en bosgebieden die momenteel op kaart $$k$$ staan. Daarbij moeten de nummers van de bosgebieden in stijgende volgorde en zonder dubbels opgelijst worden.

Als er een kaart $$k$$ (Mudcraft) wordt doorgegeven aan de ingebouwde functie str, dan moet die een beschrijving (str) van kaart $$k$$ teruggeven die een vaste structuur heeft waarin moddergebieden worden voorgesteld als een punt (.) en bosgebieden als een hekje (#). Voor de vaste structuur verwijzen naar onderstaand voorbeeld, waarbij we opmerken dat er nooit spaties staan op het einde van een regel in die stringvoorstelling.

Als er een kaart $$k$$ (Mudcraft) wordt doorgegeven aan de ingebouwde functies list, tuple of set, dan moeten die resp. een lijst (list), een tuple en een verzameling (set) teruggeven met de nummers (int) van de bosgebieden. In het geval van een lijst (list) en een tuple moeten de nummers van de bosgebieden in stijgende volgorde en zonder dubbels opgelijst worden.

Op een kaart $$k$$ (Mudcraft) moet je minstens de volgende methoden kunnen aanroepen:

• Een methode modder waaraan het nummer $$n$$ (int) van een gebied moet doorgegeven worden. De methode moet gebied $$n$$ op kaart $$k$$ omzetten naar modder, en een verwijzing naar kaart $$k$$ teruggeven.

• Een methode bos waaraan het nummer $$n$$ (int) van een gebied moet doorgegeven worden. De methode moet gebied $$n$$ op kaart $$k$$ omzetten naar bos, en een verwijzing naar kaart $$k$$ teruggeven.

• Een methode omdraaien waaraan het nummer $$n$$ (int) van een gebied moet doorgegeven worden. De methode moet gebied $$n$$ op kaart $$k$$ omdraaien (modder wordt bos en omgekeerd), en een verwijzing naar kaart $$k$$ teruggeven.

• Een methode buren waaraan het nummer $$n$$ (int) van een gebied moet doorgegeven worden. De methode moet een verzameling (set) teruggeven met de nummers (int) van alle gebieden op kaart $$k$$ die grenzen aan gebied $$n$$.

• Een methode klik waaraan het nummer $$n$$ (int) van een gebied moet doorgegeven worden. De methode moet de spelregels van Mudcraft toepassen als op gebied $$n$$ op kaart $$k$$ geklikt wordt, en een verwijzing naar kaart $$k$$ teruggeven.

De klasse Mudcraft mag ervan uitgaan dat er enkel geldige nummers van gebieden aan de methoden doorgegeven worden (gehele getallen tussen 1 en 19, grenzen inbegrepen), zonder dat dit expliciet moet gecontroleerd worden.

Voorbeeld

>>> bord = Mudcraft()
>>> bord
Mudcraft()
>>> print(bord)
  . . .
 . . . .
. . . . .
 . . . .
  . . .
>>> set(bord)
set()
>>> bord.buren(1)
{2, 4, 5}
>>> bord.buren(10)
{5, 6, 9, 11, 14, 15}
>>> bord.buren(16)
{11, 19, 12, 15}
>>> bord.bos(10)
Mudcraft(10)
>>> print(bord)
  . . .
 . . . .
. . # . .
 . . . .
  . . .
>>> bord.modder(10)
Mudcraft()
>>> print(bord)
  . . .
 . . . .
. . . . .
 . . . .
  . . .
>>> bord.omdraaien(10)
Mudcraft(10)
>>> print(bord)
  . . .
 . . . .
. . # . .
 . . . .
  . . .
>>> bord.omdraaien(10)
Mudcraft()
>>> print(bord)
  . . .
 . . . .
. . . . .
 . . . .
  . . .
>>> bord.klik(2)
Mudcraft(1, 2, 3, 5, 6)
>>> print(bord)
  # # #
 . # # .
. . . . .
 . . . .
  . . .
>>> bord.klik(2)
Mudcraft(2)
>>> print(bord)
  . # .
 . . . .
. . . . .
 . . . .
  . . .
>>> bord.klik(17)
Mudcraft(2, 13, 14, 17, 18)
>>> print(bord)
  . # .
 . . . .
. . . . .
 # # . .
  # # .
>>> bord.klik(19)
Mudcraft(2, 13, 14, 15, 16, 17, 19)
>>> print(bord)
  . # .
 . . . .
. . . . .
 # # # #
  # . #
>>> bord.klik(18)
Mudcraft(2, 13, 16, 18)
>>> list(bord)
[2, 13, 16, 18]
>>> print(bord)
  . # .
 . . . .
. . . . .
 # . . #
  . # .
>>> bord.klik(10)
Mudcraft(2, 5, 6, 9, 10, 11, 13, 14, 15, 16, 18)
>>> tuple(bord)
(2, 5, 6, 9, 10, 11, 13, 14, 15, 16, 18)
>>> print(bord)
  . # .
 . # # .
. # # # .
 # # # #
  . # .

>>> Mudcraft(2, 13).bos(16).omdraaien(18).klik(10).modder(10)
Mudcraft(2, 5, 6, 9, 11, 13, 14, 15, 16, 18)
>>> print(Mudcraft(2, 13).bos(16).omdraaien(18).klik(10).modder(10))
  . # .
 . # # .
. # . # .
 # # # #
  . # .