Galgje is een spel voor twee spelers dat met potlood en papier kan gespeeld worden. Eén van de spelers denkt aan een bepaald woord, dat de andere speler moet raden door telkens een nieuwe letter te suggereren. Om het woord te kunnen raden, krijgt die speler een patroon te zien dat initieel bestaat uit een reeks underscores (_). Hierbij stelt elke underscore een letter van het woord voor. Het aantal underscores in het patroon komt dus overeen met de lengte van het te raden woord.

Als de speler die het woord moet raden een letter suggereert die in het woord voorkomt, dan moet de andere speler de letter in het patroon invullen op alle open posities (aangegeven door underscores) waar de letter in het woord voorkomt. Als de gesuggereerde letter niet in het woord voorkomt, dan moet de andere speler een volgende stok tekenen van een stokfiguur die een galg met daaraan een hangend mannetje voorstelt. De speler die het woord moest raden, wint als hij alle letters van het woord heeft gevonden voordat de andere speler alle stokken van de stokfiguur getekend heeft. Anders wint de speler die het woord in gedachten hield.

Opgave

Implementeer de speler van een spelletje galgje die een woord in gedachten moet houden. Hierbij beschouwen we enkel woorden die bestaan uit kleine letters. De speler gebruikt echter een bedriegelijke strategie die het de andere speler zo moeilijk mogelijk maakt om het spel te winnen. Het idee achter deze strategie is zeer eenvoudig. In plaats van bij aanvang van het spelletje een vast woord van een bepaalde lengte $$n$$ te kiezen, beschouwt de speler initieel alle woorden van lengte $$n$$ als mogelijke kandidaten. Telkens wanneer de andere speler een nieuwe letter suggereert, werkt hij het patroon zo bij dat er zo veel mogelijk kandidaten overblijven die consistent zijn met het vorige patroon en alle gesuggereerde letters. Concreet ga je bij de implementatie als volgt te werk:

• Schrijf een functie kandidaat waaraan drie argumenten moeten doorgegeven worden: i) een woord (str; bevat enkel kleine letters), een patroon (str) dat reeds deels kan ingevuld zijn (bevat enkel underscores en kleine letters), en iii) de (kleine) letters (str) die reeds gesuggereerd werden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of het woord consistent is met het patroon en alle letters die reeds gesuggereerd werden. Dat is het geval als het woord dezelfde lengte heeft als het patroon, en elke positie van het patroon ofwel een letter bevat die gelijk is aan de overeenkomstige letter van het woord en voorkomt in de reeds gesuggereerde letters, ofwel een underscore bevat en de overeenkomstige letter van het woord niet voorkomt in de reeds gesuggereerde letters.

• Schrijf een functie aanvullen waaraan drie argumenten moeten doorgegeven worden: i) een woord (str; bevat enkel kleine letters), een patroon (str) dat reeds deels kan ingevuld zijn (bevat enkel underscores en kleine letters), en iii) een kleine letter (str). Hierbij mag de functie ervan uitgaan dat het gegeven woord een kandidaat is voor het gegeven patroon. De functie moet een nieuw patroon (str) teruggeven, dat bestaat uit het gegeven patroon dat verder werd aangevuld met alle voorkomens van de gegeven letter in het gegeven woord.

• Schrijf een functie kiezen waaraan drie argumenten moeten doorgegeven worden: i) een patroon (str) dat reeds deels kan ingevuld zijn (bevat enkel underscores en kleine letters), ii) de (kleine) letters (str) die reeds gesuggereerd werden (waarbij je er mag van uitgaan dat alle letters in het patroon in deze reeks letters voorkomen), en iii) een (kleine) letter (str) die niet eerder gesuggereerd werd. De functie mag ervan uitgaan dat de huidige directory een tekstbestand woorden.txt¹ bevat, dat bestaat uit een reeks woorden (enkel kleine letters) die elk op een afzonderlijke regel staan. De functie moet eerst voor alle overblijvende kandidaten (de woorden uit het bestand woorden.txt² die consistent zijn met het gegeven patroon en de reeds gesuggereerde letters (tweede argument)) een nieuw patroon bepalen dat bestaat uit het gegeven patroon aangevuld met de nieuw gesuggereerde letter (derde argument). Daarna moet de functie een tuple met twee strings (str) teruggeven. De eerste string bevat het nieuwe patroon dat in de vorige stap het vaakst bepaald werd. De tweede string is een willekeurig gekozen woord uit het bestand woorden.txt³ dat consistent is met het geselecteerde nieuwe patroon (eerste string van het tuple) en alle gesuggereerde letters (zowel de letters uit het tweede argument als de letter uit het derde argument).

Voorbeeld

>>> kandidaat('appel', '_pp_l', 'klmnop')
True
>>> kandidaat('appels', '_pp_l', 'klmnop')
False
>>> kandidaat('appel', '_pp_l', 'p')
False
>>> kandidaat('appel', '_pp_l', 'apl')
False
>>> kandidaat('appel', '__p_l', 'klmnop')
False
>>> kandidaat('appel', '_kp_l', 'klmnop')
False
>>> kandidaat('angel', '_pp_l', 'klmnop')
False

>>> aanvullen('appel', '_pp__', 'p')
'_pp__'
>>> aanvullen('appel', '_pp__', 'l')
'_pp_l'
>>> aanvullen('appel', '_pp_l', 'x')
'_pp_l'

>>> kiezen('_pp_l', 'klmnop', 'a')
('app_l', 'appel')
>>> kiezen('a___l', 'al', 'p')
('a___l', 'angel')
>>> kiezen('a___l', 'abcdefghijkl', 'p')
('a_p_l', 'ampul')
>>> kiezen('_pp_l', 'klmnop', 'x')
('_pp_l', 'appel')
>>> kiezen('_____', '', 'x')
('_____', 'angel')