Quarto is een bordspel voor twee spelers. Het wordt gespeeld op een spelbord met 16 vakjes die gerangschikt zijn in een $$4 \times 4$$ rooster.

Spelbord van Quarto bij aanvang van een spel.

Er zijn 16 verschillende speelstukken met vier onderscheidende kenmerken, bijvoorbeeld:

grootte: groot of klein
kleur: rood of blauw
vorm: rond of vierkant
vulling: vol of hol

Kenmerken en eigenschappen kunnen verschillen tussen varianten van het spel.

Bij aanvang van het spel staan alle speelstukken naast het spelbord. De eerste speler wordt geloot. Hij kiest één van de 16 speelstukken en geeft deze aan zijn tegenstander. Deze moet het gekregen speelstuk op een van de vakjes van het spelbord zetten en vervolgens één van de 15 overgebleven speelstukken uitkiezen om aan zijn tegenstander te geven. Deze zet het speelstuk op zijn beurt op een vrij vakje van het spelbord, enzoverder.

De winnaar is de speler die als eerste een quarto vormt. Dit is een rij op het spelbord waarop vier 4 speelstukken met een gemeenschappelijke eigenschap staan. Een dergelijke rij kan horizontaal, verticaal of diagonaal gevormd worden. Het kan goed zijn dat er op een spelbord meer dan één quarto gevormd wordt, en ook dat de 4 speelstukken op eenzelfde rij meer dan één gemeenschappelijke eigenschap hebben. Als alle speelstukken op het spelbord staan zonder dat er een quarto gevormd wordt, dan eindigt het spel op een gelijkspel.

Quarto onderscheidt zich van andere borspelen doordat er maar één set van speelstukken is die door beide spelers gebruikt wordt, in plaats van een set voor de ene speler en een set voor de andere speler.

Opgave

De kenmerken en eigenschappen van de 16 speelstukken die gebruikt worden bij een spelletje Quarto worden beschreven in een tekstbestand. Elke regel van het bestand bestaat uit 5 velden die van elkaar gescheiden worden door een komma (,). De velden bevatten zelf nooit komma's. De eerste regel is een hoofding die bestaat uit een veld met het woord stuk, gevolgd door vier velden met de vier onderscheidende kenmerken van de speelstukken. Daarna volgen 16 regels die elk één speelstuk beschrijven. Het eerste veld bevat het unieke karakter waarmee het speelstuk voorgesteld wordt. De andere velden zijn de vier eigenschappen van het speelstuk voor de overeenkomstige kenmerken. Dezelfde eigenschap komt nooit bij meerdere kenmerken voor. Een dergelijk tekstbestand ziet er dan bijvoorbeeld als volgt uit:

stuk,grootte,kleur,vorm,vulling
A,groot,rood,vierkant,hol
B,klein,rood,vierkant,hol
C,groot,blauw,vierkant,hol
D,klein,blauw,vierkant,hol
E,groot,rood,rond,hol
F,klein,rood,rond,hol
G,groot,blauw,rond,hol
H,klein,blauw,rond,hol
I,groot,rood,vierkant,vol
J,klein,rood,vierkant,vol
K,groot,blauw,vierkant,vol
L,klein,blauw,vierkant,vol
M,groot,rood,rond,vol
N,klein,rood,rond,vol
O,groot,blauw,rond,vol
P,klein,blauw,rond,vol

De speelstukken die in dit tekstbestand beschreven worden hebben vier onderscheidende kenmerken: grootte, kleur, vorm en vulling. Voor het kenmerk grootte onderscheiden we twee eigenschappen: groot en klein. Voor het kenmerk kleur onderscheiden we twee eigenschappen: rood en blauw. Voor het kenmerk vorm onderscheiden we twee eigenschappen: vierkant en rond. Voor het kenmerk vulling onderscheiden we twee eigenschappen: vol en hol.

De configuratie van de speelstukken op een spelbord wordt beschreven door een string (str) van 16 karakters. Deze karakters beschrijven de speelstukken die op de vakjes van het spelbord staan, uitgelezen van boven naar onder en van links naar rechts. Een karakter dat overeenkomt met het unieke karakter van een speelstuk stelt het overeenkomstige speelstuk voor (dergelijke karakters komen ook maar één keer in de beschrijving van de configuratie voor). Een karakter dat niet overeenkomt met een uniek karakter van een speelstuk stelt een leeg vakje voor (dergelijke karakters kunnen meerdere keren in de beschrijving van de configuratie voorkomen).

Gevraagd wordt:

Schrijf een functie lees_stukken waaraan de locatie (str) van een tekstbestand moet doorgegeven worden dat kenmerken en eigenschappen van de speelstukken op een spelbord beschrijft. De functie moet een dictionary (dict) teruggeven die elk kenmerk (str) uit het bestand afbeeldt op een dictionary (dict) die de eigenschappen (str) van dat kenmerk afbeeldt op een verzameling (set) met de unieke karakters (str) van alle speelstukken met die eigenschap. Hieronder — onder de voorbeeldsessie — staat de dictionary die de functie lees_stukken teruggeeft voor het tekstbestand dat we hierboven als voorbeeld gebruikt hebben.
Schrijf een functie stuk_eigenschappen waaraan een dictionary (dict) moet doorgegeven worden met de kenmerken en eigenschappen van de speelstukken op een spelbord (opgebouwd zoals de dictionaries die door de functie lees_stukken teruggegeven worden). De functie moet een dictionary (dict) teruggeven die het unieke karakter (str) van elk speelstuk afbeeldt op een verzameling (set) met alle eigenschappen (str) van het speelstuk.
Schrijf een functie maak_rooster waaraan twee argumenten moeten doorgegeven worden: i) de configuratie van de speelstukken op een spelbord en ii) een dictionary (dict) met de eigenschappen van de speelstukken op het spelbord (opgebouwd zoals de dictionaries die door de functie stuk_eigenschappen teruggegeven worden). De functie moet een voorstelling van het rooster teruggeven die bestaat uit een lijst (list) waarin de horizontale rijen van het rooster van boven naar onder opgelijst worden. Elke rij wordt zelf voorgesteld als een lijst (list) waarin de vakjes van links naar rechts opgelijst worden. Elk vakje waarop een speelstuk staat, wordt voorgesteld als een verzameling (set) met de eigenschappen van dat speelstuk. Elk vakje waarop geen speelstuk staat, wordt voorgesteld als een lege verzameling (set).
Schrijf een functie quarto waaraan dezelfde twee argumenten moeten doorgegeven worden als bij de functie maak_rooster. De functie moet een verzameling (set) teruggeven met alle rijen van het spelbord waarop vier 4 speelstukken staan met een gemeenschappelijke eigenschap. Een dergelijke rij wordt voorgesteld als een tuple met twee elementen: i) een beschrijving van de positie van de rij en ii) de gemeenschappelijke eigenschap van de vier speelstukken op die rij. Horizontale rijen worden beschreven als H$$i$$ ($$i = 1, \ldots, 4$$), waarbij de rijen van boven naar onder genummerd worden. Verticale rijen worden beschreven als V$$i$$ ($$i = 1, \ldots, 4$$), waarbij de rijen van links naar rechts genummerd worden. De hoofddiagonaal (linksboven naar rechtsonder) wordt beschreven als D1 en de nevendiagonaal (rechtsboven naar linksonder) als D2.

Opmerking

Als er op een rij vier speelstukken staan met meerdere gemeenschappelijke eigenschappen, dan moet er voor elke gemeenschappelijke eigenschap een tuple voorkomen in de verzameling (set) die door de functie quarto teruggegeven wordt. Die hebben dan hetzelfde eerste element (de positie van de rij) maar een verschillende eigenschap als tweede element.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand stukken.txt¹ zich in de huidige directory bevindt. Dit is het tekstbestand met de kenmerken en eigenschappen van de speelstukken op een spelbord dat we hierboven als voorbeeld gebruikt hebben.

        >>> stukken = lees_stukken('stukken.txt2')
>>> stukken['grootte']['groot']
{'A', 'C', 'E', 'G', 'I', 'K', 'M', 'O'}
>>> stukken['kleur']['rood']
{'A', 'B', 'E', 'F', 'I', 'J', 'M', 'N'}

>>> eigenschappen = stuk_eigenschappen(stukken)
>>> eigenschappen['E']
{'groot', 'hol', 'rond', 'rood'}
>>> eigenschappen['K']
{'blauw', 'groot', 'vol', 'vierkant'}
>>> eigenschappen['O']
{'blauw', 'groot', 'rond', 'vol'}

>>> maak_rooster('N?BI??JO?FDLMEAG', eigenschappen)
[[{'klein', 'vol', 'rond', 'rood'}, set(), {'vierkant', 'hol', 'klein', 'rood'}, {'vierkant', 'groot', 'vol', 'rood'}], [set(), set(), {'vierkant', 'klein', 'vol', 'rood'}, {'groot', 'vol', 'rond', 'blauw'}], [set(), {'hol', 'klein', 'rond', 'rood'}, {'vierkant', 'hol', 'klein', 'blauw'}, {'vierkant', 'klein', 'vol', 'blauw'}], [{'groot', 'vol', 'rond', 'rood'}, {'groot', 'hol', 'rond', 'rood'}, {'vierkant', 'groot', 'hol', 'rood'}, {'groot', 'hol', 'rond', 'blauw'}]]
>>> maak_rooster('KHEF#DCMXABJPGOL', eigenschappen)
[[{'vol', 'groot', 'blauw', 'vierkant'}, {'rond', 'hol', 'blauw', 'klein'}, {'rond', 'groot', 'hol', 'rood'}, {'rond', 'hol', 'klein', 'rood'}], [set(), {'hol', 'blauw', 'vierkant', 'klein'}, {'hol', 'groot', 'blauw', 'vierkant'}, {'vol', 'rond', 'groot', 'rood'}], [set(), {'hol', 'groot', 'vierkant', 'rood'}, {'hol', 'vierkant', 'klein', 'rood'}, {'vol', 'vierkant', 'klein', 'rood'}], [{'rond', 'vol', 'blauw', 'klein'}, {'rond', 'groot', 'hol', 'blauw'}, {'vol', 'rond', 'groot', 'blauw'}, {'vol', 'blauw', 'vierkant', 'klein'}]]

>>> quarto('N?BI??JO?FDLMEAG', eigenschappen)
{('H4', 'groot'), ('V3', 'vierkant'), ('D2', 'rood')}
>>> quarto('KHEF#DCMXABJPGOL', eigenschappen)
{('H4', 'blauw'), ('V2', 'hol'), ('D1', 'vierkant')}

In de voorbeeldsessie verwijst de variabele stukken naar de volgende dictionary (dict):

        {
    'grootte': {
        'groot': {'K', 'C', 'O', 'M', 'E', 'G', 'I', 'A'},
        'klein': {'P', 'H', 'B', 'D', 'L', 'J', 'N', 'F'}
    },
    'kleur': {
        'rood': {'M', 'B', 'E', 'I', 'J', 'N', 'A', 'F'},
        'blauw': {'P', 'K', 'C', 'O', 'H', 'G', 'D', 'L'}
    },
    'vorm': {
        'vierkant': {'K', 'C', 'B', 'D', 'I', 'L', 'J', 'A'},
        'rond': {'P', 'O', 'H', 'M', 'E', 'G', 'N', 'F'}
    },
    'vulling': {
        'hol': {'C', 'H', 'E', 'B', 'G', 'D', 'A', 'F'},
        'vol': {'P', 'K', 'O', 'M', 'I', 'L', 'J', 'N'}
    }
}

Dit zijn de twee configuraties van speelstukken op het spelbord die in de voorbeeldsessie doorgegeven worden aan de functies maak_rooster en quarto.

Configuratie van speelstukken op het spelbord die beschreven wordt door de string N?BI??JO?FDLMEAG.

Configuratie van speelstukken op het spelbord die beschreven wordt door de string KHEF#DCMXABJPGOL.