От Интернет, батка!

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

 

Не много отдавна, в една никак неотдалечена галактика, двама даджаи обмисляли как да оптимизират навигацията в сайта на Академията на Телерик. Вокан и Орож, уморени от дългото мислене върху тази задача, решили да разнообразят малко нещата, като си направят едно “даджайско състезание”. Те решили да изберат два произволни URL адреса (сочещи само към страници, свързани с Академията на Телерик – от официалния сайт, YouTube канала, студентската система и сайта на конкурса по програмиране) и да се състезават кой по-бързо ще успее да “стигне” от единия адрес до другия, единствено ползвайки хиперлинкове за “придвижване”. В едно от състезанията, Орож решил да си помогне, като генерира sitemap на сайта, в който били двата хиперлинка. Операцията била бавна, но когато завършила , Орож се ориентирал по-бързо от обикновеното. Когато показал тази хитрина на Вокан, той казал “Ахахахааа, откъде го взе това”, а Орож отговорил “От Интернет, батка!”.

Въпреки интересната случка, Вокан и Орож все още не били доволни – този sitemap бил приблизителен ориентир. Те искали бърз отговор, съдържащ всички хиперлинкове от пътя, по който трябва да се мине, за да се стигне от една страница до друга страница – ако такъв път изобщо съществувал. Готови ли сте да помогнете на Вокан и Орож, като откривате страниците, свързващи 2 други страници в мрежата от страници, свързани с Академията?

Съдържание:

Описание на “Даджайско състезание”

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

По-формално, за всеки две страници A и B ще казваме, че A е свързана към B, ако някъде в страница A има поне един хиперлинк, препращащ към страница B. Съответно път от страница X до страница Y ще наричаме такава поредица от N страници, в която страница[1] = X, страница[N] = Y и за която всяка страница[i] е свързана със страница[j], където i е в интервала [1, N-1], a за j винаги е изпълнено j = i+1. Дължината на този път е точно равен на N-1 (ако имаме 2 страници в пътя – само начална и крайна – тогава дължината на пътя ни е точно 1)

За хиперлинковете, които могат да се ползват за придвижване, важат следните правила:

  • Хиперлинковете са валидни anchor тагове в изходния HTML код на страницата, с валидни href атрибути, състоящи се от URL на страница (по-долу ще видите и характеристики за страниците).
  • Хиперлинковете НЕ Е възможно да бъдат генерирани от изпълнението на код при клиента (напр. JavaScript който добавя линкове)
  • НЕ СЕ СЧИТАТ за хиперлинкове URL адреси в чист текст. Например този текст: http://academy.telerik.com НЕ Е хиперлинк

Всички страници от пътя, включително началната и крайната, задължително трябва да бъдат от следните:

Уточнение за YouTube канала:

НЕ Е разрешено ползването на други страници от YouTube – например главната страница на канала (забележка: този линк има няколко разновидности), списъкът с всички плейлисти, списъкът с всички видеа и т.н. – НЕ могат да бъдат страници в пътя.

Също така, НЕ всички хиперлинкове от страниците на видеата и страниците на плейлистите могат да бъдат ползвани. Ето и допълнителните изисквания за хиперлинковете от позволените страниците в YouTube канала:

  • За страници на видеа:
    • могат да бъдат ползвани само и единствено хиперлинкове, намиращи се в елементи с атрибут id=”eow-description” (#eow-description), тоест в описанието на видеото
  • За страници на плейлисти
    • могат да бъдат ползвани само и единствено хиперлинкове, намиращи се в елементи с атрибут class=”primary-pane” (.primary-pane), тоест хиперлинкове към видеа от съответния плейлист

Уточнение за Студентската система на Академията на Телерик (http://telerikacademy.com)

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

НЕ Е разрешено, обаче, ползването на хиперлинкове, които се намират в някои елементи на главната страница:

  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=”fb0021a1c” (Facebook plugin)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=”RecentVideoHeader” (“Последни видео материали”)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=”ForumPostsHeader” (“Последни форум постове”)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=”BlogPostsHeader” (“Най-нови блог постове”)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=”IndexCalendarHeader” (“Календар”)

Уточнение за сайта на Конкурса по програмиране (този сайт)

Всички страници от сайта на конкурса могат да бъдат ползвани, като единствено НЕ Е разрешено ползването на хиперлинкове, намиращи се в коментари към някоя от темите. Тоест, не е разрешено ползването на хиперлинкове намиращи се в елемент с атрибут id, започващ с “comment-“.

Алгоритмична задача

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

Задача за алгоритъм за намиране на най-кратък път по хиперлинкове между две страници

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

Всички тестове ще се провеждат, като се взема предвид състоянието на абсолютно всички страници, които потенциално могат да участват в някой път (спрямо условието на задачата) от дата 6 април 2013 г. Това означава, че ако в отговорът на някой алгоритъм се генерира път, в който участват страници или хиперлинкове, появили се след 23:59:59 на 6 април 2013 г., този отговор ще бъде счетен за невалиден и алгоритъмът ще получи 0 точки за съответния тест!

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

Забележка 2: два хиперлинка може да изглеждат различно, но да сочат към един и същи ресурс – например https://konkurs.devbg.org/rules/#contest-description и https://konkurs.devbg.org/rules/.

Задача за генериране на тест – начален и краен URL адрес, между които да бъде намерен път

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

Входните данни трябва да бъдат записани в стандартен текстов файл (.txt) с ASCII кодировка, който може да бъде преглеждан в Windows среда чрез текстов редактор Notepad. За примери може да видите тестовите файлове публикувани за предишни кръгове на задачата (публичното хранилище на състезанието е на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/)

Предаването на теста ще става чрез поставянето му в папката algorithm, наред с изпълнимия файл за алгоритмичната задача. Файлът трябва да бъде именован както е името на потребителя, който го е изпратил (например ако потребителят е george.s.georgiev, то файлът трябва да носи името george.s.georgiev.txt).

При тестването, входните данни от теста ще бъдат подадени на всеки един алгоритъм, включително и на алгоритъма на автора.

Входни данни

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

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

На първият ред стои низ с URL на страницата, от която трябва да започва пътят (т.е. първата страница).

На втория ред стои низ с URL на страницата, в която трябва да свършва пътят (т.е. последната страница).

Във всички тестове задължително ще съществува път между двете страници.

Във входните данни НЕ може да се съдържа символът # (диез)

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

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

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

Изходните данни се състоят от редове, като на всеки ред е изписан по точно един URL. Този URL е стойността на href атрибута на съответния <a> елемент, който свързва две поредни страници в пътя. href атрибутът не трябва да бъде променян спрямо първоначалния му вид в съответната страница.

Например ако от страница A към страница B имаме хиперлинк, чиито код е <a href=”http://example.com/B#some-element-id”>link</a>, тогава на съответния ред от изходните данни трябва да стои низът http://example.com/B#some-element-id.

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

Допълнителни ограничения

  • Всички тестове ще се провеждат, като се взема предвид състоянието на абсолютно всички страници, които потенциално могат да участват в някой път (спрямо условието на задачата) от дата 6 април 2013 г. Това означава, че ако в отговорът на някой алгоритъм се генерира път, в който участват страници или хиперлинкове, появили се след 23:59:59 на 6 април 2013 г., този отговор ще бъде счетен за невалиден и алгоритъмът ще получи 0 точки за съответния тест!
  • Във входните данни НЕ може да се съдържа символът # (диез)
  • В изходните данни, ако алгоритъмът е избрал хиперлинк с #, то както е по условие, този диез трябва да бъде изпечатан. Тестващата система ще съобразява, че URL с диез сочи към същата страница, към която и URL без диеза и низът след него
  • От 00:00:00 до 23:59:59 часа на 6 април 2013 г. няма да бъдат правени промени (или добавяне/премахване) на хиперлинкове в която и да било страница, която според условието е възможно да участва в който и да е път.
  • За всички тестове ще съществува път между началната и крайната страница
  • Интернет връзката на тестващата машина няма да бъде спирана, но не можем да гарантираме за скоростта и надеждността ? (нито пък за всички сървъри, на които се намират потенциални участващи в различните пътища страници). Ползването на Интернет връзка (и съответно обновени ресурси, които са в разрез с първата точка от тези ограничения) е риск, който състезателите могат да преценят дали да поемат
  • Ако някой от ползваните от алгоритъма URL адреси не съществува на съответните страници, алгоритъмът ще получи 0 (нула) точки за съответния тест
  • Ако последователността от изведените от алгоритъма URL адреси не води до зададената крайна/последна страница, алгоритъмът ще получи 0 (нула) точки за съответния тест
  • Програмата трябва да завършва своята работа за най-много 5 секунди. След изтичане на времето програмата ще бъде спряна автоматично.

Примери

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

Примерен вход
https://konkurs.devbg.org
http://academy.telerik.com/school-academy/meetings/details/2012/11/22/databases
Примерен изход
https://konkurs.devbg.org/submit/
http://telerikacademy.com/Courses/Courses/Details/13
http:?/?/?academy.telerik.com/?
school-academy/meetings
meetings/details/2012/11/22/databases

Пояснение: Първо отиваме в страницата за “качване” където има линк към студентската система, оттам намираме линк към academy.telerik.com (в секцията “Полезни линкове”), откъдето пък в секция Училищна Академия избираме Уроци и оттам – линка за срещата за бази данни, която ни е целта.

Примерен вход
http://www.youtube.com/watch?v=AoewJHW9Oqc
http://academy.telerik.com/
Примерен изход
http://academy.telerik.com/

Пояснение: Намираме се в страница с видео, в чието описание има директен линк към страницата на Академията, отпечатваме го и приключваме работа.

Приложна задача – визуализация на възможните за достигане страници от стартова страница

Напишете програма, която по дадена начална страница от гореописания вид генерира визуализация на всички страници, които могат да бъдат достигнати чрез движение по хиперлинкове от нея. Програмата трябва да приема входни данни за начална страница, да обхожда достижими от нея страници, да визуализира тези страници и връзките ? с началната – било то чрез обект представящ всяка страница и връзки между страниците (както е показано тук, но с по-детайлни “върхове”), или чрез дърво подобно на файловата система, или чрез контроли които позволяват семантично приближение (semantic zoom) за наблюдение на общата картинка или на детайли от нея, или чрез 3D свят в който страниците са свързани летящи обекти и т.н. – вариантите са много. Важното е ясно и удобно да се виждат местата, до които е възможно да се стигне и как те са обвързани с началната страница. Програмата трябва да има възможност за настройка на дълбочината на визуализацията (т.е. колко далеч от началната страница да се стига) и да има опция за работа в Интернет и извън нея (върху предварително изтеглени данни).

Обобщено, приложението трябва да поддържа:

  • Въвеждане на начална страница
  • Настройване на търсенето и генерирането
  • Генериране на визуализация
    • с възможност за навигация между визуализираните страници
  • Online и Offline режим на работа

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

Приложението може да бъде уеб, десктоп, както и WinRT-базирано. Единственото ограничение е да бъде изпълнимо под Windows 7 или Windows 8 и да бъде предоставен лесен начин за стартирането му в папката application.

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

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

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

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

Краен срок

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

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