Soutěž: Machr - Generování měst
Zadání
Letní soutěž skončila a je čas na machry 
Začneme generováním měst. Vaším úkolem bude napsat aplikaci, která
dostane jako parametry string (název) a 2 čísla - šířku a výšku (obě
budou >= 1). Např.:
app.exe mesto 16 5Aplikace pak vygeneruje 2 soubory:
<zadaný_název>.png (nebo jiný běžný typ obrázku)
- na obrázku bude vygenerované město, které bude vyplňovat celou jeho plochu
- město generujte pomocí nějakého tilesetu, ten můžete buďto sami vytvořit, nebo použít tento: https://www.dropbox.com/…_tileset.png
- města se skládají (pouze) ze silnic a budov
- alespoň 10% (zaokrouhleno nahoru) každého města musí tvořit budovy, budova však nikdy nesmí být plně obklopena dalšími budovami - alespoň na jednom sousedním poli musí být silnice
- alespoň 10% (zaokrouhleno dolů) každého města musí tvořit křižovatky
- silnice musejí tvořit souvislý graf (multigraf) = z libovolného místa na silnici musí být možno dojet na libovolné jiné místo
- dejte si pozor aby na sebe silnice opticky navazovaly
<zadaný_název>.dat
- soubor bude obsahovat popis multigrafu tvořícího město - vrcholy grafu budou křižovatky / konce silnice a hrany budou cesty mezi nimi
- reprezentaci grafu nechám na vás (spolu s řešením odevzdejte popis reprezentace), jediná 3 pravidla jsou:
- musí se jednat o textový formát
- musí odpovídat vygenerovanému městu - ke každému vrcholu nějak "připojte" jeho souřadnice na mapě
- hrany budou ohodnoceny svou délkou na mapě
- pozor na to, že mezi křižovatkami může vést cest více (pak uveďte všechny), může existovat i smyčka (cyklus) na které je jen 1 křižovatka - takové můžete vynechat
- tento soubor není povinný, pokud ho ale generovat budete, můžete za to získat až 20 bodů
Ukázka možného výstupu:
app.exe mesto 5 3PNG: https://www.dropbox.com/…ya/mesto.png
DAT: https://www.dropbox.com/…k5/mesto.dat
použitý formát:
počet_vrcholů
vrcholy ve formátu [X;Y], kde X, Y jsou souřadnice, n-tý vrchol má číslo n
počet_hran
hrany ve formátu A(délka_hrany)B, kde A, B jsou čísla vrcholů, mezi kterými hrana vedeCelkem lze získat nejvýše 100 bodů:
- max 15 bodů za kód
- max 45 bodů za generování města
- max 20 bodů za generování popisu grafu
- max 20 bodů za "bezchybnost"
Povolené jazyky jsou C#, Java, C++, chcete-li použít jiný, zeptejte se v komentářích
Výhra
Vítěz dostane placku Machr a ocenění do portfolia.
Výsledky
| Jméno | bodů | Řešení ( Stáhnout vše ) |
|---|---|---|
| Mexikánec | 77 | Stáhnout řešení |
| Ladislav Ondris | 48 | Stáhnout řešení |
| DarkCoder | 38 | Stáhnout řešení |
Patrik Valkovič:18.10.2017 16:52
Ale algoritmus přece něco řeší 
Když vyplivnu prázdnou plochu,
tak je to rychlé a zadání jsem splnil.
Obdobně nedokážeš bez dalších znalostí poznat, zda je .dat vygenerovaný
dobře. Já si můžu zvolit náhodně dva body a vést cesty mezi nimi.
Zadání je opět splněno, ale je to k ničemu.
Díky všem za účast, zde jsou výsledky:
DarkCoder - 38 bodů
Kód: 13 bodů
(+) komentovaný a dobře čitelný kód
(-) v názvech (identifikátorech) nemíchej různé jazyky (sirka, mesto2D,
init, generate_map, ...), ideálně piš všechny anglicky
Generování města: 10 bodů (nesplňuje zadání pro
některé vstupy)
(-) kód nefunguje pro rozměry 1×1, 2×1, 1×2, 2×2
(-) pro stejné rozměry je město vždy stejné, generující "algoritmus" je
tedy velmi nezajímavý
(-) nesplňuje bod "alespoň 10% (zaokrouhleno nahoru) každého města musí
tvořit budovy" - např. pro rozměry 3, 50 vygeneruje 3 budovy namísto
povinných 5
Generování popisu grafu: 0 bodů (program nikdy nevygeneruje graf, popis je tedy tak nějak o ničem)
Funkčnost / bezchybnost: 15 bodů
(-) dodaný spustitelný soubor nelze spustit... Jeho název je psaný velkými
písmeny, kód však (dle mého názoru naprosto nesmyslně) kontroluje zda je
spuštěn ze souboru "towngen.exe" (malými písmeny)
( ) jinak program vypadá že funguje
Dodatečné poznámky:
seznam obrázků máš v souboru s příponou .ini, ačkoli ten soubor není v
INI formátu ( https://en.wikipedia.org/wiki/INI_file )
Mexikánec - 77 bodů
Kód: 4 body
(-) při neplatném parametru bys měl vypsat nějakou chybovou hlášku, ne
"tiše" ukončit program, už vůbec ne s kódem 0 (= všechno v pořádku)
(-) kódu by slušely nějaké ty komentáře
(-) používáš try-catch namísto podmínek - výjimky program zpomalují a
měly by značit výjimečnou situaci, ne něco, co je běžně
očekáváno
Generování města: 43 bodů
(+) město je generováno náhodně
Generování popisu grafu: 10 bodů
(-) zbytečně pomalé, jako popis (multi)grafu stačí vypisovat hrany (cesty
mezi "sousedními" vrcholy - mělo by na to stačit 1 prohledání města),
není třeba hledat cesty z každého vrcholu do každého
Funkčnost / bezchybnost: 20 bodů
(+) program vypadá že funguje, žádné chyby jsem nenašel
Dodatečné poznámky:
jediný výtvor, který město generuje náhodně, což mělo být účelem
soutěže (bohužel jsem do zadání zapomněl vepsat slovo "náhodně", čili
to z něj nebylo jasné)
Ladislav Ondris - 48 bodů
Kód: 5 bodů
( ) relativně čitelný kód, výjimkou je prohledávání města - tam bych
uvítal komentáře a ideálně oddělení do vlastní třídy
(-) křižovatky by bylo lepší si pamatovat než je neustále vytvářet skrze
metodu TryGetCrossroad
(-) název generovaných souborů je pevně daný (pro odlišný parametr
program vypíše chybu), pokud jako rozměr nezadám celé číslo > 0,
program vyhodí výjimku
(-) metoda Town.HasAlreadyGoneThrough je zbytečně pomalá, lepší než
neustále procházet již nalezenou cestu je si pro souřadnice pamatovat, zda
již byly navštíveny (např. v bool[,])
Generování města: 20 bodů
(-) pro stejné rozměry je město vždy stejné, generující "algoritmus" je
tedy velmi nezajímavý
Generování popisu grafu: 8 bod
(-) zbytečně pomalé, jako popis (multi)grafu stačí vypisovat hrany (cesty
mezi "sousedními" vrcholy - mělo by na to stačit 1 prohledání města),
není třeba hledat cesty z každého vrcholu do každého
Funkčnost / bezchybnost: 15 bodyů
(-) pro špatné zadání hází výjimky, vstup by měl být ošetřený
( ) jinak to vypadá že program funguje
Placku tedy získává Mexikánec Gratuluji 
Luboš Běhounek Satik:6.11.2017 14:04
Kód jsem neviděl, vyjádřím se jen ke tvým komentářům na komentáře
k programu
Je už celkem fuk, jaký používáš formátovaní názvů proměnných, ale
vždycky je dobrý bejt konzistentní, pokud máš něco česky, něco English,
neco činglish (třeba "inicialization"), tak pak číst ten kód po někom je
peklo, obzvlášť pokud cizinec dostane třeba kód, kde jsou kusy v češtině
.
To samý názvy proměnných, komentáře by neměly vysvětlovat název proměnný, ale doplňovat informace pro rychlejší pochopení daný části kódu, kde to nemusí bejt na první pohled vidět.
Samozřejmě není problém mít třeba řídicí proměnnou cyklu mít pojmenovanou jen "i" nebo "fr" pro soubor otevřený pro čtení, tohle jsou hodně běžné názvy, ale jakmile je to něco co se už týká danýho programu, snaž se ty názvy rozepisovat radši víc.
Název na kontrolu názvu exáče aplikace vidím poprvé a jeho smysl vůbec
nechápu
Já jsem teda rád, že Zdeněk Pavlátka furt něco takového dělá. Je to o
tom si vyzkoušet něco udělat než o té ceně (teda aspoň pro mě). Jinak
gratuluji vítězi, Mexikánec.
Luboš Běhounek Satik:6.11.2017 17:06
Když už jsme se dostali k cizincům, pokud dostanu na starost kód po cizinci, je to peklo samo o sobě.
Tohle je běžná praxe, že na stejném kódu dělají desítky lidí,
zvykej si, pokud neděláš na něčem úplně sám
Protože první kde začínám, nejsou názvy proměnných, ale komentáře vystihující účel a princip dané činnosti. To je to co dělá program srozumitelným. Tedy vystihnout účel a princip. Pokud to je jakýmkoli způsobem pro mě nepochopitelné, třeba špatně popsané, pak je to o to náročnější.
Komentáře bys neměl ani potřebovat, protože u dobře napsaný funkce většinou poznáš co dělá už z jejího názvu a názvů proměnných.
Pokud na projektu pracuje více lidí, musí se udržovat určitá firemní štábní kultura. Není možné si jen tak změnit názvy apod.To jistě ale jako programátor ve firmě moc dobře víš, co to přináší.
Měnit názvy proměnných na něco, co tu proměnnou líp vystihuje, je
právě naopak chtěný, protože to ušetří čas v budoucnu. Nikdo si ten
kód u rozsáhlejších projektů nepamatuje nazpaměť a nejvíc času při
přidávání nových věcí / opravování starých zabere právě orientace ve
starém kódu, protože většinou musíš nejdřív vůbec najít, který
místo budeš upravovat
Pokud se odkazuji či jakkoli identifikuji název programu, je dobré tuto hodnotu testovat. Pokud s touto hodnotou argumentu budu dále pracovat, pak je to snad jasné.
Rozhodně je to dost divné a nestandardní, že jen kvůli nápovědě vynucuješ název souboru... Buďto bych ten help napsal jinak, aby tam nebyl název souboru v příkladu a nebo ho zjistil při běhu a vlepil do toho help textu, takže když název změní, změní se mu i nápověda.
DarkCoder:6.11.2017 17:49
To je přeci normální. Bylo by krásné kdyby nebylo komentářů a
popisků třeba, realita je však hodně jinde. I rozdělení funkce na menší
části bez komentářů nezajistí vždy naprostou kontrolu a přehled nad
tím, co kód představuje. Stačí se vrátit po nějakém čase ke staré
aplikaci a hned si to vyžádá čas k ucelení všeho jak to tehdy bylo.
Souhlasím, měnit názvy je fajn, jen někde to musí projít schválením a
obeznámit všechny kolem. To
je naprosto v pořádku u helpu postupovat tak jak píšeš. V aplikaci to bylo
uvedeno záměrně v návaznosti na možnou chybovou hlášku.
// Kontrola spravneho poctu argumentu
if (argc != 4) {
printf("Chybny pocet zadanych parametru\n");
printf("Pouziti: towngen.exe <nazev> <sirka> <vyska>\n");
exit(1);
}Luboš Běhounek Satik:6.11.2017 18:09
J, vsak jen tvrdim, ze citelny nazvy funkci a promennych by mely mit prioritu
a az pak pripadne mit komentare, ne ze komentarem vyresis to, ze jsi promennou
pojmenoval tak, ze nikdo netusi, co dela
Tu hlasku bych resil rozhodne jinak, nez ze zakazes prejmenovani, aby help
sedel...
DarkCoder:6.11.2017 18:14
Ono je to také mnohem pohodlnější a časově méně náročnější
změnit jeden název než popsat principem x řádků textu.
Na ten název aplikace prostě nikdo nesmí sáhnout..
Ladislav Ondris:6.11.2017 21:41
Díky za mé vyhodnocení! I přesto, že jsem nevyhrál, jsem rád, že jsem
se zúčastnil a poučil jsem se.
Čekám už na dalšího machra! Jen je škoda, že se nezúčastnilo víc
lidí, příště to snad bude lepší.
A samozřejmě gratuluji vítězi
Zdeněk Pavlátka:6.11.2017 21:54
Ve městě musí být alespoň 1 budova, budova však nesmí být plně obklopena dalšími budovami - alespoň na jednom sousedním poli musí být silnice
U tohoto bodu uznávám, že v doslovném významu znemožňuje města 1×1 a
1×2 / 2×1, myšleno to bylo tak, že se ke každé budově musí dát dostat
(všude za okrajem jako by byla cesta) - pak by šly vytvořit jen z budov.
Bohužel jsem ho špatně formuloval.
n×1, 1×n pro 2<n<10 a 2×2 jsou ale jednoduché, viz obrázek.
Ladislav Ondris další machr už se připravuje
Luboš Běhounek Satik:6.11.2017 21:57
Tak jsem se na ten kod taky podival, doted jsem reagoval jen na komentare,
tady jsou nejaky moje postrehy ke kodu, ber to jako konstruktivni kritiku :
- vsechny ty konstanty jako indexy do pole image[] jsou po sobe jdouci cisla - hodil bych to do cyklu -> zkratil bys celej blok na dva radky
fscanf(fr, "%s", image[UNKN].file);
fscanf(fr, "%s", image[BUIL].file);
fscanf(fr, "%s", image[RO12].file);
fscanf(fr, "%s", image[RO23].file);
fscanf(fr, "%s", image[RO14].file);
fscanf(fr, "%s", image[RO34].file);
fscanf(fr, "%s", image[RO24].file);
fscanf(fr, "%s", image[RO13].file);- to samy nacitani obrazku a rozmeru, cca 30 radku se da zkratit na 6 diky jednomu cyklu
- mistama to michani cestiny a anglictiny pusobi az komicky, treba "tilesy" me
pobavily
- to samy algoritmus - urcite neni potreba ten algoritmus mit napsanej takhle ctyrikrat (zvlast pripady vetsi vyska / vetsi sirka a jestli je rozmer sudy nebo lichy), ale slo by to napsat obecne pro vsechny pripady
- kks a ksl bych pojmenoval treba kSudaLicha, kKratsiStrany,
je lepsi tady mit i komentar, ale stejne kdyz jsem koukal na tenhle kod, z
komentare jsem smysl tech dvou promennych nepochopil, az kdyz jsem se podival do
kodu. Clovek kdyz pak vidi kKratsiStrany, hned vi, co to je nez kdyz vidi jen tu
zkratku a nemuze si vzpomenout, co znamenala
DarkCoder:6.11.2017 22:34
- ano, lepší řešení. Důvodem byl lepší přehled pro práci s daným obrázkem. Zejména v použitém algoritmu.
- totéž co bod 1.
- Zde nesouhlasím, sudost nebo lichost možná, společně dle výšky a šířky už to tak nefunguje, proto dochází k rozdělení dle orientace. Způsob v programu nám dává snazší porozumění algoritmu. U velkých rozměrů by to šlo, u malých jsou drobné odlišnosti.
- kKratsiStrany a kSudaLicha jsou určitě vhodnější jména, pořád ale ne
úplně říkající co. Souhlasím, zde je větší komentář rozhodně
namístě, neboť se jedná o specifické proměnné. Možná kdyby se použil
název koefKratsiStrany resp. koefSudaLicha, bylo by to o poznání
srozumitelnější. To ale napadne až po "bitvě".
DarkCoder:6.11.2017 22:57
Ani u jedné varianty na sebe silnice nenavazují (podmínka 2). Tuto
podmínku lze splnit u města minimálně o velikosti 2x2. Pod podmínkou 3 beru
navazování silnic (kde např. na svislou silnici nelze zleva nebo zprava
napojit silnici vodorovnou nebo zespoda či ze shora navázat budovou, apod.).
Zkrátka pod podmínkou 2 a 3 beru to, že silnice nesmí mít konec. Jelikož
pro všechny platné vstupy splnující zadání, při kterých je možné
generovat město, existuje možnost vytvoření smyčky jako typu grafu, byl
můj program koncipován tímto směrem. Tedy aby vždy vytvořil smyčku.
Navíc možnost "obejít" řešit druhou část úlohy (datový soubor) byla
velmi lákavá.
DarkCoder:6.11.2017 23:29
Spíše jsem mohl vypsat konkrétní cestu smyčky, vybrat libovolný bod (pozici silnice), zvolit směr a popsat přesně celou trasu. Postupovat dle hodnot v poli až do počátečního bodu.
Tak třeba, na svislou silnici nemůže navazovat budova zeshora, stejně tak svislá silnice nemůže končit naspodu a na kraji zároveň (1x3, 1x4,1x5,1x6). U obrázku 2x2 je chybně pozice vpravo-nahoře a vlevo-dole. Zjednodušeně všechny konce silnic jsou chybně. Příklad 5x3 uvedený v zadání úlohy je správný.
Ještě k předchozímu příspěvku. Proměnné ksl a kkl měly pro mě
ještě jednu významnou hodnotu než jen rozlišení jak orientovat silnici,
zda doprostřed či do strany. Díky nim jsem věděl, jak je celá smyčka
dlouhá aniž bych ji musel složitě počítat. To byl pro mě významný
přínos. Otevřeně, druhou část úlohy jsem tak dokázal ošulit aniž bych
porušil zadání.
Zdeněk Pavlátka:6.11.2017 23:51
Tak třeba, na svislou silnici nemůže navazovat budova zeshora, stejně tak svislá silnice nemůže končit naspodu a na kraji zároveň (1x3, 1x4,1x5,1x6). U obrázku 2x2 je chybně pozice vpravo-nahoře a vlevo-dole. Zjednodušeně všechny konce silnic jsou chybně. Příklad 5x3 uvedený v zadání úlohy je správný.
Když to nechápeš jinak, vezměme to doslovně. "Silnice musejí tvořit souvislý graf (multigraf) = z libovolného místa na silnici musí být možno dojet na libovolné jiné místo." Do obrázku tedy doplním grafy - zelené kolečko je vrchol ze zadání, modrá čára je hrana. Pokud nevíš, co znamená souvislost grafu, vygoogli si to, tyhle grafy jsou souvislé.
Co tu tvrdíš je že město nemůže obsahovat slepou uličku (tedy musí být 2-souvislý), to ale v zadání není - to požaduje obyčejnou (1-)souvislost.
Luboš Běhounek Satik:7.11.2017 0:26
Ne, Zdeněk to má formulované dobře, to jen ty máš problém s
pochopením, co je souvislý graf .
Zobrazeno 48 zpráv z 48.