Игра “1-2-3”

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

Описание на играта “1-2-3”

Играта “1-2-3” се играе от двама съперници A и B върху правоъгълна игрална дъска състояща се от N x M кутийки (вж. фигурата), които първоначално са свободни. На всеки ход играчът, който е наред, поставя в игралната дъска фигура с размер {1 x 1}, {1 x 2} или {1 x 3} със своята буква (A или B) в хоризонтална, вертикална или диагонална посока. При поставянето на фигура тя трябва да заема 1, 2 или 3 съседни кутийки (по хоризонтал, вертикал или диагонал), като поне една от тези кутийки трябва да е свободна, а останалите могат да са вече заети с буквата на същия играч.

Първи играе играч A. След като даден играч направи своя ход, идва ред на другия играч, който поставя своя фигура върху дъската по същите правила. Играта се разиграва чрез поредица от ходове, при които двамата играчи се редуват, и завършва, когато всички полета от дъската са запълнени. Победител е играчът, който е запълнил със своята буква повече полета. При равен брой полета играта завършва наравно. Ако някой играч направи грешен ход (например постави фигура върху кутийка заета от другия играч или постави фигура с непозволена форма или излезе извън границите на дъската), той губи играта служебно и печели противникът му. Ако даден алгоритъм за играта “1-2-3” работи повече от 1 секунда на ход, той също губи играта служебно. Когато играч загуби служебно, резултатът е N*M на 0 в полза на противника му.

На фигурата по-долу е показано примерно разиграване върху дъска с размери 4 x 3, в което двамата играчи завършват на равно (6 на 6 запълнени кутийки). Фигурите, поставени при всеки пореден ход са отбелязани в различен цвят:

Алгоритмична задача – стратегия за играта “1-2-3”

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

Входни данни

Входните данни се четат от конзолата. На първия ред стоят две цели числа M и N, разделени с точно един интервал. Те задават съответно ширината на дъската (брой колони) и височината на дъската (брой редове). На следващите N реда стоят по точно M символа (без интервали между тях), съответстващи на кутийките от дъската. Символ “A” (буква A латинска, главна) означава кутийка, заета от играч A. Символ “B” означава кутийка, заета от играч B. Символ “–” (тире) означава свободна кутийка. На последния ред от входа стои един единствен символ “A” или “B“, който задава кой от двамата играчи е на ход. За край на ред се ползват стандартните за Windows символи \r\n. В края на последния ред от входа не е задължително да са изписани символите за край на ред \r\n (т.е. може да ги има или да ги няма). Няма гаранция, че входът е подаден коректно (в описания формат).

Ограничения

• Числата M и N са цели и са в сила ограниченията 3 ? M, N ? 20.
• Програмата трябва да завършва своята работа за най-много 1 секунда (в противен случай се присъжда служебна загуба).

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

Ако входът е в описания по условие формат и дъската не е запълнена (в нея има поне една свободна кутийка), програмата трябва да изведе на конзолата новото състояние на дъската след изпълнения ход. Форматът, в който се извежда дъската, е същият като формата, в който тя се подава на входа: точно N реда от по точно M символа на всеки ред, които изобразяват състоянието на всяка от кутийките (ползват се отново единствено символите “A“, “B” и “–“).

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

В края на последния ред от входа не е задължително да са изписани символите за край на ред \r\n (т.е. може да ги има или да ги няма).

Примери

Вход

Изход

Вход

Изход

Вход

Изход

Вход

Изход

Вход

Изход

4 3A— -A– –A- B

A–B-AB- –A-

3 3— — — A

—-AA —

5 3AAABA A-B-A ABBBB B

AAABAABBBA ABBBB

опатропа шай ля ля

error

2 2– AA B

error

Задача по приложно програмиране – симулатор на играта “1-2-3”

Напишете симулатор, който позволява да стартираме два алгоритъма, които играят играта “1-2-3” един срещу друг и визуализира битката между тях. Задачата няма твърдо фиксирани изисквания и дава голяма свобода по отношение на технологии, начин на визуализация, потребителски интерфейс и т.н. Тя позволява да проявите фантазия и умения по разработка на софтуер, умения по дизайн на потребителски интерфейс, по ползваемост и други.

Примерна функционалност, която можете да реализирате: зареждане на алгоритми за играч A и играч B (изпълними .exe файлове), избор на размер на дъската, изпълняване на пореден ход (с натискане на бутон или през определено време), визуализация на игровото поле по подходящ начин, отчитане и визуализиране на резултата, съобщаване кой е победил и други. Тези функционалности са примерни и вие имате свободата да имплементирате тях или други, които сметнете, че са по-важни за да бъде добър симулаторът на играта “1-2-3”.

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

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

Всяко решение, предадено от участник в конкурса (индивидуален състезател или екип), ще получи до 20 точки в зависимост от оценките получени по отделните критерии. Възможно е предаване само на алгоритмична или само на приложна част, но в този случай липсващата функционалност се оценява в 0 точки.

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

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

Анализ на първи кръг и резултати от
задача #1 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2011/2012

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

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

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

Проведено беше и тестване за това как алгоритмите се справят с некоректен вход. Резултатите отново бяха добри – повечето състезатели се справят с над 80% от примерите с некоректни входни данни.

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

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

Естествено компромисите не бяха „безплатни“ и на некоректно работещите алгоритми бе отнета точката за валидност на входа и изхода. Корекциите не повлияха значително на крайното класиране, но разбира се имаха известен ефект.

Ето и някои от по-сериозните проблеми:

• Програмата играе повече от ЕДИН ход – изискваше се отпечатване резултата от точно един ход, а не чакане на нов вход докато свърши играта.
• Печатане на излишни низове – трябваше да се отпечата само и единствено състоянието на дъската. Други низове като “Input the board”, “This is the board”, “B” и т.н. се считат за грешка, тъй като пречат на автоматизираното тестване.
• Чакане за допълнителен нов ред или end of stream – програмите трябваше да приемат точно толкова информация, колкото е нужна за описване на дъската и текущия играч, все едно тя е въведена от конзолата. Това означава, че няма как да има и end of stream.
• Размяна на M и N – някои алгоритми обръщаха редове и колони.

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

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

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

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

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

Функционалност, счетена за добра

• Изписване на имената на заредени алгоритми (чрез път или само име на файла)
• Възможност за „ръчна“ и „автоматична“ игра
• Подходяща визуализация на полето (оцветени кутии, анимации, 3D)
• Възможност за връщане на ходове напред и назад
• Възможност за многократно зареждане, визуализиране и т.н.
• Възможности за коректно оразмеряване

Функционалност, счетена за лоша

• Невъзможност за директно показване на резултатите (без да се чака визуализацията)
• Възможност за промяна стойности в клетките на полето от потребителя по време на визуализация на два алгоритъма
• Липса на стилизация на интерфейса
• Бутони с неясен текст (напр. “Button3” вместо “Browse”, “Customize” вместо “Load”)
• Объркващ или претрупан интерфейс (напр. липса на текст върху повечето на бутони)
• Неудобен интерфейс – променящи мястото си бутони, съобщения излизащи извън рамките на главния прозорец, диалогови прозорци появяващи се на различни места

Крайни резултати от първи кръг

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

Спецификация на тестовата система

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

• 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 и Телерик. Организаторите на конкурса не носят отговорност за съдържанието на предадените решения.

Поглед към следващия кръг

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

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

Награди за победителите

Първенците в първи кръг от конкурса печелят скромни награди от Академията на Телерик и могат да си ги получат в удобно за тях време от офиса на Телерик (за контакти [email protected]). Напомняме, че големите награди в конкурса (лаптопи, таблети, телефони и други) ще бъдат раздадени на финала, когато най-добре представилите се състезатели от всички кръгове ще премерят сили на живо в София.

Място	Отбор (членове)	Общо точки	Алгоритмична част (точки)	Приложна част (точки)
1	Антон Богданов, Станислава Богданова	16.5	8.5	8
2	Марио Стоилов, Ивайло Кирилов	16.0	8	8
3	Лазар Сестримски, Георги Билюков, Танер Мехмед	15.5	9.5	6
3	Станислав Гатев, Георги Ангелов	15.5	6.5	9
5	Лъчезар Цонов, Йордан Стоянов	15.0	9	6
5	Кристиан Ташков	15.0	8	7
7	Александър Георгиев	14.5	6.5	8
8	Кольо Данков, Стефан Чонов	14.0	7	7
9	Боян Желязков	11.0	8	3
9	Михаил Минков	11.0	7	4
11	Радослав Тодоров	10.5	8.5	2
12	Марин Драганов	7.5	7.5	0
13	Николай Лазаров, Иван Захариев	6.5	6.5	0
14	Кристиян Николов	6.0	6	0
15	Стоян Буланов, Ирник Дионисиев	5.5	3.5	2
15	Георги Йоловски	5.5	1.5	4

Промяна в класирането в първи кръг

Без да увъртаме – открихме, че сме допуснали грешка в оценяването на алгоритмичната част от състезанието. Коригирахме проблема и проведохме наново сблъсъците между алгоритмите. В допълнение към това за по-добро разграничаване на резултатите увеличихме броя на тестовете за валидност на входа и изхода. Отборът на първо място в старото класиране запази позицията си. Второто и третото място обаче заеха други два отбора. По-подробно описание може да прегледате по-долу.

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

За оценяването в първи кръг

Сблъсъците между алгоритмите породиха появата на доста близки резултати и направихме леки промени в оценяването. Вече закръгляме точно до първа цифра след десетичната запетая резултатите от игрите на различните игрални полета (6×4, 12×8, 20×20).

В допълнение към това, добавихме повече тестове за валидност на входа и изхода. Там оценяването е на следния принцип:

• под 50% успеваемост – 0 точки
• между 50% и 80% успеваемост – 0.5 точки
• над 80% успеваемост – 1 точка

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

Обновено класиране за първи кръг

Отбор (членове)	Общо точки	Алгоритмична част (точки)	Приложна част (точки)
Антон Богданов, Станислава Богданова	18	10	8
Александър Георгиев	17.9	9.9	8
Станислав Гатев, Георги Ангелов	17.8	8.8	9
Кольо Данков,  Стефан Чонов	16.8	9.8	7
Кристиан Ташков	16.2	9.2	7
Лъчезар Цонов, Йордан Стоянов	15.9	9.9	6
Лазар Сестримски,  Георги Билюков, Танер Мехмед	14.8	8.8	6
Марио Стоилов, Ивайло Кирилов	13.7	5.7	8
Михаил Минков	13.5	9.5	4
Боян Желязков	12.9	9.9	3
Радослав Тодоров	11.2	9.2	2
Николай Лазаров,  Иван Захариев	8.7	8.7	0
Марин Драганов	8.2	8.2	0
Стоян Буланов, Ирник Дионисиев	5.3	3.3	2
Георги Йоловски	5.1	1.1	4
Кристиян Николов	3.3	3.3	0