Riešenie súťažnej úlohy Santova hádanka

Program rieši Santa Clausovu hádanku čiže upravenú verziu Einsteinovej hádanky. Jedná sa víťazné riešenie tunajšie súťaže Predvianočné špeciál odborníka - Santova hádanka.

Spustenie

Na vyriešenie úlohy je potrebné spustiť dávkový súbor einstein.cmd. Výsledok sa zapíše do súboru a otvorí v Poznámkový blok.

Ak program spustíte priamo z príkazového riadku, riešenie sa vypíše na štandardný výstup:

java -jar einstein.jar VSTUPNI_SOUBOR

Ako vstupné súbor možno použiť zadania z adresára problems:

• santova_hadanka.txt - Súťažná Santova hádanka
• einsteinova_hadanka.txt - Einsteinova hádanka

K dispozícii je tiež jednoduché GUI, ktoré sa otvorí, ak program spustíte bez parametrov:

java -jar einstein.jar

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

Vstupný súbor

Vstupom programu je textový súbor, ktorý popisuje zadania úlohy. Ak chcete používať diakritiku, súbor musí byť kódovaný v UTF-8.

Znak '#' slúži ako riadkový komentár. Všetky znaky za '#' až do konca riadku sa ignorujú.

Zadanie úlohy sa skladá z definícií nasledujúcich objektov (pozri ďalej):

• množina
• relácia
• tvrdenie

Názvy množín, prvkov a relácií musí byť reťazce obsahujúce iba číslice, písmená, podčiarkovník a znaky s kódom> 127.

Množina

Množina je definovaná výpočtom svojich prvkov. Každá množina musí obsahovať aspoň jeden prvok. Všetky množiny musia mať rovnaký počet prvkov. Zadanie musí obsahovať aspoň 1 množinu. Počet množín nie je obmedzený.

Príklad:

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

Relácie

Relácia slúži na opis vzťahu medzi objektmi. Podporované sú len binárne relácie nad rovnakou množinou. Relácia je definovaná výpočtom svojich prvkov, tj. Dvojíc prvkov množiny.

Prí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)
}

Tvrdenie

Tvrdenie reprezentuje informáciu o hľadanom riešenie úlohy. Program rozpoznáva dva typy tvrdení.

• Tvrdenie o dvojicu
• Tvrdenie s relácií

Tvrdenie o dvojicu jednoducho hovorí, že dva objekty k sebe patria. Zapisuje sa ako dvojica prvkov množín.

Príklad:

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

Tvrdenie s relácií vyjadruje zložitejšie vzťah medzi dvoma objektmi popísaný pomocou relácie.

Príklad:

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

Toto tvrdenie je interpretované nasledovne:

• K žltej farbe patrí nejaký prvok xz množiny Domy
• K zelenej farbe patrí nejaký prvok yz množiny Domy
• Dvojica (x, y) je prvkom relácie hned_nalevo

Riešenie

Program sa snaží simulovať uvažovanie človeka s ceruzkou a papierom

Cieľom je pre každú usporiadanú dvojicu množín nájsť permutáciu popisujúce, ktoré dva objekty k sebe patria. Permutácie sa konštruujú postupne. Pre každý prvok množiny sa uchováva množina možných kandidátov. Ak pre nejaký prvok zostane iba jeden kandidát, hodnota permutácie je pre daný prvok jednoznačne určená. Ak dôjde k situácii, kedy je množina kandidátov prázdna, úloha nemá riešenie, pretože niektoré tvrdenia v zadaní sú konfliktné.

Tvrdenie o dvojici dáva okamžite hodnotu permutácie a permutácie k nej inverzná.

Následne sa opakovane aplikujú nasledujúce pravidlá:

• pravidlá tranzitívnosti
• pravidlá relácií

Pokiaľ nedôjde po aplikácii všetkých pravidiel k vyradeniu žiadneho kandidáta a riešenie nie je kompletný, program vypíše chybu, že na vyriešenie nie je k dispozícii dostatok informácií.

Pravidlá tranzitívnosti

Program využíva nasledujúce pravidlá:

1. Patrí-ly k sebe prvky (a, b) a (b, c), potom k sebe patria aj (a, c), kde prvkov a, b, c patrí do navzájom rôznych množín.
2. Nech a, b patrí do X, c do Y ad po Z a ďalej platí, že a je rôzne od b. Patrí-ly k sebe prvky (a, c) a (b, d), potom (c, d) k sebe nepatria. (Keby k sebe (c, d) patrili, muselo by platiť, že a = b, čo podľa predpokladu nie je pravda.)

Pravidlá relácií

1. Pogram prejde všetky tvrdenia s reláciami a na základe relácií vyradí všetky nevyhovujúce kandidátov.

Príklad: Majme relácii hned_nalevo(žlutá, zelená) a predpokladajme, že poradie žltého ani zeleného domu nepoznáme. Z definície vieme, že relácia obsahuje tieto 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). Odtiaľ vyplýva, že:

• žltý dom nemôže byť piaty, pretože žiadny prvok relácie nie je tvaru (?, piaty)
• zelený dom nemôže byť prvý, pretože analogicky žiadny prvok relácie nie je tvaru (prvý,?)

Zdrojové kódy

Program bol napísaný v Jave 6. K vývoju bolo použité IDE Eclipse. Zdrojové kódy sú v kódovaní UTF-8. Názvy tried a metód sú v angličtine, však riešenie pochádza z českej hlavy

Galéria