Интересна задача за любопитните


24

Здравейте,

Ники измисли една интересна задача, която няма как да има авторско решение. Даден ви е български тест и вие трябва да познаете дали определени думи са място или човек. Чекера на задачата е малко по-различен. Ще ви признае теста за верен, ако уцелите поне 35% от думите

Задачата можете да видите тук:

CLICK

Казва се "Познай името". Има и условие, и сорс код на самия чекер, в случай, че искате да го разгледате.

За да е по-интересно организираме състезание със символични награди - кой ще успее да напише най-интересен алгоритъм и да хване най-много точки на задачата в BGCoder. Краен срок: 2 февруари 23:59. Ако двама имат еднакъв брой точки ще гледаме кой пръв е изпратил решението си, т.е. който е бил по-бърз. Решавайте в линка, който съм посочил. Другите задачи в състезанието ги игнорирайте.

Ще гледаме решенията дали са смислени, а не хакерски. Събмити, които правят магии с рандъм, нагласяния спрямо тестовите резултати и т.н., ще бъдат дисквалифицирани. Само смислените решения се борят за награда.

Успех!

Поздрави,

Ивайло




Отговори



6

Здравейте,

Най-добрите решения със 100 точки са:

Rusekov

hiksa

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

Поздравления, надявам се да ви е било интересно!

Ивайло


от ivaylo.kenov (30760 точки)


0

Колеги, само аз ли съм толкова тъп та не успявам да преодолея ограничението от 256 символа за линия при четене от конзолата?! Прерових Интернет, играх си с настройките на самата конзола като буфер и шрифт, пробвах и най-различни варианти в самия код. Ето някои от тях:

1. Най-елемeнтарното:

 Console.SetBufferSize(width, height);

- Но все пак width не мога да го докарам до 3500 - колкото е допустимата дължина на стринга по задание.

2. Пренасочване на входа към поток:

 static string ReadLine()

    {
        //Console.InputEncoding = System.Text.Encoding.UTF8;
        Stream inputStream =     Console.OpenStandardInput(3500);
        string p = inputStream.ToString();
        byte[] bytes = new byte[3500];
        int outputLength = inputStream.Read(bytes, 0, 3500);
        char[] chars = Encoding.UTF8.GetChars(bytes, 0, outputLength);
        return new string(chars);        
    }
 
- Супер! Прочита целия стринг, но... OpenStandardInput работи с UTF 7 - съответно ми се получават съвсем различни символи от очакваните. Ако опитам да сетна преди това InputEncoding-a на UTF8 пък съвсем нищо не прочита.
 
3. Console.SetIn(new StreamReader(Console.OpenStandardInput(3500)));
- Същия резултат...
 
4. Четене символ по символ и конструиране на стринг с помощта на STringBuilder:
 
static string ReadLine2()
    {
       StringBuilder input = new StringBuilder();
        char ch = Convert.ToChar(Console.Read());
        while (ch != '\n') 
        {
              input.Append(ch);
           ch = Convert.ToChar(Console.Read());
        }
       return input.ToString();
    }
 
 
Ще съм благодарен ако ми обърнете внимание какво пропускам!
 

от STzvetkov (1330 точки)


0
Това ограничение е валидно само когато въвеждаш теста на ръка от черното екранче на конзолата. Не се притеснявай - в БГКодер-а няма такова ограничение. Просто избирай по-кратки тестове когато опитваш разни варианти с копи/пейст в конзолата.

от JulianG (5316 точки)

0
...или втори вариант е (за по-дълъг текст) да го вкараш в един файл и да го четеш от там.

от Flystar (1171 точки)



0
Позволено ли е през БГКодер да отворя google и да гледам броя резултати на да речем "Asparuh born at", "Asparuh location"

от hbuyukliev (0 точки)


0
Сървъра не дава достъп на изпратените решения до Интернет с оглед на сигурността. commented 5 hours ago by Ивайло Кенов Senior Ninja



2

Когато опитам да кача решението си, BGcoder го отхвърля и ми изкарва ето това съобщение:

"Èçïðàòåíèÿò êîä å ïðåêàëåíî äúëúã!"

Предполагам че проблема е в дължината на кода (6790 реда е), но може да е и нещо друго.
Някой може ли да обясни това?


от lokiko91 (790 точки)


0
7000 реда код? Ти си нечовек направо :) И.. да, най-вероятно проблема е в дължината на кода. В условието има това: "Максималният размер на сорс кода е 200 Kb." Замисли се все пак защо ти излизат такива "маймуни" вместо нормална кирилица. Нещо по регионалните настройки да си забравил?

от JulianG (5316 точки)

0
Wow, кво правиш за 7000 реда? Наистина ми е интересно

от hbuyukliev (0 точки)



0
Два въпроса по темата:
1. Проблем ли е, че събмитвам доста често код по задачата в BGCoder? Пиша малко наизуст в момента (разполагам само с code editor, а онлайн компилаторите, които намерих, не вършат работа за конкретната задача) и съответно не мога да дебъгвам с мои примери като си правя оптимизации по кода.
2. Последният тест ли смениха преди малко? Както си имах 50т. изведнъж станаха 60 с верен отговор на последния, без да съм събмитвал ново решение.
- В този ред на мисли: поздравления на колегата с пълен актив! При това цели два дни преди изтичане на срока :-)

от STzvetkov (1330 точки)


0
Единият тест беше грешен и го сменихме.

от ivaylo.kenov (30760 точки)


0
Две думи колеги.. Лексикална Семантика :D Тъкмо се разрових малко и взе да дава резултати с един приятел тук сме седнали да се мъчим.

от Plamen_Petkov (1255 точки)


9
Rusekov 100 / 100

Само че държа да уточня, че нито решението е добро, нито кода е добре написан, защото ООП-то ми е по-важно в момента и просто заради предизвикатеслтвото се включих :)

Освен това на пети тест верният отговор не е достигнат съвсем по правилата, така че реално мисля, че 90 точки съм ги хванал :)


от Rusekov (971 точки)


0
Браво, колега! Аз деля 3-тото място с още петима ентусиасти с далеч по-скромните 60т. :-)
И моят код не е кой знае колко добре струткуриран, но затова пък е кратичък: малко над 200 реда заедно с всичките "направи си сам" списъци със стандартни окончания, наречия, предлози и определителнисъществителни. Не съм чел теория по въпроса, не съм ползвал и речници. Просто си съчиних нещо, то пък се оказа, че работи (е, поне отчасти :-) Ето и кода:http://pastebin.com/1CKEEBzZ
Опитите ми да оптимизирам алгоритъма с прилагане на псевдо-статистически анализ не се увенчаха с кой знае какъв успех. Предполагам, че Николай не е искал да ни усложнява живота с тектове, в които дадено име се среща повече от веднъж :)

от STzvetkov (1330 точки)

0
Те редовете код са много условно понятие щом се ползват масиви :), а иначе Николай със сигурност ни е "усложнил живота" с повторения на имена повече от веднъж ;) П.П. Сетих се нещо. Според теб колко точки ще хванеш на този тест:
Булевард Христо Ботев е един от централните софийски булеварди и носи името на българския революционер и поет Христо Ботев. 2 Христо Ботев Христо Ботев
аз (-1) :))

от Rusekov (971 точки)



3
Здравейте колеги,
ето и моето решение на задачата за 100 точки. 
 
 
За който има интерес да разгледа решението ще обясня накратко.
 
Общо взето използваме 4 списъка от стрингове с помощта на които определяме дали даденото име е име на човек или на място. В случая използвам HashSet<string> тъй като за нуждите на програмата използвам само .Contains метода, който при HashSet има сложност единица докато при List<string> сложността е в линейна зависимост от бройката елементи които претърсваме. 
 
Първите два списъка са по-кратки и съдържат думи (или части от думи), които е много вероятно да се съдържат в самото име.
 
Завъртаме по един foreach и гледаме дали някоя (или повече) от ключовите думи, отговарящи за личност и място не се съдържа в името. За всяко срещане увеличаваме съответния брояч (имаме по един брояч за личност и място). Също правим и някои други проверки, като например дали след като сплитнем името някой от получените стрингове не завършва на някое от характерните за български фамилни имена окончания (ев, ов, ски и т.н.), като за всяко съвпадение отново увеличаваме брояча.
 
След тази поредица от проверки сравняваме броячите. Ако стойностите са различни, взимаме по-голямата и директно печатаме отговор. Ако стойностите са равни правим втората и по-задълбочена проверка използвайки другите два списъка ключови думи.
 
При втората проверка взимаме думите предхождащи въпросното име, както и думата след него. Проверяваме дали някоя от съседните думи не се съдържа в някой от списъците. Отново използваме броячи за запазване на броя съвпадения. Въпросните операции се изпълняват за всяко срещане на името във текста, тъй като ако името се среща повече от веднъж така е по-вероятно да нацелим правилно. Една от оптимизациите, които добавих в последствие е при взимане на съседните думи да се взимат предвид препинателните знаци белязващи край на изречение, тоест ако името е първа дума в изречението няма да вземем нищо от текста преди това.
 
Накрая сравняваме броячите и гледаме къде има повече точки. Ако са равни печатаме Unknown. Ако има разлика правим една финална проверка. В случай че единият от броячите има две или повече точки, а вторият има само с една точка по малко (2-1 или 3-2) отново избираме отговор Unknown с цел да избегнем загуба на точки (-2 е доста по неприятен резултат от 0 особено за тестовете с по-малко имена за проверка). В останалите случаи печатаме Person или Place в зависимост от натрупаните точки на всеки брояч.
 
Списъците с думи не са ми перфектни и сега като гледам решението на колегата STzvetkov бих взел назаем сигурно половината от неговите думи, но все пак нали принципа е важен :)
 
В общи линии това. Рефакторирах кода за да е по-четим, но пак са си 270 реда в 10 метода.
 
Благодарности на Ники за интересната задача, беше удоволствие :)



0
Много добро решение :) аз за претегляне на резултата и подаване на unknown при разлика в отговорите се сетих чак като написах примера с Христо Ботев :)

от Rusekov (971 точки)

0
Мерси колега, поздравления и на теб за високия резултат. Интересно ще ми е да разгледам и твоето решение а също така и на другите колеги потрудили се над задачата. Хвърлих доста размисли над решението и ще ми е интересно да видя и други как са подходили и какви проверки са направили.