Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

Soutěž: Machr - Generování měst

Volná diskuze Machr - Generování měst

Soutěž již skončila

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 5

Aplikace 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:
  1. musí se jednat o textový formát
  2. musí odpovídat vygenerovanému městu - ke každému vrcholu nějak "připojte" jeho souřadnice na mapě
  3. 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 3

PNG: 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 vede

Celkem 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ýhra

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í
Aktivity (1)
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Zdeněk Pavlátka:18. října 0:41

V této soutěži budete generovat města

Soutěž končí 30. října 0:00, tak se nezapomeň zapojit! :)

Editováno 18. října 0:43
Odpovědět  +2 18. října 0:41
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Pavol Hejný
Autoredaktor
Avatar
 
Nahoru Odpovědět  -1 18. října 2:06
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Nahoru Odpovědět 18. října 9:11
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
krepsy3
Redaktor
Avatar
krepsy3:18. října 13:19

Kam mám plivat soubory?
Dejme tomu že máš batch ve složce C:/Users/Zdenek/Do­cuments/Machr/, kterým spustíš můj program umístěný v C:/Winapp/Machr/krep­sy3/
.
Soubory se mají objevit v dokumentech nebo ve winapp?
.
.
A mají být přepisovány, nechány být nebo pojmenovávány <název>.png, <název>(1).png, <název>(2).png atd.?

Editováno 18. října 13:19
Nahoru Odpovědět 18. října 13:19
Programátor je stroj k převodu kávy na kód.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na krepsy3
Zdeněk Pavlátka:18. října 13:36

Kam mám plivat soubory?

Soubory generuj ve složce, ve které je program spuštěn spuštěn (např. Environment.Cu­rrentDirectory v C#) - můžeš jednoduše použít relativní cestu.

A mají být přepisovány, nechány být nebo pojmenovávány <název>.png, <název>(1).png, <název>(2).png atd.?

Soubory přepisuj.

Nahoru Odpovědět  +1 18. října 13:36
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
krepsy3
Redaktor
Avatar
Odpovídá na Zdeněk Pavlátka
krepsy3:18. října 14:10

Děkuju. Přesně o to mi šlo, jestli Environment. CurrentDirectory nebo AppDomain.Curren­tDomain.BaseDi­rectory :)

Nahoru Odpovědět 18. října 14:10
Programátor je stroj k převodu kávy na kód.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Zdeněk Pavlátka
patrik.valkovic:18. října 16:16

Nesedí mi na zadání tři věci. Na první pohled to vypadá jako algoritmická úloha, ale nikde není řečeno, co se hodnotí. Poměr cest/budov? Nejdelší cesta? Variabilita zobrazení? Potom také nevím, jestli může být místo bez budovy. Pokud ano, jak ze souboru .dat poznáš, kde jsou budovy?
No a poslední je zmínka o multigrafu. Mezi souřadnicemi [0,0] a [1,0] přece může být jen jedna cesta, proč tedy multigraf? Kdyby byly uzly pouze křižovatky, zase z toho nepoznáš mapu, protože v .dat nebudou pospány zatáčky na silnici. Pokud jsou i zatáčky uzly, tak se zase dostáváme k problému s multigrafem.

Nahoru Odpovědět  +3 18. října 16:16
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
Zdeněk Pavlátka:18. října 16:45

1. "nikde není řečeno, co se hodnotí"
Hodnotí se použitý algoritmus a jeho rychlost

2. "jak ze souboru .dat poznáš, kde jsou budovy?"
nepoznám, podívám se na obrázek...

3. "Kdyby byly uzly pouze křižovatky, zase z toho nepoznáš mapu, ..."
nikde jsem nepsal, že z .dat souboru musí být možno nakreslit mapu města...
převod je z mapy na graf, nikoli opačně.

Nahoru Odpovědět 18. října 16:45
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Zdeněk Pavlátka
patrik.valkovic:18. října 16:52

Ale algoritmus přece něco řeší :D 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.

Nahoru Odpovědět  +2 18. října 16:52
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
Zdeněk Pavlátka:18. října 17:01

Když vyplivnu prázdnou plochu, tak je to rychlé a zadání jsem splnil.

V zadání je doslova "města se skládají ze silnic a budov". Tím je myšleno že na každém místě je buďto silnice nebo budova, žádné prázdné místo tam být nesmí

Obdobně nedokážeš bez dalších znalostí poznat, zda je .dat vygenerovaný dobře.

Budu mít zdrojové kódy řešení... (tam je docela vidět jak ten .dat soubor vytváříš)

Nahoru Odpovědět  +1 18. října 17:01
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Jenkings
Redaktor
Avatar
Jenkings:22. října 21:55

Jestli mi neuteklo nic ze zadání, pak můžu v podstatě udělat to, že na souřadnice 0,0 umístím budovu, a potom od ní hadovitě poskládám silnici (naprosto bez křižovatek), které vyplní všechna ostatní pole. Tím vlastně bude algoritmus velice jednoduchý,rychlý a zcela vyhovuje zadání ?

Nahoru Odpovědět  +1 22. října 21:55
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Jenkings
Zdeněk Pavlátka:22. října 22:40

Pro ujasnění jsem upravil zadání:

  • 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
Nahoru Odpovědět 22. října 22:40
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Zdeněk Pavlátka
patrik.valkovic:22. října 22:54

Stejně to pořád neřeší problém, že není podle čeho hodnotit, ale už to vzdávám se hádat...

Nahoru Odpovědět  +2 22. října 22:54
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Jenkings
DarkCoder:22. října 23:05

Myšlenka je to správná, nicméně toto nebude fungovat ve všech případech. Respektivě ne vždy dokážeš vytvořit cestu aniž bys nemusel vytvořit křižovatku nebo splnil podmínku o spojitosti silnice.

Editováno 22. října 23:06
 
Nahoru Odpovědět 22. října 23:05
Avatar
Ladislav Ondris:26. října 14:59

Tak a je to. Jsem zvědavý na řešení ostatních :-)

Nahoru Odpovědět  +1 26. října 14:59
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Ladislav Ondris:4. listopadu 20:21

Kdy bude nějaké vyhodnocení?

Nahoru Odpovědět 4. listopadu 20:21
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Ladislav Ondris
Zdeněk Pavlátka:4. listopadu 22:41

Vyhodnocení očekávejte během zítřka.

Nahoru Odpovědět 4. listopadu 22:41
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Zdeněk Pavlátka:5. listopadu 23:51

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.HasAlrea­dyGoneThrough 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 :)

Nahoru Odpovědět  +1 5. listopadu 23:51
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Jiří Gracík
Redaktor
Avatar
Odpovídá na Zdeněk Pavlátka
Jiří Gracík:6. listopadu 4:03

Sebrat někomu body za to, že neudělal něco, co nebylo vyžadováno v zadání, je fakt frajeřina.

Nahoru Odpovědět 6. listopadu 4:03
Creating websites is awesome till you see the result in another browser ...
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Jiří Gracík
Zdeněk Pavlátka:6. listopadu 5:44

Body jsem za to nesebral... Body byly rozděleny dle srovnání výtvorů

Nahoru Odpovědět  +1 6. listopadu 5:44
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:6. listopadu 12:45

K hodnocení mé aplikace:

(-) v názvech (identifikátorech) nemíchej různé jazyky (sirka, mesto2D, init, generate_map, ...), ideálně piš všechny anglicky

Proměnné se jmény i, kks, ksl či konstanty TILESIRKA, TILEVYSKA nikomu nic detailního stejně neřeknou a je jedno v jakém jazyce tyto jména jsou. Na rozdíl od komentářů. V programu je každá proměnná a každá funkce okomentována v jednotném jazyce a to je rozhodující. Ale budiž.

(-) kód nefunguje pro rozměry 1×1, 2×1, 1×2, 2×2

Opravdu? Když je kód okomentovaný a dobře čitelný, jak je možné přehlédnout první podmínku algoritmu?

// Kontrola vytvoreni spojite cesty a rozmisteni budov
if (((sirka < 2) || (vyska < 2)) || ((sirka == 2) && (vyska == 2))) {
        printf("Nelze vytvorit spojitou cestu a rozmistit budovy\n");
        printf("Mesto nebylo vygenerovano\n");
        exit(1);
}

(-) pro stejné rozměry je město vždy stejné, generující "algoritmus" je tedy velmi nezajímavý

Prosím o doložení podmínky, že město má být vygenerováno náhodně. Opravdu aplikace nesplňuje tuto podmínku?

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

Prosím o doložení znění zadání platného k času odevzdání mé aplikace. Opravdu se chová aplikace jinak než dle tohoto zadání?

Generování popisu grafu: 0 bodů (program nikdy nevygeneruje graf, popis je tedy tak nějak o ničem)

Opravdu? Smyčka není brána jako typ grafu? Pokud je možné vytvořit město dle zadání (jsou splněny veškeré podmínky), vytváří algoritmus vždy spojitou cestu. Grafem je vždy smyčka a tedy soubor je vytvořen a graf ohodnocen jeho délkou.

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

Ano, zde je chyba ve výrazu.

// Kontrola spravnosti nazvu aplikace
if (strcmp(argv[0], "towngen.exe")) {
        printf("Chybny nazev aplikace\n");
        exit(1);
}

Výraz má být v negaci a text velkými písmeny.

Pokud už ale vytvářím kontrolu v podobě:

// Kontrola spravneho poctu argumentu
if (argc != 4) {
        printf("Chybny pocet zadanych parametru\n");
        printf("Pouziti: towngen.exe <nazev> <sirka> <vyska>\n");
        exit(1);
}

Opravdu tam je pořád kontrola na spouštěný soubor naprosto nesmyslně?

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 )

Opravdu? Co vlastnosti souboru?

konfiguracni soubor

kde definice funkce:

void inicialization(char *filename) {
FILE *fr;

// Otevreni textoveho souboru pro cteni
fr = fopen(filename, "r");
if (fr == NULL) {
        printf("Chyba pri otevirani souboru %s\n", filename);
        exit(1);
}
...
}

a volání funkce:

inicialization("towngen.ini");

( ) jinak program vypadá že funguje

Vypadá že funguje nebo že funguje? Doufám, že když už byl program podroben nějaké analýze, že byl spuštěn a ne že si přečtu jen zdrojový soubor ze kterého vyvodím závěr. Soudím že ne, to by jinak odpadlo to, že kód nefunguje pro rozměry 1×1, 2×1, 1×2, 2×2.

 
Nahoru Odpovědět  ±0 6. listopadu 12:45
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na DarkCoder
Luboš Satik Běhounek:6. listopadu 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 :D

Nahoru Odpovědět  +7 6. listopadu 14:04
https://www.facebook.com/peasantsandcastles/
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na DarkCoder
Martin Dráb:6. listopadu 14:52

Vypadá že funguje nebo že funguje? Doufám, že když už byl program podroben nějaké analýze, že byl spuštěn a ne že si přečtu jen zdrojový soubor ze kterého vyvodím závěr. Soudím že ne, to by jinak odpadlo to, že kód nefunguje pro rozměry 1×1, 2×1, 1×2, 2×2.

Tvrzení "vypadá, že funguje" si myslím tady je přesnější. Zdeněk určitě provedl nějaké to testování na různých vstupech (na kterých program fungoval), ale určitě ne na všech možných (=> mohou existovat takové, na kterých nefunguje) a pochybuji, že formálně dokázal, že kód na všech vstupech funguje správně.

Co se týče nefungování na malých rozměrech (1x1, ...), pokud na nich existují validní města, tak tvůj program zadání opravdu nesplňuje. Ale jelikož není ani úplně jasné, proti jaké verzi zadání jsi programoval, tak toto nedokážu posoudit.

Editováno 6. listopadu 14:53
Nahoru Odpovědět  +3 6. listopadu 14:52
2 + 2 = 5 for extremely large values of 2
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Luboš Satik Běhounek
DarkCoder:6. listopadu 16:13

Když už jsme se dostali k cizincům, pokud dostanu na starost kód po cizinci, je to peklo samo o sobě. 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ší. 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áší. Jednotlivec si vše může upravit obrazu svému. Vím jak daná připomínka k programu byla myšlena, proto jsem i reagoval slovy: "ale budiž".

Jaký smysl mají komentáře moc dobře vím. Program je natolik jednoduchý k pochopení, že by i některé komentáře mohli být vynechány. Spoustu z nich jsem tam nechal z důvodu toho, že zde na fóru je spousta začínajících programátorů, kterým toto pomůže a snáze pochopí činnost programu. Je to jeden z účelů těchto soutěží.

Každý jsme jiný a každému název řekne něco jiného. i, fr jsou snadno identifikovatelné. kks, ksl na pár řádek, činnost a princip algoritmu na polovinu A4, apod. Na podobné hraní už by stálo tvořit vývojářskou dokumentaci. Ale pochybuji, že by se tu do ní někdo pouštěl pro tento typ a význam úlohy.

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

 
Nahoru Odpovědět  +1 6. listopadu 16:13
Avatar
IT Man
Redaktor
Avatar
IT Man:6. listopadu 16:21

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

Nahoru Odpovědět 6. listopadu 16:21
Cokoliv a kdokoliv může jednou uspět.
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na DarkCoder
Luboš Satik Běhounek:6. listopadu 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.

Nahoru Odpovědět  +3 6. listopadu 17:06
https://www.facebook.com/peasantsandcastles/
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Martin Dráb
DarkCoder:6. listopadu 17:21

Částečně souhlasím. Ono je to totiž hodně obecné vyjádření, když existuje nekonečně mnoho kombinací. V aplikaci rozhodně nejsou provedeny veškeré kontroly vstupu odpovídajícímu zadání. Nepracuje se s limity a detailní kontrolou řetězce. Číslo je totiž hodně obecný pojem. Tvrzení: "Vypadá že funguje" je skutečně přesnější, protože těžko mohli být aplikovány všechny varianty vstupu. Nicméně není složité vyjádřit naprosto přesně platnost vstupu. V tuto chvíli by mě zajímalo, jaké vstupy byly aplikovány - možný návrh k soutěžím, vyhodnocovatel by na oplátku dodal aplikaci se kterou aplikace testoval a sdělil vstupy.

Platnost vstupu jsou dány dvěma podmínkami:

  • platnost oboru a rozsah hodnot typu int
  • každá ze stran města musí mít alespoň velikost 2 a zároveň obě strany nesmí mít velikost 2.

To jsou podmínky při kterých to vždy funguje.

  1. podmínka ta je snad jasná
  2. podmínka udává možnost vytvoření města dle zadání. Je to dáno tím že silnice nemůže tvořit spojitý graf při velikosti 1, a druhá část podmínky je že nelze vytvořit město kde bude silnice tvořit spojitý graf a zároveň bude ve městě alespoň 1 budova.

Aplikace má omezení v délce názvu města a je omezena na vstup v rozsahu 1 - 99 pro obě velikosti stran.
To je jediné přidané omezení z důvodu velikosti generovaného města. Minimální velikost strany je stanovena na velikost 1 dle zadání.

Vaším úkolem bude napsat aplikaci, která dostane jako parametry string (název) a 2 čísla - šířku a výšku (obě budou >= 1).

Co se týče fungování na malých rozměrech aplikace pochopitelně funguje,

Pokud platí první podmínka vstupu a omezení jeho rozsahu (1-99) a délky názvu města dochází k testování druhé podmínky na validaci generování města. Takže pro vstupy ala 1x1, 1x2, 1x3, atd. a 2x1, 3x1, atd. a 2x2 dochází k výpisu chybové hlášky.

// Kontrola vytvoreni spojite cesty a rozmisteni budov
if (((sirka < 2) || (vyska < 2)) || ((sirka == 2) && (vyska == 2))) {
        printf("Nelze vytvorit spojitou cestu a rozmistit budovy\n");
        printf("Mesto nebylo vygenerovano\n");
        exit(1);
}

Ano, pro tyto velikosti nelze generovat město ale aplikace na to reaguje výpisem informace o nemožnosti generování města a následně ukončuje aplikaci. Na malých rozměrech (viz výše) nemohou existovat města splňující zadání. Tedy výrok, že aplikace nesplňuje zadání v malých rozměrech, je mylný.

Ona ta původní verze už na stránce není, ale abych Tě zasvětil do rozdílů. Aplikace byla odevzdána 21.10. a nová verze je ze dne 22. října 22:40.

  • města se skládají (pouze) ze silnic a budov

zůstalo nezměněno

  • 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

původní verze obsahovala přítomnost alespoň jedné budovy, podmínka obklopení zůstala stejná

  • alespoň 10% (zaokrouhleno dolů) každého města musí tvořit křižovatky

tato podmínka v původní verzi nebyla vůbec

Změny ač vypadají drobné, dokáží změnit použití celého algoritmu.

 
Nahoru Odpovědět  +2 6. listopadu 17:21
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Luboš Satik Běhounek
DarkCoder:6. listopadu 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);
}
 
Nahoru Odpovědět 6. listopadu 17:49
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na DarkCoder
Luboš Satik Běhounek:6. listopadu 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... :D

Editováno 6. listopadu 18:10
Nahoru Odpovědět 6. listopadu 18:09
https://www.facebook.com/peasantsandcastles/
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Luboš Satik Běhounek
DarkCoder:6. listopadu 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. :-D

Na ten název aplikace prostě nikdo nesmí sáhnout.. :-D

Editováno 6. listopadu 18:15
 
Nahoru Odpovědět 6. listopadu 18:14
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 19:01
K hodnocení mé aplikace:

(-) v názvech (identifikátorech) nemíchej různé jazyky (sirka, mesto2D, init, generate_map, ...), ideálně piš všechny anglicky
Proměnné se jmény i, kks, ksl či konstanty TILESIRKA, TILEVYSKA nikomu nic detailního stejně neřeknou a je jedno v jakém jazyce tyto jména jsou. Na rozdíl od komentářů. V programu je každá proměnná a každá funkce okomentována v jednotném jazyce a to je rozhodující. Ale budiž.

O tomhle se tu už snad řeklo dost, názvy by (ideálně) měly být jednotné a samovysvětlující.

(-) kód nefunguje pro rozměry 1×1, 2×1, 1×2, 2×2
Opravdu? Když je kód okomentovaný a dobře čitelný, jak je možné přehlédnout první podmínku algoritmu?

// Kontrola vytvoreni spojite cesty a rozmisteni budov
if (((sirka < 2) || (vyska < 2)) || ((sirka == 2) && (vyska == 2))) {
        printf("Nelze vytvorit spojitou cestu a rozmistit budovy\n");
        printf("Mesto nebylo vygenerovano\n");
        exit(1);
}

Nelze vytvorit spojitou cestu a rozmistit budovy

Pro rozměry 1×1, 2×2, 1×n, n×1 (kde 1 < n < 10) město vygenerovat lze... Nejde ho vygenerovat se smyčkou, ale to po tobě nikdo nechtěl.

(-) pro stejné rozměry je město vždy stejné, generující "algoritmus" je tedy velmi nezajímavý
Prosím o doložení podmínky, že město má být vygenerováno náhodně. Opravdu aplikace nesplňuje tuto podmínku?

Náhodnost nebyla podmínkou, ale když jí někdo úspěšně použil, je jeho řešení o to lepší (zajímavější) - tedy by měl dostat více bodů (jak jsem již psal, body za tuto kategorii jsem rozdělil hlavně podle srovnání výtvorů)

(-) 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
Prosím o doložení znění zadání platného k času odevzdání mé aplikace. Opravdu se chová aplikace jinak než dle tohoto zadání?

Ke změně zadání došlo 10 dní před ukončením soutěže (které jsem myslím kvůli této změně o pár dní posunul) / 4 dny po zahájení, na změnu jsi byl individuálně upozorněn (na což jsi odpověděl, tedy jsi o změně včas věděl).

Generování popisu grafu: 0 bodů (program nikdy nevygeneruje graf, popis je tedy tak nějak o ničem)
Opravdu? Smyčka není brána jako typ grafu? Pokud je možné vytvořit město dle zadání (jsou splněny veškeré podmínky), vytváří algoritmus vždy spojitou cestu. Grafem je vždy smyčka a tedy soubor je vytvořen a graf ohodnocen jeho délkou.

Graf je tvořen vrcholy a hranami. Jak sám píšeš (vypisuješ do .dat souboru), vrcholy tam nikdy nemáš. Hrany jsou "spojnice" mezi vrcholy. Čili by mě docela zajímalo, kde tam ten graf vidíš.

Navíc jsem při hodnocení přehlédl bod "alespoň 10% (zaokrouhleno dolů) každého města musí tvořit křižovatky", tvůj výtvor tedy splňuje zadání jen pro rozměry n×m, kde n > 1, m > 1, n * m < 10 a n a m nejsou zároveň 2 - tedy na rozměrech 2×3, 2×4, 3×2, 3×3, 4×2.

(-) 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)
Ano, zde je chyba ve výrazu.

// Kontrola spravnosti nazvu aplikace
if (strcmp(argv[0], "towngen.exe")) {
        printf("Chybny nazev aplikace\n");
        exit(1);
}
Výraz má být v negaci a text velkými písmeny.

Pokud už ale vytvářím kontrolu v podobě:

// Kontrola spravneho poctu argumentu
if (argc != 4) {
        printf("Chybny pocet zadanych parametru\n");
        printf("Pouziti: towngen.exe <nazev> <sirka> <vyska>\n");
        exit(1);
}
Opravdu tam je pořád kontrola na spouštěný soubor naprosto nesmyslně?

Ano, stále mi připadá nesmyslná. Řekl bych, že se nápověda má přizpůsobit programu, ne program nápovědě.

( ) jinak program vypadá že funguje
Vypadá že funguje nebo že funguje? Doufám, že když už byl program podroben nějaké analýze, že byl spuštěn a ne že si přečtu jen zdrojový soubor ze kterého vyvodím závěr. Soudím že ne, to by jinak odpadlo to, že kód nefunguje pro rozměry 1×1, 2×1, 1×2, 2×2.

Všechny výtvory byly testovány na více různých vstupech - např. malé n a m, velké (> 50) n a malé m a naopak, velké n i m, n=m a tak dále...

Nahoru Odpovědět 6. listopadu 19:01
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:6. listopadu 21:09
  • Co se týká jednotného jazyka, beru. Ovšem samovysvětlitelnost nelze vždy zajistit. Můžeš se pokusit nastudovat a vměstnat do stručného a výstižného názvu proměnné význam proměnných kks a ksl bez použití komentáře obsahující význam této proměnné.

Pro rozměry 1×1, 2×2, 1×n, n×1 (kde 1 < n < 10) město vygenerovat lze... Nejde ho vygenerovat se smyčkou, ale to po tobě nikdo nechtěl.

Prosím tedy o vygenerování města o velikosti 1x1, 1x2, 1x3, atd. a 2x1, 3x1, atd. a 2x2 kde platí všechny následující podmínky zadání:

  • V 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
  • 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.
  • Silnice na sebe musí opticky navazovat

Stačí mi jedno řešení z výše uvedených a může být i bez smyčky.

  • Z praktického hlediska je jistě zajímavější pokud je město generováno náhodně, získává to na unikátnosti. Pravidla však hovoří jasně, nikdo by neměl být postihován či zvýhodňován. Jednou je stanovený limit, kterého mohu dosáhnout a toho se držím. V opačném případě je to porušení pravidel na straně zadavatele. Přeci není tak těžké sdělit v zadání, že ten, kdo bude mít město náhodně vygenerované a tedy při zadání konkrétního vstupu generovat různá řešení, bude ohodnocen navíc +10 body. Zní to lépe.
  • Sám jsem si změny všiml. Oceňuji zaslání informace o změně. Změna pravidel proběhla i na stránce. Bohužel až po mém odevzdání. Posun termínu odevzdání ale proběhl v tichosti. Tato informace měla proběhnout veřejně, nikdo o tom nevěděl. Než měnit zadání v průběhu, vyjádřil bych se k tomu u vyhodnocení. To že představa výsledku řešení je jiná nežli podané zadání, za to se nikdo nemusí stydět.. Každý chybujeme.
  • Grafem je vždy smyčka a ta vrcholy nemá, proto informaci o vrcholech tam nikde nenajdeš. V popisu .dat souboru (typ souboru stanovený zadáním) najdeš rozložení města, pár nepodstatných parametrů, ale hlavně to jaký je to typ grafu! A jeho délku lze určit, ta je tam také. Nevidím rozpor řešení k původnímu zadání. Rozdílnost zadání jsem již sám napsal v jednom příspěvku výše. Jelikož v původním znění zadání nebyla stanovena podmínka křižovatek a můj algoritmus s křižovatkami nepracuje, nevidím nutnost je dělat aniž bych neporušil zadání.
  • Souhlasím, že nápověda se přizpůsobuje programu. Důvodem bylo párování programu s nápovědou. Způsobů, jakým to udělat je bezpočet. Já zvolil tento.
  • Pokud je to tak, tak je to v pořádku, dle zadání. Zejména testování pro nové zadání na hodnoty 2x3, 2x4 2x5, 2x6, 2x10, 2x21 a obráceně jsou nejzajímavější, neboť na ně nelze aplikovat stejný algoritmus jako na 3x3 a více.
 
Nahoru Odpovědět 6. listopadu 21:09
Avatar
Odpovídá na Zdeněk Pavlátka
Ladislav Ondris:6. listopadu 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 :-)

Nahoru Odpovědět 6. listopadu 21:41
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 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 ;)

Nahoru Odpovědět 6. listopadu 21:54
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na DarkCoder
Luboš Satik Běhounek:6. listopadu 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 :D
  • 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 :)
Nahoru Odpovědět  +2 6. listopadu 21:57
https://www.facebook.com/peasantsandcastles/
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:6. listopadu 22:09

Každý děláme chyby, i já. Ono někdy něco dokázat formulovat tak jak to zamýšlíme nemusí být snadné.
Na obrázku je 5 variant, ale ani jedna není dle zadání správná (podmínka 2 a 3 není splněna). Nebudu napínat, takové město o velikosti 1x1, 1x2, 1x3, atd. a 2x1, 3x1, atd. a 2x2 , aby byly uvedené podmínky splněny, vytvořit nelze.

 
Nahoru Odpovědět 6. listopadu 22:09
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Luboš Satik Běhounek
DarkCoder:6. listopadu 22:34
  1. 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.
  2. totéž co bod 1.
  3. 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.
  4. 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ě". :-)
Editováno 6. listopadu 22:35
 
Nahoru Odpovědět 6. listopadu 22:34
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 22:34

podmínka 2 a 3 není splněna

A co na nich není splněno? U všech těch ukázek je silnice spojitá, tedy bod 2 platí. Žádné optické problémy (díly které k sobě nepasují) nevidím, tedy i 3. bod platí.

Nahoru Odpovědět 6. listopadu 22:34
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 22:55

Ještě k tvé poznámce -

Grafem je vždy smyčka a ta vrcholy nemá, proto informaci o vrcholech tam nikde nenajdeš.

Graf lze reprezentovat různě, např. seznam vrcholů a seznam hran, či matice sousednosti. Taková reprezentace je až na isomorfismus jednoznačná. Pak by tedy ta tvoje smyčka nějakou takovou reprezentaci měla mít, pokud ji nemá ("reprezentace" nic neobsahuje - např. prázdné seznamy), je isomorfní prázdnému grafu (tedy vlastně "ničemu", navíc "prázdný graf" se typicky nepovažuje za graf). Pokud by reprezentace existovala, mohl jsi jí vypsat.

Definice grafu z wikipedie ( https://cs.wikipedia.org/…_graf%C5%AF)#… ):

Neorientovaný graf je dvojice G = <V, E>, kde V je neprázdná množina tzv. vrcholů (někdy také uzlů) a E ⊆ {{u, v} | u, v ∈ V, u ≠ v} je množina dvouprvkových množin vrcholů, tzv. (neorientovaných) hran.

Totéž platí o orientovaných grafech a multigrafech.

Nahoru Odpovědět 6. listopadu 22:55
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:6. listopadu 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á. :-D

 
Nahoru Odpovědět 6. listopadu 22:57
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 23:04

2. podmínka

  • Ukaž mi jediné místo, na kterém na sebe silnice v mých ukázkách (v rámci jednoho města = rámečku) nenavazují. Já tam žádné takové nevidím.

3. podmínka

navazování silnic (kde např. na svislou silnici nelze zleva nebo zprava napojit silnici vodorovnou nebo zespoda či ze shora navázat budovou, apod.)

  • A co z toho nesplňuji?
Nahoru Odpovědět 6. listopadu 23:04
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:6. listopadu 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í. :-D

 
Nahoru Odpovědět 6. listopadu 23:29
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:6. listopadu 23:49

bod 2)
Představ si to v reálu, silnice ve městě.
Kruhový objezd, nemá žádný konec, toto napojení je v pořádku.
Slepá ulice, má svůj konec, nejspíš na ni navazuje budova nebo konec města, toto napojení je špatně

bod 3)
Tady už je to složitější na něčem ukázat, ale zde už je opticky vidět že na sebe dvě silnice, ač jsou u sebe, nenavazují. Zkusím přirovnat ke kostkám lega. Teď to chce velkou představivost. Pokud k vodorovně položené kostce s přichycením shora nebo zdola přiložíš shora kostku natočenou o 90° do strany, tak ji nenapojíš. Anebo typ silnice v levém dolním rohu. Nemůže tam být křižovatka, ikdyž mohou na sebe navazovat. Stejně tak tam nemůže být svislá ani vodorovná silnice. Pouze zatáčka shora-vpravo.

Teď když nad tím tak přemýšlím, neviděl jsem výstupy programu ostatních soutěžících. Jak Ti to mají?

 
Nahoru Odpovědět 6. listopadu 23:49
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 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.

Nahoru Odpovědět 6. listopadu 23:51
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na DarkCoder
Zdeněk Pavlátka:6. listopadu 23:56

Stěžuješ si na mojí změnu zadání, ale sám si do něj teď přidáváš a upravuješ co se ti hodí...

Nahoru Odpovědět 6. listopadu 23:56
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
DarkCoder:7. listopadu 0:16

Na obrázku jsi přesně vyznačil místa, která jsou špatně. Konce silnic nekorespondují se zadáním - na sebe nenavazují. Je to jako vytvoření rybářské sítě, kde její oka představuji silnice. Tedy minimální rozměr pro zajištění spojitosti a návaznosti je velikost města 2x2, k té je ale třeba přidat budovu a proto rozměr 2x3 nebo 3x2 je minimální pro splnění úlohy dle zadání. Pokud si to myslel jinak, bylo třeba to lépe formulovat a nikoli se ted naprosto zbytečně rozčilovat.

 
Nahoru Odpovědět  -1 7. listopadu 0:16
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na DarkCoder
Luboš Satik Běhounek:7. listopadu 0:26

Ne, Zdeněk to má formulované dobře, to jen ty máš problém s pochopením, co je souvislý graf :) .

Nahoru Odpovědět  +2 7. listopadu 0:26
https://www.facebook.com/peasantsandcastles/
Avatar
DarkCoder
Člen
Avatar
DarkCoder:7. listopadu 1:11

Ano, chybně jsem si vyložil zadání spojitosti se kterou tak vznikly chyby v mé aplikaci. Vítězi gratuluji.

 
Nahoru Odpovědět 7. listopadu 1:11
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 48 zpráv z 48.