====== Kdo je kdo? ======

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.

{{:2014_15:priklad_anonymni.jpg?nolink&300|}}

**  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 [[2017_2018:kdo_je_kdo:reseni|řešení]])


====== Úloha ====== 

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í. 


===== Vstup =====

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:

<code C>
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)
</code>


===== Výstup =====

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):

<code C>
3 2 6 5 4 0 1
</code>

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:
  - Jarda je na fotce na pozici 3
  - Mirek je na pozici 2
  - Luda je na pozici 6
  - Beda je na pozici 5
  - Cenek je na pozici 4
  - Mates je na pozici 0
  - Kvido je na pozici 1

Porovnej s [[2014_15:kdo_je_kdo:reseni|Obrázkem 2]].


===== Zadání a řešení =====

  * Stáhněte si soubory {{:2014_15:zadani.zip|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 [[https://hapky.fel.cvut.cz/sou/assignments.php| 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.**

===== Pomůcky a tipy =====

Zde si můžete stáhnout {{:2014_15:kdojekdo_src.zip|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 [[2017_2018:kdo_je_kdo:tridahadanka|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 [[2017_2018:kdo_je_kdo:tridareseni|Reseni]] reprezentuje řešeni ve formě seznamu dvojic <jmeno, pozice>.
  * Třída [[2017_2018:kdo_je_kdo:tridanahodny|Nahodny]] realizuje náhodný řešič, který řešení sestaví náhodným tipováním pozice každého jména.
  * Třída [[2017_2018:kdo_je_kdo:tridamain|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
  * [[http://cs.wikipedia.org/wiki/Prohled%C3%A1v%C3%A1n%C3%AD_do_%C5%A1%C3%AD%C5%99ky|prohledávání do šířky]] a
  * [[http://cs.wikipedia.org/wiki/Prohled%C3%A1v%C3%A1n%C3%AD_do_hloubky|prohledávání do hloubky]].

===== Hodnocení =====

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.