Няколко дни след крайния срок за предаване на първа задача за този сезон сме готови с резултатите! Почти всички състезатели се бяха постарали да предадат добри и ефективни решения и журито имаше сериозната задача да оцени коректно всички. Борбата за първите места беше оспорвана. В следващите редове ще разкажем как беше проведено оценяването, какви затруднения имахме (и ще направим забележки към някои участници), както и ще похвалим заслужилите! Резултатите от приложната и алгоритмичната част ще видите на края на тази публикация (така че по-нетърпеливите могат да започнат скролирането)

За оценяването и резултатите от алгоритмичната част

Задачата от първи кръг беше подбрана така, че да е възможно “хитри” алгоритми да получат по-високи точки. Не сме убедени, дали при тези ограничения има оптимално решение, като това беше и целта. Състезателите трябваше да приложат техни евристики (алгоритми, които изглеждат оптимални в много случаи, без доказателство за това) и да се борят за по-добра игра от останалите алгоритми.

Тестовете, проверката и разпределението на резултатите

Журито реши за по-голяма точност на резултатите да генерира повече тестове, с които да бъдат изпитани алгоритмите. Ето как (в общи линии) работи генераторът за тестове:

  • Зададени са няколко множества от диапазони от стойности за граници на генерираните данни
    • 3 диапазона за размер на полето
    • 3 диапазона за брой ходове
    • 3 диапазона за брой “добри региони” (бъде обяснено по-надолу)
    • 4 диапазона за височини на кули
  • “Добри региони” наричаме полета, при които имаме 4 еднакви стойности, съседи на една различна от тях стойност (т.е. визуално подобно на знака плюс, където “краищата” са с еднакви стойности).
  • Чрез няколко последователни вложени цикъла:
    • За всеки диапазон за размер се генерира произволна стойност в този диапазон,
    • За всеки диапазон за брой ходове се генерира произволна стойност в този диапазон,
    • За всеки диапазон за брой добри региони се генерира произволна стойност в този диапазон
    • За всеки диапазон от височини на кули и за всяка кула от полето се избира произволна стойност в този диапазон и се слага като височина на съответната кула.
  • За избраната стойност на брой добри региони, върху вече генерираното (в предишните стъпки) поле, на произволни позиции се генерират добрите региони
  • Генерираното поле се обхожда и всички съседни еднакви стойности се нулират (за да не останат съседни еднакви стойности)
    • Забележка: в условието е казано, че няма кули с еднакви височини – поле със стойност 0 не е кула, а липса на кула, затова можем да имаме 2 съседни празни полета

Генерираното поле се обхожда и валидира според ограниченията в условието на задачата

    • Ако валидацията е успешна, се генерира тестов файл с генерираните данни

С така описания алгоритъм за генерация, се създават точно 108 на брой тестови полета. Оттам, всеки алгоритъм е тестван върху генерираните полета. Проверяващата система:

  • Зарежда всички тестове в паметта
  • Стартира един алгоритъм
  • Започва да отброява време за изпълнение
  • Изпраща данните към конзоната на алгоритъма
  • Изчаква до прекратяване на работа на алгоритъма или до изтичането на времето
    • и се опитва да вземе всички изпечатани редове
    • при превишаване на времето системата принудително спира алгоритъма
  • Обработва получения изход от алгоритъма
    • играе всеки ход
    • ако срещне проблем във изхода спира дотам (предишните редове се зачитат)
  • Смята разликата на първоначалното поле с крайното и взема това за резултат на алгоритъма
  • Прави горепосочените неща за всички алгоритми и запазва в резултатите

След изпълнението на всички алгоритми с всички тестове, резултатите се скалират (както е описано в условието на задачата), прилагат се евентуални наказателни точки (ще обясним и за тях) и резултатите се закръглят до цели числа.

Забележка: състезателите не бива да правят заключения относно работата на проверяващата система за следващите кръгове, спрямо описанието на проверката за този кръг, тъй като за всеки кръг проверката работи по специфичен начин.

След като описахме условно как работи оценяващата система, ще обърнем малко внимание на резултатите и решенията на участниците. Голяма част от участниците бяха спазили формата за предаване на решения, което значително улесни проверката. Разбира се имаше и такива, които не се бяха “справили” с тази част, но за това ще говорим по-късно.

Резултатите за алгоритмичната част се разпределиха сравнително добре – за почти всяко число от 0 до 10 имаме по няколко отбора, като за топ резултати борбата е най-оспорвана – имаме много отбори с резултат 10 точки след закръглянето (ще публикуваме резултатие преди и след закръглянето с информативни цели, но ще вземем впредвид само закръглените). Точките, които някои алгоритми получиха на някои тестове изненадаха журито – имаше доста висока успеваемост на събарянето на кулите, като получените точки бяха в порядъка на милиони. Решенията ще бъдат достъпни публично (виж най-долу на тази публикация), така че всеки ще може да разгледа какви алгоритми са приложили участниците за високите  резултати.

 Забележки към участниците и наложени наказания при алгоритмичната част

Някои участници не бяха спазили всички изисквания, които бяха поставени (както за форматиране на входно-изходните данни, така и за структуриране на решенията в папки). Тук ще обърнем внимание на често срещаните проблеми и ще обясним защо това забавя и пречи на оценяването, и как се справихме със съответните проблеми.

Ще започнем от по-малко сериозните проблеми. Първи в този ред е проблемът с неправилното структуриране на решението. В страницата “Качи решение” е ясно и подробно описано (дори с включен пример) как трябва да бъде форматирано едно решение. Сложили сме това изискване, защото опитът показва, че някои състезатели пращат решенията си в трудни за обработка формати (който желае може да погледне “Архив” за примери). За щастие повечето участници бяха спазили това изискване. Но имаше и такива, които го бяха игнорирали – което затрудни подбирането на алгоритмичните файлове за проверка. За този проблем не сме отнемали точки, но приканваме състезателите да спазват структурата, защото при системно неспазване журито може да прецени да отнеме точки (или дори да не намери файлът, който всъщност трябва да бъде проверен).

По-сериозен проблем е, че някои алгоритми търсеха ресурсите си “там където не трябва”. В описанието за структурирането на решението пише, че в папката за алгоритмичната част може да има ресурси, които алгоритъма ползва. Това означава че такива ресурси могат да бъдат само и единствено в директория algorithm, не извън нея, например в директория application, която е на едно ниво нагоре в йерархията. С две думи, алгоритъмът има право на достъп само и единствено до директорията в която се намира (и до нейни поддиректории, разбира се) и до нищо друго. Алгоритмите, които се опитваха да намерят файлове извън папката си “хвърляха изключения” (Exceptions) и спираха да работят. Това е абсолютно грешно поведение – щом алгоритъмът не може да намери свои собствени ресурси (различни от входните данни, защото те са валидни по условие за тази задача), той трябва сам да се справи с този проблем, а не да “гърми”. Журито направи компромис и коригира кодът на тези алгоритми, за да не получат 0 точки, но разбира се наложихме наказателни точки за това (в общия случай 0.5) на съответните алгоритми.

Някой алгоритми явно опитваха да “забързат” входа и изхода с промяна на размера на буфера на прозореца конзолата, размера ? и т.н. – това е грешно поведение и не е начинът да се забърза четенето на входа! В последните дни преди крайния срок в коментарите Светлин Наков публикува информация как може да се ускори четенето и писането. Много състезатели са се справили коректно с това и останалите състезатели могат да погледнат техния код (по регламент всички решения ще бъдат качени във вида, в който са изпратени). Когато проверяващата система праща (и приема) данни до алгоритъма, може да се каже че “конзолата не е собственост на алгоритъма” и при опит за нейната манипулация, алгоритъмът отново получава exception. Отново никой състезател не се беше досетил, че трябва да провери за тази ситуация (try-catch) и отново журито внесе корекции по кода на тези алгоритми. Наложихме отново наказателни точки (около 0.5).

Най-сериозният проблем беше неправилното форматиране на изхода. Няколко алгоритъма упорито печатаха излишни редове на конзолата (от порядъка на “input the ….”, “this is….”, както и вида на полето), форматираха грешно изхода си (поставяха разнооразни скоби, тирета и други символи на място на интервалите, или пък не печатаха интервали изобщо), или четяха входните данни некоректно (разчитаха, че височината на всяка кула ще е на отделен ред, не както е описано в условието). Където успяхме – коригирахме и съответно наложихме наказателни точки. Уважаеми състезатели, спазвайте стриктно форматът на входните и изходните данни – в противен случай проверяващата система не може да интерпретира коректно отговорите, които вашите алгоритми дават!

Тази секция заема доста голяма част от цялата публикация, но това е първи кръг за този сезон и е нормално все още да не сме се доуточнили помежду си. Надяваме се, че тези забележки ще помогнат на състезателите да разберат грешките си и да предават по-качествени решения в следващите кръгове, които да позволяват по-бърза работа на журито.

За оценяването и резултатите от приложната част

В приложната част определено видяхме интересни решения. Както и миналата година, заложихме на това да оставим на състезателите креативната част – описахме това, което искахме да получим почти от гледната точка на редови потребител и очаквахме да бъдат задоволени нашите искания. Нека наблегнем повече на това – приложната част участниците трябва да разбират като създаване на продукт в реалния живот – понякога се жертва една функционалност за друга, понякога се добавя нещо, което никой друг не се е сетил, и се надмогва над конкуренцията с него, а понякога дори предложените решения от конкуренцията не са на особено високо ниво и дори едно просто но добре направено приложение печели потребителите. Това е философията на приложната част – доближаване до реалния свят, доколкото това е възможно във времето и условията, които състезателите имат.

Изготвихме критериите за оценка още при публикацията на задачата. Ето и как процедирахме със самото оценяване:

  • Всяко приложение бе стартирано самостоятелно и преглеждано щателно
  • За всяко приложение, по скалата от 0 до 10, бяха давани оценки по критериите Коректност, Справяне с грешки, Ползваемост, UI дизайн и Оригиналност
  • Оценките за всеки критерии бяха скалирани, така че оценките да се получат в описаните в условието граници
    • до 3 точки за Коректност
    • до 1 точка за Справяне с грешки
    • до 2 точки за Ползваемост
    • до 2 точки за UI дизайн
    • до 2 точки за Оригиналност
  • Крайните оценки за приложната част на всеки отбор получихме, като събрахме получените горе скалирани оценки и ги закръглихме до цели числа

Тъй като това е първи кръг, ще кажем няколко думи приблизително как журито оценява съответните критерии. Това в никакъв случай не трябва да се приема като правило, по което журито оценява, а по-скоро има за цел да представи начина на мислене на журито за съответните критерии. Изводите, които участниците могат да си направят от следващите редове са за тяхна сметка.

Как журито оценява Коректност?

Критерият коректност има цел да определи дали дадената задача е изпълнена. Коректност в реалния свят би означавало дали клиентът е получил това, което е поискал, по-конкретно дали функционалността, която е важна за определена задача е изпълнена, както и колко ефективно е това изпълнение. Тоест, това е критерия, който е най-близко до самото условие – “ако ключовите думи от условието присъстват в решението”, това е добре. Ако те присъстват по добър начин, дават верни резултати, работят достатъчно бързо и се интегрират ефективно с останалите компоненти – това води до високи оценки от журито.

В тази задача се изискваше визуализация на играта – тоест трябва да има начин да се зададат начални условия за играта, играта трябва да бъде визуализирана (като данните за полето трябва да бъдат представени чрез HTML), добре е да е видим крайният резултат, добре е да са видими извършените ходове, да може да се навигира между ходовете. Това са все неща тясно свързани с условието на задачата. Следващата стъпка след като тези неща присъстват, е да работят добре – т.е. да няма дефекти при навигацията, визуализацията да работи бързо и т.н.

Как журито оценява Справяне с грешки?

Този критерий е пълната противоположност на първия – под грешки имаме предвид непредвидени ситуации. В живота това означава: какво се случва ако ти изтрия папката с ресурсите, какво се случва ако няма права за писане по хард-диска, какво се случва ако входните данни са невалидни или непълни, какво се случва ако входните данни са твърде много, какво се случва ако потребителя кликне върху 10 бутона за 1-2 секунди, какво се случва ако потребителя се опита да хакне сайта и да направи SQL Injection, какво се случва ако базата данни падне, какво се случва ако спре тока, или приложението бъде спряно внезапно по друга причина. Все неща, които в реална ситуация са напълно възможни. Разбира се ситуациите са твърде много и не очакваме състезателите да се справят с абсолютно всичко. Но очакваме да се справят с приоритетните проблеми.

В тази задача приоритетните проблеми са: Какво става при отрицателни стойности за кули, размер или брой ходове? Какво става при наличие на невалидни команди? Какво става, ако директорията, в която приложението създава html файлове, не му е предостъпена с write права? Какво става, ако ресурсите, които приложението ползва за генериране на визуализация бъдат изтрити? Не е задължително едно приложение да може да работи пълноценно, ако се случат такива грешки – но е изключително нужно потребителя да разбере, че има проблем, който се дължи на определени обстоятелства – било то липсващи файлове или нещо друго. И това, което му бъде предоставено, трябва да бъде в неговата компетенция – не може да се разчита, че той знае какво е “Parameter cannot be null” или “Input string was not in a correct format”.

Как журито оценява Ползваемост?

Ползваемост (или usability) определя колко е лесна работата с едно приложение. Това може да бъде всичко от разположение на интерфейса (като например next и previous бутоните не трябва да са в двата края на екрана, освен ако приложението не е за таблет), лесна навигация в менютата на приложението, бързо задаване на команди за извършване на рутинни дейности (например copy-paste е нещо, което се случва доста лесно и не би трябвало операции от този порядък да изискват работа с повече от 2 менюта), предвидимост на операциите (така че потребителя да не се страхува какво ще направи даден бутон, а да го очаква преди още да го е натиснал) и интуитивност на интерфейса (т.е. един компютърно-грамотен потребител да може да се ориентира без напътствия).

Ползваемостта е дълб0ка тема, но когато става за не толкова големи приложения е лесно да се изследва. Повикайте някой – който не е участвал в разработката – и му дайте приложението. Ако 1 минута не може да си генерира полето, или пък често пъти прави едно и също нещо, което не иска да прави – е сигурно има проблем.

Как журито оценява UI Дизайн?

Дизайнът е сравнително далечна от самото софтуерно инженерство тема, която донякъде има общи точки с ползваемостта. Но в по-голямата си част тя е цветовото оформление (кои цветове с кои си ходят и защо не трябва да слагаме светло-зелени букви върху зелен фон), подредбата, подравняването и отстоянията между елементите (така интерфейса да изглежда все едно си “пасва” и няма нито нагъчкани нито “forever alone” елементи от него) и общия вид и приятност. Не е лесно да се даде дефиниция за добър дизайн и неговите компоненти, но е лесно да се разпознае такъв. За участниците, които имат артистични умения – това е мястото да се постараят и да ги упражнят. За тези, при които тези умения не са толкова развити – има много примери в света, по които може да се движите и да следвате, както и много безплатни дизайн шаблони.

Как да разбираме Оригиналност?

Оригиналност в контекста на това състезанието е имплементирането на функционалности, за които журито не би се досетило, но които въпреки това са полезни/ефектни, както и имплементирането на известни функционалности но по различен начин, който е по-добър от стандартния. Отново е трудно да дадем дефиниция какво търсим тук, защото ние всъщност не го търсим – то само идва при нас, показва се и ни взема вниманието, като нещо уникално, нещо полезно и нещо добре направено.

Оригиналността може да бъде в много форми – на това състезание видяхме няколко такива примера – тримерна визуализация, DOS-стил интерфейс (изненадващо по-удобен от някои, да речем, “стъкмени” GUI приложения) и зареждане на алгоритъм, който да играе, вместо използване на вграден в приложението (зареждането на алгоритъм не е напълно оригинално, тъй като в минали издания на състезанието е имало много такива задачи, но е оригинално за този кръг, тъй като останалите състезатели не се бяха досетили за това).

 Резултати и награждаване

Дойде и най-интересния момент – класирането. По-долу ще намерите таблица, с потребителските имена на авторите в студентската система на Телерик (или e-mail-ите, там където не сме получили потребителско име).

Ще наградим първите 3 отбора (изписани с удебелен шрифт) в класирането, за представянето им на този кръг, на 4-ти януари 2013, от 13:30 часа в Академията на Телерик (отборите ще получат официална покана и по e-mail).

Благодарим на всички за участието и се надяваме след по-малко от месец да видим решения ви за следващия кръг!

Автор 1 Автор 2 Общо Алгоритъм Приложение
at.keranov paveld3  19 10 9
mgochev 18 10 8
aleks.todorov nader.dabour 16 10 6
plamen.hristian 15 10 5
georgi.ivanov 15 8 7
gercho manchev 15 9 6
kdikov 15 9 6
venelin.petrov 14 9 5
stoyaneft merakses 14 10 4
muybien 13 5 8
psotirov 13 7 6
aslv1 erik1001 13 8 5
pemmpty lazo003 13 9 4
zdravko.beykov 13 10 3
traiko.dinev Depressor 13 10 3
krasi.nikolov ognyan.petkov 13 6 7
Iliyan 11 5 6
Nikola.Gamzakov 11 8 3
Ivaylo ognyan.angelov 10 4 6
NikolaNikolov 10 10 0
pirin 9 9 0
rplatikanov 9 9 0
jasssonpet 8 0 8
BlackEagle galingrudov 8 5 3
d_p_y 7 2 5
saykor bigerbite 7 5 2
Ivan.Dimitrov.bg makmidov 7 7 0
Nevencheto 7 7 0
mario.stoilov.9 ivailok1 6 0 6
technet 6 0 6
yonko.tsonev 5 0 5
Ivanski1024 AntonPetrov 5 0 5
JohnnyBGoode Християн Зарков 5 0 5
moshensky Stanislav Petrov 5 3 2
xakepa 5 5 0
xpxd4 martin.durchov 4 0 4
Viktor_Ivanov nikolay_spasov 4 1 3
mitko_lazarov 4 1 3
teodorkk 4 1 3
stringbitking 4 4 0
antont 3 0 3
mitko29 3 0 3
I12FLY 3 1 2
loloto 2 0 2
cocodonchev rusiqt 2 2 0
F3rrAr1 SyncCarryOn 2 2 0
boyan.zhelyazkov 1 1 0
kiril.ilarionov 1 1 0
BorisIde lubodabest 0 0 0
Daniel 0 0 0
linach 0 0 0
s_mihaylov 0 0 0

Подробни резултати и допълнителни материали

В подробните резултати се съдържат всички стъпки на оценяване описани по-горе.

  • Алгоритмична част – algorithm-results-full-info.xlsx
    • при отборите с 2-ма участници, където и двамата са предали решения, са оценявани поотделно, като за класирането е взет максималният от двата резултата
  • Приложна част – application-results-full-info.xlsx

Всички допълнителни материали от състезанието (решения на участниците, тестове, лог файлове на тестването и т.н.) ще могат да бъдат намерени няколо дни след класирането на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/.