Coś mnie wzięło i zacząłem robić Daily Challenge na LeetCode.
Zwykle kręciłem się w czołówce a nawet dostarczałem najszybsze rozwiązanie.
Wczoraj niestety przerwałem serię i nie dostarczyłem działającego rozwiązania na czas.
Chodzi o ten problem:
Find All People With Secret - LeetCode
2092. Find All People With Secret
You are given an integer
nindicating there arenpeople numbered from0ton - 1. You are also given a 0-indexed 2D integer arraymeetingswheremeetings[i] = [xi, yi, timei]indicates that personxiand personyihave a meeting attimei. A person may attend multiple meetings at the same time. Finally, you are given an integerfirstPerson.Person
0has a secret and initially shares the secret with a personfirstPersonat time0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a personxihas the secret attimei, then they will share the secret with personyi, and vice versa.The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.
Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.
Koniec końców napisałem coś co jest dwa razy szybsze niż najlżejszy kod na LeetCode, ale nie przechodzi testów na LeetCode.
Co dziwne ten sam test u mnie działa poprawnie.
Jako, że dorobiłem jest z dużymi danymi dopisałem kod, który czyta JSon danymi testowymi z pliku.
Pytanie, jakim cudem ten sam test przechodzi na mjejm maszynie (Apple Clang 15.0 + ASan & UBSan) and na LeetCode pada (clang 17.0)?
Moje rozwiązanie, które powinno działać:
class Groups {
public:
explicit Groups(int itemCount) : mGroups(itemCount) {
int i = 0;
for (auto& item : mGroups) {
item = GroupItem(i);
++i;
}
}
void join(int a, int b)
{
auto groupA = mGroups[a];
auto groupB = mGroups[b];
if (groupA.root != groupB.root) {
if (groupA.root > groupB.root) {
std::swap(a, b);
std::swap(groupA, groupB);
}
mGroups[findLastIn(a)].next = groupB.root;
assingNewRoot(groupB.root, groupA.root);
}
}
void clearNoneZeroGroups()
{
auto id = 0;
for(auto& item : mGroups)
{
if (item.root)
{
item = GroupItem{id};
}
++id;
}
}
std::vector<int> groupIndexes(int i) const noexcept
{
std::vector<int> result;
result.reserve(mGroups.size());
result.push_back(i);
while (mGroups[i].next != i) {
i = mGroups[i].next;
result.push_back(i);
}
return result;
}
private:
int findLastIn(int i) {
while (mGroups[i].next != i) {
i = mGroups[i].next;
}
return i;
}
void assingNewRoot(int from, int to)
{
mGroups[from].root = to;
while (mGroups[from].next != from) {
mGroups[from].root = to;
from = mGroups[from].next;
}
}
private:
struct GroupItem {
int root;
int next;
GroupItem() {}
explicit GroupItem(int x) : root{x}, next{x}
{}
};
std::vector<GroupItem> mGroups;
};
class Solution {
public:
std::vector<int> findAllPeople(int n, std::vector<std::vector<int>>& meetings, int firstPerson)
{
std::sort(meetings.begin(), meetings.end(), [](const auto& a, const auto& b) { return a[2] < b[2]; });
Groups groups{n};
groups.join(0, firstPerson);
int lastMeetingTime = 0;
for (auto& meeting : meetings) {
auto time = meeting[2];
if (time != lastMeetingTime) {
groups.clearNoneZeroGroups();
}
lastMeetingTime = time;
groups.join(meeting[0], meeting[1]);
}
return groups.groupIndexes(0);
}
};
Wystawiłem tez github jak ktoś chce sprawdzić testy i benchmarka: https://github.com/MarekR22/LeetCodeFindAllPeopleWihtSecret
PYTANIE
Widzi ktoś z was gdzie leży problem? Jakim cudem ten same dane testowe dają różny wynik na LeetCode i lokalnie?
kod testów:
TEMPLATE_TEST_CASE("findAllPeople", "[solutions]", my2::Solution, leetcode::Solution, my::Solution)
{
using Catch::Matchers::UnorderedEquals;
auto d = GENERATE(values<test_data::Data>({
{
6,
{ { 1, 2, 5 }, { 2, 3, 8 }, { 1, 5, 10 } },
1,
{ 0, 1, 2, 3, 5 },
},
{
4,
{ { 3, 1, 3 }, { 1, 2, 2 }, { 0, 3, 3 } },
3,
{ 0, 1, 3 },
},
{
5,
{ { 3, 4, 2 }, { 1, 2, 1 }, { 2, 3, 1 } },
1,
{ 0, 1, 2, 3, 4 },
},
{
5,
{ { 4, 3, 1 }, { 3, 2, 1 }, { 2, 1, 1 } },
4,
{ 0, 1, 2, 3, 4 }
},
{
5,
{ { 4, 3, 2 }, { 3, 2, 2 }, { 2, 1, 1 } },
4,
{ 0, 2, 3, 4 }
},
{
5,
{ { 4, 3, 3 }, { 3, 2, 2 }, { 2, 1, 1 } },
4,
{ 0, 3, 4 }
},
lazyLargeTestData(),
}));
CAPTURE(d.n, d.meetings, d.first_person);
TestType solution;
REQUIRE_THAT(solution.findAllPeople(d.n, d.meetings, d.first_person), UnorderedEquals(d.expected));
}
LeetCode twierdzi, że mój kod generuje odpowiedź:
[0,10000,9991,9992,9993,9994,9995,9996,9997,9998,9999,10001]
Gdy tymczasem odpowiedź powinna zawierać wszystkie kolejne liczby od 0 do 10001 (w dowolnej kolejności).
I taką odpowiedź uzyskuje na swojej maszynie.