Къртим мивки, лепим плочки
Задача #5 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

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

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

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

Сега Бай Иван се е обърнал към вас – ще му помогнете ли като му “прогаменирате” желаното, или ще рискувате вашата мивка да бъде ползвана за източник на плочки?

Съдържание

• Описание на плочките, пренасянето и подредбата
  • Видове фигури
  • Правила при пренасяне и дължина на път
• Алгоритмична задача – логика за подредба на плочки
  • Входни данни
  • Изходни данни
  • Ограничения
  • Примери
    • Първи пример
    • Втори пример
• Приложна задача – симулация на Бай Иван
• Критерии за оценяване
  • Оценяване на алгоритмичната част
  • Оценяване на приложната част
• Допълнителни изисквания
• Характеристики на системата, върху която ще бъде проведено тестването
• Краен срок

Описание на плочките, пренасянето и подредбата

Бай Иван, макар и голям майстор, работи по строго определени правила и с ограничен набор от “плочкови фигури“. Плочковите фигури са фигури, които се образуват от залепянето на няколко плочки една до друга, по техните ръбове. Например можем да образуваме символа “+” (плюс) като залепим 5 плочки – една по средата и четири залепени за нейните ръбове. Бай Иван работи само и единствено с определен набор от такива фигури, като никога не разделя една фигура – например не може да “откачи” една плочка от плюса. Също така, всички плочки съставящи една фигура са квадратни и с еднакъв размер.

Бай Иван обича да характеризира плочките си, за да изглежда по-умен. Той е измислил термина “централна плочка”, свързан с неговите фигури. Централната плочка е тази плочка от фигурата, която е свързана с най-много други плочки от фигурата. Така например за фигурата “+”, плочката, която е по-средата е свързана с 4 плочки, а всяка една от останалите 4 плочки е свързана с по 1 плочка (т.е. с тази по средата). Съответно тази по средата има най-много залепени за нея плочки и тя е “централна плочка” за тази фигура.

Преди да започне работа, Бай Иван винаги разчертава работната си площ на квадрати с размера на плочка, под формата на матрица и номерира квадратите спрямо реда и колоната на която се намират, започвайки от 0 (нула). Така първия квадрат на първия ред е [0, 0], втория квадрат на първия ред е [0, 1], първия квадрат на втория ред е [1, 0] и така нататък. След като получи тази матрица, Бай Иван винаги реди своите фигури така, че плочките им да съвпадат с разчертаното на земята.

Видове фигури

Има няколко вида фигури, които Бай Иван ползва. Всяка една от тях ще описваме като квадратите от една матрица, които фигурата би заела, ако централната ? плочка се намира на ред R и колона C (т.е. на позиция [R, C]).

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

• “деветоплочник” – заема позиции
  [R,C], [R-1, C], [R-1, C+1], [R, C+1], [R+1, C+1], [R+1, C], [R+1, C-1], [R, C-1] [R-1, C-1]
• “хоризонтална линия” – заема позиции [R, C], [R, C-1], [R, C+1]
• “вертикална линия” – заема позиции [R, C], [R-1, C], [R+1, C]
• “плюс” – заема позиции [R, C], [R-1, C], [R, C+1], [R+1, C], [R, C-1]
• “ъгъл горе-дясно” – заема позиции [R, C], [R-1, C], [R, C+1]
• “ъгъл долу-дясно” – заема позиции [R, C], [R, C+1], [R+1, C]
• “ъгъл долу-ляво” – заема позиции [R, C], [R+1, C], [R, C-1]
• “ъгъл горе-ляво” – заема позиции [R, C], [R, C-1], [R-1, C]

Схематично, фигурите изглеждат по следния начин (зеленият квадрат е централната плочка):

деветоплочник	хор. линия	верт. линия	плюс
горе-дясно	долу-дясно	долу-ляво	горе-ляво

С това се изчерпват всички фигури, които Бай Иван може да ползва.

Правила при пренасяне и дължина на път

Когато нашият герой пренася фигури, той има две важни правила.

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

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

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

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

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

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

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

Входни данни

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

На първия ред от входните данни стои числото N – броя фигури, разположени върху разчертаното от Бай Иван работно поле.

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

Имената на описаните по-горе фигури са както следва:

• фигура “деветоплочник”: ninetile
• фигура “плюс”: plus
• фигура “хоризонтална линия”: hline
• фигура “вертикална линия”: vline
• фигура “ъгъл горе-дясно”: angle-ur
• фигура “ъгъл долу-дясно”: angle-dr
• фигура “ъгъл долу-ляво”: angle-dl
• фигура “ъгъл горе-ляво”: angle-ul

За пример, един ред дефиниращ вертикална линия с централна плочка на позиция [1, 3] (втори ред, четвърта колона – броим от нула) ще изглежда така:

vline 1 3

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

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

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

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

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

Ограничения

• N ще бъде цяло число между 3 и 1000
• Полето (матрицата), в което Бай Иван работи е винаги с размери 500 по 500, като първия ред/колони е с номер 0 (нула) а последния ред/колона е с номер 499 (т.е. съдържа общо 250000 квадрата)
• Началното местоположение на фигурите ще бъде такова, че няма да има плочки на някоя фигура, които излизат извън полето
• Крайното местоположение на фигурите трябва да бъде такова, че нито една плочка на която и да е фигура да не излиза извън полето
• Алгоритъмът трябва да завършва работата си в рамките на 3 секунди, в противен случай ще бъде прекъсван автоматично и ще получи 0 точки за съответния тест

Примери

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

Първи пример

Примерен вход	Примерен изход
2 plus 1 1 vline 2 2	1 1 2 3
Начално състояние	Крайно състояние
Обяснение: Имаме точно 2 фигури, които се “пресичат” (имат общи позиции на плочки), съответно със зелена и синя централна плочка. Достатъчно е да преместим само едната, в случая вертикалната линия. При това преместване Бай Иван ще измине точно 1 стъпка.

Втори пример

Примерен вход	Примерен изход
3 plus 1 1 ninetile 3 1 vline 2 2	2 1 4 3 1 3
Начално състояние	Крайно състояние
Обяснение:Имаме 3 фигури, всички от които се “пресичат”. Първа във входа е фигурата плюс и затова местим нея първо – качваме я един ред нагоре (в случая това е по-скоро излишна операция, която ни удължава общия път – но не е некоректно поведение, просто е неоптимално). След това местим “деветоплочникът” и накрая преместваме “вертикалната линия” с един ред надолу и една колона надясно. Общият път, които Бай Иван ще измине носейки е 1 + 3 + 2 = 6.

Приложна задача – симулация на Бай Иван

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

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

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

Както обикновено, подтикваме състезателите да проявят творчество, като сами преценят как да имплементират изброените функционалности. Възможно е визуализацията да бъде 2D или 3D, приложението да работи в уеб среда или в Desktop режим (а защо да не бъде и Windows Store App). Журито ще оцени положително допълнителни функционалности и оригинални решения. Ето няколко (неизчерпателни и незадължителни за имплементация) идеи:

• различни по размери полета
• препятствия
• възможност за ротация на фигурите
• възможност за разбиване на фигурите на съставните им части
• Бай Пешо, който да пречи на Бай Иван
• възможност за “multiplayer”
• възможност за “запис на симулация” – запис на извършените действия и изпълняването им наново

Вярваме, че участниците ще измислят още и иновативни начини да удоволетворят Бай Иван.

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

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

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

• Данните от всеки тест на журито ще бъдат подадени на всеки един предаден алгоритъм.
• За всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест).
  • В тази задача най-добър означава най-кратко общо изминато разстояние (което оценяващата система ще изчислява на база изведените промени в местоположенията)
• Например, ако за задачата има 10 теста, то всеки ще носи по 1 точка.
  • Ако на първото поле най-добре представилият се алгоритъмът G е описал премествания, за които общият път е 10
  • алгоритъмът M – 15,
  • а алгоритъмът L – 30, то
  • в крайна сметка точките за този тест са:
    • G: 1 точка
    • M: 0.67 точки = 1/(M/G) = 1/(15/10)
    • L: 0.33 точки = 1/(L/G) = 1/(30/10)
• По същия начин се оценяват всички тестове, точките се сумират и след това се закръглят до цяло число
• Максимални точки в крайното класиране за алгоритмичната част: 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.

Краен срок

Краен срок за предаване на решения: 12 май 2013 г, 23:59:59 часа.

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