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

Soutěž: Machr na algoritmy - Hledání cest

C# .NET .NET (C# a Visual Basic) Machr na algoritmy - Hledání cest American English version English version

Zadání

V tomto machrovi budeme pokračovat v hraní s městy. Tentokrát je však nebudete generovat, ale hledat v nich cesty. Vaším úkolem bude napsat aplikaci, která dostane na standardním vstupu popis města a dotazy na cesty a bude na tyto dotazy odpovídat. Vstup bude vypadat následovně:

počet_ulic_(n)
počet_křižovatek_(m)
název_první_ulice délka_první_ulice
název_druhé_ulice délka_druhé_ulice
...
název_n-té_ulice délka_n-té_ulice
první_křižovatka
druhá_křižovatka
...
m-tá_křižovatka
počet_dotazů_(d)
první_dotaz
druhý_dotaz
...
d-tý_dotaz

Počty jsou celá kladná čísla, názvy ulic jsou tvořeny malými a velkými písmeny anglické abecedy, číslicemi a podtřžítky (např. "5_Maje"), délky ulic jsou kladná reálná čísla. Křižovatka je reprezentována seznamem ulic, které se na ní setkávají - na vstupu budou jejich názvy oddělené mezerami.
Město tvoří graf - ulice jsou hrany (každá ulice spojuje právě 2 různé křižovatky) a křižovatky jsou vrcholy. Žádné 2 křižovatky nejsou spojeny více než 1 ulicí.

Dotaz obsahuje popis dopravní situace a názvy ulic, mezi kterými má aplikace hledat cestu. Dopravní situace se skládá z uzavřených a "ucpaných" ulic. Uzavřenými ulicemi se projet nedá, v ucpaných se tvoří kolony a jejich průjezd je 4× pomalejší. Popis situace v dotazu obsahuje pouze změny oproti minulému dotazu / počátečnímu stavu města. Dotaz tedy vypadá následovně:

počet_změn_dopr._situace_(s)
první_změna název_ulice
druhá_změna název_ulice
...
s-tá_změna název_ulice
startovní_ulice
cílová_ulice

změna je ve formátu "+ b/c" nebo "-"
'+' znamená přidání dopravní komplikace, '-' odebrání
'b' značí ucpanou ulici, 'c' uzavřenou
Pozn.: Změny probíhají v pořadí, v jakém jsou uvedeny na vstupu.

Na výstup bude aplikace vypisovat nalezené cesty jako posloupnosti názvů ulic (oddělené mezerami - každou cestu na samostatný řádek). Za název poslední ulice ještě vypíše délku nalezené cesty (u startovní a koncové ulice se do celkové délky cesty započítává jen polovina jejich délek). Pokud cesta nebude existovat, vypíšete na daný řádek pomlčku ('-'). Samozřejmě nechceme libovolnou cestu, ale tu nejrychlejší (co nejmenší suma délek ulic, ucpané ulice považujeme za 4× delší), pokud takových existuje více, vypište libovolnou z nich.
Pokud bude chybně zadaný vstup (text místo čísla, nepovolený znak v názvu ulice, ...), vypíšete vykřičník ('!') - pokud je chyba v dotazu, pokračujete dalším dotazem (chybný dotaz přeskočíte jako by neexistoval), je-li chyba v popisu města, ihned skončíte.


1. Ukázka
Vstup:

3
2
5_Maje 8
Americka 5.3
Boticska 14.7
5_Maje Americka
5_Maje Boticska
2
1
+c 5_Maje
Boticska
Americka
1
- 5_Maje
Boticska
Americka

Výstup:

-
Boticska 5_Maje Americka 18

2. Ukázka
Vstup:

x

Výstup:

!

Upozornění: programy budou automaticky testovány - výstup tedy musí přesně odpovídat popsanému formátu.


Hodnotit se bude primárně efektivita zvoleného algoritmu a správnost výstupů, okrajově kvalita (a přehlednost) kódu.

Větší ukázkový vstup: https://www.dropbox.com/…t/example.in?dl=0
Očekávaný výstup: https://www.dropbox.com/…/example.out?dl=0

Dotazy k zadání můžete psát do komentářů.

Výhra

Vítěz dostane placku Machr a ocenění do portfolia.

Výhra

Zapoj se!

Chceš se zapojit do soutěže a vyhrát? Zaregistruj se!

Soutěžící

Zatím nikdo neodevzdal řešení, budeš první?

Aktivity (3)
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Zdeněk Pavlátka:13. listopadu 20:22

V tomto machrovi budeme pokračovat v hraní s městy. Tentokrát je však nebudete generovat, ale hledat v nich cesty. Vaším úkolem bude napsat aplikaci, která dostane na standardním vstupu popis města a dotazy na cesty a bude na tyto dotazy odpovídat.

Soutěž končí 26. listopadu 23:55, tak se nezapomeň zapojit! :)

Odpovědět 13. listopadu 20:22
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Martin Dráb
Redaktor
Avatar
Martin Dráb:13. listopadu 20:45

Chápu správně, že se jako změna může objevit pouze jedna ze tří možností: +b, c, nebo -?

Může se +b kumulovat (tzn. může být ucpaná ulice ještě ucpanější)?

Je povolen pouze C#/VB, nebo i ostatní, řekněme, normální jazyky?

Nahoru Odpovědět 13. listopadu 20:45
2 + 2 = 5 for extremely large values of 2
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Martin Dráb
Zdeněk Pavlátka:13. listopadu 23:53

Chápu správně, že se jako změna může objevit pouze jedna ze tří možností: +b, c, nebo -?
Může se +b kumulovat (tzn. může být ucpaná ulice ještě ucpanější)?

Může se objevit '+c' (ulice byla uzavřena), '+b' (ulice se "ucpala") a '-' (komplikace z dané ulice zmizely). Každá z možností přepíše předchozí stav. Ulice tedy může nabývat pouze 3 stavů - normální, ucpaná, uzavřená.

Je povolen pouze C#/VB, nebo i ostatní, řekněme, normální jazyky?

Jazyky nejsou explicitně omezené, čili jsou implicitně povoleny minimálně všechny "běžně používané" jazyky (C, C++, C#, Java, Python, PHP a tak dále...), jde hlavně o to abych to dokázal spustit (automatizovaně) a byl schopný se alespoň základně vyznat v kódu.

Nahoru Odpovědět 13. listopadu 23:53
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
krepsy3
Redaktor
Avatar
krepsy3:14. listopadu 8:08

Startovní a cílovou ulici vždy projíždím celou, tedy jakoby od té druhé křižovatky či slepého konce, je to tak?
Možná by bylo logičtější, že začíná a končí se ve prostřed dané ulice, ale ok :D

Nahoru Odpovědět 14. listopadu 8:08
Programátor je stroj k převodu kávy na kód.
Avatar
Odpovídá na Zdeněk Pavlátka
Lukáš Hruda (Luckin):14. listopadu 9:46

Zdravím,
sice se pravděpodobně nezúčastním, ale jelikož mi tyto soutěže přijdou zajímavé, poměrně pravidelně je zde sleduji a k tomuto zadání si nemohu odpustit pár poznámek.
Na konci zadání je uvedeno, že hodnotit se bude především efektivita zvoleného algoritmu, čímž předpokládám, že je myšlena časová náročnost výpočtu, nikde však není řečeno, jakým způsobem bude toto hodnocení provedeno.
Pokud bude efektivita vyhodnocována měřením, pak je dle mého názoru vcelku důležité uvést, co se přesně bude měřit, zda celkový běh programu nebo vyhodnocení všech dotazů či vyhodnocení každého dotazu samostatně.
Jde o to, že graf lze reprezentovat mnoha způsoby a každý z nich je vhodný pro jinou situaci.
Jelikož podle zadání se nejdříve na vstupu zadávají hrany a potom vrcholy, lze předpokládat, že řešitel nejdříve zvolí takovou reprezentaci, která mu umožní co nejjednodušší konstrukci grafu tímto způsobem, ta však ale nemusí být vhodná pro rychlé hledání cest a proto se může rozhodnout, že graf převede na jinou reprezentaci, což však může zabrat nějaký čas. Otázkou je, zda doba konstrukce a eventuálního převodu grafu, tedy předzpracování, budou v měření zahrnuty.
Dále, řešený problém popsaný v zadání je problémem hledání minimální cesty v ohodnoceném neorientovaném grafu, což je problém, dle mého názoru, v zásadě triviální, jelikož na jeho řešení existují známé algoritmy, které nejsou zásadně složité a silně pochybuji, že někdo vymyslí rychlejší (skoro mi přijde, že načtení vstupu je zde náročnější programátorský problém než to samotné hledání cest). Lze samozřejmě vymyslet nespočet heuristik, ale jejich problém je v tom, že z principu nevedou k přesnému řešení (tedy nevedou k minimální cestě, ale jen k přibližně minimální), tedy alespoň v obecném případě (pokud by bylo uvedeno, že graf je nějakým speciálním případem, například rovinným grafem, pak by situace byla trochu jiná).
Avšak, pokud by časové měření bylo provedeno pro všechny dotazy najednou, nikoliv pro každý zvlášť, pak by situace mohla být poměrně zajímavá, protože to by umožňovalo řešiteli využít informací z předchozích dotazů k urychlení těch následujících. Například, pokud dva po sobě jdoucí dotazy mají stejný výchozí vrchol, lze část výpočtu z prvního dotazu použít při vyhodnocování druhého dotazu a tím tak výpočet urychlit. Stejně tak, pokud by byl stejný koncový vrchol. Předpokládám, že by bylo možné vymyslet i způsoby, jak využít předchozích výpočtů i v případech, kdy jsou výchozí i koncový vrchol různé či kdy se mezi dotazy změní ohodnocení hran. Toto by mohlo přinést poměrně zajímavé možnosti a zajímavá řešení a jako algoritmický problém to již rozhodně není triviální.

 
Nahoru Odpovědět 14. listopadu 9:46
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na krepsy3
Zdeněk Pavlátka:14. listopadu 9:50

Startovní a cílovou ulici vždy projíždím celou, tedy jakoby od té druhé křižovatky či slepého konce, je to tak?
Možná by bylo logičtější, že začíná a končí se ve prostřed dané ulice, ale ok

Logičtější ano, ale neovlivní to která cesta je nejkratší, čili z hlediska úlohy to není moc podstatné. Ale když už jsi to navrhl...

Změna zadání: U startovní a koncové ulice se do celkové délky cesty započítává jen polovina jejich délek.

Nahoru Odpovědět 14. listopadu 9:50
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Zdeněk Pavlátka:14. listopadu 14:02

Vzhledem k tomu, že zpracování mapy proběhne 1× a dotazů může být spousta, jde hlavně o rychlost odpovídání na jednotlivé dotazy. Úloha je dosti zaměřená právě na vhodnou reprezentaci dat.

Na konci zadání je uvedeno, že hodnotit se bude především efektivita zvoleného algoritmu, čímž předpokládám, že je myšlena časová náročnost výpočtu, nikde však není řečeno, jakým způsobem bude toto hodnocení provedeno.

Hodnocení efektivity bude primárně založené na reprezentaci dat a zvoleném algoritmu (jeho implementaci). Vzhledem k tomu, že lze použít navzájem velmi odlišné jazyky, není měření času běhu moc praktické, protože stejný program v různých jazycích bude různě rychlý (např. C++ a Python).

Nahoru Odpovědět 14. listopadu 14:02
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Zdeněk Pavlátka
Zdeněk Pavlátka:19. listopadu 23:30

Přidal jsem testovací vstup a odpovídající výstup - odkazy jsou na konci zadání.

Nahoru Odpovědět 19. listopadu 23:30
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
pocitac770
Redaktor
Avatar
pocitac770:20. listopadu 15:01

Máme dělat program blbuvzdorný ve smyslu, že jako chyba se nemusí vyskytnou jenom špatné syntaktické zadání ale i špatné logické zadání (např. ulice spojuje 3 křižovatky, 2 křižovatky jsou spojeny 2 cestami...)

Editováno 20. listopadu 15:02
 
Nahoru Odpovědět 20. listopadu 15:01
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na pocitac770
Zdeněk Pavlátka:20. listopadu 21:24

Stačí kontrolovat "syntaxi". Pokud bude vstup při finálním testování (během hodnocení) správně "syntakticky", bude správně i "logicky".

Nahoru Odpovědět 20. listopadu 21:24
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Neználek
Člen
Avatar
Odpovídá na Zdeněk Pavlátka
Neználek:21. listopadu 17:32
U_SkalyKrci Na_Valentince Nam_Antonina_Pecaka Ke_Krci 15.855
U_SkalyKrci Na_Valentince Repinska Hnevkovskeho Ke_Krci 17,935
-
U_SkalyKrci Upska Cechurova Za_Lidovym_Domem Kazimirova Hnevkovskeho Ke_Krci 19,395
U_SkalyKrci Na_Valentince Ricni Basilejske_Namesti Ke_Krci 43,345
-

K zápisu desetinného čísla se má použít čárka nebo tečka?

 
Nahoru Odpovědět 21. listopadu 17:32
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na Neználek
Zdeněk Pavlátka:21. listopadu 20:06

Omlouvám se za chybu, mají tam být všude tečky (soubor jsem opravil)

Nahoru Odpovědět 21. listopadu 20:06
Kolik jazyků umíš, tolikrát jsi programátor.
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 12 zpráv z 12.