Skip to Content

Второ предварително тестване за трети кръг на сезон 2012/2013 – “големи бомби”

Написано на 02/25/2013 1:58 am, от

Проведохме и второто предварително тестване за този кръг и се радваме да видим, че някои от отбелязаните в първото тестване проблеми са вече отстранени

В това тестване включихме само отборите, които са предали решения (или са обновили решенията си) след първото тестване. С  две думи, не сме тествали наново решения, които сме тествали в предишното тестване.

Ето логът на извличането на отборите, включили се в това тестване:

Предадено от Местоположение на authors.txt файла Автор 1 Автор 2
aleks.todorov aleks.todorov\BigBombs\authors.txt aleks.todorov nader.dabour
at.keranov at.keranov\authors.txt paveld3 at.keranov
kdikov kdikov\authors.txt kdikov nikola76
mitko_lazarov mitko_lazarov\authors.txt mitko_lazarov
Ognyan.Petkov Ognyan.Petkov\authors.txt krasi.nikolov ognyan.petkov
pemmpty pemmpty\Final\authors.txt pemmpty lazo003
pirin pirin\authors.txt pirin isipro
plamen_1 plamen_1\Big Bombs\authors.txt plamen_1 hristy93
yonko.tsonev Error parsing “authors.txt” file:
Could not match any username
in “authors.txt” with user that submitted

Единствено при yonko.tsonev има малък проблем – некоректен формат на e-mail адреса, който води до объркването му с потребителско име – оттам и посочената грешка в лог файла.

Отново нямахме проблем с извличането на алгоритмите – но може да погледнете логът от извличането на алгоритмите.

Може би по-интересната част са резултатите на примерните тестове. Както обещахме, добавихме още няколко теста, които да дадат обща идея за това, което ще генерира журито на реалното тестване. По-долу можете да видите резултатите.

Забележка: тъй като предварителното тестване цели предимно да открие грешки при форматиране и изпълнение, и поради това че се провежда в извънработно време, често машината на която се провежда е с по-ниски характеристики от обявената за реалното оценяване. На тези тестове няколко отбора имат проблем с time limit, които може да не е наличен при реалната машина. Публикуваме резултатите сега, а през деня ще публикуваме допълнително резултатите върху реалната машина за тестване.

Предадено от sample-test-1.txt sample-test-2.txt sample-test-3.txt sample-test-4.txt sample-test-5.txt
aleks.todorov 42 400 224 84 126
at.keranov 0 0 0 0 0
kdikov 42 400 272 240 304
mitko_lazarov 0 0 274 24 304
Ognyan.Petkov 42 400 274 240 304
pemmpty 42 400 0 0 284
pirin 0 0 0 0 0
plamen_1 42 400 274 240 304
yonko.tsonev 0 212 56 0 96

Състезателите могат да прегледат логът от тестването и файловете с детайли за повече информация. Тестовете също са качени.

Проверихме и пратените от състезателите тестове за валидност. Там проверката е стриктна, защото тези тестове ще бъдат изпълнявани и върху други алгоритми и дори излишни интервали могат да предизвикат невалидност на теста.

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

С това завършваме предварителните тествания за този кръг и пожелаваме успех и сполучливи последни корекции преди крайния срок за предаване – 23:59 днес, 25 февруари 2013.

Update: тествахме алгоритмите отново, този път върху конфигурацията, която бе обявена и се радваме да ви съобщим, че time limit проблемите намаляха драстично. Ето как изглеждат резултатите от предварителните тестове сега:

Предадено от sample-test-1.txt sample-test-2.txt sample-test-3.txt sample-test-4.txt sample-test-5.txt
aleks.todorov 42 400 224 84 126
at.keranov 42 400 272 240 304
kdikov 42 400 272 240 304
mitko_lazarov 0 400 274 24 304
Ognyan.Petkov 42 400 274 240 304
pemmpty 42 400 0 0 284
pirin 42 400 196 240 304
plamen_1 42 400 274 240 304
yonko.tsonev 0 212 56 0 96

Разбира се, имаме и лог файл от тестването.

Всички публикации 3 Comments

Първо предварително тестване за трети кръг на сезон 2012/2013 – “големи бомби”

Написано на 02/23/2013 10:59 am, от

Проведохме първото предварително тестване за този кръг. Имахме известни проблеми с тестващата система, затова и забавихме резултатите. В това първо тестване се включиха 6 отбора. Ето и логът на извличането на самите отбори:

Предадено от Местоположение на F1″authors.txt” файлът Автор 1 Автор 2
JavaSTNT fullsubmits\JavaSTNT\authors.txt JavaSTNT
kdikov fullsubmits\kdikov\authors.txt kdikov nikola76
mitko_lazarov fullsubmits\mitko_lazarov\authors.txt mitko_lazarov
Ognyan.Petkov fullsubmits\Ognyan.Petkov\authors.txt krasi.nikolov ognyan.petkov
pirin fullsubmits\pirin\authors.txt pirin isipro
plamen.hristian Error parsing “authors.txt” file: Could not match any username in “authors.txt” with user that submitted

Изглежда отборите са предали коректно authors.txt файл. Единственият проблем е при отборът на “plamen.hristian” и се дължи на това, че в authors.txt файлът не е посочено потребителско име, а само e-mail.

При извличането на алгоритмите нямахме проблеми – всичко участници бяха предали правилно папка algorithm с изпълним файл, като някои бяха генерирали и техни тестове. За тестовете след малко.

За това предварително тестване изпълнихме само примерните тестове от условието на задачата. Довечера във второто предварително тестване ще добавим още няколко теста за по-голяма яснота.

Ето и как изглеждат резултатите:

Предадено от Първи примерен тест Втори примерен тест
JavaSTNT 0 0
kdikov 0 0
mitko_lazarov 0 0
Ognyan.Petkov 42 400
pirin 42 0
plamen.hristian 42 0

Тук е важно да отбележим, че машината, на която тествахме,  имаше проблем с Java инсталацията. Затова конкретно решението на JavaSTNT ще бъде тествано наново следобед на машината, на която ще бъде проведено и нормалното тестване.

Редакция: изпълнихме алгоритъма на JavaSTNT, но той не се стартира успешно, като хвърля съобщението “Error: could not find or load main class attack”.

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

Ето и логът от тестването, както и файловете с детайли по входа и изхода на тестовете, оценени с 0 (нула) точки.

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

  • JavaSTNT – файлът съдържа 101 реда, т.е. общо 100 команди, а на първия ред бройката команди е зададена като 98. Също така файлът трябва да бъде с име JavaSTNT.txt, а в момента е именован bb1.txt
  • Ognyan.Petkov – файлът е правилно именован и форматиран, но сборът на цените на всички единици надвишава 200 (изглежда не са взети предвид цените на мините)
  • pirin – файлът е правилно именован, но започва директно с командите за поставяне на единици, без да описва колко на брой са командите.

Проблемите не са твърде големи и се надяваме състезателите да ги коригират при следващото си предаване на решение.

Днес предварителното тестване ще се проведе при същите правила – всички решения предадени до 23:00 ще бъдат оценени и резултатите ще бъдат публикувани след 00:00 часа в понеделник (най-вероятно това ще стане по-бързо, отколкото за това първо тестване).

Всички публикации , , , 2 Comments

Анализ и резултати от втори кръг за сезон 2012/2013

Написано на 02/15/2013 8:50 pm, от

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

Datecs

DATECS са спонсори на втори кръг на конкурса за сезон 2012/2013

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

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

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

Генерирането на тестовете беше… забавно начинание. При толкова много променливи критерии (размер на поле, брой “водонедорасли”, брой ходове, брой клетки с храна спрямо големината на полето), дори с по 4-5 диапазона от стойности за всяко стигнахме до заключението, че ще са нужни около 700 теста за пълна изчерпателност. Тестовете бяха генерирани, но общото време, което щеше цялото тестване щеше да отнеме, се оказа твърде дълго – тъй като имахме алгоритми, които имаха проблеми с вход-изход (както на миналия кръг), а и беше нужно да верифицираме резултатите в последствие, решихме да съкратим броя тестове.

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

Допълнително, за всеки тестов файл генерирахме по няколко (произволен брой) “следи от форми в играта на живот”, като храна. Тоест, имахме няколко предефинирани известни форми в играта на живот и ги пускахме да се развиват върху полето, като поставяхме клетка с храна навсякъде, където се появяваше жива клетка. Разбира се, слагахме и произволно разпределена храна.

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

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

Оценяването бе извършено по новият алгоритъм за оценяване със скалиране на всеки тест, като тази система ще бъде ползвана и в следващите кръгове – в случая:

  • Всеки тест носеше 10/72 (десет седемдесетивтори) точки
  • Тези точки получаваше алгоритъма с най-висок резултат за съответния тест
  • Останалите получаваха съответната част от тези точки
  • Резултатите за всички тестове се сумираха и точките на алгоритъма с най-висок резултат  бяха скалирани до 10, а останалите получиха съответната част от тези точки

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

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

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

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

Както сме описвали, коректността определя предимно дали дадените изисквания са изпълнени и дали предаденото решение пълно в контекста на задачата. Когато се създава един уебсайт, изисквания можем да наречем mark-up валидност, правилно функциониране при различни резолюции (т.е. без размествания), валидни хиперлинкове и семантично коректен HTML. Пълнотата, тъй като бе широко понятие за тази задача, решихме да оценяване чрез директно съпоставяне на решенията на отделните отбори – тоест, колкото повече смислени елементи един сайт съдържаше и колкото по-добре бяха имплементирани те спрямо останалите сайтове, толкова по-висока “подоценка” за пълнота бе давана за журито. Грубо казано, 1.5 от максималните 3 точки за коректност давахме за валидност и още 1.5 давахме за пълнота и изпълнение.

Ето и по-популярните елементи сред решенията елементи, на базата на които журито оценява Коректност в този кръг:

  • Въведение в задачата/”мисията”
  • “Разкази”/”Истории”/”Измислици” или т.нар “lore” на английски – допълнтиелно тематично съдържание
  • Описание на алгоритмичната част
  • Изследване/анализ на форми от оригиналната Игра на Живот
  • Симулатор

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

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

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

Сайтовете на всички участници си заслужават!

Това е един призив към читателите (включителни и състезатели) – журито определено се забавлява с проверката на приложната част в този кръг. По един или друг начин всеки отбор допринесе за “оцеляването на водонедораслите” извън кръга – при това някои с доста добро чувство за хумор и оригиналност в създаденото. Така че не се чудете дали да разгледате решенията, заслужава си! Всички решенията по традиция ще бъдат качени в публичното хранилище на конкурса – линкове ще намерите по-долу в тази статия.

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

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

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

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

Автор 1 Автор 2 Общо Алгоритъм Приложение
mgochev 17 10 7
pemmpty lazo003 14 8 6
krasi.nikolov ognyan.petkov 11 5 6
pirin isipro 11 5 6
aleks.todorov nader.dabour 10 3 7
Nevencheto AngelVladov 10 0 10
aslv1 erik1001 9 2 7
cocodonchev rusiqt 9 4 5
KOCTEHYPKATA 9 5 4
manchev gercho 9 3 6
paveld3 at.keranov 9 1 8
plamen.hristian hristy93 9 3 6
psotirov 9 3 6
mariq88 d_p_y 8 2 6
mario.stoilov.9 ivailok1 7 4 3
s_mihaylov 7 5 2
kdikov 6 0 6
yonko.tsonev 6 0 6
galingrudov BlackEagle 5 1 4
Ivaylo ognyan.angelov 5 0 5
kiril.ilarionov 5 1 4
mitko_lazarov 5 2 3
PeterParushev silistra 5 5 0
georgi.ivanov 5 4 1
angel.n.stoyanov migrachev 4 4 0
martin.durchov xpxd4 4 0 4
technet 2 2 0
zdravko.beykov 2 2 0
stoyaneft merakses 1 1 0

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

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

Всички публикации, Класиране 2012/2013 4 Comments

Задача #3 за сезон 2012/2013 – големи бомби

Написано на 01/21/2013 12:00 pm, от

Големи бомби

Задача #3 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

В Га-нгнамландия нещата не са розови. И не само защото розовият цвят всъщност не съществува сам по себе си (http://www.youtube.com/watch?v=S9dqJRyk0YM), а и защото там постоянно се водят войни за щяло и нещяло. Или по-конкретно, водят се, защото едно щяло нещо дето друго нещяло да ще да му го даде – стандартни неща. Сега тече поредният конфликт и вие сте призовани да помогнете с невероятните си лидерски умения – или пък с невероятните си умения в програмирането (а защо не и с двете).

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

Основната единица, която фермерите ползват за нападение, е гуцито с гърмелка (GG), а основният пазач е оборудваното пиле (OP). Пилетата и гуцитата могат да се позиционират на определени координати на полето и да се нападат. Това се постига с малко обучения (в които не се нараняват никакви животни) и фураж, който не струва скъпо. В една стандартна битка, пилетата пазят позициите, на които са разпределени, а групи от гуцита нападат солните мини, като се опитват да ги взривят. Тъй като гуцитата могат да копаят тунели под земята, те могат да се озоват на произволна позиция в бойното поле, така че защитаващите фермери обикновено поставят пилетата в близост до мините. Когато гуцитата и пилетата попаднат в битка, гуцитата правят камикадзе атака срещу пилетата, като ако успеят едновременно пилетата и гуцитата биват унищожени, а ако пилетата успеят да унищожат гуцитата преди завършването на камикадзе атаката, пилетата оцеляват и продължават да пазят позициите си. Най-силното оръжие на фермерите е “голямата бомба“. Тя представлява… голяма бомба, която може да бъде зареждана с домашна ракия, за да ? бъде увеличена мощността. Бомбата може да бъде хвърлена навсякъде по полето, унищожавайки всичко в радиуса на взрива си.

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

Описание на битките, единиците, защитаващите и атакуващите

Единица ще наричаме всеки обект в битката – гуци с гърмелка (GG), оборудвано пиле (OP), солна мина, бомба. Всяка битка се провежда на поле, върху което защитникът е наредил своите мини и защитаващи единици, с цел да предпази възможно най-много мини и единици. Полето можем да разглеждаме като първи квадрант на двумерна Евклидова координатна система, в която всички координати са неотрицателни цели числа (но разстоянията не са цели числа). Атакуващият, от своя страна, праща свои единици на определени координати, с цел да унищожи единиците и мините на защитаващия се. Това става, като атакуващият дава команди, които да бъдат изпълнявани. Всяка команда се изпълнява напълно, преди да бъде изпълнена следващата.

Цени на единици

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

Цените на единиците са както следва:

  • гуци с гърмелка (GG): 7 пари
  • оборудвано пиле (OP): 1 пари
  • солна мина: 6 пари
  • бомба с радиус нула (т.е. унищожава само единиците на съответните координати): 10 пари
    • увеличаване на радиуса с 1: +10 пари
    • увеличаване на радиуса с 2: +20 пари
    • няма ограничение за увеличаване на радиуса, освен ресура пари, които атакуващия има

Парите, с които атакуващия и защитаващия разполагат са както следва:

атакуващ: 200 пари

защитаващ: 200 пари

Забележка: валутната единица не е от значение в случая, затова ще ползваме 10 пари, 5 пари, 20 пари и т.н.

Придвижване и позициониране

Атакуващият може в даден момент да прати определен брой гуцита на определена позиция на полето. Когато това стане, гуцитата вече се считат за “използвани” и не могат да бъдат ползвани отново, а ресурсите за тях са изразходени. Съответно, смислено за атакуващия е да праща гуцита само на координати, на които те ще проведат битка с единици на защитаващия се. Гуцитата винаги се движат в група от 1 или повече.

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

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

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

Битки

Всяка бойна единица (GG и OP) има обсег (радиус в който може да напада други единици). Битка се провежда, когато група единици на атакуващия (той може да има точно една група единици на полето в даден момент) е в обсега на поне една група единици на защитаващия се, или обратно.

Обсега е максималното евклидово разстояние, на което една единица може да нанесе поражения. Разстоянието между 2 точки се изчислява по формулата Dist = sqrt((x1 – x2)^2 + (y1 – y2)^2), където x1 и y1 са координатите на едната точка, x2 и y2 – на другата, ^2 означава втора степен, а sqrt означава корен квадратен – тоест това е стандартната формула за разстояние между 2 точки в Евклидовата равнина.

Обсега на единиците е както следва:

  • гуци с гърмелка: 1.5
  • оборудвано пиле: 2

Всяка единица може да атакува само единиците, които са в обсега ?. Така е възможно пилета да атакуват гуцита, без гуцитата да могат да отвърнат.

Когато определена единица влезе в обсега на гуцитата, те се подготвят да се взривят, като ако успеят, взривяват всички единици в обсега си. Това, дали ще успеят зависи от броя пилета, в чиито обсег са гуцитата:

  • Ако група гуцита с брой C е в обсега на точно C*2 или по-малко на брой пилета, то гуцитата ще успеят да се взривят и унищожат всички пилета в своя обсег, които е 1.5 (това не е задължително да са всички C*2 пилета, тъй като пилешкия обсег е по-голями някой от тези пилета може да са на разстояние по-голямо от 1.5).
    • В този случай всички солни мини, които са в обсега на гуцитата, също ще бъдат унищожени.
  • Ако група гуцита с брой C е в обсега на точно C*2+1 или повече на брой пилета, то гуцитата ще бъдат унищожени преди да успеят да се взривят и нито едно пиле (или мина) няма да пострада.

Големите бомби

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

Голямата бомба може да има радиус (обсег) нула, което означава, че ще унищожи само единицата, която е на същите координати, на които е пусната бомбата. Също така, радиуса на бомбата може да бъде по-голям, в който случай всички единици на разстояние съответния радиус ще бъдат унищожени, но всяко увеличение струва пари (виж по-горе в “Цени на единици”).

Aтакуващият може да използва най-много 1 бомба за цялото сражение.

Забележка: не е възможно бомбата да унищожи единици (гуцита с гърмелки) на атакуващия.

Бойното поле

Както вече казахме, бойното поле се състои от точките с целочислени координати в първи квадрант на двумерна Евклидова координатна система. Това поле обаче не заема целия квадрант, тъй като той е безкраен, а е ограничено до 100 по оста X и 100 по оста Y. Това означава, че най-отдалечените от началото на бойното поле (0, 0) координати, на които е възможно да има единици са (100, 100).

Алгоритмична задача – стратегия за атакуващия и разположение за защитаващия

В този кръг ще разделим алгоритмичната част на 2 подзадачи – първата е стандартното писане на алгоритъм, които действа от името на атакуващия, като постига възможно най-добри резултати при дадено “бойно поле” – тоест при дадени позиции на пилета и мини. Втората част ще даде възможност на отборите да опишат своя “база” с разположение на солни мини и оборудвани пилета – по същество, състезателите ще могат да напишат свой тест, който при тестването ще бъде предаден на всички алгоритми (включително алгоритъма на създателите си).

Задача за алгоритъм (изпълнимия файл) – стратегия за атакуващия

Напишете атакуващ алгоритъм, който при описано разположение на единици на защитаващия се и тяхната бройка, нанася възможно най-високи щети, като ползва ресурсът от 200 пари (не задължително всичките) за да създава единици и да ги разполага на позиции за провеждане на битката. Щетите се измерват, като сумата на цената на всички унищожени от атакуващия единици. Ако на края на атаката защитаващият е останал без солни мини, то сумата на щетите се удвоява.

Задача за генериране на тест (текстовия файл) – разположение на защитата

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

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

Предаването на теста ще става чрез поставянето му в папката algorithm, наред с изпълнимия файл за алгоритмичната задача. Файлът трябва да бъде именован както е името на потребителя, който го е изпратил (например ако потребителят е george.s.georgiev, то файлът трябва да носи името george.s.georgiev.txt).

При тестването, входните данни от теста ще бъдат подадени на всеки един алгоритъм, включително и на алгоритъма на автора.

Входни данни

Входните данни се въвеждат от стандартния вход (конзолата).

Входните данни се състоят от команди за поставяне на единици, които описват единиците в полето на защитаващия се. Командите са два вида:

  • Поставяне на група оборудвани пилета:
    • Формат: chickens брой координатаX координатаY
    • Пример: chickens 5 10 11 ще постави група от 5 пилета на координати (10, 11)
  • Поставяне на солна мина:
    • Формат: mine координатаX координатаY
    • Пример: mine 15 4 ще постави солна мина на координати (15, 4)

Не е възможно 2 команди във входните данни да имат съвпадащи координати, т.е. да се постави мина върху мина, мина върху пилета, пилета върху мина или два пъти на едни и същи позиции да се поставят пилета.

На първия ред от стандартния вход се въвежда числото N – броят команди, които ще опишат поставянето на единиците на защитаващия се.

На всеки от следващите N реда ще бъде въвеждана по една команда в описания формат.

Входните данни ще бъдат винаги валидни и в описания формат.

Изходни данни

Изходните данни се извеждат на стандартния изход (конзолата).

Изходните данни се състоят от команди, които описват единиците, с които атакуващия атакува единиците на защитаващия се. Командите са два вида:

  • Пращане на група гуцита с гърмелки:
    • Формат: pigs брой координатиX координатиY
    • Пример: pigs 7 10 11 ще прати група от 7 гуцита да се взривят на координати (10, 11)
  • Пращане на голяма бомба:
    • Формат: bomb радиус координатиX координатиY
    • Пример: bomb 2 13 4 ще взриви бомба с радиус 2 на координати (13, 4)

Програмата трябва да изпечата толкова редове, колкото команди възнамерява да даде, като всеки ред трябва да съдържа правилно форматирана команда. Всяка команда, която не е форматирана, или която превишава ресурса пари на атакуващия, няма да бъде отчитана.

Ограничения

  • Размерите на бойното поле са 100 по X и 100 по Y (включително).
  • Сборът на цената на единиците на защитника е не повече от 200 (това трябва да бъде спазено и в тестовете на участниците).
  • Сборът на цената на единиците на атакуващия трябва да бъде не повече от 200
  • Не може 2 групи единици от една и съща страна да се разполагат на една и съща позиция. Възможно е обаче атакуващия да постави група единици на едни и същи координати с група единици на защитаващия.
  • При проверката за всички сметки свързани с координати и разстояния ще бъде ползван стандартен 64-битов тип данни с плаваща запетая (известен като double в по-известните програмни езици), като стойностите ще бъдат закръгляни до 3-тата цифра след десетичната запетая.
  • Програмата трябва да завършва своята работа за най-много 1 секунда. След изтичане на времето програмата ще бъде спряна автоматично.

Примери

С тези примери ще онагледим правилно форматиран вход и изход. Примерите имат за цел само да покажат правилния формат, а не да дават оптимално решение на задачата.

Примерен вход Примерен изход
4
chickens 5 1 2
chickens 6 3 2
mine 2 2
chickens 4 3 3		 pigs 7 3 4
pigs 4 2 2
pigs 3 1 3
Първа, втора и трета команда на атакуващия + резултат

Първа, втора и трета команда на атакуващия + резултат

Обяснение:

На горните картинки кафявата точка е група гуцита, червените точки са групи пилета, а синята точка е солна мина. При първата команда, атакуващия праща 7 гуцита на координати (3, 4). Те са в обсега на 2 групи пилета – (3, 2) и (3, 3) – общо 6 + 4 = 10 пилета. От своя страна, горната група пилета са в обсега на гуцитата, но долната не е (тъй като е на растояние 2). Тъй като общия брой пилета, които са в битка с гуцитата, е по-малък от броя гуцита умножен по две, гуцитата успяват да се взривят и да унищожат пилетата на координати (3, 3). При втората команда са пратени гуцита точно на координатите на мината, но те са в обсега на 2 групи пилета, чиято бройка надвишава умножената по две бройка на гуцитата и съответно гуцитата са унищожени без да се взривят. На третата команда са пратени 3 гуцита на координати (1, 3), които са в обсега на 1 група от 5 пилета. Тези пилета не са достатъчни да спрат гуцитата от взривяване и биват унищожени. В допълнение, солната мина на координати (2,2) е достатъчно близко до гуцитата, за да бъде в техния обсег и също бива унищожена. Накрая остава 1 група от 6 пилета на координати (3, 2).

Общата сума на цените всички унищожени единици на защитника за отделните команди е: 4 + 0 + (5 + 6) = 15. Тъй като в края на атаката защитникът няма оставащи солни мини, сумата се удвоява и става 30 – съответно резултатът на атакуващия алгоритъм за този тест е 30.

 

Примерен вход Примерен изход
8
mine 2 2
mine 3 2
chickens 30 2 1
chickens 30 3 1
chickens 34 1 2
chickens 34 4 2
chickens 30 2 3
chickens 30 3 3		 bomb 2 3 2
Обяснение:Защитникът е изразходил всичките пари като е скупчил голямо количество пилета, защитаващи 2 солни мини. Атакуващия пуска бомба с радиус 2 върху едната солна мина, като този радуис е достатъчен, при тази подредба на единиците на защитника, да унищожи всички единици. Общата цена на унищожените единици е 200 и поради липсата на оцелели мини, тази сума се удвоява и става 400 – съответно резултатът на атакуващия алгоритъм за този тест е 400.

Приложна задача – имплементация на “Големи бомби”

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

Обобщено, приложението трябва да поддържа:

  • Въвеждане на единиците на защитаващия се
  • Въвеждане на командите на атакуващия
  • Визуализация на битката
  • Визуализация на резултати
  • Възможност за запазване на резултати и преглеждане на таблица с резултати на играчи – т.нар. scoreboard, hall/wall of fame и т.н.

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

Приложението може да бъде уеб, десктоп, както и WinRT-базирано. Единственото ограничение е да бъде изпълнимо под Windows 7 или Windows 8 и да бъде предоставен лесен начин за стартирането му в папката application.

Критерии за оценяване

Оценяване на алгоритмичната част

При оценяването ще бъдат генерирани тестове от журито, с различни подредби на единици на защитаващия се играч. Освен това, ще бъдат ползвани коректните тестове пратени от участниците. Тежестта ще бъде 50 на 50, тоест тестовете на журито ще носят общо толкова точки, колкото общо тестовете предадени от участниците.

  • Данните от всеки тест на журито, както и данните от всеки тест на участниците, ще бъдат подадени на всеки един предаден алгоритъм.
  • За всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест).
  • Например, ако за задачата има 10 теста от които 5 са на състезатели и 5 на журито, то всеки ще носи по 1 точка.
    • Ако на първото поле най-добре представилият се алгоритъмът G има резултат 30
    • алгоритъмът M има резултат 15,
    • а алгоритъмът L има резултат 10, то
    • в крайна сметка точките за този тест са:
      • G: 1 точка
      • M: 0.5 точки
      • L: 0.33 точки
  • По същия начин се оценяват всички тестове, точките се сумират и след това се закръглят до цяло число
  • Максимални точки в крайното класиране за алгоритмичната част: 10

Оценяване на приложната част

Оценяването на приложната задача ще се извърши по-следните критерии:

  • Коректност (доколко са имплементирани посочените функционалности) – 2 точки
  • Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 2 точки
  • Ползваемост (доколко е удобна и интуитивна е работата с уебсайта) – 2 точки
  • UI дизайн (доколко е приятен и удобен уебсайтът) – 2 точки
  • Оригинални функции и решения, които да впечатлят журито – 2 точки
  • Максимални точки в крайното класиране за приложната част: 10

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например C#, PHP, C, C++, Delphi, Python, WPF, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows 7 среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълен сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).

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

Характеристики на системата, върху която ще бъде проведено тестването

  • Intel® Xeon® CPU E31225 @ 3.10 GHz
  • 16 GB RAM
  • 128 MB Video Memory (dedicated) Intel® HD Graphics video card
  • 232 GB HDD
  • Microsoft Windows 7 64-bit OS
    • за предалите приложна част на WinRT, тестването на приложната част ще бъде извършено на система с минимални характеристики OS Windows 8 64-bit, 6 GB RAM, Intel i7-720QM, 1GB ATI Mobility Radeon HD 4250.

Краен срок

Краен срок за предаване на решения: 25 февруари 2013 г, 23:59:59 часа.

Решенията се предават в студентската система на Академията на Телерик, на адрес http://telerikacademy.com/Courses/Courses/Details/13 според инструкциите, описани в раздела “Качи решение” на официалния сайт на състезанието.

Всички публикации, Задачи 2012/2013 , , , , , , , , , , , , 69 Comments

Второ предварително тестване за втори кръг на сезон 2012/2013

Написано на 01/19/2013 11:04 pm, от

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

Новооткрити проблеми в някои решения

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

  • При някои тестове видяхме изходни данни, които не следват формата на описаните – един забележим проблем е наличието на интервали между символите в изхода – такива не трябва да има.
  • Някои състезатели изглежда неволно са оставили отпечатването на допълнителна информация и съобщения. Напомняме, че при оценяването, това ще бъде считано за грешен формат на изхода
  • Unhandled Exception – някои решения хвърлят exception по време на работата си, добре е състезателите да погледнат за тези ситуации

Някои от старите проблеми, като ползвани на неналични dll-и все още присъстват в някои решения.

Отбори, резултати и логове

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

Отбори

Автор 1 Автор 2
aleks.todorov nader.dabour
paveld3 at.keranov
mariq88 d_p_y
kiril.ilarionov
krasi.nikolov ognyan.petkov
mgochev
mitko_lazarov
Nevencheto AngelVladov
pemmpty lazo003
PeterParushev silistra
pirin isipro
yonko.tsonev

Лог на извличането на отборите

Предадено от Местоположение на “authors.txt” файлът Автор 1 Автор 2
aleks.todorov aleks.todorov\H20nongrowns\authors.txt aleks.todorov nader.dabour
at.keranov at.keranov\authors.txt paveld3 at.keranov
d_p_y d_p_y\authors.txt mariq88 d_p_y
georgi.ivanov Could not find “authors.txt”
kiril.ilarionov kiril.ilarionov\authors.txt kiril.ilarionov
krasi.nikolov krasi.nikolov\authors.txt krasi.nikolov ognyan.petkov
mario.stoilov.9 Error parsing “authors.txt” file:
Too many lines in file – max 2
martin.durchov Error parsing “authors.txt” file:
Too many lines in file – max 2
mgochev mgochev\authors.txt mgochev
mitko_lazarov mitko_lazarov\authors.txt mitko_lazarov
Nevencheto Nevencheto\mySubmit\authors.txt Nevencheto AngelVladov
pemmpty pemmpty\final\authors.txt pemmpty lazo003
PeterParushev PeterParushev\authors.txt PeterParushev silistra
pirin pirin\authors.txt pirin isipro
plamen.hristian Error parsing “authors.txt” file:
Could not match any
username in “authors.txt”
with user that submitted
yonko.tsonev yonko.tsonev\authors.txt yonko.tsonev

Резултати на алгоритмите

Предадено от test.000.001.in.txt test.000.002.in.txt
aleks.todorov 4 7
at.keranov 4 8
d_p_y 7 14
georgi.ivanov 0 0
kiril.ilarionov 0 0
krasi.nikolov 0 0
mgochev 8 8
mitko_lazarov 0 0
pemmpty 0 0
PeterParushev 8 14
pirin 4 5
plamen.hristian 8 7
yonko.tsonev 0 0

Лог на извличането на алгоритмите

Предадено от Местоположение на “algorithm” директорията Име на .exe файла на алгоритъма
aleks.todorov \H20nongrowns\algorithm \H20nongrowns\algorithm\Vodonedorasli-Algo.exe
at.keranov \algorithm \algorithm\Algae.exe
d_p_y \algorithm \algorithm\Algorithm.exe
georgi.ivanov \NonGrowingAlgae\algorithm \NonGrowingAlgae\algorithm\NonAlgae.exe
kiril.ilarionov \algorithm \algorithm\algorithm.exe
krasi.nikolov \algorithm \algorithm\algorithm.exe
mario.stoilov.9 Could not find “algorithm” folder
martin.durchov Could not find “algorithm” folder
mgochev \algorithm \algorithm\Algorithm.exe
mitko_lazarov \algorithm \algorithm\Game_of_Life.exe
Nevencheto \mySubmit\algorithm No files in “algorithm” folder
pemmpty \final\Algorithm \final\Algorithm\GameOfLife.exe
PeterParushev \algorithm \algorithm\vodonedorasli.exe
pirin \algorithm \algorithm\VodoNedorasliAlgo.exe
plamen.hristian \Vodonedorasli\algorithm \Vodonedorasli\algorithm\Algorithm.exe
yonko.tsonev \algorithm \algorithm\Vodonerasli.exe

Както и при тестването в петък, всички файлове от тестването, както и двата тестови файла, можете да намерите в публичното хранилище на конкурса, този път на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/season-2012-2013/round-2/pretest-day-2/.

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

Крайният срок за предаване на решения за този кръг е днес, неделя, 20 януари 2013, 23:59:59 часа.

Всички публикации , , , , , , , , , Comments Off on Второ предварително тестване за втори кръг на сезон 2012/2013

Първо предварително тестване за втори кръг на сезон 2012/2013

Написано на 01/18/2013 11:50 pm, от

Завършихме процеса на първото предварително тестване за този кръг. С това тестване, както по-рано споменахме, целяхме да открием проблеми във формата на предадените решения и проблеми при изпълнението на предадените алгоритми. В тестването бе проверено наличието на правилно форматиран authors.txt файл, папка algorithm и наличието в нея на изпълним файл, върху който бяха изпълнени примерните тестове от условието на задачата.

Открити проблеми

Около 1/3 от участвалите в предварителното тестване имаха някакви проблеми в предаденото от тях решение. Ето някои от по-особените проблеми:

  • Правописна грешка в името на authors.txt файла – тъй като обработката на предадените файлове става автоматично, всякакви грешки в имената на файловете водят до ненамирането им
  • Правописна грешка в името на algorithm директорията – най-често липса на буквата “h”
  • Неправилен формат на authors.txt – някои автори форматират authors.txt файла си по разбираем, но неправилен начин спрямо изискванията за форматиране (описани на страницата Качи Решение и онагледени с този пример) – това пречи на автоматичната обработка на файла. Файлът трябва да съдържа точно два реда, като на всеки ред, разделени с интервали са изброени: потребителско име, e-mail и студентски номер от профила в http://telerikacademy.com
    • съавтори без профил в посочения сайт могат да изписват “измислено” потребителско име, като то единствено ще бъде ползвано в класирането (измисленото потребителско име не трябва да съдържа интервали)
  • Shortcut файл вместо изпълним файл – не е правилно поставянето на “пряк път” към изпълним файл. Според изискванията за предаване, задължително е наличието на изпълним (.exe) файл в директорията algorithm, тъй като това е единственият начин той да бъде намерен и стартиран от проверяващата система
  • Липса на ползвани от изпълнимия файл ресурси в директорията algorithm – някои автори пропускат да сложат dll файлове или други ресурси които ползват. Така алгоритъмът им не успява да се стартира успешно. Всички ресурси, които алгоритъмът ползва трябва да бъдат в директорията algorithm – не в директория application, или някъде другаде из предадените файлове, или на машината на предаващия, която е недостъпна за журито.

Повечето от тези проблеми са незначителни, но пречат на автоматичната проверка. Приканваме авторите да коригират съответните проблеми, за да бъде проверен трудът им коректно, без нужда от корекции от журито.

Отбори взели участие в тестването

В таблицата са изписани потребителксите имена на авторите в отборите, взели участие в първото предварително тестване. Тези “отбори” са извлечени автоматично от authors.txt файлът, стига той да е бил коректно предаден. Ако вашето потребителско име или вашият съотборник липсват в тази таблица, или сте некоректно разпределени, а сте предали решението си до 23:15 на 18 януари 2013, моля проверете дали authors.txt файлът, който сте предали съответства на примера и изискванията посочени в “Качи решение“.

Автор 1 Автор 2
aleks.todorov nader.dabour
paveld3 at.keranov
kiril.ilarionov
krasi.nikolov ognyan.petkov
mgochev
Nevencheto AngelVladov
pemmpty lazo003
yonko.tsonev

Нескалирани резултати на предадените алгоритми по име на предаващия

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

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

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

Редакция: таблицата е обновена в 18:14 на 19.01.2013 (обосновка по-долу)

Потребителско име на предалия Първи примерен тест Втори примерен тест
aleks.todorov 4 7
at.keranov 4 8
georgi.ivanov 0 0
kiril.ilarionov 7 13
krasi.nikolov 0 8
mgochev 8 8
pemmpty 0 0
PeterParushev 8 14
pirin 4 5
plamen.hristian 8 7
yonko.tsonev 0 0

Допълнителна информация и инструкции

Призоваваме всички участници, които не се намират в таблицата на отборите, или не са очаквали посочените в последната таблица резултати, да прегледат добре формата на решенията, които са предали. За допълнителна информация, участниците могат да прегледат log-файловете в публичното хранилище на конкурса:

Всички тези файлове, както и други, могат да бъдат намерени в тази директория на хранилището.

Предстоящото (второ) предварително тестване

Следващото (второ) предварително тестване ще бъде проведено в събота (днес), 19 януари 2013, като в него ще участват всички отбори, предали решенията си до 23:00 часа. Резултатите ще бъдат публикувани в статия подобна на тази между 00:00 и 03:00 часа. Ако журито установи, че няма да успее да публикува резултатите в това време, това ще бъде обявено в тази публикация, непосредствено след този текст.

Редакция: Открихме малка грешка в проверяващата система и обновихме резултатите от предварителното тестване (системата включваше в резултата живите клетки в началото, а не в края). Файловете с резултати и логове също са обновени

Всички публикации 2 Comments

Промени в оценяването на алгоритмичната част, срока и предварително тестване

Написано на 01/08/2013 12:30 pm, от

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

Промяна в срока за предаване

Удължаваме срока за предаване на решенията за задачата от втори кръг до 20 януари, неделя (преди това беше 17 януари).

Промяна в оценяването на алгоритмичната част

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

Отсега нататък (освен ако не е изрично споменат0), всички тестове ще носят еднакъв брой точки и сумата на точките от всички тестове ще е 10. Тоест, поле 10 на 10 ще носи същите точки като поле 1000 на 1000. Това ще стане, като за всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест, а не за сбора от всички тестове като преди). Например:

  • ако за задачата има 10 теста, то всеки ще носи по 1 точка.
  • Ако на първото поле най-добре представилият се алгоритъмът G има резултат 30
  • алгоритъмът M има резултат 15,
  • а алгоритъмът L има резултат 10, то
  • в крайна сметка точките за този тест са:
    • G: 1 точка
    • M: 0.5 точки
    • L: 0.33 точки
  • По същия начин се оценяват всички останали тестове, точките се сумират и след това се закръглят до цяло число

И сега едно пояснение. Тъй като с това оценяване малките и големи полета получават еднакви точки, а това не е коректно спрямо алгоритмите, които работят добре и за големи полета, ще има количествена разлика между тестовете с малки полета и тези с големи полета. Тестовете с малки полета ще бъдат по-малко от тестовете с големи полета (съотношението ще е около 30/70 или 40/60 в полза на тестовете с големи полета, но това е по-скоро пример отколкото нещо конкретно).

Забележка: тук “малки” и “големи” полета е ползвано заради условията на задачите до този момент. По-нататък същото ще важи съответно за “ниска” и “висока” сложност – за първите два кръга сложността е правопропорционална на големината на полето, но това не винаги ще е така.

Предварително тестване на алгоритмите

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

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

Предварителното тестване ще се проведе в петъка и съботата преди крайния срок (т.е. на датите 18 и 19 януари) и ще протече по следния начин:

  • За да участват в първото предварителното тестване, всички състезатели предават решения до 23:00 часа в петък, като само последно предадените решения от всеки отбор се оценяват
    • Забележка: предадените решения не е нужно да са напълно функционални – върху тях ще бъдат изпълнени само примерните тестове дадени в условието и тези резултати няма да се зачитат в реалното оценяване
  • Журито стартира автоматизирана проверка на подредбата на решенията, извличане на автори и отбори и изпълнение на примерните тестове
  • Журито публикува информация в 24:00 часа, петък срещу събота, (във формата на логове и таблици с отбори) относно коректността на решенията. Възможно е известно закъснение в зависимост от броя на некоректно предадените решения
  • Състезателите коригират решенията си и ги предават до 23:00 в събота, за да участват във второ предварително тестване, като процесът се повтаря
    • Забележка: състезателите могат да участват във второто предварително тестване, дори без да са участвали в първото
  • Трето предварително тестване няма да се провежда, и крайният срок за предаване на решения за оценка е неделя, 20 януари, 23:59:59 часа.

С тези мерки се надяваме да избегнем забавяния при тестването, корекции от журито върху алгоритмите и налагане на наказателни точки. Моля обърнете внимание, че правилното форматиране на предаденото решение (папка algorithm, папка application и файл authors.txt) е важно, тъй като в следващите кръгове извличането на алгоритмите за тестване и на отборите ще бъде автоматизирано).

Участието в предварителното тестване е по желание на участниците, но журито силно го препоръчва.

Всички публикации , , , , , 3 Comments

Наградихме шампионите от първи кръг за сезон 2012/2013

Написано на 01/06/2013 3:43 pm, от

Както обещахме, в петък, 13:30 наградихме отборите на първите 3 места в класирането за първи кръг. Всеки отбор имаше представител, който получи наградите за него и неговия съотборник, а ние заснехме връчването на наградите.

Както разказахме в анализа на резултатите за първи кръг, алгоритмите на първите в класирането получиха равни точки след закръглянето, така че подредбата на първите 3 места бе определена от това колко добре отборите се бяха справили с приложната част един спрямо друг.

В следващите редове ще кажем по две думи за всяко от местата

Трето място

“Бронза” взе отборът на Надер Дабур и Александър Тодоров. Алгоритъмът им се представи доста добре, а приложната част на отбора изпълваше всички поставени изисквания, като наред с това бе удобен за ползване. Видимо съотборниците се бяха постарали и съвсем малко ги раздели от първо и второ място, но трето място в такъв конкурс определено е добро постижение.

Надер Дабур получава сертификат

От двамата съотборници, Надер имаше възможност да присъства на награждаването и на него връчихме всички награди за трето място – сертификати за постижението от Академията на Телерик и слушалки предоставени от PC Magazine.

Второ място

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

Михаил Гочев получава сертификат

Михаил получи сертификат и тениска, както и LG Bluetooth – награда от PC Magazine за второ място.

Михаил Гочев получава награда от PC Magazine

Първо място

Атанас Керанов и Павел Колев взеха първото място. Както и при другите два отбора, техният алгоритъм се представи доста силно, но това което наистина ги отличи бе приложната част. А тя беше нещо доста сериозно – уеб приложение с 3D визуализация в реално време (ползваща WebGL) , която предоставяше и всичко изисквано. Несъмнено трудът за създаване на приложение, което работи добре не е за подценяване, но това приложение надграждаше и предизвикваше интерес повече от тези на останалите участници и с това създателите му заслужиха първото място.

Павел Колев получава сертификат

С нас беше Павел, който получи наградите за своя отбор – обичайните сертификати от Академията, както и голямата награда за първо място от PC Magazine – дънна платка Z77K Sapphire.

Павел Колев получава награда от PC Magazine

Финални думи

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

Наградени 1 кръг 2012/2013

Всички публикации , , , , , , , 1 Comment

Анализ и резултати от първи кръг за сезон 2012/2013

Написано на 12/21/2012 1:30 pm, от

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

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

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

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

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

  • Зададени са няколко множества от диапазони от стойности за граници на генерираните данни
    • 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/.

Всички публикации, Класиране 2012/2013 17 Comments

Задача #2 за сезон 2012/2013 – водонедорасли

Написано на 12/17/2012 3:05 pm, от

Водонедорасли
Задача #2 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

Datecs

Datecs са спонсори на втори кръг на конкурса за 2012/2013 година

Годината е 2115 (краят на света никога не идва навреме). Учените от Националната Астробиологическа Институция за Широкоспектърно-Космическа Валидация на Организми (НАИШ-КВО) са открили нещо, което наричат “интересна планета”. Интересното на планетата е, че в атмосферата ? има газове, които типично се произвеждат от живи организми. НАИШ-КВО решават – да пратят екип от астронавти, които да посетят планетата и да изследват ситуацията там – независимо какво ще струва това.

Когато астронавтите достигат планетата след достатъчно дълго пътуване, за да изгледат How I Met Your Mother, Дързост и Красота, както и израстването на едно цвете (последното не е филм) астронавтите слизат от Галактическия Обект за Транспорт на други Обекти (GOTO) и започват да изследват планетата. Откритията показват, че няма достатъчно висши форми на живот, за да има с кого да си пият Бързия Интоксикант за Рехабилитация и Активизация (БИРА), но за сметка на това големи области от планетата са покрити от водоподобна слуз, в която по особено интересен начин живеят малки организми. Тези организми изглежда имат доста силен потенциал за развитие. Още повече, изследванията показват, че тези организми, докато са активни, могат да бъдат ползвани за произвеждане на Живо Извлечение с Вискозитет Алфа от Бързия Интоксикант за Рехабилитация и Активизация (ЖИВАБИРА). За съжаление организмите са твърде малко към този етап. Затова астронавтите ги нарекли “водонедорасли”. Със сегашното им темпо на развитие, астронавтите няма да доживеят да създават ЖИВАБИРА от водонедорасли.

След дълги изследвания, астронавтите открили, че начина по който организмите се развиват може почти да бъде сведен до един известен, но забравен математически модел, наречен “Играта на живота”. Следователно, астронавтите, с правилната намеса, могат да ускорят значително развитието на водонедораслите. Идеята е за всяка “локва” (така астронавтите наричат областите с водоподобна слуз) да се съберат водонедораслите и да се преподредят, така че да се развиват по-бързо. Тъй като астронавтите се затрудняват да смятат всеки път подходящата подредба (гледайте вие толкова дълго сериали, да ви видим), ви молят да им помогнете, като напишете софтуер, който измисля такива подредби, че след определено време да може да се извлече максимална полза от една локва. Има ли желаещи?

Описание на “Водонедораслите” и “Играта на живота”

Местата, в които водонедораслите живеят, ще наричаме “локви”. Съществената част от всяка локва е разграфена от астронавтите като квадратна решетка, като всяка клетка от тази решетка може да съдържа или точно едно водонедорасло (такава клетка наричаме жива), или да бъде празна (такава клетка наричаме мъртва), или да съдържа храна (водонедораслите фотосинтезират, но имат способности и да изяждат определени частици). Оказва се, че развитието на водонедораслите може да се моделира математически чрез известния клетъчен автомат “Играта на живота”.

“Играта на живота”

Това не е игра в традиционния смисъл. Да си представим едно квадратно поле, което се състои от малки квадратни клетки, каквито са нашите  “решетки” на локвите. Всяка клетка може да бъде жива или нежива (мъртва). Всяка клетка има ред и колона (координати), на които се намира в решетката. Всяка клетка също така има и съседи, които са най-много 8 на брой. Ако редът и колоната за една клетка означим с R и C съответно, то съседите на тази клетка са: (R-1, C-1), (R-1, C), (R-1, C+1), (R, C-1), (R, C+1), (R+1, C-1), (R+1, C), (R+1, C+1) – стига, разбира се, някоя от изброените да не е извън решетката. Така клетките, които са в някой от ъглите на решетката имат 3 съседа, а клетките, които са в край на решетката, без да са в ъгъл, имат 5 съседа.

Играта на живота се “играе” на ходове, които астронавтите ще наричат единици време. За всяка клетка, в процеса на преминаване в следващата единица време (следващия ход), могат да се случат следните неща:

  • Ако клетката е “жива”
    • И има 2 или 3 “живи” съседа в текущата единица време, тя остава “жива” в следващата единица време (ход)
    • В противен случай клетката ще бъде “мъртва” в следващата единица време (ход)
  • Ако клетката е “мъртва”
    • И има точно 3 “живи” съседа в текущата единица време, тя ще стане “жива” в следващата единица време (ход)
    • В противен случай клетката ще остане “мъртва” в следващата единица време (ход)

Играта на живота е известен клетъчен автомат, за който астронавтите знаят и са разучавали в Интернет (вж. статията по темата в Wikipedia).

Правилата важат по същия начин за водонедораслите, с уговорката че ако имаме клетка с водонедорасло, то тя е жива, а ако водонедораслото умре, клетката става празна/мъртва (т.е. тези термини ще бъдат ползвани като синоними по-нататък).

Храната

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

Качество на локва

Астронавтите искат да направят възможно най-добро развитие на водонедораслите за определено време. Затова те са измислили начин да оценяват определена “локва” за това колко добро е поколението в нея в произволен момент от времето. С две думи, качеството на локвата в определен момент от време е сбора на всички клетки съдържащи живи водонедорасли с броя клетки храна, които са били изядени, при условие че броят на живите клетки в този момент е различен от нула. Например ако имаме в определен момент от време (определен ход) 10 живи клетки и до този момент 3 клетки с храна са били изядени (независимо в продължение на колко хода), то качеството на поколението в локвата е 13 в този определен момент. Важно е да се отбележи, че ако в определен момент от време в локвата няма нито една жива клетка, то тогава качеството на поколението в локвата става нула (като няма поколение, няма качество). Например ако началната подредба е направена, изядени са след определен брой ходове 5 клетки храна, и в момента на премерване се окаже, че няма нито една жива клетка, качеството не е 0+5=5, а е 0, поради липсата на живи клетки.

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

Алгоритмична задача – генератор на начална подредба на водонедорасли

Преди генерирането на началната подредба решетката, на която и да е локва се състои от празни клетки и клетки с храна (но е възможно и да няма клетки с храна).

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

Генераторът трябва да опише решетката, която се получава, когато направи първоначалната подредба на водонедораслите – тоест да опише решетката с всичките ? празни клетки, живи клетки и клетки с храна.

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

Входни данни

Входните данни се въвеждат от стандартния вход (конзолата).

На първия ред от стандартния вход се въвежда цялото число T – единиците време, след които ще бъде извършено измерването. Например ако T е 1, ще мине 1 единица време, ще се изчислят новите живи, мъртви и изядени клетки (ако има такива) и ще бъде направена оценката.

На втория ред се въвежда цялото число V – броят водонедорасли, които трябва да бъдат поставени.

На третия ред се въвежда цялото число N – размерът на квадратната решетка (броят редове и колони).

На всеки един от следващите N реда се въвеждат по N символа. Символите биват два вида: нули (‘0’) и латинскa буквa F (‘F’), като съответно нулите означават празна клетка, а буквите F означават храна. Тези символи описват всяка една клетка от всеки един ред в решетката – съответно първия символ на първия ред описва дали първата клетка на първия ред е празна или съдържа храна, втория символ описва дали втората клетка на първия ред е празна или съдържа храна и т.н.

Входните данни ще бъдат винаги валидни и в описания формат.

Изходни данни

На стандартния изход трябва да бъдат отпечатани точно N на брой реда с по N на брой символа – като всеки символ описва съответната клетка от съответния ред на решетката в началната подредба, която алгоритъмът е избрал.

Символите биват 3 вида: нула (‘0’), латинска буква F (‘F’) и символът + (‘+’), като съответно нулата и буквата F носят същото значение, както при входните данни, а символът + обозначава поставено водонедорасло (жива клетка).

Ограничения

  • 1 ? T ? 1000
  • 3 ? N ? 1000
  • 3 ? V ? (N * N) – 5
  • Програмата трябва да завършва своята работа за най-много 3 секунди. След третата секунда програмата ще бъде спряна автоматично.
  • Всички водонедорасли трябва да бъдат разпределени, тоест, в изходните данни трябва да има точно V на брой символа +, в противен случай алгоритъмът ще получи нула точки за тестът, на който е върнал различен от V на брой символа +

Примери

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

Първи пример

Примерен вход Примерен изход
2
3
5
00000
00F00
0FFF0
00F00
00000		 00000
00F00
0+++0
00F00
00000

Обяснение

Алгоритъмът е преценил, че е най-подходящо да постави 3-те клетки в средата на полето, във форма, известна като blinker в “Играта на живота”, съответно изяждайки 3 клетки храна. Ето как биха се развили така поставени водонедораслите за 2 единици време:

Нулева единица време
(т.е. при поставянето)		 1-ва единица време 2-ра единица време
(т.е. сега е измерването)
00000
00F00
0+++0
00F00
00000		 00000
00+00
00+00
00+00
00000		 00000
00000
0+++0
00000
00000

За нулевата единица време са изядени 3 клетки храна, на първата единица време са изядени още 2 клетки храна, на втората единица време не са изядени клетки храна. Тоест, на края на втората единица време, “качеството” на полето е 3 (изядени клетки храна) + 2 (изядени клетки храна) + 3 (останали живи клетки) = 8 и алгоритъмът ще получи резултат 8 точки за този тест.

Втори пример

Примерен вход Примерен изход
1
6
7
0000000
0000000
00F0000
000F000
0000000
0000000
0000000		 0000000
0++0000
0+F0000
000F+00
000++00
0000000
0000000

Обяснение за втори пример

Алгоритъмът е преценил да постави дадените 6 клетки около храната в така наречената форма beacon от “Играта на живота”. Ето как биха се развили в този случай водонедораслите за дадената 1 единица време:

Нулева единица време
(т.е. при поставянето)		 1-ва единица време
(т.е. сега е измерването)
0000000
0++0000
0+F0000
000F+00
000++00
0000000
0000000		 0000000
0++0000
0++0000
000++00
000++00
0000000
0000000

За нулевата единица време не е изядена нито една клетка храна. На първата единица време, обаче 2 живи клетки се появяват върху позицията, където се намира храната – съответно храната бива изядена (2 клетки). Съответно “качеството” на полето е 8 (живи клетки в този момент) + 2 (клетки изядена храна) = 10 и алгоритъмът ще получи резултат 10 точки за този тест.

Приложна задача – описание на алгоритъма за водонедораслите под форма на уебсайт

Астронавтите имат за задача да опишат мисията и откритията си. И защото Интернет е станал основен начин за разпространяване на информация, астронавтите трябва да опишат мисията си като направят уебсайт за нея. Споменахме ли, че сте с тях на планетата? Не сме… е вече сте!

Уебсайтът трябва да бъде базиран на HTML и CSS  (като нивото на усвояване на HTML5 e същото, каквото е при браузър Chrome последна версия през януари 2013). Възможно е ползване и на други клиентски технологии, които се поддържат от Chrome последна версия за януари 2013.  Уебсайтът трябва да бъде предаден като един или повече HTML файла, заедно със съответните им ресурси (стилове, скриптове, картинки и т.н., ако, разбира се, има такива). Задължително трябва да има един HTML файл с име index.html, който да бъде главната страница на уебсайта, като ако има други страници в index.html трябва да има хиперлинкове към тях. По желание на състезателите може да се ползват и сървърни технологии – като в този случай осигуряването на сървър, качването на уеб приложението на него и осигуряването на достъп през Интернет до приложението е отговорност на състезателите (състезателите предоставят работещ линк). По регламент целият код на уеб приложението трябва да бъде предаден (в случая уебсайт без сървърна част, описаните по-горе HTML, CSS и подобни файлове са и кодът, т.е. те са напълно достатъчни).

Уебсайтът има основна цел да опише “Играта на живота” в контекста на водонедораслите. Това включва описание на начина, по който се развиват поколенията на водонедораслите, различни интересни подредби на водонедорасли и храна и анализ на комбинации между тях, описание на алгоритмичните методи, които състезателите са ползвали (или са искали да ползват) за решаване на алгоритмичната част, примери как би работила алгоритмичната част в дадени ситуации, както и всичко друго, което състезателите могат да включат по темата (по желание може да се направи и описание на “планетата”, екипировката на астронавтите и т.н.). Тук е важно да се отбележи, че журито почти няма да държи толкова на литературен стил (но все пак “asdf asdf”, “lorem ipsum” и подобни няма да се отразят положително), а по-скоро ще търси правилно структурирана като семантика информация, валидност на кода на страницата, спазване на стандартите, удобство при разглеждане на информацията и т.н.

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

Критерии за оценяване

Оценяване на алгоритмичната част

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

  • Всеки алгоритъм ще бъде пуснат да генерира начална подредба за всяка една от “решетките”.
  • За всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест, а не за сбора от всички тестове като преди).
  • Например, ако за задачата има 10 теста, то всеки ще носи по 1 точка.
    • Ако на първото поле най-добре представилият се алгоритъмът G има резултат 30
    • алгоритъмът M има резултат 15,
    • а алгоритъмът L има резултат 10, то
    • в крайна сметка точките за този тест са:
      • G: 1 точка
      • M: 0.5 точки
      • L: 0.33 точки
  • По същия начин се оценяват всички тестове, точките се сумират и след това се закръглят до цяло число
  • Максимални точки в крайното класиране за алгоритмичната част: 10

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

Оценяването на приложната задача ще се извърши по-следните критерии:

  • Коректност (доколко уебсайтът следва съвременните уеб стандарти и се валидира успешно спрямо тях, структурира семантично информацията и има съдържание по темата) – 3 точки
  • Ползваемост (доколко е удобна и интуитивна е работата с уебсайта) – 3 точки
  • UI дизайн (доколко е приятен и удобен уебсайтът) – 2 точки
  • Оригинални функции и решения, които да впечатлят журито – 2 точки
  • Максимални точки в крайното класиране за приложната част: 10

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например C#, PHP, C, C++, Delphi, Python, WPF, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows 7 среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълен сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).

За приложната част се изисква да бъде предаден пълен сорс код. Приложната част трябва задължително да се отваря в браузър (Chrome, последна версия за януари 2013). Състезателите имат право да направят приложната част като уебсайт, състоящ се от определен брой HTML страници, от които има една главна страница с име index.html, плюс съответните им ресурси. В този случай при отварянето на index.html, трябва уебсайтът да функционира правилно и да осигурява навигация до останалите страници, ако има такива. Състезателите също имат право да направят уеб приложение със сървърна част, при което единствено трябва да осигурят линк към приложението си, качено някъде в Интернет, както и пълният му сорс код. Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), сериозни затруднения при намирането и стартирането на приложението могат да намалят присъдените от журито точки.

Характеристики на системата, върху която ще бъде проведено тестването

  • Intel® Xeon® CPU E31225 @ 3.10 GHz
  • 16 GB RAM
  • 128 MB Video Memory (dedicated) Intel® HD Graphics video card
  • 232 GB HDD
  • Microsoft Windows 7 64-bit OS

Краен срок

Краен срок за предаване на решения: неделя, 20 януари 2013 г, 23:59:59 часа.

Решенията се предават в студентската система на Академията на Телерик, на адрес http://telerikacademy.com/Courses/Courses/Details/13 според инструкциите, описани на раздела “Качи решение” на официалния сайт на състезанието.

Всички публикации, Задачи 2012/2013 , , , , , , , , 49 Comments