I know nothing about algorithm names, so I don't really know if my solution is called something specific, but this is what I did for part 2: I implemented a kind of strange bubble sort (I think?) where I iterated over the numbers in each group separately, going from the last number to the first. For each number in the group (let's call it A), I iterated over every rule that applies to it (like A | B), and for each rule, I iterated backwards over every number in the group again (let's call this one C). Then, if the current rule says that C should be behind A (because C is the element B in the rule), I swap them, and repeat from the beginning until the group is sorted.
I hope I explained it well. Words are not my strong suit, haha. However, this is the code: for(int i=0; ilen-1;o>=0;o--){ int e=g->elements[o]; // for each rule for(int ri=0; riA == e){ // for each element behind current element for(int y=o-1; y>=0; y--){ int pe = g->elements[y]; if(pe == r->B){ g->valid = 0; g->elements[y] = e; g->elements[o] = pe; goto repeat; } } } } } }
On part 2, what u suggest sound like "Topological sort". Can try to look up to it. Kinda overkill for this problem since each query comes with a very small N = len(nums). It was O(N) solution for each query tho. So pretty much optimal if you can get it done.
tbh, I didn't fully understood the proposed solution for part 2. I used a function to compare 2 pages, based on the rules there are 3 options - A is before B, A is after B, or doesn't matter. And then put this function in "sorted" function("key" parameter) to order the elements. It was easier in python2, they changed a bit and it is a bit more troublesome in python3, you need to transform your function into a lambda using "functools.cmp_to_key", but still. Other approach would be to implement sorting yourself, my preferred would be insertion sort, which is not so complex and is doing fine on small lists, and use the respective comparison rules directly there(instead of )
I solved it with regexp. An ordering like 1|5 is translated to a regexp (\b5\b)(,.*)(\b1\b) which is a negative rule. If it matches, the ordering has to be changed. So what I did is to create an regexp for every ordering rule and matched them against the input.
Finally, someone with communication skills explaining AoC. Congrats and Thank You!
I know nothing about algorithm names, so I don't really know if my solution is called something specific, but this is what I did for part 2: I implemented a kind of strange bubble sort (I think?) where I iterated over the numbers in each group separately, going from the last number to the first. For each number in the group (let's call it A), I iterated over every rule that applies to it (like A | B), and for each rule, I iterated backwards over every number in the group again (let's call this one C). Then, if the current rule says that C should be behind A (because C is the element B in the rule), I swap them, and repeat from the beginning until the group is sorted.
I hope I explained it well. Words are not my strong suit, haha. However, this is the code:
for(int i=0; ilen-1;o>=0;o--){
int e=g->elements[o];
// for each rule
for(int ri=0; riA == e){
// for each element behind current element
for(int y=o-1; y>=0; y--){
int pe = g->elements[y];
if(pe == r->B){
g->valid = 0;
g->elements[y] = e;
g->elements[o] = pe;
goto repeat;
}
}
}
}
}
}
On part 2, what u suggest sound like "Topological sort". Can try to look up to it. Kinda overkill for this problem since each query comes with a very small N = len(nums). It was O(N) solution for each query tho. So pretty much optimal if you can get it done.
So useful, Thank you jackie 😊
thank you so much
tbh, I didn't fully understood the proposed solution for part 2. I used a function to compare 2 pages, based on the rules there are 3 options - A is before B, A is after B, or doesn't matter. And then put this function in "sorted" function("key" parameter) to order the elements. It was easier in python2, they changed a bit and it is a bit more troublesome in python3, you need to transform your function into a lambda using "functools.cmp_to_key", but still.
Other approach would be to implement sorting yourself, my preferred would be insertion sort, which is not so complex and is doing fine on small lists, and use the respective comparison rules directly there(instead of )
I solved it with regexp. An ordering like 1|5 is translated to a regexp (\b5\b)(,.*)(\b1\b) which is a negative rule. If it matches, the ordering has to be changed. So what I did is to create an regexp for every ordering rule and matched them against the input.
Thank you❤
Thanks
Obrigado garota s2
So pretty!