Водонедорасли
Задача #2 от конкурса на Telerik и PC Magazine Bulgaria, сезон 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 според инструкциите, описани на раздела “Качи решение” на официалния сайт на състезанието.