Здравейте колеги,
ще ми е интересно да споделите как "видяхте" изпита.
Аз лично не съм доволен от представянето си, тотално забих на тези suffix-и и от 12:30 до 3 само това правих....
След десетки опити така и не можах да мина performance тестовете :| и в крайна сметка набих една ламбда, колкото да минат поне correctness тестовете :)
Наистина жалко, че неможахме да си напишем (сами) първа задачка :P
От мен толкова:
Здрасти,
И аз като теб доста се чудех на suffix-ите, но към края на изпита се сетих как да ги напарвя. Това, което не се сетих е как да направя detonate-а бърз(само половината от тестовете му за бързина ми минаха). Всичко друго мина на моя компютър и само този detonate ми остана:)
Иначе, ако някой иска да види как аз съм подходил, ето моето решението:
Май направихме темите по едно и също време. Няма смисъл според мен да се използва Reverse в компаратора при положение, че стриновете могат да се обходят с обратен фор. А ако все пак се ползва по-добре да е:
str = str.Reverse().ToString();
a не:
str = new string(str.Reverse().ToArray());
Като цяло задачата беше много готина - поздравления на авторите.
Ето го и моето решение ако някой му е интересно. Със сигурност имам някоя излишна структура - bunnysByTeam сравнително лесно може да се махне.
Тестовете (PerformanceDetonate_WithOneBunnyDetonatingMultipleTimes_With10000BunniesInOneRoomInDifferentTeams го подкарах след изпита)
char.MaxValue + suffix .... (как не се естих)
заспала работа моята :D, пробвах с RangeFrom, RangeTo, пробвах при добавянето да вкарвам всеки възможен съфикс в речник suffix,orderedset<bunny> ... но това не ми дойде на акъла :D
Здраве да е!
Наистина поздравления за задачката, беше забавна :)
Убии ме, това решение за suffix-а откъм performance нямаше да се сетя. PerformanceDetonate_WithOneBunnyDetonatingMultipleTimes_With10000BunniesInOneRoomInDifferentTeams теста ми минаваше през по-голяма част от времето 50/50 (а мине а не) но в един момент реши да минава всеки път но доста близко до границата >_>
Ще споделиш ли как си направил suffix-a?
ПС: имах същия проблем с детонейт
Наистина беше интересна задачата и си падна бая главоблъскане, изгубих доста време в това да сменям структури, докато най-накрая оцеля тези, които всъшност ми бяха най-подходящи, и от там не ми остана време да си поблъскам главата повечко за performance на suffix-ите, може би ако имах още 30-40 минути, щях да ги хвана, просто не можех да си напасна правилното използване на рейндж. Гърмят ми и 2 performance теста на детонейта, там ми е бая мазало, трябва да разгледам някое решение с бърз детонейт.
Здравейте,
Ето и моето решение. Всички тестове ми минаха 
Частта със suffix-ите съм я решил по малко бавен начин и в началото не минаваше всичко, но добавих оптимизация - като един suffix мине, след това, ако се повтори, вече го имам в dictionary :)
Detonator-ът ми мина бързо - тук просто добавих още един речник от стаи със зайчетата, разделени по отбори във всяка стая и така лесно отсявах тези от същия тим.
Частта със стаите една до друга я реших по не много оптимален начин, но сметнах, че в случая по-добре лист, от колкото LinkedList - не мислех, че ще ми се налага често да добавям в началото.
https://github.com/ktodorovv/Data-Structures-Exam-27-March-2016/
Здравейте,
И на мен ми хареса задачата.
Относно suffix-ите, като видях в условието, че трябва да са сортирани по ASCII кода на обърнатото име, ми дойде на акъла да пазя обърнатите имена в OrderedDictionary с обикновен Ordinal Comparator, който не се налага да си пиша сам и да сведа търсенето по суфикс, до търсене по префикс.
А относно това:
str = str.Reverse().ToString();Няма да работи, защото ToString() ще върне нещо подобно:
System.Linq.Enumerable+<ReverseIterator>d__74`1[System.Char]Аз лично обръщах имената с:
Ето го моето решение:
https://github.com/psdimitrov/DataStructures/tree/master/Exam/BunnyWars
Поздрави!
Прав си, че няма да стане обръщането както съм го написал горе, но аз реално го правих с обратен фор, а това го писах без да го тествам.
Много забавно начало и много яка задача!! :Д
Да споделя и аз неволя :))
1) Неможах да си изтегля за доста дълго време Wintellect-a , заради прекаленото дълго име на пътя на проекта!!! :D
2) Още една обеца на ухото - Ползвах suffix функцията от First-Last, и не се усетих да махна цикъла tring.EndsWith" ", понеже дървото си ми ги дава подредени през компаратора :))
3) Също така не се усетих, че структурата OrderedDictionary<string,SortedSet<Bunny>> която ползвах за вземане на заек (ползвах я в почти всички функции свързани с BunnyName и т.н.- която ползваше компаратора, ми забави всичките функции.
Попитах Наско защо ми се забавиха всички функции - еми не трябва да се ползва тази структура освен за List Preffix-a! :D докато се усетя обаче - още загуба на време - и трябваше да си правя нова за вземането на зайци :))
Докато смелям всичко и неусетно времето мина, точно накрая мъчих само 3-те последни Performance за List Suffix - и не успях да си предам на време оправената функция от 2)
Готин изпит и много ценни уроци дава всеки път!
Поздрави и успех на занапред!
Владо
Всички материали от изпита (условия, скелети, авторски решения) са качени в страницата на курса.
Резултати може да очаквате до началото на курса по Алгоритми.
Като обобщение решението е следното:
А как става next / previous? Понеже е OrderedDictionary и стаите са подредени, RangeFrom(roomId, false) връща всички стаи след текущата и с Take(1) можем да вземем следващата.
Същото е и с Previous, само че ползваме RangeTo(roomId, false), за да получим енумератор за всички стаи преди текущата. Даваме .Reversed(), за да обхожда енумераторът наобратно, и пак вземаме първата.
this.rooms.RangeFrom(roomId, false).Take(1);
this.rooms.RangeTo(roomId, false).Reversed().Take(1);
Друг вариант е да пазим стаите в един допълнителен OrderedSet<int> и да ползваме IndexOf(roomId), за да вземем индекса на стаята в черно-червеното дърво отдолу. Оттам нататък казваме roomsSet[index + 1] или roomsSet[index - 1].
Остават 2 метода:
public class OrdinalSuffixComparator : IComparer<Bunny>
{
public int Compare(Bunny bunnyX, Bunny bunnyY)
{
var x = bunnyX.Name;
var y = bunnyY.Name;
for (int iX = x.Length - 1, iY = y.Length - 1;
iX >= 0 && iY >= 0; iX--, iY--)
{
if (x[iX] > y[iY]) return 1;
if (x[iX] < y[iY]) return -1;
}
if (x.Length == y.Length) return 0;
if (x.Length > y.Length) return 1;
return -1;
}
}
Имайки зайците подредени по това правило, можем да ги извлечем с един Range().
var low = new Bunny(suffix, 0, 0);
var high = new Bunny(char.MaxValue + suffix, 0, 0);
return this.bunniesOrderedBySuffix.Range(low, true, high, false);
Всички имена по-големи или равни на suffix или започват с него, или са с по-големи символи. За да не хванем и "по-големите" стрингове, слагаме горна граница char.MaxValue + suffix. По условие всички имена ще са с латински букви или цифри. Т.е. няма да има символ с по-голям ASCII код от MaxValue. Следователно, ако един стринг е по-голям от горната граница, то значи някой символ след MaxValue e по-голям -> има различен суфикс и затова попада извън горната граница.
Радвам се, че задачата ви е харесала. Мога само да съжалявам за първа, но пък нищо не пречи да си я решите сега (ще ви трябва за алгоритмите :D).
Здравейте, тъй като трябваше да очакваме резултати до началото на круса по алгоритми, а курсът започва днес. Аз все още нямам резултат от изпита, и при другите явили се колеги ли е така?
Не мисля че проблема е при теб, просто оценките не са излезли. (и при мен няма)
Значи, все още чакаме. :)
Колеги, мина доста време от изпита, все още ли нямате резултати?
Май се оказа доста трудоемко оценяването на 1 задача с написани Unit тестове при положение, че резултатите се очакваха са излязат около 5-ти, а днес сме 11-ти.
Някой с по-актуална информация кога да очакваме резултати?
20 минути сигурно убих за единия тест на Detonate докато се усетя, че всъщност напразно обхождам колекциите когато имаш само 1 team. Една бърза проверка в началото дали броя на отборите е <= 1 и всичко полетя в зелено за тоя метод :)