Soutěž: Machr na OOP - Tvorba silniční sítě

C# .NET .NET (C# a Visual Basic) Machr na OOP - Tvorba silniční sítě American English version English version

Soutěž již skončila

Zadání

Vítám Vás u dalšího machra na OOP a algoritmy. Vašim úkolem bude navrhnout silniční síť pro část krajiny podle zadaných kritérií. Algoritmus a OOP budou hodnoceny nezávisle na sobě. Placky budou rozdány pro OOP i pro algoritmus.

Povolené jazyky jsou kromě C# také Java, C++ a PHP. Další jazyky po konzultaci se mnou. Pokud povolím další jazyk, uvedu to v komentářích, proto prosím čtěte i komentáře.

Zadání

Program si bude muset přečíst data ze souboru input.txt a výstup uložit do souboru output.txt. Program se bude skládat z několika částí, které lze do určité míry řešit samostatně. Celkový počet bodů bude rozdělen mezi pod úkoly. Souřadnice jsou udávány v pravoúhlém souřadnicovém systému. Ukázkový „input.txt“ :

MESTA
0: 12.60; 14.80
1: 18.40; 20.40
2: 14.60; 18.70

SILNICE
0: 14; 3.00
1: 25; 2.00
2: 48; 0.50

FINANCE
565

PODMINKY
1; 2; 4.00
0; 2; 21.60

KRAJINA
2.50; 5.00; 6.00; 10.00; 11.00
0.40; 2.00; 2.00; 2.20; 3.10

1. - Program v souboru dostane tabulku měst a dostupných silnic. Město je určeno svou pozicí v pravoúhlé soustavě souřadnic. Silnice je určena svoji cenou a časem, který odpovídá jednotkové délce silnice (řekněme 1 kilometr). Města budou vždy minimálně dvě, cesta vždy minimálně jedna.

  • Město s indexem 0 je na pozicích X[12.6, 14.8]
  • Město s indexem 1 je na pozici Y[18.4, 20.4]
  • Silnice s indexem 0 stojí 14 korun na jednotku délky a cesta bude trvat 3 minuty
  • Pokud postavím silnice typu 0 mezi městy s indexy 0 a 1, bude cena dálnice |XY|*14 = 8 * 14 = 112 korun a cesta bude trvat |XY| * 3.0 = 24 minut. Poznámka: |XY| je vzdálenost mezi městy 0 a 1.

Vašim úkolem bude spojit všechny města tak, aby se dalo z každého města dostat do libovolného jiného města (každé město musí být připojeno k silniční síti). Silnice můžou být pouze přímé a postaveny mezi dvěma městy.

2. - V souboru budou dále uvedeny finance a podmínky, které silniční síť musí splňovat. Finance bude číslo, které nesmíte překročit. Podmínky jsou definované jako index počátečního města, index cílového města a čas, který nesmí cesta překročit.

  • Celkem mám na výstavbu 565 korun
  • Z města o indexu 1 se musím dostat do města o indexu 2 za 4 minuty
  • Z města o indexu 0 se musím dostat do města o indexu 2 za 21.6 minuty

Úkolem bude navrhnout silniční síť tak, aby podmínky splnila a nepřekročila dostupné finance. Počet dostupných financí bude v souboru vždy, podmínky být uvedeny nemusí (poté by byl uveden pouze nápis PODMINKY bez záznamů). Počet řešení, které podmínky i maximálně finance splňují, může být několik. Stačí vypočítat pouze jedno.

3. - V souboru bude uveden seznam krajin, které se v regionu vyskytují. Rychlost provozu na silnici závisí na vzhledu krajiny. Krajina může rychlost provozu zpomalit nebo zrychlit. První číslo je konstanta, která bude násobit čas pro danou silnic v této krajině. Další čtyři parametry určují obdélník (krajiny mají pouze obdélníkový tvar) – počáteční bod (x,y) a rozměry obdélníku (šířka a výška).

  • První krajina násobí potřebný čas konstantou 2.5 – bude-li silnice o indexu 0 probíhat touto krajinou, je potřeba počítat 2.5*3.0=7.5 minuty na jednotku délky.
  • První krajina má levý horní roh v souřadnicích 5,6 a dolní pravý roh v souřadnicích 5+10 = 15, 6+11 = 17.

Vašim úkolem bude navrhnout silniční síť tak, aby byly splněny předcházející podmínky a zároveň byly do výpočtu zahrnuty krajiny.

Čísla, která jsou zapsány v ukázkovém vstupním souboru s desetinou čárkou, budou mít vždy dvě desetinná čísla. Počet různých měst, cest, podmínek a krajin může být maximálně 1000.
Testovací soubory budou připraveny tak, že bude vždy možné spojit všechny města, dodržet podmínky a vlézt se do rozpočtu – bude vždy existovat alespoň jedno řešení. Pro úspěšné splnění testu stačí najít pouze jedno řešení.

Připravil jsem testovací soubory, na kterých můžete aplikaci vyzkoušet. Můžete je najít zde.

Výstupní formát

Do výstupního souboru bude program vypisovat pouze silnice, které budou spojovat jednotlivé města. Bude se jednat o sérii celých čísel, oddělené středníkem. Bude uvedeno město, ze kterého silnice vychází, dále město, do kterého silnice vede a typ silnice, kterou program použil. Pro ukázkový příklad a první úkol (spojení všech měst), může soubor vypadat následovně:

0;1;1
1;2;2

Město o indexu 0 je spojeno s městem o indexu 1 silnicí typu 1. Město o indexu 1 je spojeno s městem o indexu 2 silnicí typu 2.

Výhra

Vítěz dostane placku Machr na OOP nebo algoritmus a ocenění do portfolia.

Výhra

Výsledky

Jméno bodů Řešení ( Stáhnout vše )
tomisoka 50 Stáhnout řešení
JOF 41 Stáhnout řešení
Jenkings 35 Stáhnout řešení
Ladislav Ondris 5 Stáhnout řešení
BlugW 0 Stáhnout řešení
Patrik Smělý (SogoCZE) 0 Stáhnout řešení
Honza Bittner 0 Stáhnout řešení
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Tentokrát budeme programovat aplikaci, která co nejefektivněji navrhne silniční síť pro část krajiny. Čas si dáme dva týdny.

Soutěž končí 11.10.2015 13:00:00, tak se nezapomeň zapojit! :-)

Odpovědět  +2 27.9.2015 12:42
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
IT Man
Redaktor
Avatar
IT Man:

BlugW: zase prázdné řešení nebo jsi opravdu za 3 minuty stihl udělat celé zadání? :D

Nahoru Odpovědět  +1 27.9.2015 13:06
Když nevíš jak dál, podá ti ruku někdo, od koho by jsi to nečekal. A tu šanci musíš přijmout!
Avatar
BlugW
Redaktor
Avatar
Odpovídá na IT Man
BlugW:

Zkoušel jsem jestli je to už opravené :D

Nahoru Odpovědět  +2 27.9.2015 13:22
Pořiď si mac na www.appletrh.cz. Novinky a zajímavosti ze světa Apple na https://www.applemagazin.eu
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

Předem avizuji že ještě nevím, zda se stihnu zúčastnit,ale měl dvě otázky ohledně krajin.:

Pokud silnice prochází nějakým typem krajiny, tak se tou konstantou krajiny násobí celá délka dané silnice, nebo jen ta část která se nachází uvnitř této krajiny?

A druhá otázka tak trochu záleží na odpovědi na tu první, ale pokud by silnice procházela více krajinami, pak celou silnici postupně vynásobím konstantami pro všechny tyto krajiny ?

Nahoru Odpovědět 27.9.2015 19:51
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Jenkings
patrik.valkovic:

Násobí se vždy jen délka v krajině. Musíš zjistit délku v konkrétní krajině. Výchozí je konstanta 1.

Nahoru Odpovědět  +1 27.9.2015 20:01
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na patrik.valkovic
Jenkings:

Díky.
Určitě se pokusím něco vymyslet, ale v tomhle si moc nevěřím :(

Nahoru Odpovědět 27.9.2015 20:03
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ladislav Ondris:

Mám dva dotazy.

  1. Musí být spojeno každé město s každým?
  2. Proč ve výstupním formátu u příkladu není spojení měst 0 a 2, když je toto propojení zadané v podmínce? Nebo ta podmínka platí pouze, jestliže propojení mezi těmito městy uskutečníme?

Díky.

Nahoru Odpovědět 27.9.2015 20:32
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ladislav Ondris
patrik.valkovic:

Cesty musí být udělané tak, aby se šlo dostat z libovolného města do libovolného jiného (ale můžeš projít skrz několik měst). Graf může ve výsledku vypadat například takto: http://ltwp.net/…es/graph.png. Z jednoho města mžůe vybíhat jeden nebo i několik cest.
Podle podmínek určíš, zda existuje dostatečně rychlá cesta. Například v příkladu se dostaneš z 0 do 2 skrz 0 -> 1 -> 2. Tedy projdeš městem 1 k tomu, abys spojil město 0 a 2.
Stačí to vysvětlit takhle?

Nahoru Odpovědět  +1 27.9.2015 21:42
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

No, já jsem stále ve stádiu úvah,ale pořád ne a ne na nic přijít. Ve všech nápadech, které jsem zatím měl by vznikaly křížící se silnice a podobné anomálie a jediné co jsem zatím nevyloučil je brute-force metoda :D

Nahoru Odpovědět 27.9.2015 21:53
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Silnice se křížit mohou :D Ale spíš si to představ jako že můžeš silnici přemostit :D Kdyby se měli ještě křížit, dostal bys mnohem složitější problém s více proměnnými :D

Nahoru Odpovědět 27.9.2015 21:55
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na patrik.valkovic
Jenkings:

Ano, ale už tím, že se dostanu do situace,kdy se silnice kříží, tak dostávám v podstatě neefektivní řešení.

Tudíž začínám dost vážně uvažovat nad brute-force metodou se zpětnou kontrolou :D :D

Nahoru Odpovědět 27.9.2015 21:59
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Jenkings
patrik.valkovic:

To nevím, jestli si pomůžeš :D Vzhledem k tomu, že tam jsou dvě proměnné (cena a čas) se dostáváš do NP složitosti (musíš spočítat prvně psočítat graf, který spojuje města, kde ten stejný graf se může sám měnit v závislosti na typu silnice. A nad každým takovým grafem musíš ještě spočítat, zda vyhovuje cenou i podmínkám). Je to řešení, ale problém by měl být napsaný tak, aby spočítal cesty v rozumném čase (né za 10 hodin) - takové řešení není správné :D

Nahoru Odpovědět  +2 27.9.2015 22:05
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Ladislav Ondris:

Díky moc za vysvětlení. Už je mi to jasný :-)

Nahoru Odpovědět 27.9.2015 22:31
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
rikenbekr
Člen
Avatar
rikenbekr:

Chápu spravně že silnice se nedrží čtvercové sítě?

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

Ne, silnice nemají čtvercový tvar - spojují města mezi sebou. nejlépe se k tomu hodí právě obrázek, který jsem poslal tři příspěvky zpátky.

Nahoru Odpovědět  +1 27.9.2015 22:43
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
rikenbekr
Člen
Avatar
rikenbekr:

A s jakou přesností se má počítat délka případné silnice?

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

Když se podíváš na zadání, tak je to otázka irelevantní.
Čas máš na dvě desetinná místa, výsledný čas pro podmínku musí být menší než toto číslo (i kdyby jen o 0,0001).
Ale řekněme, že na 4 desetinná místa.

Nahoru Odpovědět  +1 27.9.2015 22:54
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ladislav Ondris:

Zkouším si přepočítat uvedený příklad, ale nevychází mi to. Nevychází mi podmínka, že z města 0 do města 2 musíme být do 8.6 minut. Ve výstupních údajích máš, že povede cesta z města 0 do města 1 po silnici typu 1, což jsou 2 minuty pro jednotku vzdálenosti. Město 0 je od města 1 vzdáleno 8.06 jednotek vzdálenosti. Což je něco přes 16 minut. Ještě jsme se nedostali do města 2 a už nám neplatí podmínka. Taky mi nevycházejí finance na tyto vzdálenosti. Řekne mi někdo, kde se stala chyba? :-)

Editováno 27.9.2015 23:30
Nahoru Odpovědět  +1 27.9.2015 23:28
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ladislav Ondris
patrik.valkovic:

Chyba je u mě ;-)
Je to jen ukázka vstupu a ukázka výstupu. Výstup by splnil pouze podmínku 1, ale zbylé už ne. V tomto případě dokonce ani řešení neexistuje (v testovacích souborech bude řešení vždy!). jednalo se pouze u ukázku vstupního a výstupního formátu.

edit: ukázkový vstupní soubor jsem přepsal, teď by to už mělo vycházet.

Editováno 27.9.2015 23:39
Nahoru Odpovědět  +1 27.9.2015 23:37
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět 27.9.2015 23:43
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

Tak zatím to vypadá že jsem vyzkoušel všechny slepé cesty :D
takže nejspíš odkládám, a třeba mně ještě něco napadne během těch 13 dní :D

Nahoru Odpovědět 28.9.2015 9:48
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Jenkings
patrik.valkovic:

Uvidím co ostatní, ale jestli to moc nepůjde, tak bych mohl tak 5 dní před koncem napsat postup, jak by se to mohlo řešit ;-) Alespoň použité algoritmy.
Proto piště i ostatní, jak jste na tom ;-)

Nahoru Odpovědět 28.9.2015 10:51
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na patrik.valkovic
Jenkings:

Zatím jsem si tak nějak napsal vizualizaci problému, a zpracování vstupu, tak aby se s tím dalo jednoduše pracovat. Takže když přijde múza tak se na to můžu rovnou vrhnout :D

Nahoru Odpovědět 28.9.2015 11:02
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Odpovídá na patrik.valkovic
Ladislav Ondris:

No já jsem zatím ve fázi na papíře a rozmýšlení, jak to udělat :-)

Nahoru Odpovědět 28.9.2015 11:21
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
D0ll0k
Člen
Avatar
D0ll0k:

Můžu to udělat ve WPF?

Nahoru Odpovědět 28.9.2015 12:09
Ten, co se snaží "programovat"
Avatar
polemes
Redaktor
Avatar
polemes:

Ceny dostanou vsichni co odpovi spravne?

Nahoru Odpovědět 28.9.2015 12:48
5 + 5 = 1010
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na D0ll0k
patrik.valkovic:

K čemu WPF, když to stejně musí vypsat výsledek do souboru? To je zbytečné, ale jak chceš, sám si to stížíš.

Nahoru Odpovědět 28.9.2015 12:54
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na polemes
patrik.valkovic:

Cenu dostane jen nejlepší řešení. Zpravidla bývá pouze jedno. Pokud bude kvalitních řešení více, snad se mi podaří domluvit s Zdeněk Pavlátka, že by mohlo dostat ocenění více lidí.

Nahoru Odpovědět 28.9.2015 12:56
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
polemes
Redaktor
Avatar
polemes:

a musi ty cesty ten program vypocitat sam?

Nahoru Odpovědět 28.9.2015 13:00
5 + 5 = 1010
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na polemes
patrik.valkovic:

Samozřejmě, máš to už v prvním bodu.

Nahoru Odpovědět 28.9.2015 13:01
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
polemes
Redaktor
Avatar
polemes:

promin sry

Nahoru Odpovědět 28.9.2015 13:01
5 + 5 = 1010
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

No, tak mapa bez silnic sice vypadá hezky,ale co z toho :D

Nahoru Odpovědět  +1 28.9.2015 19:29
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ondrca
Redaktor
Avatar
Ondrca:

Koukám, že nejhorší bude asi naparsovat ten input :D

Nahoru Odpovědět 28.9.2015 19:52
Zase jsem o něco chytřejší
Avatar
Odpovídá na Ondrca
Michal Haňáček:

Proč? Oddělovače jsou jasně dané ... :-)

Nahoru Odpovědět 28.9.2015 19:54
Každé rozhodnutí a každý krok v životě nás někam posune. Bohužel jen některé nás posouvají dopředu.
Avatar
Ondrca
Redaktor
Avatar
Nahoru Odpovědět 28.9.2015 19:57
Zase jsem o něco chytřejší
Avatar
D0ll0k
Člen
Avatar
D0ll0k:

Tak jsem zkejsnul hned na convertovani stringu do double...

Nahoru Odpovědět 29.9.2015 14:56
Ten, co se snaží "programovat"
Avatar
D0ll0k
Člen
Avatar
Odpovídá na Milan Křepelka
D0ll0k:

Díky, ale ja jsem měl na mysli konvert z input.txt do double. Nejdou mi zapsat desetinne cisla, jen cela.

Nahoru Odpovědět  +1 29.9.2015 21:18
Ten, co se snaží "programovat"
Avatar
Odpovídá na D0ll0k
Štefan Pružinský:

Ahoj. Aj napriek tomu, že si môj súper Ti poradím. :) Metóda double.Parse() konvertuje desatinné čísla v tvare:

4,33

a nie tvare:

4.33

Riešenie je však jednoduché, stačí to ošetriť takto:

string s = "25.14";
double number = double.Parse(s.Replace('.', ','));

Veľa zdaru! :)

Nahoru Odpovědět  -3 29.9.2015 21:28
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na D0ll0k
patrik.valkovic:

Když víš, že budou všechny čísla v tomto formátu, je lepší použít

Thread.CurrentThread.CultureInfo = new CultureInfo("en-US");

Máš jistotu, že to pojede na všech systémech.

Nahoru Odpovědět  +4 29.9.2015 21:30
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Štefan Pružinský:

Inak, parsovanie už mám hotové. :)
patrik.valkovic
Veľmi pekné a zaujimavé zadanie. Dúfam, že sa mi podarí vymyslieť správny algoritmus a zapojiť sa do súťaže. :)

Nahoru Odpovědět  +1 29.9.2015 21:31
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
Odpovídá na patrik.valkovic
Štefan Pružinský:

Aha, tak priznávam omyl. :) Záleží to do regionálneho nastavenia.

Nahoru Odpovědět 29.9.2015 21:33
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
JOF
Tým ITnetwork
Avatar
JOF:

Ahoj,
to zadání vypadá super. Doufám, že stihnu taky něco vytvořit.
Měl bych 2 dotazy.
Mohou se vyskytovat i záporné souřadnice? (jen pro kontrolu vstupu)
Pokud silnice povede přesně po hranici krajiny, bude se na ní vztahovat pravidlo této krajiny?
(Ve speciálním případě - co když budou mít 2 krajiny společnou hranici a po této hranici povede také silnice?)
Dík za odpovědi.

 
Nahoru Odpovědět 30.9.2015 9:23
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na JOF
patrik.valkovic:

Dobré otázky :)
Souřadnice záporné nebudou, ale koneckonců, když použiješ float.Parse, tak by ti to mělo být jedno, protože to přechroustá ;-)
Na hranici krajiny se také vztahuje pravidlo krajiny. Hranice dvou krajin se dotýkat nebudou. Krajiny se nebudou ani překrývat (nevím, jestli jsem to už někde zmiňoval).

Nahoru Odpovědět 30.9.2015 9:50
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
D0ll0k
Člen
Avatar
Odpovídá na Štefan Pružinský
D0ll0k:

Díky moc. Ani nevíš, jak jsi mi pomohl s tou čárkou.

Nahoru Odpovědět  +1 30.9.2015 14:29
Ten, co se snaží "programovat"
Avatar
Ondřej Krsička
Redaktor
Avatar
Ondřej Krsička:

Může být jeden úsek silnice typu 1 a druhý typu 2? nebo má jedna silnice jen jeden typ?

 
Nahoru Odpovědět 30.9.2015 16:28
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Jedna silnice má pouze jeden typ. Ten vždy začíná a končí ve městě, nemůže se uprostřed cesty změnit ;-)
Vidím, že je to zadání pro vás lehké, když ještě vymýšlíte, jak si to zkomplikovat :D

Nahoru Odpovědět  +3 30.9.2015 16:30
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

Zjištění vzdálenosti a času je lehký, ale to dál nevim nevim. stačí na ten samotnej generátor matika ZŠ do 8. třídy? :D

 
Nahoru Odpovědět 30.9.2015 18:22
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Jistě, to je jen otázka algoritmu ;-) Pohledej na internetu a určitě něco najdeš :)

Editováno 30.9.2015 18:48
Nahoru Odpovědět  -1 30.9.2015 18:48
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na D0ll0k
Štefan Pružinský:

Nemáš začo, ale myslím, že Patriková rada bola komplexnejšia a univerzálnejšia. :)

Nahoru Odpovědět 30.9.2015 19:12
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
Odpovídá na patrik.valkovic
Štefan Pružinský:

Potom to však stráca zmysel... :(

Nahoru Odpovědět  +1 30.9.2015 19:13
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

Netuším, co bych měl hledat :D

 
Nahoru Odpovědět 30.9.2015 19:24
Avatar
vosa53
Člen
Avatar
Odpovídá na Štefan Pružinský
vosa53:

Přesně tak, je to přece machr na algoritmy a OOP, měli bychom to tudíž vymyslet sami. To už rovnou můžeme soutěžit kdo najde lepší algoritmus... Mně nejtěžší zatím příjde zjištění jak dlouhá část silnice a jestli vůbec koliduje s určitou krajinou.

 
Nahoru Odpovědět  +2 30.9.2015 19:28
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na vosa53
patrik.valkovic:

Jestli silnice koliduje s jinou je pouze analytická geometrie, nic víc.
Je to machr na algoritmy, ne machr na tvoření algoritmu. Ty algoritmy už byli vymyšleny kvůli jejich univerzálnosti. Když budeš řešit nějakou úlohu, budeš si vždy vymýšlet algoritmus? no to není jen najít si algoritmus, jde i o to algoritmus správně implementovat na určitý problém, který řešíš. Taky je potřeba umět algoritmy "zřetězit", abys dostal požadovaný výsledek. U této úlohy je algoritmů hned několik (v základu 2), ale je třeba také řešit spoustu věcí okolo. Nemyslím si, že by šo vymyslet algoritmus, který by nahradil již existující s tím, že by byl efektivnější. Padla tady zmínka o hrubé síle - ale jak dlouho to bude počítat? Něco nového jen těžko vymyslíš.

Nahoru Odpovědět  +2 30.9.2015 20:37
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
vosa53
Člen
Avatar
Odpovídá na patrik.valkovic
vosa53:

Ok, asi máš pravdu. :)

Editováno 30.9.2015 21:08
 
Nahoru Odpovědět 30.9.2015 21:07
Avatar
Patrik Smělý (SogoCZE)
Tým ITnetwork
Avatar
Patrik Smělý (SogoCZE):

Sakra, omylem jsem klikl na tlačítko odevzdat :D to tam není žádná ochrana ? Vždyť jsem ani nevybral žádný soubor ...

Nahoru Odpovědět 2.10.2015 14:27
PHP můj oblíbený jazyk......
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Patrik Smělý (SogoCZE)
patrik.valkovic:

Ošetřené to není, ale myslím že David to už má v TODO listě ;-)

Nahoru Odpovědět 2.10.2015 14:30
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Patrik Smělý (SogoCZE)
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
Patrik Smělý (SogoCZE):

Však to snad je funkce formulářové frameworku, teda aspoň u svého to tak mám :D. No to je jedno každopádně se omlouvám :).

Nahoru Odpovědět 2.10.2015 14:32
PHP můj oblíbený jazyk......
Avatar
Odpovídá na patrik.valkovic
Ondřej Langr (andysekcze):

TODO: udělat si TODO list? :D... Just a joke. Nebýt línej tak se taky účastním :-P

Nahoru Odpovědět  +1 2.10.2015 14:33
I have a charger. I have Note 7. Umh I haven't Note7.
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

No, tak se přiznejte, pokročil někdo ?
Já už si s tím lámu hlavu skoro týden a pořád mně nenapadlo nic uspokojivého.
Googlil jsem několik hodin a taky jsem nic podnětného nenašel. I když je pravda že jsem vyzjistil že to nějak souvisí s teorií grafů atd, nicméně o této problematice nevím téměř nic. V podstatě jsem jen věděl že něco takového existuje...

Největší trable mám asi s tou variabilitou typů silnic, která nabourá každý můj nápad,ale nejsem si jistý že by to fungovalo i kdybych tenhle faktor opomenul. Konzultoval jsem tenhle problém už i s kolegy z VŠ, ale ani tam jsem moc neuspěl :(

Nahoru Odpovědět  +2 2.10.2015 21:07
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Odpovídá na Jenkings
Štefan Pružinský:

Tak, musím sa priznať, že som sa na to pozrel zhruba na nejakých 5 hodín. Idem z farbou von...rozmýšľal som nad vytvorením grafu na základe pomeru dĺžka/krajina (podla Primovho algoritmu) a následnom "spĺňaní" daných podmienok. Spĺňanie podmienok malo prebiehať podľa už vypočítaného grafu, avšak spätne:

mám nejakú cestu z mesta A do mesta B a vyskúšam, či spĺňa podmienky. Ak nie, tak sa presuniem o 1bod (=mesto) dozadu a od neho urobím cestu priamo k cieľu. Následne overujem, či cesta spĺňa podmienky. Ak nie, celý postup opakujem (=zase o 1 dozadu atď).

Problém je v tom, že tento algoritmus je v istých situáciach nesprávny... Rozmýšľal som aj nad nájdením najefektívnejších ciest spĺňajúcich podmienky a následnom prevedení Primovho algoritmu... Bohužiaľ, je potrebné nájsť akýsi prienik medzi najefektívnejším spojením ciest a najefektívnejším splnení podmienok. To sa mi zatiaľ bohužiaľ nedarí. :(
Čo sa týka výpočtu dĺžky v krajine, či mimo...je to úplne jednoduché. Ešte dodám, že som ešte nerozmýšľal nad detekciou krajín. Ale o tom potom. :) Vonkoncom máme ešte týždeň a ja dúfam, že ešte niečo vymyslíme a dotiahneme to do úspešného konca. :)

Nahoru Odpovědět 2.10.2015 21:50
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
Ladislav Ondris:

Hodně štěstí přeju všem :-) je to těžká úloha, to se musí uznat :-D

Já myslím, že jsem přišel na algoritmus, který by mi to mohl vyřešit. Samozřejmě si budu muset ještě dost věcí upravit podle sebe, aby to fungovalo, jak chci já. Uvidíme, jestli ten algoritmus vlastně půjde použít, protože se vždycky může naskytnout nějaký nečekaný problém :-)

Nahoru Odpovědět  +1 2.10.2015 22:03
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Štefan Pružinský
Jenkings:

ano, Dijkstrův algoritmus jsem taky zvažoval,ale na něj se mi nepodařilo aplikovat ten problém s výběrem typů silnic/spojů... To je zatím asi největší překážka, jinak kolize a délky silnic mám již také vypočítávané,ale zatím jsem se ani nedostal k tomu, abych je uvažoval jako kritérium při hledání.

Nahoru Odpovědět  +1 2.10.2015 22:11
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Odpovídá na Jenkings
Štefan Pružinský:

Aha...a máš už aj niečo napísané, alebo ťa stále púta papier a pero? :D U mňa je to vo fázy začiatku...mám už nejaké myšlienky a taktiež Parser, ale hlavná fáza začína až na ďalší týždeň. Tento týždeň bola čistá nestíhačka. :)

Nahoru Odpovědět 2.10.2015 22:32
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Štefan Pružinský
Jenkings:

No já mám napsaný ten parser a vizualizaci, abych to viděl přímo tak jak to je, a mohl si to kontrolovat na konkrétním příkladu.Takže vždycky myšlenku zkouším přímo kódem,ale prostě mně zatím nenapadlo žádné uspokojivé řešení, a musím konstatovat že u malého množství bodů se mi zatím opravdu nejlépe osvědčila metoda částečného brute-force :D :D

Nahoru Odpovědět 3.10.2015 8:13
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
JOF
Tým ITnetwork
Avatar
Odpovídá na Jenkings
JOF:

Taky předpokládám, že využiju algoritmus pro nalezení minimální kostry z teorie grafů, ale pro další optimalizace už nic obecného neznám :-(

 
Nahoru Odpovědět 4.10.2015 12:45
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

Tak, zatím bez uvažování efektu krajin, jsem se snažil nějak udělat algoritmus hledání minimální kostry,do kterého bych později mohl aplikovat i další podmínky, nicméně se mi nedaří, ho vyladit.

viz. screen -> to rozhodně není nejefektivnější silniční síť :(

Editováno 4.10.2015 15:51
Nahoru Odpovědět  +1 4.10.2015 15:50
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Jenkings
Redaktor
Avatar
Jenkings:

A pokud by se někdo chtěl trochu zasmát, tak se mi shodou několika náhod a omylů v algoritmu zřejme podařilo nechtěně vyřešit "problém obchodního cestujícího"

Nahoru Odpovědět  +3 4.10.2015 18:53
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

No jsem moc moc zvědavý na řešení :)

Nahoru Odpovědět 4.10.2015 19:57
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ladislav Ondris:

Můj algoritmus na vytvoření silniční sítě funguje, řekl bych, pěkně. Avšak bez ostatních věcí (krajina, podmínky), ale to snad stihnu do neděle dodělat :-) Stačí si najít vhodný algoritmus, který by se do tohoto případu hodil a upravit ho. :-)

Nahoru Odpovědět  +1 5.10.2015 22:21
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Ladislav Ondris
Ondřej Krsička:

Držím pěsti. :) Pro mě je to jiná liga :D

 
Nahoru Odpovědět 6.10.2015 19:57
Avatar
Odpovídá na Ondřej Krsička
Ladislav Ondris:

Je to velice těžká úloha. Spousty problému, které se musí řešit. Nejtěžší je vymyslet jak. Pokusím se to hlavně dodělat tak, aby to fungovala jak má. :-)

Nahoru Odpovědět  +1 6.10.2015 20:33
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Ladislav Ondris
Ondřej Krsička:

To jo no.
PS: Máš dobrý motto, ikdyž já někdy dělám chyby i při jednoduchých problémech :D

 
Nahoru Odpovědět  +1 6.10.2015 20:56
Avatar
rdaek
Člen
Avatar
rdaek:

Napadá mě spočítat vzdálenost mezi městy a pospojovat vždy nejkratší které ještě není v síti.. Škoda že teď nemám moc času jinak bych se zapojil :/

Nahoru Odpovědět 7.10.2015 17:05
Důležité je udělat program blbuvzdorným... Je pravda že mi často dost vzdorují :D
Avatar
polemes
Redaktor
Avatar
polemes:

A bude až skonci soutez nekde na stahnuti spravne reseni (me by zajimalo jak se to melo udelat)

Nahoru Odpovědět 9.10.2015 19:25
5 + 5 = 1010
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na polemes
patrik.valkovic:

Já jsem řešení nevypracoval, takže jedině musíš počkat, jestli úlohu někdo vyřeší. Můžu poté napsat maximálně postup, jakým se to mělo řešit.

Nahoru Odpovědět 9.10.2015 19:27
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

To je velká škoda. Snad to někdo vyřešil, a snad pochopitelně a čitelně :D každopádně ti sem dám všechno co jsem udělal. Lepší jak to nechat v "šuplíku".

 
Nahoru Odpovědět 9.10.2015 21:20
Avatar
Odpovídá na Ondřej Krsička
Ladislav Ondris:

Mně už zbývají jen podmínky. Jestli se mi podaří, tak ale bohužel moc čitelné nebudou :-D :-D

Nahoru Odpovědět 9.10.2015 21:59
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

Nesliboval jsi Patriku nějakou nápovědu?

 
Nahoru Odpovědět 9.10.2015 23:14
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Sliboval, ale potom se tu začali objevovat komentáře, podle kterých to vypadalo, že jste na správné cestě, tak jsem neradil.

Nahoru Odpovědět  +1 10.10.2015 10:32
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Ondřej Krsička:

Nejde mi to odevzdat, po kliknutí to ukáže, že stránka nejde zobrazit

 
Nahoru Odpovědět 11.10.2015 11:25
Avatar
Nahoru Odpovědět 11.10.2015 11:29
Nesnáším {}, proto se jim vyhýbám.
Avatar
Nahoru Odpovědět 11.10.2015 11:29
Nesnáším {}, proto se jim vyhýbám.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Pokud to nepůjde, tak to dej někam na internet a pošli mi odkaz to do zpráv.

Editováno 11.10.2015 11:56
Nahoru Odpovědět 11.10.2015 11:55
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

No, stejně toho mám málo, tak to sem ani nebudu dávat.

 
Nahoru Odpovědět  -1 11.10.2015 12:57
Avatar
Odpovídá na Ondřej Krsička
Michal Žůrek (misaz):

pošli i když máš málo, algoritmy mají být malé.

Nahoru Odpovědět 11.10.2015 13:00
Nesnáším {}, proto se jim vyhýbám.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Ondřej Krsička - pošli mi co máš, nezapomínej, že je to machr i na OOP.

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

Machr skončil, další práce se už neberou v potaz.
Dejte mi teď chvíli čas. Vzhledem ke komplexnosti zadání mi chvíli potrvá, než to zhodnotím, tak buďte prosím trpěliví.

Nahoru Odpovědět 11.10.2015 13:04
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ladislav Ondris:

Já toho taky mám málo :) ale kódu spoustu :-D :-D no..u jednoduších testovacích souborů to celkem funguje, ale u těch těžších už to má problém. Je tam ještě spoustu chyb a nedostatků :-D

Nahoru Odpovědět 11.10.2015 13:18
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Popravdě, mě se právě rozbil generátor inputů :D Takže trpělivost ;-)

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

Jeden z ukázkových input souborů :)

MESTA
0; 6.35; 23.59
1; 26.95; 5.26
2; 24.80; 32.37
3; 36.08; 9.60
4; 32.30; 14.66
5; 4.72; 6.86
6; 29.50; 29.69
7; 36.30; 20.85
8; 1.08; 32.33
9; 16.73; 26.33
10; 6.92; 29.87
11; 4.38; 30.03
12; 10.31; 32.76
13; 2.90; 15.62
14; 23.40; 15.36
15; 19.82; 24.70
16; 36.69; 8.63
17; 4.97; 3.57
18; 16.31; 14.03
19; 3.47; 26.16
20; 3.59; 33.41
21; 24.04; 5.98
22; 34.37; 15.43
23; 13.13; 25.79
24; 5.10; 10.56
25; 2.02; 37.44
26; 14.18; 4.79
27; 27.52; 16.49
28; 19.21; 36.92
29; 34.95; 32.03
30; 29.46; 20.46
31; 26.20; 16.94
32; 34.84; 20.02
33; 10.17; 20.87
34; 24.72; 32.73
35; 4.54; 27.05
36; 28.86; 30.57
37; 22.73; 13.51
38; 5.82; 38.40
39; 35.66; 34.88
40; 19.64; 17.11
41; 10.52; 12.84
42; 13.33; 22.38
43; 10.51; 31.90
44; 21.11; 28.48
45; 24.36; 19.39
46; 19.08; 11.44
47; 7.21; 7.10
48; 11.14; 14.34
49; 5.25; 32.26
50; 1.07; 12.36
51; 6.03; 14.98
52; 8.58; 23.61
53; 22.05; 14.01
54; 10.67; 20.81
55; 1.26; 0.08
56; 9.94; 13.37
57; 3.61; 12.46
58; 9.51; 18.27
59; 39.76; 36.24
60; 8.38; 25.15
61; 7.97; 17.43
62; 33.88; 39.60
63; 6.30; 38.72
64; 27.26; 21.32
65; 29.62; 27.38
66; 16.03; 38.15
67; 6.81; 38.36
68; 13.80; 26.91
69; 17.81; 3.55
70; 18.13; 19.00
71; 39.04; 24.34
72; 13.20; 33.84
73; 3.50; 38.68
74; 4.84; 26.99
75; 32.50; 4.83
76; 3.99; 20.88
77; 7.01; 31.15
78; 29.73; 22.45
79; 7.71; 11.95
80; 33.54; 19.94
81; 10.45; 25.02
82; 36.32; 11.78
83; 6.55; 5.25
84; 38.65; 22.60
85; 8.42; 32.66
86; 7.02; 28.97
87; 18.39; 9.54
88; 35.22; 28.58
89; 16.48; 2.64
90; 34.88; 11.20
91; 34.17; 25.94
92; 31.35; 22.65
93; 37.18; 27.40
94; 39.39; 5.86
95; 10.01; 38.20
96; 8.55; 14.02
97; 28.01; 1.41
98; 27.29; 38.25
99; 0.03; 22.23

SILNICE
0; 15; 5.90

FINANCE
10000000

PODMINKY
15; 58; 4,042.51
67; 13; 4,432.47
61; 80; 7,025.57
90; 24; 4,702.80
80; 36; 10,321.75
11; 17; 9,181.71
73; 74; 12,849.40
90; 52; 9,226.13
2; 80; 10,908.87
41; 65; 9,203.01
17; 74; 7,996.48
10; 75; 11,062.49
25; 81; 3,158.13
7; 39; 1,396.81
58; 38; 2,331.88
49; 61; 3,523.08
91; 21; 720.51
12; 8; 18,444.59
40; 35; 4,871.15
8; 65; 16,473.94
8; 83; 15,518.70
60; 14; 3,771.09
85; 38; 6,899.10
32; 64; 5,124.71
12; 26; 5,822.71
5; 93; 7,543.47
35; 11; 13,818.09
68; 41; 4,847.21
48; 92; 4,259.27
87; 80; 5,778.44
73; 51; 11,732.81
65; 42; 9,077.15
87; 50; 4,338.69
25; 52; 6,828.60
61; 81; 155.32
11; 67; 4,861.84
72; 76; 15,298.84
56; 33; 4,504.59
14; 96; 5,877.37
89; 87; 6,145.50

KRAJINA
3.10; 6.35; 5.26; 20.60; 18.33
1.83; 9.60; 32.30; 22.77; 3.78
1.29; 4.38; 29.87; 2.54; 0.16
4.79; 27.38; 6.81; 10.77; 9.22
0.73; 22.65; 37.18; 4.75; 2.21
0.32; 16.98; 25.54; 11.66; 3.24
3.46; 4.51; 29.05; 35.06; 0.76
0.21; 4.15; 0.30; 26.90; 4.73
4.72; 32.35; 38.61; 6.72; 0.06
3.90; 38.35; 29.96; 0.59; 0.12
2.86; 0.84; 14.80; 2.04; 20.83
0.66; 33.10; 22.61; 0.58; 2.62
4.28; 36.83; 36.09; 0.97; 1.96
4.41; 3.71; 31.44; 3.81; 0.52
4.43; 30.09; 20.93; 4.54; 0.41
1.49; 4.48; 38.18; 16.34; 0.67
2.01; 31.66; 0.82; 6.42; 0.83
1.01; 9.29; 24.31; 9.20; 0.89
0.37; 3.18; 19.86; 2.36; 5.78
3.26; 35.90; 22.96; 0.31; 0.73
1.44; 19.66; 30.43; 2.76; 0.02
4.30; 33.84; 33.44; 0.44; 3.80
3.11; 33.04; 1.99; 3.65; 1.84
4.73; 38.36; 12.21; 0.62; 4.91
3.60; 34.18; 30.47; 0.38; 1.28
4.64; 37.17; 19.54; 1.41; 3.27
3.69; 3.51; 36.44; 11.06; 0.36
0.16; 1.03; 6.30; 2.67; 1.21
0.16; 36.79; 2.35; 0.73; 0.27
0.52; 4.89; 32.30; 4.17; 3.86
4.23; 29.34; 17.79; 1.74; 1.64
2.72; 37.73; 25.63; 1.27; 1.13
2.05; 14.74; 26.11; 1.20; 1.15
0.94; 1.94; 10.94; 2.75; 0.67
4.05; 3.05; 21.59; 0.08; 2.92
3.55; 21.06; 30.53; 6.55; 0.49
2.89; 33.11; 26.15; 1.48; 1.58
4.26; 4.42; 30.39; 0.78; 0.29
1.57; 35.83; 26.82; 1.98; 1.43
4.43; 17.72; 39.45; 19.55; 0.27
2.45; 29.98; 21.60; 1.57; 5.39
3.65; 6.09; 8.14; 0.07; 0.61
0.92; 29.79; 16.73; 7.46; 1.00
4.93; 33.19; 19.72; 0.49; 0.25
3.39; 4.04; 14.47; 0.09; 4.97
4.52; 39.73; 10.62; 0.07; 26.33
1.98; 29.02; 37.14; 0.55; 0.88
3.66; 13.37; 31.07; 20.34; 0.79
3.57; 4.47; 26.30; 7.70; 1.66
4.94; 31.29; 5.83; 4.11; 0.67
Nahoru Odpovědět 11.10.2015 13:58
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
JOF
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
JOF:

Za prvním číslem u měst a silnic by měla být dvojtečka, ne? Takhle mi to nepřečte ...

 
Nahoru Odpovědět  +1 11.10.2015 17:25
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na JOF
patrik.valkovic:

Jo, omlouvám se, už jsem to upravil, má tam být tečka.
Když jsi se už ozval, co je nejasného na zadání

Program si bude muset přečíst data ze souboru input.txt a výstup uložit do souboru output.txt

??
Nedodržel jsi ani ukládání do souboru, ale ani formát. Tak mi řekni, jak to mám opravovat pro 50 vstupních souborů?

To zadání bylo takhle dáno úmyslně a ne ze srandy. Pokud byste něco takového udělali na vysoké (vysokoškoláci určitě potvrdí - Jindřich Máca), tak máte všechno špatně. Kontroluje to stroj, a pokud soubor nenajde, tak 0 bodů. A je jedno, jestli máte sebedokonalejší algoritmus.

Nahoru Odpovědět  +1 11.10.2015 17:29
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
JOF
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
JOF:

Jasně, nemám to hotové, psal jsem to.
Spíš jsem to posílal na posouzení tříd.
Ale podle zadání tam má být opravdu dvojtečka a ne středník ani tečka.

 
Nahoru Odpovědět 11.10.2015 17:34
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Abyste neřekli, že se flákám, posílám menší ukázku :)
Jenkings a JOF jsou jedinné dvě řešení, které zvládly i něco víc, než jen základní vstupy (soubor o 2 nebo 4kb). Nicméně pro 15 a 24kb také v rozumném čase nic :)
Kód jsem ještě neprocházel, chystám se na něj ;-)

Nahoru Odpovědět 11.10.2015 18:52
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na patrik.valkovic
Jenkings:

No, upřímně řečeno ten můj algoritmus taky nedělá skoro nic.
Povedlo se mi jen rozparsovat vstup a najít nějaký strom toho grafu. Jen jsem vymyslel nějaký svůj algoritmus, který vyhledává velice zajímavé grafy. Nicméně jsem měl co dělat, aby to fungovalo alespoň tak aby se propojily všechny města bez cyklů atd.

Měl jsem rozpracované i započítání efektů té krajiny,ale už jsem to ani nestihl dodělat. K podmínkám spojnic bych se z 99% ani nedostal vůbec :(

Nahoru Odpovědět 11.10.2015 19:04
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Jenkings
Ondřej Krsička:

Kde ty algoritmy hledáte, jak je upravujete, jak to všechno děláte? to je jako nějaká chytrá knížka, ve které to je, nebo co? Kdyžtak se někdo můžete na toto téma rozepsat / doporučit nějaký článek/knížku nebo tak něco.

 
Nahoru Odpovědět 11.10.2015 19:30
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Jenkings:

No já jsem nejdřív hledal nějaké algoritmy na internetu,ale nakonec jsem si napsal/vymyslel tak nějak vlastní ;) (co se týče tohohle konkrétního případu)

Už od začátku je to ale jen o tom mít analytické myšlení, a to se z knížky nenaučíš. Prostě si musíš ten problém dokázat představit nějak komplexně, a rozložit si ho na co největší množství malých podproblémů, které následně řešíš.

Editováno 11.10.2015 19:32
Nahoru Odpovědět 11.10.2015 19:32
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Jenkings
Ondřej Krsička:

Poradíš mi, jak toto trénovat?

 
Nahoru Odpovědět  -1 11.10.2015 19:49
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Tak třeba tento případ. Co budeš řešit jako první věc?

Nahoru Odpovědět 11.10.2015 19:52
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

No, vyřešil jsem, jak zjistit mezi městem vzdálenost a čas se započtením krajin. To jsem řešil první.

Ale u toho generátoru možná udělat pole možných cest seřazených podle velikosti a od nejmenších po nejdelší propojovat, ale to by nakonec mělo každý město s každým cestu, takže nějak jinak. To mě tak napadlo.

Nebo určit jedno město jako centrum a do něj že musí být cesta ze všech měst, tudíž by zároveň byla cesta odkudkoli kamkoli.

 
Nahoru Odpovědět 11.10.2015 20:01
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

Ale to by mi nejspíš vznikla hvězdice, takže tyto dvě věci zkombinovat a jedno město vždy připojit k nejbližšímu ještě nepřipojenýmu. Až by se udělaly uzavřené skupiny měst, tak by se z každé skupiny jedno město propojilo s jedním z nejbližší skupiny, která ještě není napojená na jinou skupinu.

 
Nahoru Odpovědět 11.10.2015 20:04
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Špatně. Co když ti nevychází podmínky? To budeš celou síť generovat znova a znova, dokud to nebude fungovat?
Pole možných cest je také pracné. Máš n měst, to znamená, že budeš mít n! cest. To je příliš.
Pokud budeš mít jedno město jako centrum, tak rozhodně nebudeš mít nejefektivnější síť.
Takže znovu, jaký úkol musíš udělat jako první?

Nahoru Odpovědět 11.10.2015 20:07
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

Zpracovat vstup a dát do pole nebo do pole objektů?

 
Nahoru Odpovědět 11.10.2015 20:11
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Jenkings:

Trénovat ? důležité je začít na lehčích situacích.
Za příklad si můžeš vzít třeba matiku ve škole. Dostaneš příklad přes dva řádky a taky nevystřelíš výsledek od boku, ale už automaticky jdeš od těch malých problémů až se dostaneš postupně k výsledku velkého příkladu. Víš že násobení a dělení má přednost před sčítáním a odčítáním, + role závorek atd. takže si nejdříve vyřešíš závorky, potom si teprve vypočítáš násobení a dělení a nakonec sečteš a odečteš. (ne vždy to je přesně takhle,ale je to jen příklad)

A postupně to funguje i s programováním :)

Editováno 11.10.2015 20:14
Nahoru Odpovědět 11.10.2015 20:13
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Jenkings
Ondřej Krsička:

Nemyslel jsi ten příklad jako že když neumím násobit, tak nemůžu umět ani např. lomený výrazy?
Nebo podproblémy řešit od toho nejjednoduššího a pak až dělat to složitý?

 
Nahoru Odpovědět 11.10.2015 20:17
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Paradoxně, u tohoto příkladu musíš jít od zadu. Tedy první si vygenerovat nejkratší cesty podle podmínek, a teprve potom doplnit síť. Proč? Protože nejrychlejší cesta mezi dvěma body je pouze jedna, zatímco sítí máš mnohonásobně víc (přesné číslo ti neřeknu, ale počítej s exponenciálním přírůstkem). je tedy jednodušší zkoušet různé variace nejrychlejších cest, než generovat všechny možné sítě a na nich teprve testovat, zda splňují podmínky.
Vidíš v tom tu logiku? je jednodušší vygenerovat nejrychlejší cestu a z ní graf (jeden), než ve grafech (mnoha) vždy hledat cestu.

Nahoru Odpovědět 11.10.2015 20:18
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Jenkings:

mínil jsem tím pouze to, že to prostě musíš umět rozložit na podproblémy a ty řešit :)

Nahoru Odpovědět 11.10.2015 20:19
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na patrik.valkovic
Jenkings:

Nad touhle metodou jsem upřímně řečeno taky uvažoval, ale bylo tam pro mně v tu chvíli pár problémů se kterými jsem si nevěděl rady, takže jsem to musel přehodnotit a udělat to aspoň tak aby to umělo najít graf. Nicméně si myslím, že nejzásadnější věc kterou jsem nemohl rozlousknout bylo to, na základě čeho vybrat typ té spojnice/cesty

Editováno 11.10.2015 20:22
Nahoru Odpovědět 11.10.2015 20:22
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ondřej Krsička
Redaktor
Avatar
Ondřej Krsička:

Jo ještě aby seděly podmínky, to jsem vůbec nezvažoval.

** je jednodušší vygenerovat nejrychlejší cestu a z ní graf (jeden), než ve grafech (mnoha) vždy hledat cestu.**

Z principu chápu, ale cestu a z ní graf vůbec nechápu co je to graf z něčeho.

 
Nahoru Odpovědět 11.10.2015 20:23
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Jenkings:

ohledně toho grafu:
jde o to,že celý příklad předpokládá znalost matematické "teorie grafů". Takže ještě před započetím prací bylo potřeba si o tom dost nastudovat (tedy aspoň pro nás, kteří jsme o tom nevěděli před zadáním této soutěže téměř nic)

Nahoru Odpovědět 11.10.2015 20:25
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
rikenbekr
Člen
Avatar
rikenbekr:

Budou řešení poté uveřejněna ke stažení?
Pokud ne byl by mi některý autor ochotný řešení zaslat?

Editováno 11.10.2015 20:26
Nahoru Odpovědět 11.10.2015 20:25
In world without fences and walls, who needs Gates and Windows?
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Jenkings
patrik.valkovic:

To je bolavé místo. Když se podíváš na zadání, optimalizuješ mezi cenou / časem. Máš funkci dvou proměnných, která nelze určit algoritmem. Zde nezbývá nic jiného, než zapojit hrubou sílu.
Pomůžou tomu nějaké optimalizace, ohledně výběru cest ze vstupu (například cesta, která stojí 15 a má časovou konstantu 1, je rozhodně horší, než cesta, která stojí 15 a má časovou konstantu 0,5). Tím můžeš vyfiltrovat pár typů cest, ale potom jde použít jen hrubá síla. Zvláště v případě, kdy je více podmínek, které můžou záviset na stejné cestě.
Budeš brát v potaz všechny možnosti, která splňují časovou podmínku, a ještě splňují cenu.

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

Řešení myslím bývají veřejné po ohodnocení.

Nahoru Odpovědět 11.10.2015 20:29
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Jenkings
Ondřej Krsička:

Teorie grafů.. to jsem možná někde slyšel. Fakt jen slyšel.
Myslíte, že mi pomůže/něco přinese nastudování té teorie grafů? Nebo je to moc těžká matika nebo to až tak důležitý není?
Kdyžtak nějaký doporučení, jak si to nastudovat? z nějaký knížky, online, wiki...?

 
Nahoru Odpovědět  -1 11.10.2015 20:32
Avatar
Denis Homolík (Alfonz):

Nemyslím že by to zrovna bylo těžké k nalezení. :)
http://lmgtfy.com/?…

Nahoru Odpovědět 11.10.2015 20:36
Vše je možné, dokud si to myslíte!
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Jenkings:

stačí si vygooglit "teorie grafů" a vyhodí ti to jak wiki, tak spousty odborných skript, ale podle mého názoru je potřeba pro plné pochopení poměrně dlouhá doba. Já jsem toto využil poprvé až teď v soutěži, nicméně záleží na tom čemu se chceš věnovat, a tato problematika má rozhodně více uplatnění než jen hledání spojnic měst. Záleží tedy na tobě co pokládáš za důležité/přínosné

Nahoru Odpovědět  +1 11.10.2015 20:37
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

Není to nic složitého. Jen se odprosti od představy, že je to série sloupečků v Excelu :D
Graf se skládá z uzlů a hran. V našem případě je uzel město a hrana je cesta. Většina algoritmů pracuje právě s grafy.
Nějaké ukázky:
https://jeremykun.files.wordpress.com/…ncolored.png?…
http://1.bp.blogspot.com/…s1600/p1.png
http://www.codeproject.com/…ected-Graphs

Algoritmy se poté liší v tom, jak s grafem pracují.

Nahoru Odpovědět 11.10.2015 20:39
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
B42P6
Člen
Avatar
B42P6:

Zdravím program na tvorbu cestnej siete som začal písať ale nestihol som ho ešte dokončiť (Algoritmus mám stačí ho iba implementovať do kódu ;) ) (určite ten program ešte dokončím ;) ) . Zaujímalo by ma či beriete do úvahy to, že ak je možnosť postaviť/upraviť jednu alebo viac ciest tak aby vyriešila viac podmienok bude to lacnejšie . Čo ak to bude iba jediná možnosť(2 podmienky, financie iba na 1 cestu) ?

PS: Dúfam že cieľom je nájsť čo najlacnejšie riešenie :)

Editováno 11.10.2015 20:55
Nahoru Odpovědět 11.10.2015 20:53
'long long long' is too long for GCC
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na B42P6
patrik.valkovic:

Cílem je vlézt se do rozpočtu a splnit podmínky. Machr už ale skončil, další řešení už neberu.

Nahoru Odpovědět 11.10.2015 20:56
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
B42P6
Člen
Avatar
Odpovídá na patrik.valkovic
B42P6:

Jasné, chápem že ďalšie riešenia už neberieš. Len by ma zaujímalo či pri testovaní používaš inputy v ktorých je jediné riešenie postaviť jednu alebo viacero ciest tak aby ju mohlo použiť viac podmienok.

Nahoru Odpovědět 11.10.2015 21:01
'long long long' is too long for GCC
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na B42P6
patrik.valkovic:

Řešení používám takové, že se mi náhodně vygenerují města, ty se téměř náhodně pospojují a z nich poté určím podmínky, nic víc :D
Rozhodně to nedělá nejefektivnější cesty (spíš nejméně efektivní) a je tedy hodně velká šance postavit lepší síť. Nicméně pro velký počet měst to nezvládá žádný program.
https://onedrive.live.com/redir?…

Nahoru Odpovědět 11.10.2015 21:04
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

ty dva obrázky jsou hezký, na codeproject kouknu, ale tohle nedávám
https://cs.wikipedia.org/…%C5%99_barev

 
Nahoru Odpovědět  +1 11.10.2015 21:10
Avatar
Jenkings
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Jenkings:

Taky to moc nechápu, ale musím ti poděkovat za odkaz. Nenapadlo by mně že i tohle se dá řešit pomocí grafů :)

Nahoru Odpovědět 11.10.2015 21:13
Největší časovou náročnost má výpočet časové náročnosti..
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Jenkings
Ondřej Krsička:

Není zač, na wiki jsem našel **Teorie grafů **a tam byl na toto odkaz :)
Kdyžtak jsem založil nový téma. v sekci Matematika a Fyzika, můžete se mi tam mrknout ;)

 
Nahoru Odpovědět 11.10.2015 21:16
Avatar
B42P6
Člen
Avatar
Odpovídá na patrik.valkovic
B42P6:

Akože to nieje najefektívnejšie? Keď postavíš cestu ktorá bude zdieľaná (zdieľaná znamená že trasa z mesta A do mesta B a zároveň trasa z mesta C do mesta D bude prechádzať cez túto cestu) 2 alebo viacerými podmienkami môže to byť lacnejšie, samozrejme nemusí to platiť vždy ,ale s tým počítam.

Editováno 11.10.2015 21:46
Nahoru Odpovědět 11.10.2015 21:45
'long long long' is too long for GCC
Avatar
coells
Redaktor
Avatar
Odpovídá na patrik.valkovic
coells:

Nezvládá to žádný program, protože to zvládnout nejde. Tvoje zadání vede na NP těžkou úlohu. Dokázat to nemůžu, ale s trochou zkušenosti je to vidět na první pohled. Na nalezení řešení prostě musíš mít štěstí a ke každému algoritmu se dá vymyslet protipříklad, který [v rozumném čase] vyřešit nedokáže.

 
Nahoru Odpovědět  +4 11.10.2015 23:47
Avatar
Odpovídá na coells
Ladislav Ondris:

Ale když si napíšeš dobrý program, tak proč by nemohl zvládnout vytvořit lepší síť?

Nahoru Odpovědět 12.10.2015 17:44
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
coells
Redaktor
Avatar
Odpovídá na Ladislav Ondris
coells:

Obávám se, že nerozumím otázce? Nicméně existuje velká spousta problémů, pro které nedokáže nikdo napsat dost "dobrý" program.

 
Nahoru Odpovědět 12.10.2015 20:22
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na coells
patrik.valkovic:

Zvládnout to samozřejmě jde. O tom, že je to NP problém samozřejmě vím, také je to zmíněno v jednom z předchozích příspěvků, že balancuješ mezi cenou / rychlostí.
Proto je zadání dané tak, že musí splnit rozpočet (nikde není napsáno, že má mít síť nejmenší cenu). A potom už to v rozumném čase vyřešit jde.

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

Díky všem za účast, zde jsou výsledky:

BlugW - 0 bodů
Prázdné řešení

Patrik Smělý (SogoCZE) - 0 bodů
Prázdné řešení

tomisoka - 50 bodů
Program vytvoří síť a to i pro složitější zadání.
Co se týče návrhu, jsem z toho trochu zmatený. I když v C++ dělám, některé obraty jsou už moc hardcore :D
Nicméně, všechny algoritmy jsou pouze v jedné třídě. To by se vyksytovat nemělo. Samotná metoda Setup je hrooozně dlouhá. Měla by být rozdělena do samostatných metod. Při parsování se neustále opakuje stejná část kódu, to by šlo také vyřešit samostatnou metodou.
Co se řešení týče, spojení všech měst se všemi není moc efektivní. I když poté cesty ubíráš, dokud jsou ještě splněny podmínky.
Ve výsledku je sice síť nejefektivnější, ale výpočet trvá dlouho. I tak mě překvapuje, že to spočítá v rozumném čase.
Naštěstí jsem se podíval na atribut -quick, což je přesně to, co měl program dělat defaultně.
Ačkoliv se mi podstata kombinace všech měst se všemi moc nelíbí, program spočítá cestu relativně rychle a správně (včetně podmínek). Toto řešení tey vyhrává Machra na algoritmy.

Jenkings - 35 bodů
Program vytvoří síť, ale nebere v potaz podmínky. Také nezvládá větší zadání.
Z hlediska OOP je pár věcí, které jsou špatně. Spousta tříd má veřejné properties. Měli by být alespoň public get, private set, nebo read-only. V Parseru jse neustále opakuje stejný kód při vytváření jednotlivých tříd. Bylo by lepší tento k=od vložit do samostatné metody. V Path nedává Region map smysl. Proč nepředat regiony přímo do funkce getTime? Nikde jinde se z regiony nepracuje.
Dále je tu třída Solver. Opět má veřejnou kostru, což by se vykytovat nemělo. Když ji někdo omylem z vnějšku změní, celá kostra bude nevalidní. Také spuštění výpočtu hned v konstruktoru není moc šikovné. Kontruktor je od toho, aby konstruoval třídu (již podle názvu), ne aby prováděl složité výpočty. naopak se mi líbí použití anonymních metod. Trošku jsem nepobral mazání poslední cesty v případě, že je síť cyklická. Jestli v tom byl nějaký záměr, tak se omlouvám a nevidím ho.

Honza Bittner - 0 bodů
Prázdné řešení

JOF - 41 bodů
Program vytvoří síť, ale nebere v potaz podmínky. Také nezvládá větší zadání.
Začnu Map třídou. Jednak samotné generování všech možných cest není moc efektivní. Pro vytváření objektů mohla existovat samostatná třída - oddělení načítání dat a výpočet. Také vytváření Listů v konstruktoru je zbytečné, když by šli vytvořit přímo u deklarace. Nepochopil jsem přístup, proč rozkládáš cestu na RoadParts. Problém regionů šel řešit efektivněji, aniž bys cestu rozkládal. Soubor Globals je zajímavý sám o sobě. Kdyby tam nebyl, pochopíl to, kdyby tam byli dvě možnosti (tedy rozdělení podle ; a :; tak to taky pochopím, ale pouze tento jeden, proč? :D
Co se Location týče, proč je definování zároveň s Line v jednom souboru? Chápu to u Road a RoadPart, ale Line a Location spolu nijak nesouvisí. Funkce Intersect je hodně nepřehledná, a tak ti budu věřit, že dělá, to co má :D
Region.GetInter­sectionWithRo­adPart by dle názvu mělo spíše vrátit Line, než body - ale to je jen otázka implementace.
trošku se mi nezdá třída Way a její statické metody. Kdyby jsi potřeboval algoritmus rozšířit, bude se to dělat těžko. Výhodnější by bylo pro výpočet algoritmu nadefinovat další třídu, která bude pouze počítat.
Jinak se mi řešení líbí nejvíc. Když opomineme ty algoritmy v jedné metoě, je projekt rozdělen hezky do tříd a používá i správné modifikátory přístupu. Na některých místech by šlo pouze využít read-only properties (C#6). Některé algoritmy propadávají skrz několik tříd a špatně se dohledávají.
Tohle řešení vyhrává Machra na OOP.

Ladislav Ondris - 5 bodů
Bohužel program nespočítá ani jednoduchý případ. Neívm, jestli je někde zacyklený, ale počítat 5 minut a použít skoro giga RAM je moc.
Co se kódu týče, spoustu obratů, kde používáš foreach, jde nahradit Linqem. Řešení bude rychlejší a přehlednější. Chválím použití Borůvkova algoritmus, který se v tomto případě hodí nejvíce. Co se Manager třídy týče, metoda ModifyRoads je šíleně dlouhá. Určitě by se měla rozdělit na několik metod. Také mít vechny algoritmy v jedné třídě není šikovné. Stejný případ, jaký jsem psal u JOFa. Není problém mít jednu třídu pro jeden algortmus. Některé části, které počítáš v Manager, se přímo dotýkají jiných tříd - tyto algoritmy by měli být ve třídách, se kterými souvisí.
U Component máš vedle veřejné Towns ještě metodu AddTown, která je zbytečná. Také můžeš foreach nahradit metodou List.Contain, která dělá to stejné. Třída IO by se měla podle názvu starat o načtení a uložení dat, ne o jejich parsování, ale dejme tomu. Máš také nadefinovanou třídu Point, což je zbytečné. ve WindowsBase assembly je Point již definovaný, a to včetně metod, které se dají využít i v tomto případě. V Road třídě máš property DistaneTown, která je zbytečná, protože jde lehce dopočítat. Pokud ji někde zapomeneš přepsat, budeš mít nevalidní data. Také by to chtělo alespoň vyhodit výjimku, když najde více průniků. A ještě taková drobnost, Math.Sqrt vrací douuble, proč celá unkce nevrací double a vyhneš se zbytečnému přetypování?
Hlavním problémem je třída Manager, která obsahuje naprosto všechny algoritmy. Ty by mohly být rozděleny do samostatných tříd, starajících se o výpočet. Také lze spoustu cyklů nahradit Linqem.

Placku tedy získává tomisoka, JOF. Gratuluji :)

Akceptované řešení
+5 Zkušeností
Řešení problému
Nahoru Odpovědět  +2 12.10.2015 21:55
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Čeho jsem si hlavně všiml:

  • Algoritmy v jedné třídě. Každý algoritmus by měl mít svoji vlastní třídu.
  • Zbytečné vyhodnocení if/else. Pokud je if(.....) return true; else return false; můžu rovnou použít return ....(to co bylo v ifu)
  • Špatné použití přístupových modifikátorů. Hlavně je potřeba dát pozor na to, aby nám strukturu, kterou máme, nikdo z vnějšku nezměnil - poté by již nebyla validní a nemůžeme tedy spoléhat na to, že výsledky jsou správné.
Nahoru Odpovědět 12.10.2015 21:58
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

A co jsem ještě nezmínil, byla to skvělá úloha na vícevláknové programování :)
jedno vlákno spočítá cestu pro podmínky, další vlákno doplní graf a třetí vlákno jej zvaliduje. S trochou optimalizace bude čas několikrát menší oproti jednovláknové aplikaci :)

Nahoru Odpovědět 12.10.2015 22:05
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
JOF
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
JOF:

Dík za kritické zhodnocení mého řešení i za placku ;-)
A samozřejmě gratulace pro Tomisoku!
Měl bych jeden dotaz k vyjádření: "...vytváření Listů v konstruktoru je zbytečné, když by šli vytvořit přímo u deklarace...". Myslel jsem, že funkčně je úplně jedno, kde se to vytváří a technicky, že je toto řešení čistší. Proč to takhle není správně?

 
Nahoru Odpovědět 12.10.2015 23:09
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na JOF
patrik.valkovic:

Co je čistší je otázka. V principu si vytváření Listu nezávisí na ničem jiném. Pokud bys do kontruktoru dostal napříkald počet elementů, které bude List obsahovat, můžeš mu rovnou nastavit Capacity.
Pro přehlednost bych vytváření Listu dal přímo k deklaraci. Máš jistotu, že tam ten List vždy bude. Nemůže se ti třeba stát, že zapomeneš v kontruktoru vytvořit instanci.

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

Ještě mě napadá případ, kdy máš několik konstruktorů, které se navzájem nevolají. V každém konstruktoru bys vytvářel instance listů. V této situaci určitě budeš souhlasit, že čistší řešení je vytvářet instance při deklaraci.

Nahoru Odpovědět  +1 13.10.2015 7:37
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na patrik.valkovic
Jan Vargovský:

Spíše mi řekni případ, kdy máš konstruktory, které navzájem nejsou závislé.

 
Nahoru Odpovědět 13.10.2015 11:20
Avatar
Ondřej Langr (andysekcze):

http://teorie-grafu.cz/…ti-grafu.php link pro ty kdo by chtěl

Editováno 13.10.2015 21:53
Nahoru Odpovědět 13.10.2015 21:52
I have a charger. I have Note 7. Umh I haven't Note7.
Avatar
polemes
Redaktor
Avatar
polemes:

jak to že placku dostal JOF a ne tomisoka?

Nahoru Odpovědět 25.10.2015 21:20
5 + 5 = 1010
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na polemes
patrik.valkovic:

Byly to dva machři v sobě. tomisoka dostal ocenění za algoritmus, JOF poté za OOP.

Nahoru Odpovědět 25.10.2015 21:22
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
polemes
Redaktor
Avatar
polemes:

Ahá ono to nikde nebylo uvedeno :)

Nahoru Odpovědět 25.10.2015 21:28
5 + 5 = 1010
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 141 zpráv z 141.