Здрасти,

И аз като теб доста се чудех на suffix-ите, но към края на изпита се сетих как да ги напарвя. Това, което не се сетих е как да направя detonate-а бърз(само половината от тестовете му за бързина ми минаха). Всичко друго мина на моя компютър и само този detonate ми остана:)

Иначе, ако някой иска да види как аз съм подходил, ето моето решението: 

https://github.com/krasi070/DataStructures/tree/master/Exam

Май направихме темите по едно и също време. Няма смисъл според мен да се използва Reverse в компаратора при положение, че стриновете могат да се обходят с обратен фор. А ако все пак се ползва по-добре да е:

str = str.Reverse().ToString();

a не:

str = new string(str.Reverse().ToArray());

Като цяло задачата беше много готина - поздравления на авторите.

Ето го и моето решение ако някой му е интересно. Със сигурност имам някоя излишна структура - bunnysByTeam сравнително лесно може да се махне.

Тестовете (PerformanceDetonate_WithOneBunnyDetonatingMultipleTimes_With10000BunniesInOneRoomInDifferentTeams го подкарах след изпита)

Наистина беше интересна задачата и си падна бая главоблъскане, изгубих доста време в това да сменям структури, докато най-накрая оцеля тези, които всъшност ми бяха най-подходящи, и от там не ми остана време да си поблъскам главата повечко за 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, който не се налага да си пиша сам и да сведа търсенето по суфикс, до търсене по префикс.

А относно това:

Няма да работи, защото ToString() ще върне нещо подобно:

 Аз лично обръщах имената с:

Ето го моето решение:

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)

Готин изпит и много ценни уроци дава всеки път!

Поздрави и успех на занапред!

Владо

Всички материали от изпита (условия, скелети, авторски решения) са качени в страницата на курса.

Резултати може да очаквате до началото на курса по Алгоритми.

Като обобщение решението е следното:

• "Главната структура", в която пазим всички зайци е Dictionary<string, Bunny> за бързо добавяне / търсене / триене.
• Оттук нататък ни трябват операциите AddRoom, RemoveRoom (бързо добавяне/триене на стая) и Previous/Next (трябва ни ред, за да достъпим съседните стаи). За да имаме подредба и бързо добавяне / търсене / триене на стаи, ползваме подредено дърво (Ordered-нещо си). Може би OrderedSet<int>.
  • Detonate (бие демидж на зайци от чужд отбор в стаята) -> очевидно изисква пазене на зайци за съотвена стая. Следоветелно горната структура може би е OrderedDictionary<int, List<Bunny>>. Обаче при детонация трябва да проверяваме всеки един заек дали е от различен тийм. При наличието на тестове от сорта 10000 заека от 1 тийм в 1 стая това ще е бавно. Затова я модифицираме на OrderedDictionary<int, List<Bunny>[]>. С други думи пазим стаите подредени и за всяка - масив от отборите (защото са винаги най-много 5). А за всеки един отбор пазим зайците в него.
  • По условие обаче Detonate може да убие зайци и те ще трябва да бъдат премахнати. Триенето в List е O(n), затова можем да жертваме памет за сметка на бързо триене като използваме LinkedList. И като резултат имаме OrderedDictionary<int, LinkedList<Bunny>[]>.

А как става 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 метода:

• ListBunniesByTeam по име в низходящ ред. Имаме фиксиран брой отбори и за всеки един трябва да пазим зайците подредени -> OrderedSet<Bunny>[]. В метода връщаме bunniesByTeam[team].Reversed().
• ListBunniesBySuffix, сортирани по име в обратен ред (отзад-напред по стринга) -> ползваме OrderedSet<Bunny>. Тук подредбата е по-интересна и трябва да подадем custom comparator, който да сравнява както е описано в условието. Този comparator e де факто Ordinal, с тази разлика, че е наобратно. Tочно както на подготовката си написахме компаратор за префиксите, така и в тази задача правим същия, но сега цикълът започва от края на стринговете:

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-ти.

Някой с по-актуална информация кога да очакваме резултати?