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

  • Изпит в Софтуерната Академия на Телерик – C# втора част

    Posted on February 11th, 2013 Krasi Nikolov No comments

    Записах се за изпит за първата възможна дата, защото напоследък съм затрупан от ангажименти и ми се щеше да отпиша поне C# от списъка с проблеми за решаване. Като подготовка за изпита, реших няколко задачи от миналогодишните и не бях особено обнадежден. От една страна, за решаването на всяка задача ми отиваха поне 2-3 часа, от друга страна стигаха до 80-90%. Нямах нито една задача на 100%, всеки път достигах до time limit. Read the rest of this entry »

  • Сортиране чрез сливане

    Posted on January 10th, 2013 Krasi Nikolov No comments

    Ще се постарая накратко и възможно най- просто да обясня, как може да се напише клас на c#, който сортира масив по рекурсивния метод.
    Първо накратко да обясня, какво представлява метода за сортиране чрез сливане. Взема се един масив с n елемента и се разделя на n отделни масива с по 1 елемент. След това на всяка стъпка, всеки масив се обединява със следващия и се сортира. Например ако имаме един масив с 8 елемента, той се дели на 8 масива с по един елемент. На първа стъпка, първият се сравнява със втория, третия с четвъртия… и така се получават 4 масива с по 2 подредени елемента. Същата операция се повтаря и с вече подредените масив, докато накрая не остане само един подреден масив.
    А сега да обясня, как аз решавам този проблем.
    Read the rest of this entry »

  • Triple Rotation Of Digits

    Posted on December 29th, 2012 Krasi Nikolov No comments
    using System;
     
    class Program
    {
        static void Main()
        {
            int k = int.Parse(Console.ReadLine());
            for (int i = 0; i < 3; i++)
            {
                int count = CountNumbers(k);
                if (count == 1)
                {
                    break;
                }
                int lastDigit = k % 10;
                k = k / 10;
                for (int j = 0; j < count-1; j++)
                {
                    lastDigit *= 10;
                }
                k = lastDigit + k;
            }
            Console.WriteLine(k);
        }
        static int CountNumbers(int n)
        {
            int count = 0;
            do
            {
                n = n / 10;
                count++;
            } while (n> 0);
            return count;
        }
    }
    

    Read the rest of this entry »

  • Poker

    Posted on December 29th, 2012 Krasi Nikolov No comments

    На тази задача, доста се затрудних със “Streight”. Все още не бях направил, да тества А 2 3 4 5 6, но проверката през bgcoder ми даваше 100 %. Загубих още 1 час затова, бях 500/500, но ми се щеше задачите да са верни.

    using System;
    
    class Poker
    {
        static void Main()
        {
            string result;
            int[] cards = new int[5];
            for (int i = 0; i < 5; i++)
            {
                cards[i] = StringToNumber(Console.ReadLine());
            }
            Array.Sort(cards);
            bool isStraight = false;
            if (cards[0] == cards[4])
            {
                result = "Impossible";
            }
            else if ((cards[0] == cards[3]) || (cards[1] == cards[4]))
            {
                result = "Four of a Kind";
            }
            else if (((cards[0] == cards[2]) && (cards[3] == cards[4])) ||
                ((cards[0] == cards[1]) && (cards[2] == cards[4])))
            {
                result = "Full House";
            }
    
            else if (IsStraight(cards))
            {
                result = "Straight";
            }
            else if ((cards[0] == cards[2]) || (cards[1] == cards[3]) || (cards[2] == cards[4]))
            {
                result = "Three of a Kind";
            }
            else if (((cards[0] == cards[1]) && (cards[2] == cards[3])) ||
                ((cards[0] == cards[1]) && (cards[3] == cards[4])) ||
                ((cards[1] == cards[2]) && (cards[3] == cards[4])))
            {
                result = "Two Pairs";
            }
            else if ((cards[0] == cards[1]) || (cards[1] == cards[2]) || (cards[2] == cards[3]) ||
                (cards[3] == cards[4]))
            {
                result = "One Pair";
            }
            else
            {
                result = "Nothing";
            }
            Console.WriteLine(result);
        }
    
    
    
    
        static bool IsStraight(int[] card)
        {
            int[] current = card;
            bool isStraight = true;
            for (int i = 1; i < current.Length; i++)
            {
    
                if ((current[i] != current[i - 1] + 1) && (current[i] != current[i - 1] + 9))
                {
                    isStraight = false;
                    break;
                }
            }
    
            return isStraight;
        }
    
        static int StringToNumber(string text)
        {
            int number = 0;
            switch (text)
            {
                case "J":
                    number = 11;
                    break;
                case "Q":
                    number = 12;
                    break;
                case "K":
                    number = 13;
                    break;
                case "A":
                    number = 14;
                    break;
                default:
                    number = int.Parse(text);
                    break;
            }
            return number;
        }
    }