Игра на тролове

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

 

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

Изследвания на INT32 (Института за Наблюдение на Троловете, основан през 1932 г.) разкриват, че напоследък троловете все по-често играят една интересна и находчива игра, която от института наричат “Игра на тролове”. Те дори са склонни да я играят с чуждоземци (например хора). Е, ако съответния чуждоземец има нещастието да изгуби… ще оставим това на историята да разкаже. От друга страна, при печалба, троловете позволяват на чуждоземецът свободно да обитава техните земи, което дава огромни възможности за наблюдение на културата на тези толкова интересни създания, дори участие в хранителния им режим.

За да не рискуват последствията (и миризмата) от една игра с троловете,  учени от Казмоданския Висше Образователно-Разузнавателен Елитен Чародейски Институт (КВО-РЕЧИ) съвместно с INT32 са решили да изпратят парен робот (няма пари за слънчеви батерии), програмиран да изиграе успешна игра на предстоящите турнири и след това да наблюдава троловете, в името на научния прогрес. Тъй като в КВО-РЕЧИ и INT32 няма много програмисти, те молят вас за помощ. Ще помогнете ли за разкриването на вечната мистерия на троловете?

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

Играта се играе в квадратно поле, съставено от N*N квадратни плочки (всяка страна има по N плочки), като на всяка плочка има кули от каменни кубчета, наредени едно върху друго. В играта се въвеждат концепцията на “съседни плочки“, “съседни кули” и “височина на кула“. Височина на кула наричаме броя кубчета, от които се състои една кула върху дадена плочка. Две плочки са съседни, ако имат обща страна, т.е. една плочка може да има най-много 4 съседни плочки (ако е в някой от ъглите има 2, а ако е на някоя от страните, без да е в ъгъл, има 3). Съседни кули съответно ще наричаме всички кули, които са върху съседни плочки.

В началото на играта няма кули, с еднакви височини, които да са съседи. Играчът получава право на точно C на брой хода, като може на всеки ход да прави точно една от следните две операции:

• Да добавя едно кубче върху някоя кула (т. е. увеличаване на височината на една кула).
• Да взема едно кубче от някоя кула (т. е. намаляване на височината на една кула).

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

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

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

Алгоритмична задача – стратегия за “Игра на тролове”

Напишете програма (алгоритъм), която управлява парния робот на КВО-РЕЧИ, така че той да играе “Игра на тролове” възможно най-успешно, спрямо дадените ходове и игрално поле.

Входни данни

Входните данни се четат от конзолата. На първия ред стои числото C – броят ходове, на които роботът има право. На втория ред стои числото N – дължината на страната на квадратното игрално поле (т.е. броя плочки във всеки ред и всяка колонка в игралното поле).

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

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

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

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

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

Командата може да бъде “put” или “take” (без кавичките) – съответно обозначаваща поставяне или вземане на кубче. Двете цели положителни числа описват съответно редът и колонката (т.е. координатите на кулата), от които трябва да бъде извършено поставянето или вземането на кубче.

Забележка: троловете и програмистите започват да броят от 0 – тоест координатите на първата плочка на първия ще бъдат 0 0, а не 1 1. Съответно координатите на втората плочка на първия ред ще бъдат 0 1, координатите на третата плочка на първия ред ще бъдат 0 2 и т.н.

Ако изходът е правилно форматиран, но съдържа по-малко от C на брой реда, се считат за изиграни само толкова ходове, колкото редове са били изведени.

Ограничения

• Числата C и N са цели и са в сила ограниченията 1 ? C, N ? 1000.
• В началото никоя кула няма да има височина по-голяма от 1000
• Програмата трябва да завършва своята работа за най-много 3 секунди. След третата секунда програмата ще бъде спряна автоматично.
• Ако на една плочка не са останали кубчета, ако програмата се опита да вземе кубче от тази плочка, този ход ще се счита за “пропилян”, тоест нищо няма да се случи, но играчът няма да бъде наказан.
• Възможно е крайният резултат да е отрицателен (например ако само добавяме кубчета, без да вземаме и без да се случват изравнявания на височини).
• При невалиден ход (например невалидна команда координати извън игралното поле) играчът може да получи наказание по преценка на журито.

Пример

Примерен вход	Примерен изход
2 4 1 2 3 4 5 6 7 8 9 1 8 7 1 2 3 4	put 2 3 take 3 1

Обяснение

Ход 1: повишаваме седмицата с едно	Резултат: 3 съседни осмици и зануляване	Ход 2: намаляваме двойката с едно	Резултат: 3 съседни единици и зануляване
1 2 3 4 5 6 7 8 9 1 8 7 1 2 3 4	1 2 3 4 5 6 7 8 9 1 8 8 1 2 3 4	1 2 3 4 5 6 7 0 9 1 0 0 1 2 3 4	1 2 3 4 5 6 7 0 9 1 0 0 1 1 3 4
Краен резултат: За първи ход на полето са останали 8 + 8 + 7 кубчета по-малко (автоматично 8 + 8 + 8, но сме добавили 1). За втори ход сме намалили с още 4 кубчета (автоматично 1 + 1 + 1 и още 1 от вземане на кубче). Разликата между първоначалния брой кубчета и крайния брой кубчета след изиграване на ходовете е 27 и това е резултатът ни за този пример.

Още един пример

Примерен вход	Примерен изход
4 3 1 2 3 5 6 7 9 1 8	take 0 2 take 0 2 take 0 2 take 0 2
Краен резултат: просто сме опитали да вземем 4 пъти от тройката на първия ред. Първият път се получават две съседни двойки и те се нулират. Следващите 3 хода са празни (опитваме да вземем от празна плочка). Като резултат получаваме 5 точки от първия ход и по 0 от останалите 3 хода (общо 5 точки). Забележка: това е валидно поведение, независимо че не печели възможно най-много точки.

Задача по приложно програмиране – визуализация на “Игра на тролове”

Учените от КВО-РЕЧИ не се изчерпват от идеи бързо. Освен алгоритъм за игра с троловете, имат нужда и от визуализация на това как е протекла играта, за да може да изследват както поведението на алгоритъма, така и какви подобрения могат да направят, за бъдещи срещи.

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

Вашата задача е да напишете програма, която играе и визуализира “Игра на тролове”, като:

• Приема същите входни данни в описания вече формат или в друг формат по ваше желание.
  • Форматът трябва да бъде описан по някакъв начин – било със подсказки по време на изпълнение на програмата или в допълнителен файл, или по друг начин.
  • По желание може да се реализира и потребителски интерфейс за интерактивно въвеждане на игралното поле.
  • Генерира отделна уеб страница за всеки ход от играта.
    • Страницата трябва визуализира състоянието на игралното поле в този момент и може да съдържа и друга полезна информация (по ваш избор).
    • Всяка страница трябва да има връзка (hyperlink) към страниците описващи предишния и следващия ход. По желание може да бъде реализирано автоматично преминаване към следващия ход (с 1 или няколко секунди изчакване).
    • Начинът на визуализация не е строго дефиниран – състезателите имат свобода да решат как ще покажат игралното поле (таблица, картинки с камъни, само числа, графики, стилове, интерактивност, …), както и да визуализират текущия ход, така че визуализацията да бъде удобна и привлекателна за разглеждане.
    • Състезателите имат право да ползват както HTML, така и CSS и JavaScript, такива че страниците да изглеждат коректно на съвременен уеб браузър от 2012 г.
    • Приложението има права за четене и писане в директорията, в която се намира изпълнимият му файл.
    • Отваря автоматично страницата, описваща първия ход:
      • Това може да стане чрез извикване на уеб браузъра по подразбиране.
      • По желание състезателите имат право да вградят визуализацията в собственото си приложение, при положение че тя е базирана на HTML и работи по същия начин, както в по-известните съвременни браузъри.
      • Приемане на входни данни за играта.
      • Генериране на толкова на брой изходни файлове, колкото ходове трябва да бъдат изиграни.
      • Визуализиране на отделните страници и навигация между тях (например чрез браузър или вградена визуализация в приложението).

Обобщени задължителните функционалности на приложението

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

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

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

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

• Всеки алгоритъм ще бъде пуснат да играе на всяко едно от игралните полета.
• Резултат на един алгоритъм е сумата от резултатите му на различните игрални полета.
• Накрая, алгоритъмът с най-висок общ резултат, ще получи 10 точки в крайното класиране, а останалите ще получат пропорционален процент от тези точки, закръглен до цяло число.
• Ако резултатът на най-добрия алгоритъм е G, а резултатът на някой от алгоритмите е P, то този с резултат P ще има крайни точки = P/G * 10, закръглено до цяло число.
• Пример: ако играят алгоритми A, B и C, и алгоритъм B има резултат 520, алгоритъм C – 260, а алгоритъм A – 95 точки, крайните точки в класирането ще са следните: B – 10 точки; C – 5 точки; A – 2 точки.
• Максимални точки в крайното класиране за алгоритмичната част: 10

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

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

• Коректност (доколко задължителните функционалности работят) – 3 точки
• Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 1 точка
• Ползваемост (доколко е удобна и интуитивна е работата с приложението) – 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

Краен срок

Краен срок за предаване на решения: 16 декември 2012 г.

Инструкции за предаване на решения ще бъдат публикувани в раздел “Качи решение” в следващите седмици