Kamarádi z vojny, Jarda, Mirek, Luďa, Béďa, Čeněk, Mates a Kvído mají sraz po mnoha letech a na závěr si udělají společné foto. Vzpomenou si na svého bývalého velitele a fotku mu pošlou. S trochou škodolibosti mu ovšem neprozradí přímo, kdo je kde na obrázku. Poskytnou mu pouze nápovědu, která ho při troše důvtipu dovede k cíli.

Obrázek 1. Fotka beze jmen.

Nápověda se skládá z kusých informací typu:

• jakou barvu kalhot má/nemá daná postava
• jakou barvu košile má/nemá daná postava
• kdo s kým přímo sousedí/nesousedí
• kdo je nalevo/napravo od koho

Příklad nápovědy k Obrázku 1:

• Jarda má modré kalhoty
• Kvído má červené kalhoty
• Luďa nemá modré kalhoty
• Mirek má žlutou košili
• Béďa má hnědou košili
• Čeněk má žlutou košili
• Mates nemá červenou košili
• Jarda sousedí s Mirkem
• Béďa nesousedí s Mirkem
• Mirek je nalevo od Ludi
• Čeněk je nalevo od Bédi
• Kvído je nalevo od Jardy
• Luďa je napravo od Kvída

Poznáš kdo je kdo podle zadané nápovědy? (Pro ověření, zde je řešení)

Je dána posloupnost postav v pořadí, v jakém se vyskytují na fotce. Každá postava je definovaná barvou kalhot a barvou košile. Dále je definována množina omezení, která musí být všechna splněna. Cílem je nalézt přiřazení pozic všem postavám tak, aby byla dodržena všechna definovaná omezení.

Vstupní soubor obsahuje dva řádky

• seznam jmen oddělených mezerami
• seznam barev použitých v úloze

následováno seznamem postav, uvozeným řádkem s textem “postavy:”, v pořadí jak jsou na obrázku (z pohledu pozorovatele), kde

• každá postava je definována na jednom řádku dvojicí “barva_kalhot-barva_košile”

následováno seznamem omezení těchto typů

• sousedi(jmeno1, jmeno2) … vazba, vyjadřující, že jmeno1 sousedí s jmeno2
• nesousedí(jmeno1, jmeno2) … jmeno1 NEsousedí s jmeno2
• nalevood(jmeno1, jmeno2) … jmeno1 je na obrázku nalevo od jmeno2
• napravood(jmeno1, jmeno2) … jmeno1 je napravo od jmeno2
• maKosiliBarvy(jmeno, barva) … postava jmeno ma kosili barvy barva
• nemaKosiliBarvy(jmeno, barva) … postava jmeno NEma kosili barvy barva
• maKalhotyBarvy(jmeno, barva) … postava jmeno ma kalhoty barvy barva
• nemaKosiliBarvy(jmeno, barva) … postava jmeno NEma kalhoty barvy barva

Ne všechna omezení musí být v dané úloze definována.

Příklad vstupního souboru k Obrázku 1:

Jarda Mirek Luda Beda Cenek Mates Kvido
zluta hneda cervena modra
 
postavy:
hneda-modra
cervena-hneda
modra-zluta
modra-cervena
cervena-zluta
zluta-hneda
zluta-zluta
 
omezeni:
sousedi(Jarda, Mirek)
nesousedi(Beda, Mirek)
 
nalevoOd(Mirek, Luda)
nalevoOd(Cenek, Beda)
nalevoOd(Kvido, Jarda)
napravoOd(Luda, Kvido)
 
maKosiliBarvy(Mirek, Zluta)
maKosiliBarvy(Beda, hneda)
maKosiliBarvy(Cenek, zluta)
nemaKosiliBarvy(Mates, cervena)
 
maKalhotyBarvy(Jarda, modra)
maKalhotyBarvy(Kvido, cervena)
nemaKalhotyBarvy(Luda, modra)

Výstupem je právě jedno řešení zapsané jako permutace celých čísel od 0 do N-1 (N je počet postav vystupujících v dané úloze), podle které jsou postavám v pořadí, v jakém byly uvedeny ve vstupním souboru, přiřazeny pozice, na kterých se mají vyskytovat na fotce.

Příklad správného výstupu k úloze definované v ukázkovém vstupním souboru viz výše (pozor: čísluje se od 0):

3 2 6 5 4 0 1

Takže tato posloupnost čísel přiřazuje pozice postavám ze vstupní posloupnosti “Jarda Mirek Luda Beda Cenek Mates Kvido” následujícím způsobem:

1. Jarda je na fotce na pozici 3
2. Mirek je na pozici 2
3. Luda je na pozici 6
4. Beda je na pozici 5
5. Cenek je na pozici 4
6. Mates je na pozici 0
7. Kvido je na pozici 1

Porovnej s Obrázkem 2.

• Stáhněte si soubory zadani1.txt a zadani2.txt. Každý soubor obsahuje zadání jedné úlohy ve formátu viz výše. Nelepkněte se, pro jednoduchost jsme volili krátká (jakoby čínská) jména
• Vytvořte výstupní textové soubory reseni1.txt a reseni2.txt s řešením zapsaným dle formátu viz výše.
• Soubory s výsledky zazipujte do jednoho archivu s příponou .zip (na jeho jménu nesejde) a odevzdejte do odevzdávacího systému Hapky. POZOR: Řešení můžete odevzdávat opakovaně. Pokaždé však zabalte obě řešení, pokud je máte.

Zde si můžete stáhnout základní třídy napsané v Javě pro načtení zadání hádanky a další jednoduché operace, včetně třídy s jednoduchým řešičem, který je ovšem tak jednoduchý, že správné řešení nenajde

• Třída Hadanka obsahuje struktury pro popis daného zadání hádanky, tj. seznam jmen, použité barvy, seznam postav (zadané barvou kalhot a košile) v daném pořadí, a všechna omezení, která musí být splněna.
• Třída Reseni reprezentuje řešeni ve formě seznamu dvojic <jmeno, pozice>.
• Třída Nahodny realizuje náhodný řešič, který řešení sestaví náhodným tipováním pozice každého jména.
• Třída Main ukazuje, jak se vytvoří objekt typu Hadanka, který načte zadání, zpracuje všechna omezení a spustí náhodný řešič.

Při návrhu řešení se můžete inspirovat metodami prohledávání stavového prostoru, viz

• prohledávání do šířky a
• prohledávání do hloubky.

Celkově můžete získat za tuto úlohu 20 bodů rozdělených takto

• 7 bodů za správně vyřešené zadání 1
• 13 bodů za správně vyřešené zadání 2.