Игра „Пукане на балони“

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

Описание на играта “Пукане на балони”

Играта „Пукане на балони“ се играе от един играч на правоъгълна стена (матрица) от балони. Всеки балон е една част (клетка) от тази стена. Така реално имаме редове и колони от балони и координатите на един балон се описват чрез съответните ред и колона в които се намира. Нека матрицата има R реда и C колони. Ще номерираме редовете и колоните по следния начин:

• Най-горният ред има номер 0
• Най-долният ред има номер R-1
• Най-лявата колона има номер 0
• Най-дясната колона има номер C-1

Така например балонът в горният ляв ъгъл се намира на ред 0 и колона 0.

Съседи на един балон ще наричаме балоните, които са му директно вляво, вдясно, отгоре и отдолу (тоест един балон има най-много 4 съседа при пълна матрица с балони). Например съседите на балона на позиция (1, 1) са балоните на позиции (0, 1), (1, 2), (2, 1), (1, 0).

Всеки балон е оцветен в някакъв цвят. Този цвят ще описваме с числата от 1 до 4 включително. На всеки ход, играчът пука по един балон. Когато един балон бъде спукан, на негово място остава празно пространство и се предизвиква верижна реакция – пукат се всички негови съседи със същия цвят. Те от своя страна пукат всички техни съседи със същия цвят и така нататък. Когато верижната реакция свърши останалите балони се пренареждат по следния начин: всеки балон, под който има празно пространство, пада надолу (т.е. отива на по-голям по номер ред) докато под него няма друг балон или не стигне до най-долния ред. Тоест, няма случай, в който над празно пространство (празна клетка) остават балони (на картинката е показан пример, в който балонът на позиция (1, 5) бива спукан)

За всеки балон, спукан по време на верижна реакция, играчът печели точки, равни на броя балони спукани в тази верижна реакция. Тоест, ако в една верижна реакция са спукани M балона, играчът печели M*M точки (напр. за 4 спукани балона в една верижна реакция, играчът печели 16 точки).

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

Алгоритмична задача – стратегия за играта “Пукане на балони”

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

Входни данни

Входните данни се четат от конзолата. На първия ред стоят две цели числа R и C – броят редове и броят колони в стената (матрицата). На всеки един от следващите R реда има по C цели числа, разделени с интервали – поредица от цветовете на балоните от съответния ред. Редовете са изредени от 0 до R-1 (отгоре надолу), а колоните – от 0 до C-1 (отляво надясно).

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

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

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

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

Ограничения

• Числата R и C са цели и са в сила ограниченията 3 ? R, C ? 300.
• Числата, задаващи цветовете на балоните са в интервала [1…4].
• Програмата трябва да завършва своята работа за дадена стена с балони за най-много 3 секунди (в противен случай се присъждат 0 точки).

Примери

Резултатът в първия пример е 8*8 + 1*1 + 3*3 = 74, във втория е 6*6 + 3*3 = 54, а в третия е съответно 15*15 = 225.

Вход	Изход		Вход	Изход		Вход	Изход
3 4 1 2 2 2 3 3 3 3 3 3 3 3	3 2 0 2 0 2 1		3 3 2 3 2 2 2 2 3 2 3	2 1 1 2 1		3 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4	1 0 0

Задача по приложно програмиране – симулатор на играта “Пукане на балони”

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

Симулаторът задължително трябва да предоставя следните функционалности:

• Генериране на стена (матрица) по зададени дължина и височина (с размери в гореописаните ограничения)
• Зареждане на стена от входен файл, форматиран по гореописания начин
• Възможност за избор на играч (алгоритъм или човек)
• Изпълнение на ход от играта (когато играе човек да може да избере балон, който да спука), а когато играе алгоритъм, той избира поредния балон за пукане
• Визуализация на ходовете от играта
• Показване на крайния резултат след края на играта

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

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

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

При оценяването ще бъдат генерирани 5 различни по големина игрални полета.

• Всеки алгоритъм ще бъде пуснат да играе на всяко едно от игралните полета.
• Резултат на един алгоритъм е сумата от резултатите му на различните игрални полета.
• Накрая, алгоритъмът с най-висок резултат, ще получи 10 точки в крайното класиране, а останалите ще получат пропорционален процент от него, закръглен до цяло число.

Максимални точки в крайното класиране за алгоритмичната част: 10.

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

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

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

Максимални точки в крайното класиране за приложната част: 10.

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

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

За алгоритмичната част се изисква да бъде предаден пълният сорс код + изпълним файл за 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

Анализ на пети кръг и резултати

Върнахме в детските години за малко (а състезателите за по-дълго) със задачата от пети кръг на състезанието на PC Magazine и Telerik. Участниците трябваше да направят алгоритми, които предизвикват верижни реакции на пукане на балони в правоъгълна матрица (и да го правят бързо), както и приложения, които да визуализират процеса. И в този кръг се оказа, че интересът към визуализирането (изобщо приложните програми) е по-голям, но трябва да се отбележи, че видяхме хитри подходи и в алгоритмичната част. Както обикновено, ето мислите ни над делата на участниците, и както обикновено, резултатите за този кръг може да видите по-надолу (а ние продължаваме с описание на процедурата по оценяването в следващите редове).

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

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

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

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

Крайни резултати

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

 

Отбор	Краен резултат	Алгоритъм	Приложение
Станислав Гатев и Георги Ангелов	17	10	7
Димитър Дилянов Иванов	2	0	2

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

http://pcmagazine-telerik-contest.googlecode.com/svn/trunk/