Soutěž: Machr na algoritmy - Sudoku
Zadání
Jak již název machra napovídá, budete si tentokrát hrát se sudoku. Přesněji řečeno ho budete řešit. Ještě přesněji řečeno napíšete konzolovou aplikaci, která ho vyřeší za vás.
Vstup bude vypadat nějak takto:
_ _ _ 1 _ 2 _ _ _
3 _ 9 8 _ 4 1 _ 7
8 _ _ _ _ _ _ _ 2
_ 3 _ 4 _ 6 _ 7 _
4 _ _ _ _ _ _ _ 1
_ 1 _ 2 _ 5 _ 9 _
5 _ _ _ _ _ _ _ 8
1 _ 6 5 _ 3 9 _ 4
_ _ _ 6 _ 8 _ _ _(mezi znaky jsou mezery, rozložení chybějících čísel může být
jakékoli)
Výstup bude stejný, jen místo podtržítek vypíšete doplněné
číslice.
Pokud by se stalo, že řešení existuje více, vypište jedno z nich, je jedno které.
Povolené jazyky: C, C++, C#, Pascal, Java, Python
Pokud budete chtít použít jiný (nebo budete mít nějaký dotaz k
soutěži), zeptejte se v komentářích.
Výhra
Vítěz dostane placku Machr a ocenění do portfolia.
Výsledky
krepsy3:5.12.2016 18:25
Moc bych DateTime nevěřil, co se týče přesnosti, která nemusí být zrovna na milisekundy, ale může se odvíjet např. od délky časového kvanta pro plánování vláken na procesoru (což může znamenat granularitu třeba 10-16 ms). Takže to chce zprůměrovat větší množství pokusů, aby takové měření o něčem vypovídalo.
Jasně, ale orientačně ti to postačí - víš jestli je to asi 10 ms, 50
ms, 200 ms nebo 2000 ms 
Schválne som nechal spočítať koľko krát sa pri riešení volala rekurzia.
Patrik Valkovič:7.12.2016 16:43
No ono ve chvíli, kdy ti spadne program protože StackOverflow (přitom se
nikdy nezacyklil, ale byl napsán korektně), tak to začneš řešit
Výsledky testování můžete vidět na obrázku, zde (dev-lighter) jsou vstupy použité při testování.
Pozn.: červený křížek u času je překročení limitu (10 sekund)
Díky všem za účast, zde jsou výsledky:
Lukáš Křehula - 75 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 15 / 20 bodů
- program je celkem rychlý (v porovnání s ostatními)
Kód: 15 / 25 bodů
- nějaké ty komentáře tam jsou
- Main metoda je docela šílenost, určitě není nutné tam mít tolik vnořených bloků, zkus více používat continue
Vlado Cukalovsky - 57 bodů
Správnost výstupu: 42 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 14 / 15
Rychlost: 0 / 20 bodů
- program je velmi pomalý (v porovnání s ostatními)
Kód: 15 / 25 bodů
- vypadá celkem dobře, obsahuje nějaké ty komentáře
- z hlediska algoritmu pomalý, zkoušení všech možností obvykle nebývá
moc dobrá strategie
D0ll0k - 77 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 10 / 20 bodů
- program je středně rychlý (v porovnání s ostatními)
Kód: 23 / 25 bodů
- přehledný, vysvětlený v komentářích
Michael Škrášek - 75 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 10 / 20 bodů
- program je středně rychlý (v porovnání s ostatními)
Kód: 20 / 25 bodů
- přehledný, komentovaný
Pozn. je sice hezké, že máš barevný výstup, titulek konzole apod., ale jaksi to nefunguje s automatickým testováním - tam totiž jaksi chybí ta konzole...
Patrik Valkovič - 92 bodů
Správnost výstupu: 55 / 55 bodů
- jsi jediný, kdo neměl ve výstupu nic navíc -> +10 bodů
- správně vyřešeno: 15 / 15
Rychlost: 17 / 20 bodů
- program je velmi rychlý (v porovnání s ostatními)
Kód: 20 / 25 bodů
- přehledný, trochu komentovaný
[me|]13944[/me|] - 70 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 5 / 20 bodů
- program je celkem pomalý (v porovnání s ostatními)
Kód: 20 / 25 bodů
- přehledný, komentáře tam také jsou
- pozn. interface se obvykle pojmenovává s I na začátku (IElement)
Libor Šimo (libcosenior) - 85 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 20 / 20 bodů
- program je velmi rychlý (v porovnání s ostatními)
Kód: 20 / 25 bodů
- přehledný, pěkně komentovaný kód
- pozn. docela by mě zajímalo, k čemu tam máš tu podmínku...
if (spusti());Luboš Běhounek Satik - 80 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný přídavný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 10 / 20 bodů
- program je středně rychlý (v porovnání s ostatními)
Kód: 25 / 25 bodů
- vypadá celkem dobře, jsou tam i nějaké ty komentáře
- chválím použití unit testů
krepsy3 - 70 bodů
Správnost výstupu: 42 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 14 / 15
Rychlost: 5 / 20 bodů
- program je celkem pomalý (v porovnání s ostatními)
Kód: 23 / 25 bodů
- přehledný, vysvětlený v komentářích
rikenbekr - 82 bodů
Správnost výstupu: 45 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 15 / 15
Rychlost: 15 / 20 bodů
- program je celkem rychlý (v porovnání s ostatními)
Kód: 22 / 25 bodů
- přehledný, skvěle komentovaný
LukasMegPrask - 52 bodů
Správnost výstupu: 27 / 55 bodů
- ve výstupu neměl být žádný text navíc
- správně vyřešeno: 9 / 15
- u některých vstupů ti to hází ArrayIndexOutOfBoundsException (do depthFirstSearchAndFillNumbers občas předáváš pole délky 0)
- u jiných tvůj program tvrdí, že neexistuje řešení
Rychlost: 5 / 20 bodů
- program je celkem pomalý (v porovnání s ostatními)
Kód: 20 / 25 bodů
- pěkně komentovaný, celkem přehledný
- pozn. regulární výraz, kterým ověřuješ správnost vstupu, by se dal výrazně zkrátit:
"[123456789_] [123456789_] atd." -> "[1-9_]( [1-9_]){8}"Ladislav Ondris - 30 bodů
Správnost výstupu: 0 / 55 bodů
- ve výstupu neměl být žádný text navíc
- máš chybu v kódu vypisujícím výstup - GetUpperBound vrací nejvyšší index, ne počet prvků!
-> vypisoval jsi čtverec 8×8 místo 9×9
Rychlost: 15 / 20 bodů
- program je celkem rychlý (v porovnání s ostatními)
Kód: 15 / 25 bodů
- trochu komentovaný
- připadá mi trochu zbytečné mít pro vstup a výstup 2 extra třídy, kde v každé je 1 celkem krátká metoda...
- podmínka typu x == true je trochu podivná...
Placku tedy získává patrik.valkovic Gratuluji 
Libor Šimo (libcosenior):4.2.2017 8:12
Funkcia spusti() má návratovú hodnotu bool a ošetruje správnosť vstupu
užívateľa. Snažil som sa spraviť kód "blbuvzdorný".
if (!kontrola_vstupneho_pola(vstup)) {
printf("\nZarucene nespravne zadanie!\n");
return false;
}
bool kontrola_vstupneho_pola(char p_s[][18]) {
int i, j;
// kontroluje
for (i = 0; i < 9; i++) {
for (j = 0; j < 17; j++) {
// ci su na spravnom mieste podtrzniky alebo cislice okrem nuly
if ((j % 2 == 0) && !((isdigit(p_s[i][j]) && p_s[i][j] != '0') || (p_s[i][j] == '_')))
return false;
// ci su na spravnom mieste medzery
if (!(j % 2 == 0) && !(p_s[i][j] == ' ')) {
return false;
}
}
}
return true;
}Gratulujem <a href="http://www.itnetwork.cz/portfolio/6863"
class="member-card" data-member-id="6863">patrik.valkovic</a> k
získaniu placky.
Mrzí ma len, že som počítal aj s možnosťou nevyriešenia zadania (mohlo
byť aj neriešiteľné)
if (vypocitaj_vsetko(sudoku, 0, 0)) {
napln_hracie_pole_char_z_int(sudoku, vystup);
vypis_hracie_pole_char(vystup);
printf("\nVyriesene.\n");
}
else
printf("\nNema riesenie!\n");a tým som pridal k výstupu ďalší string. 
Keby Patrik nedostal tých 10 bodov naviac, mal by som placku ja.
Zdeněk Pavlátka:4.2.2017 10:19
Tu podmínku jsem zmínil proto, že za sebou měla prázdný příkaz.
Mrzí ma len, že som počítal aj s možnosťou nevyriešenia zadania (mohlo byť aj neriešiteľné)Psal jsem, že "Pro každý zadaný vstup bude existovat alespoň jedno
řešení.". Dokonce koukám, že to byla odpověď pro tebe Jinak gratuluji k nejrychlejšímu
programu
Libor Šimo (libcosenior):4.2.2017 10:40
Som absolutny samouk. Nikto ma okrem Herouta a itnetworku nic neucil.
Ale nevadi, aj tak som rad., ze som aspon druhy. Je to pokrok.
Zobrazeno 50 zpráv z 207.
