Zápočtový test 22. 1. 10:00

Cílem semináře je seznámit posluchače s jazykem C#, prostředím platformy .NET a tvorbou aplikací s grafickým uživatelským rozhraním. Předpokládají se znalosti objektově orientovaného programování.
Lamisil2

Zápočtový test 22. 1. 10:00

Příspěvek od Lamisil2 »

Ahoj tak zadání vypadalo takhle:
Naprogramujte "Simulator Hada".

Cilem ulohy je odsimulovat prubeh hry, ktery je popsan souborem.
V souboru je popis bludiste a potom poporade popis jednotlivych hadu.
Popis bludiste se sklada z rozmeru na prvnim radku (sirka x vyska)
a potom z matice znaku odpovidajici velikosti. Znaky znamenaji

. prazdne policko
X plne policko
S misto kam je vhozen had . Tato mista maji poradi definovane lexikograficky podle radku a potom sloupce.

Nasleduje popis jednotlivych hadu (podle usporadani znaku S). Had je popsan na jednom radku tremi udaji
1, delka
2, pocatecni smer - E W N S
3, program - sekvence cisel a znaku L a R. L zmeni smer hada doleva a R doprava.
Zmena smeru se hned projevi posunem v tom smeru.
Tedy napriklad sekvence LRLRLRLRLRLRLRLR udela "schody", LLLL se toci na 4 polickach
Pokud je v programu cislo n, had pobezi pristich n kroku aktualnim smerem.
Kdyz se dorazi na konec sekvence, pokracuje se znova od zacatku.

Had narazi na jineho hada, na sebe nebo na zed. Cilem je zjistit v kterem kroku ktery had narazi a najit viteze, ktery vydrzi
nejdele.

Poznamky!!!
- V kazdem kroku simulace se pohnou vsichni zivi hadi
- Mrtvoly hadu v bludisti zustavaji.
- Bludiste se "opakuje" - pokud tomu nebrani zed, dostane se had z leveho okraje doprava, z horniho dolu a podobne.
- Had neroste (nema co by sezral) s jedinou vyjimkou a to je zacatek hry. V prvnim kroku maji hadi delku jedna,
v nasledujicich rostou, dokud nedosahnou plne delky.
- Simulace se muze zacyklit! Tedy trasa hada (hadu) se opakuje aniz by do neceho narazil.
To je treba detekovat a oznamit uzivateli.

Vystupem ma tedy byt cislo hada a pocet kroku ktere se odsimulovaly nez narazil.
Pokud se hra zacykli, vypise se info o hadech kteri narazili pred cyklem, pocet
kroku nez se simulace dostala do cyklu a delka cyklu.

Vse se indexuje od nuly.


------------------------------
Priklad vstupu definujici bludiste 20x10 ktere ma jen "zed na okraji". Do bludiste jsou vpusteni 3 hadi.
Prvni ma delku 4, zacina na pozici prvniho S, vyjizdi na zapad a v prvnim kroku se otoci doleva, pak doprava, pak doleva a tak dale
a nakonec narazi do zdi v 8mem kroku, jeste nez se dostane k polozce 100.
Druhy had ma delku 10 a kouka na vychod. V zapeti zahne doleva (nahoru) a jede tim smerem 10 kroku. Drive ale narazi do zdi a konci
ve 4. kroku. Posledni had, vyrazi na jih a konci ve 3. kroku narazem na zed.



#RozmeryBludiste
20 10
#TvarBludiste
XXXXXXXXXXXXXXXXXXXX
X..................X
X...S..............X
X..................X
X...........S......X
X..................X
X......S...........X
X..................X
X..................X
XXXXXXXXXXXXXXXXXXXX

#Popis prvniho hada
4 W LRLRLRLR100LR
#Popis druheho hada
10 E L10L10L10L10
#Popis tretiho hada
1 S 50
Na zacatku nam cvicici jeste upresnil nektere veci. Napriklad ze hadovi se nejdriv prodlouzi hlava a potom se mu teprve zkrati ocas, takze napriklad had delky 4 s programem LLLL by naboural sam do sebe. Potom jeste ze v ramci jednoho kroku je poradi posouvani hadu stejne jako jejich poradi ve vstupu. Jinak podle me stejne nakonec nekontroloval zadny speky, takze tyto veci nebyly zas tak dulezity. Na zacatku nam dal asi 6 vstupnich dat, na kterejch jsme si to mohli zkouset a na kterych to i kontroloval (mimo jiných).
Uživatelský avatar
DZuXO
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 20. 1. 2009 11:28
Typ studia: Informatika Bc.

Re: Zápočtový test 22. 1. 10:00

Příspěvek od DZuXO »

ach jaj som to strasne zlamil :-( nevedel som si spomenut na maticu rotacie o uhol, aby som mohol jednoducho otacat hadovi hlavu o 90°... tak som to robil IFmy a vsetkymi moznostami a som sa v tom uplne zamotal. V kazdom pripade asi by som aj tak nezvladol urobit detekciu cyklu... ako (by) ste to robili ? Resp, ako by si mal nejak sikovne zaznemanavat tie stavy ? napada ma len jedno riesenie, ale to si radsej necham pre seba, myslim, ze je dost EVIL :lol:
UIRA — UIRA Isn't a Recursive Acronym.
Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 17. 5. 2007 20:09
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zápočtový test 22. 1. 10:00

Příspěvek od Yawgmoth »

myslim, že evil řešení mu nevadilo :)

já měl natvrdo stav hada jako čtveřici intů - pozice na mapě, směr, pozice v programu
stav celého tahu byl list stavů všech hadů
a pak byl list už prošlých stavů tahu - vždycky jsem tupě projel celý list jestli nový stav tahu už náhodou nebyl (tj po složkách porovnat všechny hady ... naštěstí equals na struktuře funguje hezky žejo) .. pokud ano, pak je to cyklus, pokud ne, přidat stav do listu ...

na tom bludišti 100x100 to už bylo dost pomalé, přecijen stavů na konci bylo přes 10000 .. nicméně to bylo jednoduché na implementaci a stačilo ... jestli někdo má jiné jednoduché a elegantnější řešení tak se podělte :)

Kolik lidí to nakonec dalo?
Uživatelský avatar
tomasslavicek
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 4. 6. 2009 19:03
Typ studia: Informatika Bc.

Re: Zápočtový test 22. 1. 10:00

Příspěvek od tomasslavicek »

Tak zápočet dostalo 6 (možná 7) lidí, z nějakých 22 přihlášených. Úloha nebyla těžká, ale opravdu to chtělo, aby člověk už měl něco naprogramováno. Odevzdávat se začalo až cca půl hodiny před koncem, bylo tam hodně psaní. Co jsem viděl, u většiny lidí to kontroloval poměrně poctivě, chtěl vidět výsledky všech vstupů, náhled do kódu jak jste reprezentovali hady a říct, jak jste řešili detekci cyklů. Naopak mi vůbec nekontroloval načítání vstupu, nebo jak jsem řešil ostatní metody. Čas se na konci neprodlužoval, hlavním těžištěm problému bylo to hlavně stihnout odladit. Pokud jste se ve výsledku lišili někde o jedničku, nebyl to problém.

Detekci cyklů jsem taky řešil zapamatováním stavů všech hadů ve všech krocích a pak lineárním průchodem a kontrolováním, jestli už ten stav nastal. Pro velká bludiště sice výpočet trval asi 15 sekund, ale uznal mi to. Lépe by se to asi dalo řešit pomocí HashSetu nebo Dictionary. Na co chtělo ale dát velký pozor, pokud by bylo bludiště šířky 20 bez stěn na kraji a had měl v předpisu jet 100 políček rovně, znovu stejný stav nenastal po 20 krocích, ale až po nějakých 100 nebo 101. Potom by totiž mohl ještě zahnout a třeba narazit a cyklení by to nebylo.
Odpovědět

Zpět na „NPRG035 Jazyk C# a platforma .NET“