IT Blog
RSS icon Email icon
  • От интернет батка

    Posted on April 8th, 2013 Krasi Nikolov No comments

    Покрай многото ангажименти в Академията и извън нея не ни остана много време за тази задача от конкурса. В процеса на работа, първоначалните ми очаквания се обърнаха на 180°. Смятах, че ще е лесно да открия някакъв софтуер с който да сканирам сайтовете и моята работа ще бъде да търся най прекият път между две страници. В процеса на работа се оказа, че основната част от работата е да напиша софтуер, който да сканира сайтовете. В тази област не познавам добре възможностите, които дава .NET, така че избрах да напиша PHP скрипт.
    Като начало си направих една функция, която да връща всички href атрибути в един файл. За да постигна това използвах CURL заявка в PHP.

        $ch = curl_init();
        $userAgent = 'Mozilla/4.0 (compatible; MSIE 5.01; Windows NT 5.0)';
        curl_setopt($ch, CURLOPT_USERAGENT, $userAgent);
        curl_setopt($ch, CURLOPT_URL, $target_url);
        curl_setopt($ch, CURLOPT_FAILONERROR, true);
        curl_setopt($ch, CURLOPT_FOLLOWLOCATION, true);
        curl_setopt($ch, CURLOPT_AUTOREFERER, true);
        curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
        curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, false);
        curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false);
        curl_setopt($ch, CURLOPT_HEADER, true);
        curl_setopt($ch, CURLOPT_TIMEOUT, 10);
        curl_setopt($ch, CURLOPT_ENCODING, "gzip");
        $html = curl_exec($ch);
    

    Единственото нещо което ми създаде огромни трудности, беше да се досетя че сайта telerikacademy.com подава съдържанието си компресирано. Отне ми цял ден да тествам всякакви енкодинга и накрая решението се оказа много просто.(gzip)
    Следващата стъпка беше да вкарам получения резултат в един DOMDocument за обработка, това в голяма степен улеснява обработката на една html страница. Тук трябваше да филтрирам съдържанието което ми трябва

        //Add content in DOMDocument
        $dom = new DOMDocument();
        @$dom->loadHTML($html);
    
        // Remove parts that I don't need
        if (stripos($target_url, '://telerikacademy.com')) {
            $div = $dom->getElementById('RecentVideos');
            if ($div) {
                $div->parentNode->removeChild($div);
            }
            $div = $dom->getElementById('LetestForumPosts');
            if ($div) {
                $div->parentNode->removeChild($div);
            }
            $div = $dom->getElementById('Calendar');
            if ($div) {
                $div->parentNode->removeChild($div);
            }
            $div = $dom->getElementById('BlogPosts');
            if ($div) {
                $div->parentNode->removeChild($div);
            }
            $div = $dom->getElementById('fb0021a1c');
            if ($div) {
                $div->parentNode->removeChild($div);
            }
        }
        if (stripos($target_url, '://konkurs.pcmagbg.net')) {
            $div = $dom->getElementById('respond');
            if ($div) {
                $div->parentNode->removeChild($div);
            }
        }
    

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

        // Here I build list of anchor tags
        $xpath = new DOMXPath($dom);
        if (stripos($target_url, '://www.youtube.com/playlist')) {
            $hrefs = $xpath->evaluate('//div[contains(@class,"primary-pane")]//a');
        } else if (stripos($target_url, '://www.youtube.com/watch')) {
            $hrefs = $xpath->evaluate('//p/a');
        } else {
            $hrefs = $xpath->evaluate('body//a');
        }
    
        //Build list of links
        $links = array();
        for ($i = 0; $i < $hrefs->length; $i++) {
            $href = $hrefs->item($i);
            $url = $href->getAttribute('href');
    
            $full_url = url_to_absolute($target_url, $url);
            if (stripos($full_url, '#')) {
                $position = stripos($full_url, '#');
                $full_url = substr($full_url, 0, $position);
            }
    
            $path = parse_url($full_url, PHP_URL_PATH);
            $ext = pathinfo($path, PATHINFO_EXTENSION);
    
            if (isInSearch($full_url) && !inList($full_url, $links) && ($full_url != $target_url) && !$ext) {
                array_push($links, array('full_url' => $full_url, 'url' => $url));
            }
    
        }
    

    Така вече имах готова функция, която взема едно URL и вади всички негови наследници, като асоциативен масив с абсолютен и релативен път. Следващата стъпка беше да се направи функция, която да направи пълен списък на страниците и връзките между тях. Тук реших да направя два списъка и да опростя нещата. В първият списък пазя само имената на страниците, като на всяко име задавам ID. Във вторият списък на всяко ID ми съответства списък от ID-та, които показва всички връзки от текущата страница. Така имах готов списък от наследници, които можех да ползвам в по нататъшната обработка. Записах си резултата в два текстови файла и можех да се прехвърля в .NET среда.

    function makeSearch(&$pages) {
        $id = 0;
        $page_id = 0;
        $adj_list = array();
        while (isset($pages[$id])) {
            // find links in one url
            $url_result = findLinks($pages[$id]['full_url']);
            if ($url_result) {
                // add url to queue
                $current_list = array();
                foreach ($url_result as $url) {
                    if (!in_array($url, $pages)) {
                        $page_id++;
                        $pages[$page_id] = $url;
                        array_push($current_list, $page_id);
                    } else {
                        array_push($current_list, array_search($url, $pages));
                    }
                }
                $adj_list[$id] = $current_list;
            } else {
                unset($pages[$id]);
            }
    
            $id++;
            $countPages = count($pages);
            echo "Count pages - $id / $countPages
    ";
        }
        return $adj_list;
    }
    

    Във C# вече нещата бяха сравнително прости. Трябваше да парсна, двата файла, списъка на наследство и имената на линковете. За да пазя информацията избрах Dictionary заради бързия достъп.

            private static Dictionary<int, List> adjacencyList = new Dictionary<int, List>();
            private static Dictionary<int, Url> pages = new Dictionary<int, Url>();
    

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

                Queue queue = new Queue();
                List path = new List();
                queue.Enqueue(new Tuple<int,List>(start,new List{start}));
                HashSet visited= new HashSet();
                visited.Add(start);
    

    След това проверявам текущия елемент и ако той е решение, преминавам към печат на изхода.

                    Tuple<int, List> element = queue.Dequeue() as Tuple<int, List>;
                    if (element.Item1 == searched)
                    {
                        path = element.Item2;
                        break;
                    }
    

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

                        foreach (var link in adjacencyList[element.Item1])
                        {
                            if (!visited.Contains(link))
                            {
                                visited.Add(link);
                                List currentPath = element.Item2.ConvertAll(a => a);
                                currentPath.Add(link);
                                queue.Enqueue(new Tuple<int, List>(link, currentPath));
                            }
                        }
    

    Нещото което ми остава да покажем изхода и задачата е решена.
    Github source

  • Big Bombs

    Posted on March 3rd, 2013 Krasi Nikolov No comments

    Задачата за третия етап от конкурса на PC Magazin и Telerik, беше много интересна. За първи път имаше доста програмиране в приложната част. Правилата на играта, която трябваше да се имплементира, са сравнително прости.
    Имаме поле 101х101, защитникът разполага със солни мини, които трябва да се охраняват. Самата защита се осъществява от оборудвани пилета. Нападателят разполага с две бойни единици: Голяма бомба, която има радиус от 0 до 19, и гуци с гърмелка, което има радиус 1.5. Read the rest of this entry »

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

    Posted on December 21st, 2012 Krasi Nikolov No comments

    Представям ви нашето решение на първата задача от Конкурса по програмиране на Телерик и PC Magazine Bulgaria.

    Read the rest of this entry »