Soutěž: Machr na algoritmy - Regulární výrazy

C# .NET .NET (C# a Visual Basic) Machr na algoritmy - Regulární výrazy American English version English version

Soutěž již skončila

Zadání

V dnešním machrovi si zkusíme implementovat funkcionalitu, kterou využíváme téměř v každé aplikaci. Budou to regulární výrazy. Regulární výraz je sekvence znaků, podle kterých vyhledáváme v zadaném textu shodu.

Rozhraní

Pogram dostane na standardním vstupu zadaný text ukončený znakem nového řádku. Dále dostane regulární výraz, opět ukončený znakem nového řádku. Program vrací hodnotu 0, jestliže byla nalezena shoda. V případě, že shoda nalezena nebyla, program vrátí hodnotu 1. Jestliže regulární výraz nebude validní, program vrátí hodnotu 2. To jsou případy, kdy bude obsahovat znaky, které nemají žádný význam, nebo formát regulárního výrazu nebude správný (například nebude ukončena závorka). Na standardní výstup program nic nevypisuje, pouze vrátí návratový kód.

Implementace

Regulární výrazy budou rozděleny do několika kategorií. Doporučuji implementovat funkcionalitu postupně, jak je vypsána.

  • Pouze jednotlivé znaky. Prakticky se kontroluje pouze to, zda je vzor totožný s textem. Text i vzor bude obsahovat pouze číslice, malé a velké písmena bez diakritiky a mezeru. To platí pro všechny následující body. Pokud bude ve vzoru nebo textu znak, který do této skupiny nepatří (například "č"), program vrátí hodnotu 2.
  • Vzor bude obsahovat množiny, které se zapisují mezi hranaté závorky. Například pro vzor [agt] je shoda v řetězci, který obsahuje pouze jeden ze znaků "a", "g", "t". Jestliže nebude hranatá závorka ukončena, program vrátí hodnotu 2.
  • Vzor bude obsahovat operátory, kontrolující počet výskytů předchozího znaku. Je to znak * (předchozí znak se nemusí vyskytovat, nebo se může libovolně opakovat), + (předchozí znak se musí vyskytovat minimálně jednou) a znak ? (předchozí znak se nemusí vyskytovat, nebo se vyskytuje právě jednou).
  • Množiny můžou být zapsány i rozpětím. Tedy [a-z] jsou všechna malá písmena, [a-zA-Z] jsou všechna písmena, [0-9] jsou všechny číslice. Kromě toho lze množinu zadat speciálním tvarem [:alpha:] pro všechna písmena, [:upper:] pro velká písmena, [:lower:] pro malá písmena, [:num:] pro číslice a [:alnum:] pro všechny znaky kromě mezery.
  • Do tohoto bodu musel regulární výraz pojmout celý text. To je důležité. V dalším kroku se bude kontrolovat, jestli bude nalezen regulární výraz kdekoliv v textu. Při prvním výskytu se program ukončí a vrátí hodnotu 0.
  • Předposlední varianta přidává znak "^" do množin a obrací význam. Jestliže [abc] pasuje na text, který obsahuje "a", "b" nebo "c", [^abc] pasuje na text, který obsahuje libovolný znak kromě "a" "b" nebo "c".
  • V poslední iteraci program bude umět zpracovat znak "^" mimo množinu (značí začátek slova) a znak "$" (značí konec slova). Například regulární výraz "^aha" vrátí 0 (úspěch) pro slovo "aha", ale 1 (neúspěch) pro slovo "dlaha".

Hodnocení
Jsou povoleny jazyky C++, C#, Java a PHP. Další jazyky po domluvě.
Bude samozřejmě hodnocena funkcionalita, ale i kvalita kódu!

Nakonec bych chtěl napsat pár rad pro snadnější implementaci.

  • Dodržte rozhraní. Program nemá výstup, vrací pouze návratový kód, do konzole nic nevypisujte.
  • Regulární výrazy se zpravidla řeší konečným stavovým automatem. Jeden zdroj můžete najít na Itnetwork. Kromě toho je na internetu spousta materiálu k tomuto tématu.

EDIT: Pro úspěšné řešení je nutné mít řešení otestované! V odevzdaném řešení tedy musí být i projekt s testy.

Níže uvedené příklady předpokládají kompletně splněné zadání. nejdřív je uveden vzor, poté text.

"Petr" "Vcera jsem byl s Petrou"
"[a-z]k" "trakar"
"vr+" "vrrrrr" i "vratnice" ale ne "vana"
"vr?a" "vrah" i "vana" ale ne "vrrrrr"
"m[^h-z]" "mazat", ale ne "umucit"
"^stre" "na strese" ale ne "prostredi"
"[a-zA-Z0-9 ]*" vyhovuje všemu

Výhra

Vítěz dostane placku Machr, pár samolepek a ocenění do portfolia.

Výhra

Výsledky

Jméno bodů Řešení ( Stáhnout vše )
tomisoka 90 Stáhnout řešení
pocitac770 85 Stáhnout řešení
dave_23 70 Stáhnout řešení
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

V dnešním machrovi si zkusíme implementovat regulární výrazy.

Soutěž končí 21. února 20:00, tak se nezapomeň zapojit! :)

Odpovědět  +3 8. února 11:07
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Atrament
Člen
Avatar
Odpovídá na patrik.valkovic
Atrament:

s/standartní/stan­dardní/g

 
Nahoru Odpovědět 8. února 12:58
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Atrament
patrik.valkovic:

Jo díky, vždycky si to odvodím špatně :/ :D

Nahoru Odpovědět 8. února 13:08
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
budacjozef98
Člen
Avatar
budacjozef98:

Python je povoleny ? :)

 
Nahoru Odpovědět 8. února 13:51
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na budacjozef98
patrik.valkovic:

Nechceš použít něco jiného? :D Já Python neumím :(

Nahoru Odpovědět 8. února 14:29
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Michael Škrášek:
Text i vzor bude obsahovat pouze číslice, malé a velké písmena bez diakritiky a mezeru

To znamená, že text nebude obsahovat ani čárky, tečky? ... to je divný ne, co to pak bude za text :D

Nahoru Odpovědět 8. února 14:37
Proč to dělat složitě, když to jde jednoduše.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Michael Škrášek
patrik.valkovic:

Jo zdá se to, ale uvědomuješ si, jak bys to tím stížil? To by znamenalo přidání escapování znaků, začátek a konec slova by taky probíhalo na základě několika podmínek (na rozdíl od prosté mezery). Buď rád, že je to jak je :D

Nahoru Odpovědět 8. února 14:39
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Nahoru Odpovědět 8. února 14:43
Proč to dělat složitě, když to jde jednoduše.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Pozn.: byl přidán další požadavek - testy ;-)

Nahoru Odpovědět  +1 8. února 14:56
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Posix
Člen
Avatar
Posix:

Můžem k implementaci použít regulární výrazy? :D

Nahoru Odpovědět  -1 8. února 16:38
Proč to dělat jednoduše, když to jde složitě.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Posix
patrik.valkovic:

No....jakou čekáš odpověď? :D Hezky naparsovat :)

Nahoru Odpovědět  +1 8. února 16:43
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Lukáš Křehula
Redaktor
Avatar
Odpovídá na patrik.valkovic
Lukáš Křehula:

Nemohl by jsi přidat nějaký příklad vstup-regex-výstup?

 
Nahoru Odpovědět  +3 8. února 17:24
Avatar
tomisoka
Redaktor
Avatar
Odpovídá na patrik.valkovic
tomisoka:

Zajímavé téma, jen by mě zajímalo pár věcí:
Co si mám představit pod tímto:

Kromě toho lze množinu zadat speciálním tvarem [:alpha:] pro všechny znaky


Do tohoto bodu musel regulární výraz pojmout celý text.

Toto mě mírně mate, máme tedy implementovat jednotlivě všechny možné kategorie, nebo stačí splnit všechny tyto parametry v jednom programu?


Regulární výrazy se zpravidla řeší konečným stavovým automatem.

Doufám, že toto není povinnost, protože tento způsob mi přijde mírně nepřehledný.


V odevzdaném řešení tedy musí být i projekt s testy.

Jak funguje tohle? Ještě nikdy jsem žádné takovéto testy k mému projektu nepřidával. Stačí soubor s příkladovými vstupy + jejich výstup?


Přidaná funkcionalita je žádaná? Např '.' pro libovolný znak.


BTW:

Je to znak * (předchozí znak se nemusí vyskytovat, nebo se může libovolně opakovat), + (předchozí znak se musí vyskytovat minimálně jednou) a znak ? (předchozí znak se nemusí vyskytovat, nebo se vyskytuje právě jednou).

 
Nahoru Odpovědět 8. února 20:10
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na tomisoka
patrik.valkovic:

Díky, asi nějaký autocorrect :(
1 - [:alpha:] jsou všechna písmena, je to opraveno.
2 - Musel pojmout celý text znamená, že pro vstup "ad abcd" a regulární výraz "abcd" měl program vrátit 1 (neúspěch), protože prvotní sekvence "ad" nebyla zadána.
3 - Kategorie jsem se snažil seřadit podle obtížnosti. Iterativním přístupem se mi to jeví jako nejschůdnější řešení, ale samozřejmě postup nechám na vás ;) Samozřejmě program bude pouze jeden, který bude obsahovat všechny kategorie.
4 - Stavový automat povinný není, ale to že se to pomocí něho obvykle řeší má své důvody (a přehlednost je jedním z nich). Je to machr, máte se něco nového naučit, tak proč to nezkusit ;-)
5 - O testování se tu rozepisovat nebudu. Najdi si na Googlu Unit testy, potom tě to už nasměruje.
6 - Tečku jsem zapomněl :( Nicméně už to opravovat nebudu a další funkcionalita není vyžadována.

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

[:alpha:] platí pořád jen a-Z (tj bez diaktritiky)?

Nahoru Odpovědět 9. února 16:06
Proč to dělat jednoduše, když to jde složitě.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Posix
patrik.valkovic:

Ano, ale pozor. Formální zápis je [a-zA-Z], coz je ekvivalence k [:alpha:].

Nahoru Odpovědět 9. února 16:12
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Štefan Pružinský:

Ahoj, mohol by si uviesť pár exemplárnych vstupov a výstupov z použitím daných operátorov na lepšiu ilustráciu.

Nahoru Odpovědět  +1 9. února 16:35
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Nahoru Odpovědět  +1 9. února 16:39
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
1Pupik1989
Člen
Avatar
1Pupik1989:

Javascript může být? Včera jsem dopsal překladač, tak bych ho zkusil trochu ořezat. :D

 
Nahoru Odpovědět 9. února 20:19
Avatar
Odpovídá na patrik.valkovic
Ondřej Štorc:

Mohou být množiny definovány i takhle: [a-Z], nebo ho lze zapsat jen takhle: [a-zA-Z]?

Nahoru Odpovědět  -1 9. února 20:38
Život je příliš krátký na to, abychom bezpečně odebírali USB z počítače..
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na 1Pupik1989
patrik.valkovic:

No tak nakonec jsem se rozhodl, že může být i Javascript, ale podmínka konzolové apliakce zůstává. Nechci to pouštět v prohlířeči, proto se prosím podívej na JSDB (http://www.jsdb.org/index.html). Počítej s tím prosím.
To stejné platí pro PHP, bude spuštěno v konzoli!! Nevím, jestli jsem to dostatečně zdůraznil. Pro bližší informace prostudujte http://www.thecave.info/…-input-user/ a http://stackoverflow.com/…ble-possible.
Množina nemůže být definována [a-Z], platí pouze [a-zA-Z] ale samozřejmě i další kombinace (uvedu zítra v demo vstupech).
[a-t] [a-z0-7] [a-tA-T] a podobně. Ale nemůžou být spolu znaky různé kategorie [a-9] [a-Z] atd (v takových situacích program vrátí 1 (neúspěch).

Nahoru Odpovědět  +1 9. února 21:46
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na Ondřej Štorc
Štefan Pružinský:

Asi nie... Btw. teším sa na ďalší spoločný súboj. :D

Ano, ale pozor. Formální zápis je [a-zA-Z], coz je ekvivalence k [:alpha:].

Editováno 9. února 21:51
Nahoru Odpovědět 9. února 21:49
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
Odpovídá na patrik.valkovic
Štefan Pružinský:

Tak si ma predbehol...

Ale nemůžou být spolu znaky různé kategorie [a-9] [a-Z] atd (v takových situacích program vrátí 1 (neúspěch).

Nemám to byť náhodou 2? Výraz nie je validný, nie?

Nahoru Odpovědět 9. února 21:51
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Štefan Pružinský
patrik.valkovic:

Jo, už mi to nejde opravit (včetně těch překlepů) :(

Nahoru Odpovědět 9. února 21:52
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Štefan Pružinský:

Myslím, že ide. Teraz som to skúšal... Nastav si kurzor na konečnú pozíciu toho tlačidla a počas refreshu kontinuálne klikaj... Hodí Ťa to späť do formulára komentáru, kde ho môžeš upraviť... :)

Editováno 9. února 21:56
Nahoru Odpovědět 9. února 21:54
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Byly přidány ukázky.

Nahoru Odpovědět 10. února 14:11
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
balaz.marek94:

Môže byť aj čosi takéto?

[a-z] [:upper::lower:]m[:alnum: ]

Ak to náhodou nebude vidno, tak vo výraze sú dve medzery :)

 
Nahoru Odpovědět 11. února 9:23
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na balaz.marek94
patrik.valkovic:

Ne, kombinovat se můžou pouze zápisy zapsané s pomlčkou. [:upper::lower:] je přece [:alpha:]. Nicméně může být zápis

[a-z ]

To znamená nějaké malé písmeno nebo mezera. I tohle je platné:

[a-tABC0-2 ]
Nahoru Odpovědět 11. února 9:28
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
balaz.marek94:

Chápem, ešte jedna otázka, asi hlúpa keďže klasické regulárne výrazy ju používajú, ale predsa. Môže byť výraz zapísaný aj takto? :-)

[a-z]m[a-z]
 
Nahoru Odpovědět 11. února 14:52
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na balaz.marek94
patrik.valkovic:

Samozřejmě. To znamená libovolné malé písmeno, potom m následujícím opět libovolným malým písmenem.

Nahoru Odpovědět 11. února 14:59
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
1Pupik1989
Člen
Avatar
1Pupik1989:

"vr?" "vrah" i "vana" ale ne "vrrrrr"

Opravdu? Já bych řekl, že "vrrrrr" projde.

 
Nahoru Odpovědět 11. února 19:55
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na 1Pupik1989
patrik.valkovic:

? znamená, že se nevyskytuje nebo se vykytuje jednou. To znamená že vrah projde, vana taky (r se vykytovat nemusí).
A jak se na to teď dívám, "vrrr" skutečně projde :D Ale kdyby byl vzor "vr?a", tak vana i vrah projdou, ale vrr už ne ;-)

Nahoru Odpovědět 11. února 19:59
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
1Pupik1989
Člen
Avatar
Odpovídá na patrik.valkovic
1Pupik1989:

To je pravda. Jen jsem se 2x nad tím pozastavil, než jsem napsal. Projde vlastně vše co začíná na "v". ;-)

 
Nahoru Odpovědět 12. února 10:16
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Odpovídá na patrik.valkovic
Zdeněk Pavlátka:

Všechny příklady vrací 0 (úspěch).

"vr+" "vrrrrr" i "vratnice" ale ne "vana"

To je trochu podivná formulace, nejpreve napíšeš, že všechny vrací nulu, ale pak v příkladech uvádíš i možnosti, které by projít neměly

Nahoru Odpovědět 12. února 11:12
Kolik jazyků umíš, tolikrát jsi programátor.
Avatar
Odpovídá na patrik.valkovic
Štefan Pružinský:

Do tohoto bodu musel regulární výraz pojmout celý text. To je důležité. V dalším kroku se bude kontrolovat, jestli bude nalezen regulární výraz kdekoliv v textu. Při prvním výskytu se program ukončí a vrátí hodnotu 0.

Myslíš to všeobecne, alebo doslovne? V kontexte, v ktorom to bolo povedané to znamená niečo ako:
Nesprávne (pre direktívy text, +, ?, *, [] platí: "Do tohoto bodu musel regulární výraz pojmout celý text"):

Pattern: fr*d?[^d-z]
Text: ABCD/frrrdc/jska - potencionálna, ale neuznaná zhoda => nejde o celý text, ale len o výsek z neho

Správne:

Pattern: fr*d?[^d-z]
Text: /frrrdc/

pozn.: // ohraničuje zhodu.

A naopak direktívy $ a ^ na začiatku/konci textu treba hľadať na hocijakom mieste v texte. Znie to trochu nelogicky a malo by to byť skôr úplne naopak, nie? Prípadne si tým poukazoval na dva odlišné módy programu... Vopred ďakujem za vysvetlenie. :)

Nahoru Odpovědět 13. února 15:06
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Štefan Pružinský
patrik.valkovic:

Ano a ano. Buď implementujete verzi, která zkoumá celý text (verze 1), nebo verzi, která zkoumá jednotlivé části textu (proto jsou direktivy ^$ zařazeny až na konec).
Zadání je vymyšleno k iterativnímu vývoji. Do té doby bude kontrolován celý text. V další iteraci se program vylepší, aby mu stačila pouze část textu. Bylo by vhodné přidat informaci o fázi vývoje do projektu.

Nahoru Odpovědět 13. února 15:11
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Posix
Člen
Avatar
Posix:

Asi bysme měli řešit i backtracking, že?
např

"vr?rak" => "vrak" "vrrak" "vrrrak"
Nahoru Odpovědět 15. února 16:21
Proč to dělat jednoduše, když to jde složitě.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Posix
patrik.valkovic:

První a druhé projde, třetí už ne (můžou být maximálně 2 r).

Nahoru Odpovědět 15. února 17:26
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Posix
Člen
Avatar
Odpovídá na patrik.valkovic
Posix:

a jo, třetí by nemělo

Nahoru Odpovědět 15. února 17:31
Proč to dělat jednoduše, když to jde složitě.
Avatar
Odpovídá na patrik.valkovic
Štefan Pružinský:

Ešte jedná, zdanlivo primitívna otázka: Bude všetok text/vzorka v jednom odstavci?
Jeden odstavec:

No tak nakonec jsem se rozhodl, že může být i Javascript, ale podmínka konzolové apliakce zůstává. Nechci to pouštět v prohlířeči, proto se prosím podívej na JSDB (http://www.jsdb.org/index.html). Počítej s tím prosím. To stejné platí pro PHP, bude spuštěno v konzoli!! Nevím, jestli jsem to dostatečně zdůraznil. Pro bližší informace prostudujte http://www.thecave.info/…-input-user/ a http://stackoverflow.com/…ble-possible. Množina nemůže být definována [a-Z], platí pouze [a-zA-Z] ale samozřejmě i další kombinace (uvedu zítra v demo vstupech). [a-t] [a-z0-7] [a-tA-T] a podobně. Ale nemůžou být spolu znaky různé kategorie [a-9] [a-Z] atd (v takových situacích program vrátí 1 (neúspěch).

Viac:

No tak nakonec jsem se rozhodl, že může být i Javascript, ale podmínka konzolové apliakce zůstává. Nechci to pouštět v prohlířeči, proto se prosím podívej na JSDB (http://www.jsdb.org/index.html). Počítej s tím prosím.
To stejné platí pro PHP, bude spuštěno v konzoli!! Nevím, jestli jsem to dostatečně zdůraznil. Pro bližší informace prostudujte http://www.thecave.info/…-input-user/ a http://stackoverflow.com/…ble-possible.
Množina nemůže být definována [a-Z], platí pouze [a-zA-Z] ale samozřejmě i další kombinace (uvedu zítra v demo vstupech).
[a-t] [a-z0-7] [a-tA-T] a podobně. Ale nemůžou být spolu znaky různé kategorie [a-9] [a-Z] atd (v takových situacích program vrátí 1 (neúspěch).
Nahoru Odpovědět 16. února 14:36
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
tomisoka
Redaktor
Avatar
Odpovídá na Štefan Pružinský
tomisoka:

Text i vzor bude obsahovat pouze číslice, malé a velké písmena bez diakritiky a mezeru.

Ale reálně pokud by ti tam dal i více řádků tak by to funkcionalitě nemělo uškodit.


A taky moc by to nešlo vzhledem k inputu:

Program dostane na standardním vstupu zadaný text ukončený znakem nového řádku. Dále dostane regulární výraz, opět ukončený znakem nového řádku.

 
Nahoru Odpovědět  +2 16. února 14:52
Avatar
Odpovídá na tomisoka
Štefan Pružinský:

Práve o to ukončenie znakom nového riadku mi išlo... Moja chyba - nehľadal som odpoveď v zadaní. Díki. :)

Nahoru Odpovědět  +1 16. února 14:57
Najefektívnejším spôsobom debuggingu je modlitba. :)
Avatar
pocitac770
Redaktor
Avatar
pocitac770:

Bere se jako validní "regulární výraz" i prázdný výraz?

 
Nahoru Odpovědět 18. února 23:08
Avatar
Nahoru Odpovědět 18. února 23:11
Nesnáším {}, proto se jim vyhýbám.
Avatar
pocitac770
Redaktor
Avatar
Odpovídá na Michal Žůrek (misaz)
pocitac770:

Právě, že mě to napadlo, že všechny podmínky splňuje, tak se pro jistotu ptám, protože na tuhle problematiku tady snad zatím nikdo nenarazil :D

 
Nahoru Odpovědět  +1 18. února 23:14
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na pocitac770
patrik.valkovic:

Ano, ale z principu vždy vrátí 0 (úspěch).

Nahoru Odpovědět  +1 18. února 23:15
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
pocitac770
Redaktor
Avatar
pocitac770:

Z těch Unit Testů jsem teda fakt jelen... Chápu to dobře, že vlastně máme vytvořit zvlášť projekt s třídou, přes kterou budeme simulovat jednotlivé vstupy? A máme udělat jeden "test" pro každý bod?

 
Nahoru Odpovědět 21. února 15:25
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na pocitac770
patrik.valkovic:

Program má určitě i nějakou vnitřní logiku, kterou by bylo vhodné otestovat. Formu a rozsah testů nechávám na vás.

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

Soutěž ukončena, pokusím se to do zítřka opravit.

Nahoru Odpovědět 21. února 23:42
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:

tomisoka - 90 bodů
Výborné řešení. Neprošly pouze 4 vstupy, ale to bylo pravděpodobně špatnou formulací v zadání. N druhou strany, je rozdíl mezi koncem slova a koncem fráze! Ačkoliv jsi proti tomu měl námitky, nakonec jsi přeci jen udělal stavový automat (ať si to uvědomuješ nebo ne). Chválím chytré parsování vstupu (jako jedinný). Jen názvy tříd byly trochu matucí a chyběly testy.

pocitac770 - 85 bodů
Prošli všechny řešení až na 7. Bohužel pro některé vstupy vyhazoval program výjimky, a v takových situacích nemůžu udělit splnění soutěže. I když je v programu náznak stavového automatu, ta validace je naprosto šílená. Pokud bych začal přidávat další požadavky, tak je tento stav neudržitelný. Navíc je vše v jedné metodě.

dave_23 - 70 bodů
Oceňuji snahu o implementaci stavového automatu. Bohužel program neprošel ve 21 případech. Také chválím dokumentaci (jako jedinný)!! Jeden test se píše do jedné metody (aby od sebe šli odlišit). Když ti teď nějaký test neprojde, tak nezjistíš, pro kterou hodnotu. Vím že je to dost psaní navíc, ale z dlouhodobého hlediska je to mnohem lepší.
A mimochodem - pokrytí kódu testama bylo skoro 95%, dobrá práce :)

Placku tedy získává tomisoka Gratuluji :)

Akceptované řešení
+20 Zkušeností
+1 bodů
Řešení problému
Nahoru Odpovědět 22. února 21:24
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
patrik.valkovic:

Kdo by měl zájem, zde jsou všechna testovací data: http://1drv.ms/1QW4Gy7
Nejsou tam složitější situace, ty se mi nechtělo vymýšlet.

Druhá otázka, měli byste zájem o miniseriál na tento konkrétní příklad? Praktickou implementaci?

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

Aha, tak tím pádem jsem nepochopil co vše se bere jako stavový automat a odvolávát tu zmínku o nepřehlednosti.
K těm ^ $ jsem to ani zase tak nepitval a udělal jsem to tam jak jsem to pochopil z dřívějšího používání regexů. To by vysvětlovalo proč mi tyto znaky přišly jako skoro nepoužitelné...
Jinak názvy tříd mi přijdou celkem jasné, tak nevím.

 
Nahoru Odpovědět 22. února 21:57
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na tomisoka
patrik.valkovic:

Stavový automat je posloupnost stavů, které na sebe navazují. U tebe je stav třeba porovnání písmene. Pokud znak odpovídá, přechází se na další objekt, pokud ne, tak vrací 1 (konečný stav) a automat končí (v tomto případě nevalidním vstupem). Automat může být ještě rozvětvený (do jednoho stavu se lze dostat několika cestami), v takovém případě by si návrh, jak ho máš ty, s tím neporadil (to ale nebyl případ této úlohy).

Nahoru Odpovědět 23. února 18:24
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
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 53 zpráv z 53.