Библейски код

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

Търсене на скрити кодове

От стотици години религиозни водачи, изследователи и псевдоизследователи търсят скрити кодове и послания в свещени книги и писания като Библията, Корана и Ведите. С годините са разработени различни концепции за “тайни кодове” и методи за тяхното намиране. Един от популярните такива методи за търсене на скрити кодирани съобщения в текст е ELS (Equidistant Letter Sequence). В най-простия си вариант този метод се състои в следното:

1. Оригиналното текстово съдържание на свещена книга или друг “магически” текст се превръща в поредица от букви. За целта се изтриват всички препинателни знаци заедно с празното разстояние между думите и параграфите в текста и всички букви се превръщат в главни и се долепят една след друга.
2. С получената поредица от букви се запълва последователно по редове правоъгълна матрица с размер R реда и C колони, започвайки от произволно избрана начална буква.
3. В получената матрица от букви се търсят думи от скрито послание, разположени в ELS редица (поредица от букви на еднакви отстояния). ELS редиците могат да са разположени хоризонтално, вертикално или по диагонално. Всяка дума от ELS редица може да започва на произволна позиция в матрицата и буквите, които я съставят, трябва да са разположени през еднакви разстояния по хоризонтал и вертикал (вж. фигурата по-долу).

Да разгледаме следния примерен текст:

Математици доказаха, че тайните кодове от Библията могат да се получат случайно като се изпробват твърде многото варианти за думи и букви. Ако рядка буква не се среща, сменяме думата със синоним. Пробвайте сами и ще се убедите!

Ако приложим описания метод и запишем текста в матрица със 7 реда и 25 колони, започвайки от 10-тия символ на текста, можем да намерим в него тайното съобщение “Наков пак ще пие бира“:

В примера първият ред и последният ред не са част от матрицата. От всичките 187 букви от входния текст първите 9 и последните 3 не се ползват. Останалите 175 букви са записани в матрицата (7 реда по 25 букви на ред = 175 букви).

Алгоритмична задача – търсене на скрити кодове

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

Входни данни

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

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

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

На следващия ред трябва да се отпечата максималният брой намерени думи М. На следващите M реда трябва да се отпечатат по една дума от търсените входни думи, следвана от интервал и от 4 числа, разделение с интервали: StartRow, StartCol, RowStep, ColStep (начален ред и колона и разстояние до следващата буква по редове и колони). Редовете се номерират с числата от 1 до R от горе надолу. Колоните се номерират с числата от 1 до C от ляво надясно.

Ограничения

• Входът се подава в кодиране “windows-1251”.
• Броят думи W е цяло число в диапазона [1…20].
• Всяка дума от търсените съдържа между 1 и 30 букви (кирилица или латиница).
• Броят L на редове с изречения е цяло число в диапазона [1…20 000].
• На един ред от входа може да има не повече от 500 символа.
• Думите и текстът, в който се търсят, са на български или на английски език.
• Намерената начална позиция за матрицата Offset трябва да е цяло число в диапазона [1…10 000 000].
• Броят редове R на намерената матрица трябва да е цяло число в диапазона [1…50].
• Броят колони C на намерената матрица трябва да е цяло число в диапазона [1…50].
• Максималният брой намерени думи M трябва да е цяло число в интервала [1..W].
• Числата StartRow и StartCol трябва да задават валидна начална позиция в матрицата, т.е. StartRow трябва да е цяло число в диапазона [1..R] и StartCol трябва да е цяло число в диапазона [1..C].
• Програмата трябва да завършва своята работа за най-много 20 секунди, в противен случай се присъждат 0 точки.

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

Примери

Вход	Изход
6 наков структуроопределяща бира ще пие пак 3 Математици доказаха, че тайните кодове от Библията могат да се получат случайно като се изпробват твърде многото варианти за думи и букви. Ако рядка буква не се среща, сменяме думата със синоним. Пробвайте сами и ще се убедите!	10 7 25 ИДОКАЗАХАЧЕТАЙНИТЕКОДОВЕО ТБИБЛИЯТАМОГАТДАСЕПОЛУЧАВ АТСЛУЧАЙНОКАТОСЕИЗПРОБВАТ ТВЪРДЕМНОГОТОВАРИАНТИЗАДУ МИИБУКВИАКОРЯДКАБУКВАНЕСЕ СРЕЩАСМЕНЯМЕДУМАТАСЪССИНО НИМПРОБВАЙТЕСАМИИЩЕСЕУБЕД 5 бира 5 4 0 4 наков 1 15 1 -2 ще 7 18 -1 -6 пак 7 4 -1 1 пие 3 19 1 2

Задача по приложно програмиране – GUI за търсене на скрити кодове

Да се разработи цялостно приложение с потребителски интерфейс към крайния потребител за търсене на скрити кодове. Приложението може да бъде настолно или уеб базирано. То трябва да поддържа следната функционалност:

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

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

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

Алгоритмична задача – критерии за оценяване

Оценяването се извършва с набор от тестове:

За всеки тест се присъждат всичките точки или част от тях. Ако резултатът е оптимален (т.е. намерени са максималният възможен брой думи, които съществуват в някоя от матриците на текста), се присъждат всички точки. Ако резултатът съдържа по-малко думи от оптималния брой, се присъждат частични точки пропорционални на броя намерени думи към максималния брой думи. Например ако за даден тест оптималният брой думи, които могат да се намерят в него, е 10, а вашата програма намери 8, ще ви бъдат присъдени 80% от точките за този тест.

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

Общия брой точки се изчислява като се сумират точките от тестовете и се закръглят до цяло число.

Приложна задача – критерии за оценяване

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

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

За алгоритмичната част се изисква да бъде предаден пълният сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), предайте само сорс кода.

За приложната част се изисква да бъде предаден пълен сорс код + изпълним .exe файл (когато е възможно). При уеб приложения (например на PHP, Python, ASP.NET, Java EE или JavaScript) предайте техния код + кратки инструкции за настройка и стартиране.

 

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

Мина повече време от очакваното, но резултатите за втори кръг от конкурса по програмиране на PC Magazine и Телерик вече са налице. Състезателите и този път се бяха постарали да представят ефективни и интересни решения на дадената задача. Генерирани бяха тестове (по зададените в условието критерии), които да изпитат предаденото както откъм коректност, така и откъм бързодействие. Резултатите този път са интересни с това, че победителят е с далеч по-малко от пълните 20 точки, а същевременно първите отбори са с близки точки – някои са се справили по-добре с алгоритмичната, други с приложната, а трети – и с двете части по малко. Естествено, в следващите редове ще разкажем за тестването и за впечатленията си от този кръг. Самите резултати са накрая  на тази статия (хайде scroll-вайте сега).

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

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

• Създава се матрица с размери до 50 на 50 и се запълва произволно с някои от буквите от определена азбука (българска, английска или и двете)
• В тази матрица се намират произволни последователности от „скрити думи“
• Създават се определен брой копия на матрицата
• От всяко копие се премахват определен брой „скрити думи“ (като се променят букви от тях, като новите букви гарантирано не съвпадат с букви от която и да е друга търсена дума)
• Матрицата съдържаща всички „скрити думи“ и останалите матрици се разбъркват и след това се подреждат в последователен текст
• В началото и в края на текста се добавя още произволен текст
• В получения текст се вмъкват произволно нови редове и символи (запетаи, точки, удивителни, въпросителни, тирета, плюсове и т.н.)

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

Добрата новина е, че има решение, което откри всички от генерираните „скрити думи“ във всички тестове. Лошата е, че нито един алгоритъм не работеше напълно вярно (дори и „най-добре откриващият“). Имаше грешки в кодировката, отместени матрици, грешно намерени позиции на „скрити думи“, дори грешно предадени решения. Там, където бързи корекции в алгоритмите или проверяващия алгоритъм бяха възможни, направихме такива. Естествено, всеки алгоритъм получи наказателни точки спрямо тежестта на проблема, който имаше.  Някои алгоритми получаваха различни резултати при тестове, генерирани по еднакви критерии (напр. 3 думи в 5 изречения на английски език) един след друг, затова резултатите от такива тестове бяха усреднени.

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

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

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

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

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

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

Крайните резултати за приложната част се формираха като комплексна оценка за всяко едно приложение от оценките на журито, заедно с оценките от първите два етапа (коректност и справяне с грешки). Отборите, непредали приложна част получиха 0 точки за тази част. Резултатът на най-добре представилият се отбор в тази част се доближи до максималните 10 точки, като отново беше близо до резултат на друг от отборите.

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

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

Отбор	Краен резултат	Алгоритъм	Приложение
Антон Богданов, Станислава Богданова	10	2	8
Марин Драганов	9	9	0
Георги Ангелов, Станислав Гатев	9	1	8
Марио Стоилов, Ивайло Кирилов	5	0	5
Радослав Тодоров	3	0	3
Юлиян Гюров	1	1	0

(извиняваме се ако сме сгрешили изписването на нечие име)