Řešení soutěžní úlohy Santova hádanka

Program řeší Santovu hádanku neboli upravenou verzi Einsteinovy hádanky. Jedná se vítězné řešení zdejší soutěže Předvánoční speciál machra - Santova hádanka.

Spuštění

K vyřešení úlohy je třeba spustit dávkový soubor einstein.cmd. Výsledek se zapíše do souboru a otevře v Poznámkovém bloku.

Pokud program spustíte přímo z příkazové řádky, řešení se vypíše na standardní výstup:

java -jar einstein.jar VSTUPNI_SOUBOR

Jako vstupní soubor lze použít zadání z adresáře problems:

• santova_hadanka.txt - Soutěžní Santova hádanka
• einsteinova_hadanka.txt - Einsteinova hádanka

K dispozici je také jednoduché GUI, které se otevře, pokud program spustíte bez parametrů:

java -jar einstein.jar

Program vyžaduje Javu 6 nebo vyšší.

Vstupní soubor

Vstupem programu je textový soubor, který popisuje zadání úlohy. Pokud chcete používat diakritiku, soubor musí být kódován v UTF-8.

Znak '#' slouží jako řádkový komentář. Všechny znaky za '#' až do konce řádku se ignorují.

Zadání úlohy se skládá z definic následujících objektů (viz dále):

• Množina
• Relace
• Tvrzení

Názvy množin, prvků a relací musí být řetězce obsahující pouze číslice, písmena, podtržítko a znaky s kódem > 127.

Množina

Množina je definována výčtem svých prvků. Každá množina musí obsahovat alespoň jeden prvek. Všechny množiny musí mít stejný počet prvků. Zadání musí obsahovat alespoň 1 množinu. Počet množin není omezen.

Příklad:

Domy = {první_dům, druhý_dům, třetí_dům, čtvrtý_dům, pátý_dům}

Relace

Relace slouží k popisu vztahu mezi objekty. Podporovány jsou pouze binární relace nad stejnou množinou. Relace je definována výčtem svých prvků, tj. dvojic prvků množiny.

Příklad:

hned_nalevo = {
  (první_dům, druhý_dům),
  (druhý_dům, třetí_dům),
  (třetí_dům, čtvrtý_dům),
  (čtvrtý_dům, pátý_dům)
}

Tvrzení

Tvrzení reprezentuje informaci o hledaném řešení úlohy. Program rozpoznává dva typy tvrzení.

• Tvrzení o dvojici
• Tvrzení s relací

Tvrzení o dvojici jednoduše říká, že dva objekty k sobě patří. Zapisuje se jako dvojice prvků množin.

Příklad:

# Tonda žije v bílém domě
(Tonda, bílá)

Tvrzení s relací vyjadřuje složitější vztah mezi dvěma objekty popsaný pomocí relace.

Příklad:

# Žlutý dům stojí hned nalevo od zeleného.
hned_nalevo(žlutá, zelená)

Toto tvrzení je interpretováno následovně:

• K žluté barvě patří nějaký prvek x z množiny Domy
• K zelené barvě patří nějaký prvek y z množiny Domy
• Dvojice (x, y) je prvkem relace hned_nalevo

Řešení

Program se snaží simulovat uvažování člověka s tužkou a papírem

Cílem je pro každou uspořádanou dvojici množin najít permutaci popisující, které dva objekty k sobě patří. Permutace se konstruují postupně. Pro každý prvek množiny se uchovává množina možných kandidátů. Pokud pro nějaký prvek zbude pouze jediný kandidát, hodnota permutace je pro daný prvek jednoznačně určena. Dojde-li k situaci, kdy je množina kandidátů prázdná, úloha nemá řešení, protože některá tvrzení v zadání jsou konfliktní.

Tvrzení o dvojici dává okamžitě hodnotu permutace a permutace k ní inverzní.

Následně se opakovaně aplikují následující pravidla:

• Pravidla tranzitivity
• Pravidla relací

Pokud nedojde po aplikaci všech pravidel k vyřazení žádného kandidáta a řešení není kompletní, program vypíše chybu, že k vyřešení není k dispozici dostatek informací.

Pravidla tranzitivity

Program využívá následující pravidla:

1. Patří-ly k sobě prvky (a, b) a (b, c), potom k sobě patří také (a, c), kde prvk a, b, c patří do navzájem různých množin.
2. Nechť a, b náleží do X, c do Y a d do Z a dále platí, že a je různé od b. Patří-ly k sobě prvky (a, c) a (b, d), potom (c, d) k sobě nepatří. (Kdyby k sobě (c, d) patřily, muselo by platit, že a = b, což podle předpokladu není pravda.)

Pravidla relací

3. Pogram projde všechna tvrzení s relacemi a na základě relací vyřadí všechny nevyhovující kandidáty.

Příklad: Mějme relaci hned_nalevo(žlutá, zelená) a předpokládejme, že pořadí žlutého ani zeleného domu neznáme. Z definice víme, že relace obsahuje tyto prvky: (první_dům, druhý_dům), (druhý_dům, třetí_dům), (třetí_dům, čtvrtý_dům), (čtvrtý_dům, pátý_dům). Odtud plyne, že:

• žlutý dům nemůže být pátý, neboť žádný prvek relace není tvaru (?, pátý)
• zelený dům nemůže být první, neboť analogicky žádný prvek relace není tvaru (první, ?)

Zdrojové kódy

Program byl napsán v Javě 6. K vývoji bylo použito IDE Eclipse. Zdrojové kódy jsou v kódování UTF-8. Názvy tříd a metod jsou v angličtině, nicméně řešení pochází z české hlavy

Galerie

Program byl vytvořen v roce 2013.