Do nového roku jako lepší programátoři? Znovu otevíráme večerní školu programování. Nette framework, návrhové vzory, testování nebo vůbec poprvé kurzy ASP.NET dostupné odkudkoli v republice.

Soutěž: Machr na algoritmy - Mastermind

Ostatní jazyky Ostatní programovací jazyky Machr na algoritmy - Mastermind

Soutěž již skončila

Zadání

V dnešním machrovi si zkusíte napsat program, který vyřeší logickou hru Mastermind. Jedná se o logickou hru, v česku známou pod názvem Logik a určitě ji všichni znáte z dětství. Kdo ne, připomenu Logik.

My si ovšem hru trochu zobecníme. V původní verzi se vyskytovalo 6 barev a byly 4 pozice, do kterých bylo možné barvy umístit. Pro machra může být pozic i barev variabilní množství. Počet pozic a barev program dostane na standardním vstupu. Následně bude program vypisovat kombinace (opět na standardní výstup). Pro každou kombinaci program na standardním vstupu dostane počet barev, které program uhádl, ale neumístnil na správnou pozici. Následně dostane číslo udávající počet barev, které jsou uístěny na správné pozici. Protože by se z barvami špatně pracovalo, nahradíme je čísly indexovanými od nuly. Uvedu příklad.

Budeme předpokládat standardní pravidla, tedy 4 místa a 6 barev. Můj program si vymyslí kombinaci "2 0 3 4".

>4 6            #počet míst, počet barev
<0 1 2 3        #kombinace vypsaná programem
>3 0            #3 ze 4 barev správých barev použity, žádná z nich není na správním místě
<2 1 4 3
>2 1            #2 barvy nejsou na správním místě, 1 barva je na svém místě
<2 0 3 4
>0 4            #všechny 4 barvy jsou na svém místě

Použití operátor větší a menší (<,>) pouze symbolizuje vstup a výstup z programu.

Pravidla:

  • Nejlépe bude vyhodnocen program, který vyřeší zadané kombinace v nejmenším počtu kroků (pro 4 místa a 6 barev stačí 5 tahů)
  • Jedna barva může být v jedné kombinaci použita vícekrát (například kombinace "0 0 0 0" je také platná)
  • Program se musí po obdržení vstupu "0 k" kde k je počet míst (tedy ve chvíli, kdy program uhádne všechny barvy a jejich pozice) ukončit.

Ještě jednou opakuji, že se pracuje pouze ze standardním vstupem a výstupem (pro C++ cin/cout; pro C# třída Console, pro Javu System.out a System.in, atd.). Kromě zadaných hodnot nic jiného nevypisujte. Vstupy budou přesně ve formátu, jak je popsáno výše, není tedy potřeba ošetřovat vstupy.

Povolené jazyky jsou: C, C++, C#, Java, Python, JavaScript (pod NodeJS).

EDIT: Není přesně řečeno, jak se bude vyhodnocovat vzor, ve kterém se vyskytuje více stejných barev. Doporučuji přečíst komentáře, kde je to blíže popsáno.

Výhra

Vítěz dostane placku Machr, pár samolepek a ocenění do portfolia.

Výhra

Soutěžící

Jméno Odesláno
John Doe 21. ledna 12:01
Libor Šimo (libcosenior) Včera 17:28
grygerek.tomas Včera 23:13
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

V této soutěži si napíšete algoritmus, který vyřeší hru Mastermind.

Soutěž končí 22. ledna 23:59, tak se nezapomeň zapojit! :)

Odpovědět  +6 10. ledna 21:02
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět 10. ledna 22:03
Život je příliš krátký na to, abychom bezpečně odebírali USB z počítače..
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):
>4 6            #počet míst, počet barev
<0 1 2 3        #kombinace vypsaná programem
>3 0            #3 ze 4 barev správých barev použity, žádná z nich není na správním místě
<2 1 4 3   // tu je to o čom píšem
>1 1            #1 barva není na správním místě, 1 barva je na svém místě
<2 0 3 4
>0 4            #všechny 4 barvy jsou na svém místě
>4 6            #počet míst, počet barev
<0 1 2 3        #kombinace vypsaná programem
>3 0            #3 ze 4 barev správých barev použity, žádná z nich není na správním místě
<2 1 4 3
>1 1            #1 barva není na správním místě, 1 barva je na svém místě
<2 0 3 4
>0 4            #všechny 4 barvy jsou na svém místě
>4 6            #počet míst, počet barev
<0 1 2 3        #kombinace vypsaná programem
>3 0            #3 ze 4 barev správých barev použity, žádná z nich není na správním místě
<2 1 4 3
>1 1            #1 barva není na správním místě, 1 barva je na svém místě
<2 0 3 4
>0 4            #všechny 4 barvy jsou na svém místě

Prečo je 1 v tej istej pozícii ako predtým, keď tam je toto:

>3 0            #3 ze 4 barev správých barev použity, žádná z nich není na správním místě

Ako tvoj program mohol vedieť, že práve jednička tam nie je?

Nahoru Odpovědět 11. ledna 11:04
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Atrament
Člen
Avatar
Atrament:

Můj program si vymyslí kombinaci "2 0 3 4".

Nemělo by tam být, že uživatel si vymyslí tu kombinaci? Jak to zadání čtu, tak to chápu tak, že počítač je ten co hádá a uživatel ten co tu kombinaci zná a odpovídá. Nebo to chápu špatně?

 
Nahoru Odpovědět 11. ledna 11:19
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Protože se mi nechtělo rozepisovat delší ukázku, kterou bych fakt hádal :D Prostě si představ že mě "osvítilo" a zrovna jsem tam dal správnou kombinaci ;)

Nahoru Odpovědět  +1 11. ledna 11:42
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Atrament
patrik.valkovic:

Ano, počítač hádá a uživatel si vymyslí kombinaci. Samozřejmě to nebudu všechno testovar ručně, takže si napíšu vlastní program, který si bude vymýšlet kombinace a na ně bude spouštět váš program. Proto je tam "můj program si vymyslí kombinaci".

Nahoru Odpovědět 11. ledna 11:43
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Nebo v tomto případě byl ten hádací program tak blbý, že znovu zkusil číslo na stejné pozici....hold smůla no :D

Nahoru Odpovědět 11. ledna 11:59
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Toto

<2 1 4 3
>1 1            #1 barva není na správním místě, 1 barva je na svém místě

je správne? Nemá ta byť?

<2 1 4 3
>2 1            #2 barva není na správním místě, 1 barva je na svém místě
Nahoru Odpovědět 11. ledna 12:12
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

Upřímně řečeno mi to zadání přijde dost chaoticky popsané :/

Nahoru Odpovědět 11. ledna 12:41
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Ešte jedna vec.
Je možné zadanie pre viac miest ako je počet farieb?
Teda napríklad

>6 4            #počet míst, počet barev
Nahoru Odpovědět 11. ledna 12:44
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Ano, v té ukázat jsem se sekl. Opravím až budu u PC. Samozřejmě může být více míst než barev.

Nahoru Odpovědět 11. ledna 14:09
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Jenkings
patrik.valkovic:

Co ti na tom přijde chaotické?

Nahoru Odpovědět 11. ledna 14:13
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Nie je mi jasne ako by sa vyhodnotilo
2 2 3 3

Nahoru Odpovědět 11. ledna 19:04
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:
2 2

Tedy dvě barvy umístěny správně, u dvou se netrefilo místo.

Nahoru Odpovědět 11. ledna 19:09
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět  +1 11. ledna 19:18
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Promiň ne oprava, bude to "0 2"...2 barvy na svém místě.

Nahoru Odpovědět 11. ledna 19:44
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
rikenbekr
Člen
Avatar
Odpovídá na patrik.valkovic
rikenbekr:

a pokud bude kombinace například:

4 5 2 4

a tipovaná kombinace

1 2 3 4

tak bude odpověď

2 1

nebo

2 0

nebo

1 1
Nahoru Odpovědět 12. ledna 9:29
In world without fences and walls, who needs Gates and Windows?
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na rikenbekr
patrik.valkovic:
1 1

Čtyřka na svém místě, dvojka není na svém místě.
Postup vyhodnocení: Nejdříve se kontrolují správná místa. Pokud je nějaké číslo na svém místě, tak se pro další vyhodnocení ignoruje. Následně se vyhodnocují barvy, které nejsou na svém místě a to postupně po první shodu. Tedy podívám se na jedničku - není ve vzoru. Potom na 2 - není na svém místě, přidá se puntík, potom trojka - není ve vzoru. Čtyřka byla vyignorovaná v prvním kroku.

Nahoru Odpovědět 12. ledna 9:50
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
rikenbekr
Člen
Avatar
Odpovídá na patrik.valkovic
rikenbekr:

a pro

4 5 2 4

a tipovanou

1 4 3 4

?

Nahoru Odpovědět 12. ledna 9:55
In world without fences and walls, who needs Gates and Windows?
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na rikenbekr
patrik.valkovic:

Stejný postup - nejdříve se zkontrolují znaky na svém místě (poslední 4-ka) a poté se postupně kontrolují znaky, které nejsou na svém místě. Tedy druhá 4 v původním výrazu je, ale ne na svém místě.

1 1

Kdyby tipovaná kombinace byla

3 4 4 4

Tak zase je poslední 4 na své místě, druhá čtyřka by se spárovala s první čtyřkou (není na svém místě) a protože ty dvě čtyřky, co se vzoru byly, byly v předchozích dvou krocích "vyignorovány", tak se ta třetí čtyřka nemá s čím spárovat. Tedy zase

1 1
Nahoru Odpovědět 12. ledna 10:00
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
rikenbekr
Člen
Avatar
Nahoru Odpovědět 12. ledna 10:02
In world without fences and walls, who needs Gates and Windows?
Avatar
Odpovídá na patrik.valkovic
Martin Vejvoda:

Jak se to bude hodnotit? Podle počtu pokusů?

Nahoru Odpovědět 12. ledna 16:56
while (!asleep()) sheep++;
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Martin Vejvoda
patrik.valkovic:

Je to napsané v zadání. Ano, budou se sčítat pokusy, které program potřeboval.

Nahoru Odpovědět  +1 12. ledna 18:15
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět 13. ledna 13:39
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Jak to myslíš? Výstupy jsou různé kombinace a tam vypisuješ čísla. Nevím, na co se ptáš.

Nahoru Odpovědět 13. ledna 15:06
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Libor Šimo (libcosenior):

V zadani mas

Můj program si vymyslí kombinaci "2 0 3 4".

Tak som si myslel, ci to nechces ako stringy kvoli programovej kontrole.

Nahoru Odpovědět 13. ledna 15:13
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

No on to vypisuješ na standardní výstup, takže se to ve výsledku do řetězce převede. Já už si to zpracuju ze standardního výstupu.

Nahoru Odpovědět 13. ledna 15:22
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Ja to zatial vypisujem ako cisla s medzerami, aj za poslednym je medzera. Takze by to teda nemalo vadit.

Nahoru Odpovědět 13. ledna 15:31
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Nahoru Odpovědět 13. ledna 15:31
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

OK, akurat ti nezavidim vyhodnocovanie, ak bude viac sutaziacich.

Editováno 13. ledna 15:33
Nahoru Odpovědět 13. ledna 15:32
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Toto tvrdenie je na 100%?

pro 4 místa a 6 barev stačí 5 tahů)

Nahoru Odpovědět 14. ledna 9:28
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Anglická Wiki

In 1993, Kenji Koyama and Tony W. Lai found a method that required an average of 5625/1296 = 4.340 turns to solve, with a worst-case scenario of six turns. The minimax value in the sense of game theory is 5600/1296 = 4.321.

Nahoru Odpovědět 14. ledna 9:59
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět 14. ledna 10:47
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior):

Je to fakt zlozite. Dufam, ze to stihnem do terminu.

Nahoru Odpovědět 15. ledna 19:28
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Libor Šimo (libcosenior)
patrik.valkovic:

Není to zas tak těžké. Popřípadě můžu termín prodloužit, nemám s tím problém.

Nahoru Odpovědět 15. ledna 19:35
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Nic nepredlzuj. Oni sa najdu sikovnici. ;-)

Nahoru Odpovědět 15. ledna 19:36
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na patrik.valkovic
Libor Šimo (libcosenior):

Ja uz vlasne nieco mam, ale pri 4/6 urcite nebude len max 5 tahov, az tak genialny nie som, ale zatial to funguje na rozne situacie, aj ked s viac pokusmi.
Dufam, ze toto nastartuje aj dlasich zaujemcov o placku. :-)

Nahoru Odpovědět 15. ledna 19:43
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Tak pospěště, máte poslední dva dny a ještě nemám ani jedno řešení :)

Nahoru Odpovědět 21. ledna 9:06
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Soutěž skončena. Protože mám ještě zkoušky, vyhodnocení očekávejte ve čtvrtek večer :)

Nahoru Odpovědět  +2 0:00
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět  +2 8:30
Není proč se klanět.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 40 zpráv z 40.