IT Blog
RSS icon Email icon
  • Битката за гьола – финален кръг

    Posted on June 29th, 2013 Krasi Nikolov No comments

    За начало може би е добре накратко да опиша, каква беше задачата за финалния кръг на конкурса. Даден е един гьол с радиус 100. В този гьол разполагаме две жаби с радиус 3.5, едната жаба я управляваме ние а другата се управлява от чужд алгоритъм. Играта протича на етапи, като на всеки етап размера на гьола намалява с единици. За всеки етап всяка жаба може да скача на разстояние 2. Освен това жабите могат да изстрелват куршуми, които се движат със скорост 10 единици за етап. След всеки изстрел, жабата трябва да презареди, т.е. жабата има право да стреля отново след 7 етапа. Всяка жаба която излезе от гьола или бъде уцелена от куршум умира. Пълните правила може да видите на сайта на конкурса – условие
    След като анализирахме условието на задачата стигнахме до следните изводи:
    1. Жабата може да избяга от куршум, ако разстоянието до него е по- голямо от 23.5.
    2. Във връзка с първото, ако двете жаби се приближават, нашата жаба трябва да спре да стреля на разстояние 53.5. Така ще може да сме презаредили и да стреляме на разстояние по- малко от 23.5
    Следващото нещо което ни направи впечатление, беше че жабата ни може да избяга единствено ако не е близо до ръба на гьола. Когато сме на ръба, може да се окаже, че за да избягаме, трябва да напуснем кръга. Това вече драстично усложняваше задачата на нашата жаба, така стигнахме до извода, че не е много добре да сме близо до ръба и всяка жаба близо до ръба ще бъде затруднена. Така стратегията на нашата жаба се състоеше от няколко много прости правила за нейното поведение:
    1. Жабата върви право към центъра, така стоим максимално далеч от ръба на гьола.
    2. Когато стигнем центъра оставаме там.
    3. Стреляме непрекъснато докато сме на разстояние по- голямо от 56.
    4. Ако разстоянието падне под 56, спираме да стреляме за да може да презаредим до 23.5
    5. Когато разстоянието до противника падне под 23.5 стреляме. Той вече не може да бяга.
    6. Ако забележим противников куршум на разстояние под 33.5 избягваме изстрела, в посока перпендикулярна на треакторията на изстрела. След това продължаваме по посока на центъра.
    Нека да покажа най- важните елементи от нашия код.

            static void Main(string[] args)
            {
                Dangerous = new List<Point>();
                ReadInput();
                if (Dangerous.Count > 0)
                {
                    Point escapePoint = FindEscapeDirection();
                    Console.WriteLine("move " + escapePoint.X + " " + escapePoint.Y);
                }
                else
                {
                    Console.WriteLine("move 0 0");
                }
                double distanceToEnemy = FindDistance(MyFrog.Position, EnemyFrog.Position);
                if ((distanceToEnemy > 56 || distanceToEnemy < 23.5) && MyFrog.CanShootAfter == 0)
                {
                    Console.WriteLine("shoot " + EnemyFrog.Position.X + " " + EnemyFrog.Position.Y);
                }
                else
                {
                    Console.WriteLine();
                }
            }
    

    Това е основната логика по която работи нашия алгоритъм. Нещото което не се вижда тук е, че Dangerous е списък от точките по които биха преминали опасните противникови куршуми. Опасни са куршуми които са на разстояние по малко от 33.5.

                BulletsCount = int.Parse(Console.ReadLine());
                if (BulletsCount > 0)
                {
                    Bullets = new Bullet[BulletsCount];
                    for (int i = 0; i < BulletsCount; i++)
                    {
                        string[] line = Console.ReadLine().Split(' ');
                        Bullets[i] = new Bullet()
                        {
                            From = new Point() { X = double.Parse(line[0]), Y = double.Parse(line[1]) },
                            To = new Point() { X = double.Parse(line[2]), Y = double.Parse(line[3]) }
                        };
                        FindDangerousPoints(Bullets[i]);
                    }
                }
    

    Тук четем куршумите на полето и ги изпращаме във FindDangerousPoints(Bullets[i]); където проверяваме дали има опасни.
    Това е самата проверка за опасни куршуми.

            private static void FindDangerousPoints(Bullet bullet)
            {
                double deltaX = (bullet.To.X - bullet.From.X) / 10;
                double deltaY = (bullet.To.Y - bullet.From.Y) / 10;
                double oldDistance = FindDistance(bullet.From, MyFrog.Position);
                Point point = new Point() { X = bullet.From.X + deltaX, Y = bullet.From.Y + deltaY };
                double currentDistance = FindDistance(point, MyFrog.Position);
                if (oldDistance > currentDistance && currentDistance < 30)
                {
                    bool dangerousAdded = false;
                    while (oldDistance > currentDistance)
                    {
                        var oldPoint = new Point() { X = point.X, Y = point.Y };
                        if (currentDistance < 4.5)
                        {
                            Dangerous.Add(oldPoint);
                            dangerousAdded = true;
                        }
                        oldDistance = currentDistance;
                        point.X += deltaX;
                        point.Y += deltaY;
                        currentDistance = FindDistance(point, MyFrog.Position);
                    }
                    if (dangerousAdded)
                    {
                        Dangerous.Add(point);
                    }              
                }
            }
    

    Двете условия за опасни куршуми са:
    1. oldDistance > currentDistance – проверяваме да ли куршума се приближава.
    2. currentDistance < 30 - проверяваме дали е в опасна близост В общи линии до тук нещата са тривиални, но нещото с което наистина се гордея е начина по които пресмятам посоката за бягство на жабата. За да го сметна вземам две последователни ударни точки на куршум и спрямо тях изчислявам посока за перпендикулярно бягство. [sourcecode language="csharp"] private static Point FindEscapeDirection() { Point escapePoint = new Point(); if (Dangerous.Count == 1) { double deltaX = MyFrog.Position.X - Dangerous[0].X; double deltaY = MyFrog.Position.Y - Dangerous[0].Y; escapePoint.X = MyFrog.Position.X + deltaX; escapePoint.Y = MyFrog.Position.Y + deltaY; } else { double deltaX = Dangerous[0].Y - Dangerous[1].Y; double deltaY = Dangerous[0].X - Dangerous[1].X; escapePoint.X = MyFrog.Position.X - 2*deltaX; escapePoint.Y = MyFrog.Position.Y + 2*deltaY; } return escapePoint; } [/sourcecode] Това е цялата логика по- която работи нашия алгоритъм. Написахме го за не повече то 5-6 часа и смятахме, че ще имаме достатъчно време за приложната част. По голяма част от времето на финалния кръг отделихме за приложната част, която за съжаление не успяхме да завършим. Приложната ни част представлява, MVC 4 приложение, което при всеки ход подава входа към два алгоритъма. Взема техния отговор, обработва го и го подава към UI. Със съвсем леки модификации нашето приложение, може да работи като игра между човек и алгоритъм. За съжаление, отделихме прекалено много време за бек-енда и накрая просто не успяхме да зъвършим фронт-енда. Тук може да намерите целият код, на нашия алгоритъм и приложение. - код
    Тук може да видите резултатите от нашето участие. – резултати

  • От интернет батка

    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 »