Diskuze k úloze číslo 5
Toto fórum slouží výhradně k diskuzím o úloze číslo 5. Během hry je zakázáno diskutovat o zadání i řešení této úlohy kdekoliv jinde, než zde. K diskuzi o ostatních úlohách prosíme využijte jim příslušná fóra. Prosíme, nekažte hru ostatním!
Vysvětlení k páté úloze a omluva orgů
Jirka Benc (org)
(13. 11. 2009 - 22:39)
Sbalit(1)
Hráčům, kteří se trápili s tím, že jim skript tvrdil, že mají správné heslo, a robotek ho odmítal, dlužíme vysvětlení.
Úloha měla mít jednoznačné řešení. Nikdo z testerů se netvářil, že tomu tak není; bohužel, na některé věci se přijde až při živé hře. Ve chvíli, kdy jsme chybu zjistili, už úlohou prošlo slušné množství hráčů, z nichž někteří zkoušeli různá hesla, která skript bral jako správná (a robotek ne), až po nějaké době přišli i na to "naše správné".
Debata orgů byla bouřlivá (a docela dlouhá). Zvažovali jsme různá řešení, například přidat do zadání úlohy, že řešení je smysluplné slovo. Tím bychom ale znevýhodnili ty, kteří už měli úlohu vyřešenou. Nebo nechat robotka, aby uznával vše, co projde skriptem. To by zase znevýhodnilo ty, co taková hesla zkoušeli, a po delší době přišli na to "správné".
Nakonec jsme došli k závěru, že jediné řešení problému, které nikoho nepoškodí, je nechat úlohu tak, jak je, a přidat nápovědu. Nápovědu jsme dali bez časového postihu a posíláme ji za nejnižší možnou dobu, která je možná - za 3 hodiny (ve chvíli, kdy jsme nápovědu zaváděli, byl aktuální nejdelší čas řešení dvě a půl hodiny).
Moc se všem omlouváme, a doufáme, že tohle bude největší letošní zádrhel.
Úloha měla mít jednoznačné řešení. Nikdo z testerů se netvářil, že tomu tak není; bohužel, na některé věci se přijde až při živé hře. Ve chvíli, kdy jsme chybu zjistili, už úlohou prošlo slušné množství hráčů, z nichž někteří zkoušeli různá hesla, která skript bral jako správná (a robotek ne), až po nějaké době přišli i na to "naše správné".
Debata orgů byla bouřlivá (a docela dlouhá). Zvažovali jsme různá řešení, například přidat do zadání úlohy, že řešení je smysluplné slovo. Tím bychom ale znevýhodnili ty, kteří už měli úlohu vyřešenou. Nebo nechat robotka, aby uznával vše, co projde skriptem. To by zase znevýhodnilo ty, co taková hesla zkoušeli, a po delší době přišli na to "správné".
Nakonec jsme došli k závěru, že jediné řešení problému, které nikoho nepoškodí, je nechat úlohu tak, jak je, a přidat nápovědu. Nápovědu jsme dali bez časového postihu a posíláme ji za nejnižší možnou dobu, která je možná - za 3 hodiny (ve chvíli, kdy jsme nápovědu zaváděli, byl aktuální nejdelší čas řešení dvě a půl hodiny).
Moc se všem omlouváme, a doufáme, že tohle bude největší letošní zádrhel.
Re: Diskuze k úloze číslo 5
Robert-Antonio
(13. 11. 2009 - 22:50)
Sbalit(1)
Inu teď už je to jasnější. Původně mi šifrátorská hrdost nedovolila použít bruteforce, ale poté co mi robotek odmítl uznat krásné řešení plné káček a ixek, jsem se naštval a nechal projet dotyčným grepem celý slovník. A jak to bylo najednou rychlé :)
hovnival
9.packet
(14. 11. 2009 - 13:59)
Sbalit(6)
Mám dotaz. K čemu je ve skriptu tahle kontrola:
if echo $HESLO | grep -qv '^...h\?o\?v\?n\?i\|v\?a\?l\?...$';
Mám pocit, ze tímto "filtrem" projde všechno. Má hovnivál sloužit jako nápověda: hovnivál -> kadibudka?
Nebo jsem něco přehlédl?
A další věc, jaktože grep bere vyescapované znaky v regexu, jako by byly nevyescapované?
if echo $HESLO | grep -qv '^...h\?o\?v\?n\?i\|v\?a\?l\?...$';
Mám pocit, ze tímto "filtrem" projde všechno. Má hovnivál sloužit jako nápověda: hovnivál -> kadibudka?
Nebo jsem něco přehlédl?
A další věc, jaktože grep bere vyescapované znaky v regexu, jako by byly nevyescapované?
Re: hovnival
Michal Kubeček
(14. 11. 2009 - 14:24)
Sbalit(1)
On Sat, Nov 14, 2009 at 01:59:01PM +0100, 9.packet wrote:
>
> A další věc, jaktože grep bere vyescapované znaky v regexu, jako by
> byly nevyescapované?
Příkaz grep defaultně používá basic regular expressions, ne extended.
U GNU verze se to dá přepnout přepínačem -r.
>
> A další věc, jaktože grep bere vyescapované znaky v regexu, jako by
> byly nevyescapované?
Příkaz grep defaultně používá basic regular expressions, ne extended.
U GNU verze se to dá přepnout přepínačem -r.
Re: hovnival
ndru.smigi
(14. 11. 2009 - 14:28)
Sbalit(1)
Mi osobně to opravdu jako nápověda posloužilo, ve chvíli kdy částečné řešení prošlo druhým (a tedy i třetím) grepem se to dalo uhodnout.
Re: hovnival
anicka (org)
(14. 11. 2009 - 14:46)
Sbalit(2)
> Mám pocit, ze tímto "filtrem" projde všechno. Má hovnivál sloužit jako
> nápověda: hovnivál -> kadibudka? Nebo jsem něco přehlédl?
To je pravda. A přesně z tohoto důvodu to s úlohou dopadlo tak špatně,
jak to dopadlo. Kdybych se nepřehlédla a bylo to napsané tak, aby to
dělalo, co jsem měla v úmyslu, aby to dělalo, bylo by řešení
jednoznačné. Smůla je, že testeři i orgové, co to četli po mně, mi na
to skočili. Je mi to moc líto :-(
Ale hovnivál měl být jen takový vtípek. Opravdová nápověda na kadibudku
mělo být řešení podobné, leč jednodušší úlohy předtím.
> nápověda: hovnivál -> kadibudka? Nebo jsem něco přehlédl?
To je pravda. A přesně z tohoto důvodu to s úlohou dopadlo tak špatně,
jak to dopadlo. Kdybych se nepřehlédla a bylo to napsané tak, aby to
dělalo, co jsem měla v úmyslu, aby to dělalo, bylo by řešení
jednoznačné. Smůla je, že testeři i orgové, co to četli po mně, mi na
to skočili. Je mi to moc líto :-(
Ale hovnivál měl být jen takový vtípek. Opravdová nápověda na kadibudku
mělo být řešení podobné, leč jednodušší úlohy předtím.
Re: Diskuze k úloze číslo 5
honza.hadacek
(15. 11. 2009 - 9:45)
Sbalit(1)
Tak jsem si rikal ze na to uz neprijdu... Porad jsem na to koukal a rikal jsem si ka---u....a sakra co to muze bejt. Tak jsem sel spat. V noci jsem se probudil a najednou mi bylo vsecko jasny :D!
Re: Diskuze k úloze číslo 5
Tomáš Poledný
(15. 11. 2009 - 13:57)
Sbalit(9)
Jak jste to řešily? Já jsem si rozepsal na papír co těma grepama projde a pak jsem to dával do hromady. Jde to řešit i jinak než tím že tomu narvu slovník? Já jsem byl celkem nešťastný, protže hned poprvé jsem našel 2 řešení a pořád jsem nechápal proč mi to robůtek nechce vzít.
Re: Diskuze k úloze číslo 5
tomi
(15. 11. 2009 - 14:50)
Sbalit(7)
No, "nejsprávnější" řešení by asi mohlo být udělat průnik jazyků těch pěti regulárních výrazů, což je celkem lehká věc. Tedy, kdyby to mělo jednoznačné řešení, jinak by to bylo hrozně neužitečné :-)
Re: Diskuze k úloze číslo 5
9.packet
(16. 11. 2009 - 11:01)
Sbalit(6)
Jak se dělá průnik regulérních výrazů?
Re: Diskuze k úloze číslo 5
tomi
(16. 11. 2009 - 12:08)
Sbalit(5)
K oboum se sestrojí konečný automat (lze provést mechanicky), z nich se vyrobí automat pro průnik (lze provést mechanicky), a z tohoto automatu se dají vypsat všechny slova, která přijímá (lze provést mechanicky, ale může toho být nekonečně mnoho).
Detaily o tom, jak to funguje a jak to provést, popisují tyhlety učební texty, jakožto nejspíš i wikipedie a další internetové zdroje:
http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf
http://www.cs.vsb.cz/jancar/TEORET-INF/ti-text.2007-08-31.pdf
http://www.cs.vsb.cz/kot/animace.php
Je dost možný, že někdy někde v rámci nějakých bakalářek vznikly nějaké online demonstrační programy, pomocí kterých by si to člověk mohl zkusit, ale nevím o ničem konkrétním.
Detaily o tom, jak to funguje a jak to provést, popisují tyhlety učební texty, jakožto nejspíš i wikipedie a další internetové zdroje:
http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf
http://www.cs.vsb.cz/jancar/TEORET-INF/ti-text.2007-08-31.pdf
http://www.cs.vsb.cz/kot/animace.php
Je dost možný, že někdy někde v rámci nějakých bakalářek vznikly nějaké online demonstrační programy, pomocí kterých by si to člověk mohl zkusit, ale nevím o ničem konkrétním.
Re: Diskuze k úloze číslo 5
Bilbo
(16. 11. 2009 - 14:11)
Sbalit(4)
Lze provest sice mechanicky, ale obecne slozitost automatu pro prunik muze byt exponencialni (kdyz vezmeme X regularnich vyrazu, trivialne lze sestavit nedeterministicky regularni automat prijimajici jazyk prijimany temi regexpy, ale prevest to na deterministicky muze znamenat v jistych pripadech exponencialni narust stavu)
A aby to navic bylo human-readable?
Napsat program co vezme podobnych 5 regexpu a sestavi z toho jeden dlouhy hnusny chrchel odpovidajici tem peti regexpum neni ani tak tezke.
Napsat program co vezme podobnych 5 regexpu a sestavi z lidsky aspon trochu pochopitelny regexp je uz asi dosti obtizne.
A aby to navic bylo human-readable?
Napsat program co vezme podobnych 5 regexpu a sestavi z toho jeden dlouhy hnusny chrchel odpovidajici tem peti regexpum neni ani tak tezke.
Napsat program co vezme podobnych 5 regexpu a sestavi z lidsky aspon trochu pochopitelny regexp je uz asi dosti obtizne.
Re: Diskuze k úloze číslo 5
tomi
(16. 11. 2009 - 14:12)
Sbalit(3)
Nikdo nechtěl vyrábět čitelný regexp, cílem bylo vypsat slova toho jazyka.
Re: Diskuze k úloze číslo 5
Martin Mares (org)
(16. 11. 2009 - 17:34)
Sbalit(2)
K čemuž ještě nemusí sestrojení průnikového automatu vést, protože průnikový
automat může snadno být exponencialně velký.
automat může snadno být exponencialně velký.
Re: Diskuze k úloze číslo 5
xhire
(15. 11. 2009 - 15:51)
Sbalit(1)
Napsal jsem si na papír "normální" regexpy (bez těch šílených lomítek), a pak si je postupně do jiného skriptu kopíroval a ověřoval své tipy (výsledné sedící vzory jsem si opět poznamenával, čímž jsem nakonec (de fakto náhodou) došel k výslednému výrazu (že ten výraz vážně sedí, mě mile překvapilo, protože tak lehké jsem to nečekal (naproti tomu musím říct, že než jsem přistoupil na tuhle metodu, tak jsem se s tím "chvíli" trápil ;c))).
Re: Diskuze k úloze číslo 5
valach.pavel
(15. 11. 2009 - 18:45)
Sbalit(1)
Dáváte mi trochu zabrat. S regulárními výrazy jsem nikdy pořádně neuměl - a tak mi trvalo, než jsem pochopil, jaké podmínky musím splnit. Heslový skript jsem si přepsal tak, aby mi ověřoval tipy a říkal, jaké podmínky mi musí ještě splnit... - no a pak to bylo do 15 minut vyřešené.
Re: Diskuze k úloze číslo 5
pebble
(18. 11. 2009 - 13:26)
Sbalit(1)
Resi se tu vaznejsi veci, vim. Me az zas tak netrapily, bo mi zatim jako spravna hesla vzdy vysla smysluplna slova (~napoveda).
Mmch, ke konstrukci skriptu: pomerne elegantni mi prijde tato:
grep <cokoliv_chcete> <<<$promenna
Mmch, ke konstrukci skriptu: pomerne elegantni mi prijde tato:
grep <cokoliv_chcete> <<<$promenna