# How exactly does recursion work with iterators?

Show 50 post(s) from this thread on one page
Page 1 of 2 12 Last
• June 12th, 2018, 07:58 PM
Kingdominth4
How exactly does recursion work with iterators?
Hello. So I'm working on a Hackerrank exercise: "Journey to the Moon". In which you are given a list of pairs of astronauts that are bounded and one has to traverse through the provided list and link all connected pairs of astronauts. The result is an integer number that represents all possible non-bounded pairs in a set of n astronauts given the provided list of bounded astronaut pairs.

I have completed most of the solution of the problem, and my program even works for most simple cases. However, it fails on larger cases--primarily those where the iterator reaches the end of the list but there is more than one pair remaining within the list of astronauts.

My solution to this problem involves recursion and iteration through the list of astronauts (which is a set), while its elements are simultaneously deleted. And indeed, the particular error that prompted me to make this post is an iterator invalidation error. Though, I made sure to add safeguards to make sure the iterator never points to a delete element in the list of astronauts.

I debugged my program and was able to track down what exactly was causing my solution to crash, with a particular problematic test case. In this test case of 70 pairs, around the time when 53 of those pairs were remaining in the list of astronauts and when temp_set's (a set pointer passed to my recursive function) size was 18. The most recent recursive call finished iterating through the list of astronauts when iterator it went out of bounds triggering the while condition: it != astronaut->end(), returned its result to the next most recent recursive call-- here is where the issue lies-- whose iterator value was also undefined but not equal to astronaut->end(). The returned items were inserted into temp_set and, for some reason, the while loop was also checked. This time the check it != astronaut->end() triggered the error: list iterator incompatible. But why?

I thought with sets an invalidated iterator only triggers an error when that iterator tries to access an item in a set. But, this should not be the case in it != astronaut->end().

The iterator value that triggered this error was equal to: (-572662307, -572662307) while astronaut->end() was equal to: (-842150451, -842150451)

The IDE I am using is the free version of visual studio 2015 and I am using the compiler that was included with the package.

The input that I used to debug is: https://hr-testcases-us-east-1.s3.am...e=text%2Fplain

The details on the problem can be found at: https://www.hackerrank.com/challenge.../code/73601862

Thank you in advance for your assistance! Here is my code.

Code:

```#include "stdafx.h" #include <vector> #include <iostream> #include <string> #include <algorithm> #include <fstream> #include <stack> #include <unordered_set> using namespace std; vector<string> split_string(string); template <> struct hash<pair<int, int> > {         size_t operator()(const pair<int, int>& x) const noexcept         {                 return (size_t)x.first * x.second + x.first + x.second;         } }; struct custom_set : unordered_set<int> {         void pair_insert(pair<int, int> pair)         {                 insert(pair.first);                 insert(pair.second);         }         void pairs_insert(std::initializer_list <pair<int, int>> pairs)         {                 for (pair<int, int> pair : pairs)                 {                         insert(pair.first);                         insert(pair.second);                 }         } }; pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,         custom_set * temp_set, unordered_set<pair<int, int>>::iterator it); bool do_not_repeat; // Complete the journeyToMoon function below. int journeyToMoon(int n, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut) //astronaut ids numbered : [0, n-1] {         //vector<bool> bIsBoundAstronaut(n); //list of all astronauts; true corresponds to bounded         //vector<int> set_of_free_astronauts;                 vector<unordered_set<int>> sets_of_bounded_astronauts;         vector<int> num_bounded_astronauts_each_set;         int num_bounded_astronauts_total = 0, num_free_astronauts = 0, result = 0;                 while (!astronaut->empty())         {                 //*astronaut->begin()++                                 pair<int, int> id_pair = *astronaut->begin();                 custom_set * temp_set = new custom_set;                 journeyToMoon(id_pair, astronaut, temp_set, ++astronaut->begin());                 sets_of_bounded_astronauts.push_back(*temp_set);                 num_bounded_astronauts_each_set.push_back(sets_of_bounded_astronauts.back().size()); //why doesn't this work???? won't return size                 num_bounded_astronauts_total += sets_of_bounded_astronauts.back().size(); //why won't this work???? won't return size                 delete temp_set;         }         num_free_astronauts = n - num_bounded_astronauts_total;         for (int i = 0; i < num_bounded_astronauts_each_set.size() - 1; i++)         {                 for (int j = i + 1; j < num_bounded_astronauts_each_set.size(); j++)                         result += num_bounded_astronauts_each_set[i] * num_bounded_astronauts_each_set[j];                 result += num_free_astronauts * num_bounded_astronauts_each_set[i];         }         result += num_free_astronauts * num_bounded_astronauts_each_set.back() + (num_free_astronauts * (num_free_astronauts - 1))/2;         return result; } pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int> , hash<pair<int, int>>> * astronaut,         custom_set * temp_set, unordered_set<pair<int, int>>::iterator it) {                 while (!astronaut->empty() && it != astronaut->end()) {                 // copy the current iterator then increment it                 astronaut->erase(id_pair1);                 pair<int, int> id_pair2 = *it++;                         if (id_pair2.first == id_pair1.first || id_pair2.first == id_pair1.second || id_pair2.second == id_pair1.first                         || id_pair2.second == id_pair1.second)                 {                                                temp_set->pairs_insert({ id_pair1, journeyToMoon(id_pair2, astronaut, temp_set,                                 id_pair2 != *astronaut->begin() ? astronaut->begin() : ++astronaut->begin()) });                 }         }         astronaut->erase(id_pair1);         temp_set->pair_insert(id_pair1); //the case where id_pair1 is not matched with any other pairs in the list and also the case         //where astronaut.size() == 1; if it so happens that id_pair1 was already inserted then the functionality of sets prevents duplicates         return id_pair1; } int main() {                 //ofstream fout(getenv("OUTPUT_PATH"));         string np_temp;         std::getline(std::cin, np_temp);         vector<string> np = split_string(np_temp);         int n = stoi(np[0]);         int p = stoi(np[1]);         unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut = new unordered_set<pair<int, int>, hash<pair<int, int>>>(p);         for (int i = 0; i < p; i++) {                 int a, b;                 std::cin >> a >> b;                 astronaut->insert(pair<int, int>(a, b));                 }         std::cin.ignore(numeric_limits<streamsize>::max(), '\n');         int result = journeyToMoon(n, astronaut);         //fout << result << "\n";         std::cout << result << "\n";         //fout.close();         delete astronaut;         return 0; } vector<string> split_string(string input_string) {         string::iterator new_end = unique(input_string.begin(), input_string.end(), [](const char &x, const char &y) {                 return x == y && x == ' ';         });         input_string.erase(new_end, input_string.end());         while (input_string[input_string.length() - 1] == ' ') {                 input_string.pop_back();         }         vector<string> splits;         char delimiter = ' ';         size_t i = 0;         size_t pos = input_string.find(delimiter);         while (pos != string::npos) {                 splits.push_back(input_string.substr(i, pos - i));                 i = pos + 1;                 pos = input_string.find(delimiter, i);         }         splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));         return splits; }```
• June 13th, 2018, 02:01 AM
wolle
Re: How exactly does recursion work with iterators?
Without looking at your code, you most likely are changing a data structure while iterating over it.

This is consistent with your bug description; The code works for smaller cases because then the data structure doesn't re-organize internally but with larger cases it does and the iterator becomes invalidated.
• June 13th, 2018, 07:09 AM
2kaud
Re: How exactly does recursion work with iterators?
If you used using to set up new type names for commonly used data types eg

Code:

```using Paii = pair<int, int>; template <> struct hash<Paii> {         size_t operator()(const Paii& x) const noexcept         {                 return (size_t)x.first * x.second + x.first + x.second;         } }; using unsetpii = unordered_set<Paii, hash<Paii>>; using unsetpiiIt = unsetpii::iterator;```
and used these in the code, then your code would be much easier to read!

You have an error in the definitions of journeyToMoon() when you use an incorrect iterator type.

Code:

```pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,         custom_set * temp_set, unordered_set<pair<int, int>>::iterator it);```
should be

Code:

```pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,         custom_set * temp_set, unordered_set<pair<int, int>, hash<pair<int, int>>>::iterator it);```
which if the using type definitions were used would become

Code:

`Paii journeyToMoon(Paii id_pair1, unsetpii* astronaut, custom_set* temp_set, unsetpiiIt it);`
(and similar for the definiton).

which is much easier to understand and less likely to have a type error.
• June 15th, 2018, 03:18 AM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by Kingdominth4
The details on the problem can be found at: https://www.hackerrank.com/challenge.../code/73601862

That link didn't work if you're not a member of hackerrank but this one seems to do,

https://www.hackerrank.com/challenge...e-moon/problem

A pair of astronauts can be viewed as a point in a 2D coordinate system. If two pairs have an astronaut in common they can be viewed as linked with a line. In graph theory one would say that all linked pairs form a connected component (which in this problem represents one country). Finding all connected components is a standard problem,

https://en.wikipedia.org/wiki/Connec...(graph_theory)

Now that it is known which astronauts belong to which country the problem reduces to a standard combinatorics problem. Let's say we have a number of urns and all astronauts from the same country are in the same urn.

We now generate all combinations of 2 urns out of all urns. From each such 2 urn combination we get the number of possible pairs of astronauts from two different countries by simply multiplying the number of astronauts in the two urns. If we repeat this for all 2 urn combinations we end up with a grand sum total that is the solution to this problem.
• June 15th, 2018, 03:55 PM
Kingdominth4
Re: How exactly does recursion work with iterators?
Hi! Thank you so much for replying to me post. I am sorry it took me so long to get back with you. I couldn't find the time 2 days ago to reply and apparently the site was down yesterday.

I apologize that my code was difficult to parse. I thank you for your suggestions on improving readability and coherent code is something I really strive to create. Though, about your suggestion. Wouldn't using "using Paii = pair<int,int>" on top of "using namespace std" cause name clash? Or are you implying that I should use "using Paii = pair<int, int>" over "using namespace std"? Couldn't I achieve the same affect of "using Paii = pair<int, int>" with a "#define" instead?

Also, fixed the method signature like you suggested (thank you) which actually worked for another test case; however, you solution still didn't work for the test case in question. I still can't understand why though.

I'm especially confused about how the iterator it value changed from (-842150451, -842150451) to (-572662307, -572662307) and why the while loop condition is even being checked between recursive calls: the while loop condition should not have to be checked to apply the returned value from the previous recursive call. Yet it does. I do not understand this also.

Although the error that you pointed out definitely contributed to the problem, perhaps there is something else going on too. The conditions that caused error are still the same as I initially specified. Thanks a bunch. My code is updated as follows:

Code:

```#include "stdafx.h" #include <vector> #include <iostream> #include <string> #include <algorithm> #include <fstream> #include <stack> #include <unordered_set> using namespace std; vector<string> split_string(string); template <> struct hash<pair<int, int> > {         size_t operator()(const pair<int, int>& x) const noexcept         {                 return (size_t)x.first * x.second + x.first + x.second;         } }; struct custom_set : unordered_set<int> {         void pair_insert(pair<int, int> pair)         {                 insert(pair.first);                 insert(pair.second);         }         void pairs_insert(std::initializer_list <pair<int, int>> pairs)         {                 for (pair<int, int> pair : pairs)                 {                         insert(pair.first);                         insert(pair.second);                 }         } }; pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut,         custom_set * temp_set, unordered_set<pair<int, int>, hash<pair<int, int>>>::iterator it); // Complete the journeyToMoon function below. int journeyToMoon(int n, unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut) //astronaut ids numbered : [0, n-1] {         //vector<bool> bIsBoundAstronaut(n); //list of all astronauts; true corresponds to bounded         //vector<int> set_of_free_astronauts;                 vector<unordered_set<int>> sets_of_bounded_astronauts;         vector<int> num_bounded_astronauts_each_set;         int num_bounded_astronauts_total = 0, num_free_astronauts = 0, result = 0;                 while (!astronaut->empty())         {                 //*astronaut->begin()++                                 pair<int, int> id_pair = *astronaut->begin();                 custom_set * temp_set = new custom_set;                 journeyToMoon(id_pair, astronaut, temp_set, ++astronaut->begin());                 sets_of_bounded_astronauts.push_back(*temp_set);                 num_bounded_astronauts_each_set.push_back(sets_of_bounded_astronauts.back().size()); //why doesn't this work???? won't return size                 num_bounded_astronauts_total += sets_of_bounded_astronauts.back().size(); //why won't this work???? won't return size                 delete temp_set;         }         num_free_astronauts = n - num_bounded_astronauts_total;         for (int i = 0; i < num_bounded_astronauts_each_set.size() - 1; i++)         {                 for (int j = i + 1; j < num_bounded_astronauts_each_set.size(); j++)                         result += num_bounded_astronauts_each_set[i] * num_bounded_astronauts_each_set[j];                 result += num_free_astronauts * num_bounded_astronauts_each_set[i];         }         result += num_free_astronauts * num_bounded_astronauts_each_set.back() + (num_free_astronauts * (num_free_astronauts - 1))/2;         return result; } pair<int, int> journeyToMoon(pair<int, int> id_pair1, unordered_set<pair<int, int> , hash<pair<int, int>>> * astronaut,         custom_set * temp_set, unordered_set<pair<int, int>, hash<pair<int, int>>>::iterator it) {                 while (it != astronaut->end()) {                 // copy the current iterator then increment it                 astronaut->erase(id_pair1);                 pair<int, int> id_pair2 = *it++;                         if (id_pair2.first == id_pair1.first || id_pair2.first == id_pair1.second || id_pair2.second == id_pair1.first                         || id_pair2.second == id_pair1.second)                 {                                                temp_set->pairs_insert({ id_pair1, journeyToMoon(id_pair2, astronaut, temp_set,                                 id_pair2 != *astronaut->begin() ? astronaut->begin() : ++astronaut->begin()) });                 }         }         astronaut->erase(id_pair1);         temp_set->pair_insert(id_pair1); //the case where id_pair1 is not matched with any other pairs in the list and also the case         //where astronaut.size() == 1; if it so happens that id_pair1 was already inserted then the functionality of sets prevents duplicates         return id_pair1; } int main() {                 //ofstream fout(getenv("OUTPUT_PATH"));         string np_temp;         std::getline(std::cin, np_temp);         vector<string> np = split_string(np_temp);         int n = stoi(np[0]);         int p = stoi(np[1]);         unordered_set<pair<int, int>, hash<pair<int, int>>> * astronaut = new unordered_set<pair<int, int>, hash<pair<int, int>>>(p);         for (int i = 0; i < p; i++) {                 int a, b;                 std::cin >> a >> b;                 astronaut->insert(pair<int, int>(a, b));                 }         std::cin.ignore(numeric_limits<streamsize>::max(), '\n');         int result = journeyToMoon(n, astronaut);         //fout << result << "\n";         std::cout << result << "\n";         //fout.close();         delete astronaut;         return 0; } vector<string> split_string(string input_string) {         string::iterator new_end = unique(input_string.begin(), input_string.end(), [](const char &x, const char &y) {                 return x == y && x == ' ';         });         input_string.erase(new_end, input_string.end());         while (input_string[input_string.length() - 1] == ' ') {                 input_string.pop_back();         }         vector<string> splits;         char delimiter = ' ';         size_t i = 0;         size_t pos = input_string.find(delimiter);         while (pos != string::npos) {                 splits.push_back(input_string.substr(i, pos - i));                 i = pos + 1;                 pos = input_string.find(delimiter, i);         }         splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));         return splits; }```
• June 15th, 2018, 04:03 PM
Kingdominth4
Re: How exactly does recursion work with iterators?
Thank you for replying! How is this the case with unordered_set? Could you elaborate? Can reordering be avoided, and if not, does that mean unordered_set is not the appropriate data structure to be using after all? Thanks! A lot of the overhead of the problem was solved by using an unordered_set so that's why that data structure was my default, but perhaps there is a better way to: store unique elements, whose order is not important, and provide constant time access to its elements for deletion.

Really, the crux of my implementation of the problem hinges on the property of deletion that just described. Maybe there is a data structure that is more apt for that?
• June 15th, 2018, 05:03 PM
Kingdominth4
Re: How exactly does recursion work with iterators?
Thanks for summarizing the problem. I did not tackle the problem in the fashion you described. Though I wonder if your interpretation would be easier to solve.

I apologize. I now realize that I didn't provide much insight into my approach of solving this problem. I can explain. My solution involved the application of set theory. As the problem describes, two astronauts are bounded (meaning they are not available to be represented as pair in the final solution) if they directly appear as a pair within the provided list of astronauts or if they a linked transitively to one of the astronauts that directly appear in said pair. The final solution should reflect the total number astronauts that are not bounded together (or in other words "free"). That solution involves a sum of the amount of resulting pairs from the Cartesian product between every two sets of bounded astronauts, resulting pairs from the Cartesian product between the set of free astronauts and every set of bounded astronauts, and the subsets of size two within the free set itself. Such a sum represents the total amount of astronauts that can be grouped together from a list of astronauts that can't be.

Bounded astronauts can be grouped together in sets, where one such set represents all the astronauts that are prohibited from appearing together as a pair of two in the final solution. You have to correctly group all transitively linked astronauts within a given set to solve the problem. Given a pair pair1: <a1, a2>, that task entails finding all pairs that include a1, and then finding all pairs that include a2.

If there are any pairs matching the previous condition, we must then consider that pair pair2: <a3, a4> and add its astronaut (only one because by definition, one of its astronauts must be a1 or a2 and there for is already included in the set of bounded astronauts) to the set of astronauts that can't be grouped with a1 and a2. Every pair in the list of astronauts must be checked against pair1, and then against pair2, and so on, since there may be more than two pairs that include a1 or a2, a3 or a4, and so on.

Once the last transitively linked pair is checked against all the remaining astronauts in the list (the end of the astronaut list is reached), we know that there are no more bounded astronauts in the list of astronauts (at least for the current pair). We can then visit the next most current pair and continue checking it against the remaining astronauts in the list (provided that it hasn't already been checked against all the remaining astronauts). This situation occurs until pair1 has been checked against all the astronauts in the list. And once it has, the first set of bounded astronauts is made (there can be more than one set if there are pairs of astronauts in the list that are not transitively linked to pair1--in which case, the process is repeated with the first instance of said pairs).

You can see how this interpretation naturally encourages the use of recursion, which is what I used. And the only way to check a pair against all pairs in the list is to somehow iterate through the list of astronaut pairs, which is why I used the while loop. But for some reason the condition of the while loop is causing an error, when I don't think it should.

Why does "it != astronaut->end()" cause an error with the value (-572662307, -572662307)? Obviously there is a value there. And although that value is not equal to the value of astronaut->end(): (-842150451, -842150451), it should not be prompting the error "list iterators incompatible", right?

Also, sorry. I didn't realize that the link was dead. Though I can include the 70 integer pairs if that is necessary to diagnose the problem.
• June 16th, 2018, 12:19 AM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by Kingdominth4
Though I wonder if your interpretation would be easier to solve.

So do I and that's why I'm tempted to give it a go. :)

I would appreciate if you would post the 70-pairs test case.
• June 16th, 2018, 06:06 AM
2kaud
Re: How exactly does recursion work with iterators?
Quote:

Though, about your suggestion. Wouldn't using "using Paii = pair<int,int>" on top of "using namespace std" cause name clash?
I mean consider (I've done some other tidying up)

Code:

```#include <vector> #include <iostream> #include <string> #include <algorithm> #include <fstream> #include <unordered_set> using namespace std; vector<string> split_string(string); using Paii = pair<size_t, size_t>; template <> struct hash<Paii> {         size_t operator()(const Paii& x) const noexcept         {                 return x.first * x.second + x.first + x.second;         } }; using Unsetpii = unordered_set<Paii, hash<Paii>>; using UnsetpiiIt = Unsetpii::iterator; using Unseti = unordered_set<int>; struct custom_set : Unseti {         void pair_insert(Paii pair)         {                 insert(pair.first);                 insert(pair.second);         }         void pairs_insert(const initializer_list<Paii>& pairs)         {                 for (auto pair : pairs)                         pair_insert(pair);         } }; Paii journeyToMoon(Paii id_pair1, Unsetpii *astronaut, custom_set *temp_set, UnsetpiiIt it); // Complete the journeyToMoon function below. size_t journeyToMoon(size_t n, Unsetpii *astronaut) //astronaut ids numbered : [0, n-1] {         //vector<bool> bIsBoundAstronaut(n); //list of all astronauts; true corresponds to bounded         //vector<int> set_of_free_astronauts;         vector<Unseti> sets_of_bounded_astronauts;         vector<size_t> num_bounded_astronauts_each_set;         size_t num_bounded_astronauts_total = 0, num_free_astronauts = 0, result = 0;         while (!astronaut->empty())         {                 //*astronaut->begin()++                 const auto id_pair = *astronaut->begin();                 const auto temp_set = new custom_set;                 journeyToMoon(id_pair, astronaut, temp_set, ++astronaut->begin());                 sets_of_bounded_astronauts.push_back(*temp_set);                 num_bounded_astronauts_each_set.push_back(sets_of_bounded_astronauts.back().size()); //why doesn't this work???? won't return size                 num_bounded_astronauts_total += sets_of_bounded_astronauts.back().size(); //why won't this work???? won't return size                 delete temp_set;         }         num_free_astronauts = n - num_bounded_astronauts_total;         for (size_t i = 0; i < num_bounded_astronauts_each_set.size() - 1; ++i)         {                 for (size_t j = i + 1; j < num_bounded_astronauts_each_set.size(); ++j)                         result += num_bounded_astronauts_each_set[i] * num_bounded_astronauts_each_set[j];                 result += num_free_astronauts * num_bounded_astronauts_each_set[i];         }         result += num_free_astronauts * num_bounded_astronauts_each_set.back() + (num_free_astronauts * (num_free_astronauts - 1)) / 2;         return result; } Paii journeyToMoon(Paii id_pair1, Unsetpii *astronaut, custom_set *temp_set, UnsetpiiIt it) {         while (it != astronaut->end()) {                 // copy the current iterator then increment it                 astronaut->erase(id_pair1);                 const auto id_pair2 = *it++;                 if (id_pair2.first == id_pair1.first || id_pair2.first == id_pair1.second || id_pair2.second == id_pair1.first                         || id_pair2.second == id_pair1.second)                                 temp_set->pairs_insert({id_pair1, journeyToMoon(id_pair2, astronaut, temp_set,                                         id_pair2 != *astronaut->begin() ? astronaut->begin() : ++astronaut->begin())});         }         astronaut->erase(id_pair1);         temp_set->pair_insert(id_pair1); //the case where id_pair1 is not matched with any other pairs in the list and also the case                                                                         //where astronaut.size() == 1; if it so happens that id_pair1 was already inserted then the functionality of sets prevents duplicates         return id_pair1; } int main() {         //ofstream fout(getenv("OUTPUT_PATH"));         string np_temp;         getline(cin, np_temp);         const auto np = split_string(np_temp);         const auto n = stoul(np[0]);         const auto p = stoul(np[1]);         const auto astronaut = new Unsetpii(p);         for (size_t i = 0; i < p; ++i) {                 size_t a, b;                 cin >> a >> b;                 astronaut->emplace(a, b);                 //astronaut->insert(Paii(a, b));         }         cin.ignore(numeric_limits<streamsize>::max(), '\n');         const auto result = journeyToMoon(n, astronaut);         //fout << result << "\n";         cout << result << "\n";         //fout.close();         delete astronaut;         return 0; } vector<string> split_string(string input_string) {         const char delimiter = ' ';         // Remove duplicate spaces         const auto new_end = unique(input_string.begin(), input_string.end(), [&](const char &x, const char &y) {                 return x == y && x == delimiter;         });         // Remove left-overs from duplicate at end         input_string.erase(new_end, input_string.end());         // Make sure ends with a delimiter         if (input_string.back() != delimiter)                 input_string.push_back(delimiter);         vector<string> splits;         // Split string on space         for (size_t i = (input_string.front() == delimiter), pos = 0; (pos = input_string.find(delimiter, i)) != string::npos; i = pos + 1)                 splits.push_back(input_string.substr(i, pos - i));         return splits; }```
using has different meanings depending upon how its used. In the case of

Code:

`using Paii = pair<size_t, size_t>;`
its the modern equivalent of

Code:

`typedef pair<size_t, size_t> Paii;`
• June 16th, 2018, 08:46 AM
wolle
Re: How exactly does recursion work with iterators?
I've come up with a solution now according to the strategy in my post #4. The test cases from the problem description work but I would need more to be sure.

The first part of the algorithm (the graph theory) is linear in the number of pairs and the second part (the conbinatorics) is linear in the number countries, so it should be O(N) altogether.

Code:

```#include <vector> #include <utility> #include <unordered_map> #include <unordered_set> #include <functional> #include <algorithm> #include <stack> using Astro = int; using Pair = std::pair<Astro, Astro>; using PairList = std::vector<Pair>; int journeyToMoon2(const int n, const PairList& pairs) {         // definitions         const int ASTROS = n; // number of astronauts         const auto equal = [] (Pair l, Pair r) {return l.first == r.first;};         const auto hash = [] (Pair p) {return std::hash<Astro>{}(p.first);};         using PairSet = std::unordered_multiset<Pair, decltype(hash), decltype(equal)>; // hash table for pairs, equal relation is on first astronaut in a pair                 PairSet straight(10, hash, equal); // pairs are stored as is         PairSet reversed(10, hash, equal); // pairs are reversed and stored         const auto reverse_pair = [](Pair p) {                 return Pair(p.second, p.first);         };         const auto add_pair = [&] (Pair p) { // add pait to both hash tables                 straight.emplace(p); // straight                 reversed.emplace(reverse_pair(p)); // reverse         };         const auto remove_pair = [&] (Pair p) { // remove certain pair from both hashtable                 const auto range1 = straight.equal_range(p);                 const auto iterator1 = std::find(range1.first, range1.second, p);                 if (iterator1 != range1.second) straight.erase(iterator1);                 const Pair r = reverse_pair(p);                 const auto range2 = reversed.equal_range(r);                 const auto iterator2 = std::find(range2.first, range2.second, r);                 if (iterator2 != range2.second) reversed.erase(iterator2);         };         const auto any_pair = [&] () { // pick any pair                 return *straight.begin();         };         const auto no_pairs = [&] () { // no more pairs                 return straight.empty();         }; // setup         using Urn = std::vector<Astro>;         using Urns = std::vector<Urn>;         Urns urns;        // the urns         using AstroSet = std::unordered_set<Astro>;         AstroSet astrosInPairs; // stores all astronauts that are present in the list of pairs         for (Pair p : pairs) {                 add_pair(p); // add pairs to hash tables                 astrosInPairs.insert(p.first);                 astrosInPairs.insert(p.second);         }         for (Astro i=0; i<ASTROS; ++i) { // astronauts that are not in the pair list get one urn each                 if (astrosInPairs.count(i) == 0) {                         Urn urn;                         urn.push_back(i);                         urn.shrink_to_fit();                         urns.push_back(urn);                 }         }         astrosInPairs.clear();         // Part 1 - generating all urns with austronauts from the same country         while (!no_pairs()) { // as long as there are pairs                 std::stack<Pair> stack;                 const auto push_stack = [&] (Pair p) {                         stack.push(p);                 };                 const auto pop_stack = [&] () {                         Pair p = stack.top();                         stack.pop();                         return p;                 };                 AstroSet set; // tempporary storage for astrounauts the will go into one urn                 push_stack(any_pair()); // push any pair                 while (!stack.empty()) { // when empty all astronouts from a common country have been identified                         const Pair p = pop_stack(); // pop a pair                         remove_pair(p); // remove it from both hash tables                         set.insert(p.first); // store both astronauts of the pair                         set.insert(p.second);                                 // identify all other pairs that share an astronout with this pair                         const auto range1 = straight.equal_range(p);                         std::for_each(range1.first, range1.second, push_stack);                         const auto range2 = reversed.equal_range(p);                         std::for_each(range2.first, range2.second, push_stack);                         const Pair r = reverse_pair(p);                         const auto range3 = straight.equal_range(r);                         std::for_each(range3.first, range3.second, push_stack);                         const auto range4 = reversed.equal_range(r);                         std::for_each(range4.first, range4.second, push_stack);                 }                 Urn urn(set.begin(), set.end()); // load urn with astronauts                 urn.shrink_to_fit();                 urns.push_back(urn); // store urn         }         { // print urns                 std::cout << "The urns ="  << std::endl;                 int i=0;                 for (Urn urn : urns) {                         std::cout << (i++) << ": " ;                         for (Astro a : urn) {                                 std::cout << a << " " ;                         }                         std::cout << std::endl;                 }         }                 // Part 2 - generate all combination of 2 urns and sum up all possible pairs of astronouts from different countries. /*         int sum = 0;         const int URNS = int(urns.size());         for (int i=0; i<URNS; ++i) { // first urns                 const int ni = int(urns[i].size());                 for (int j=i+1; j<URNS; ++j) { // second urns                         const int nj = int(urns[j].size());                         sum += ni*nj; // multiply the number of astronauts of urn 1 and 2 and add to sum                 }         } */                 // the above nested loops can be optimized to no nesting                 // with the use of an array of accumulated sums like /*        const int URNS = int(urns.size());         std::vector<int> accSum;         for (int i=0; i<URNS; ++i) accSum.push_back(int(urns[i].size())); // copy urn sizes         for (int i=URNS-1; i>0; --i) accSum[i-1] += accSum[i]; // calculate accumulated sums         int sum=0;         for (int i=0; i<URNS-1; ++i) sum += int(urns[i].size())*accSum[i+1]; // perform summing */                 // and the above 3 loops merged into one         int sum = 0;         {                 int accSum = 0;                 for (int i=int(urns.size())-1; i>0; --i) {                         accSum += int(urns[i].size());                         sum += accSum * int(urns[i-1].size());                 }         }         return sum; } void test() {                 // sample 0 from problem description         PairList pairs_sample_0 = { //                {5, 3}, // not a pair, 5 astronauts                 {0, 1},                 {2, 3},                 {0, 4}         };         int result_0 = journeyToMoon2(5, pairs_sample_0);         std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should                 // sample 1 from problem description         PairList pairs_sample_1 = { //                {4, 1}, // not a pair, 4 astronauts                 {0, 2}         };         int result_1 = journeyToMoon2(4, pairs_sample_1);         std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should }```
• June 16th, 2018, 05:55 PM
Kingdominth4
Re: How exactly does recursion work with iterators?
100 70
0 11
2 4
2 95
3 48
4 85
4 95
5 67
5 83
5 42
6 76
9 31
9 22
9 55
10 61
10 38
11 96
11 41
12 60
12 69
14 80
14 99
14 46
15 42
15 75
16 87
16 71
18 99
18 44
19 26
19 59
19 60
20 89
21 69
22 96
22 60
23 88
24 73
27 29
30 32
31 62
32 71
33 43
33 47
35 51
35 75
37 89
37 95
38 83
39 53
41 84
42 76
44 85
45 47
46 65
47 49
47 94
50 55
51 99
53 99
56 78
66 99
71 78
73 98
76 88
78 97
80 90
83 95
85 92
88 99
88 94
• June 16th, 2018, 06:03 PM
Kingdominth4
Re: How exactly does recursion work with iterators?
Thanks, I wasn't aware that using could be used like that. And thank you for polishing up the code. I agree, it looks a lot more legible.
• June 16th, 2018, 06:29 PM
Kingdominth4
Re: How exactly does recursion work with iterators?
And a few more:

10 7
0 2
1 8
1 4
2 8
2 6
3 5
6 9

10 20
0 1
0 3
0 4
1 2
1 3
1 5
1 7
1 8
1 9
2 8
2 7
3 5
3 8
3 7
4 9
4 5
4 6
4 7
6 8
6 7

10000 2
1 2
3 4

Wow, your program looks impressive. It seems you also used a while loop to iterate through the list. What is the benefit of using a lambda expression that returns "straight.empty()" as the while condition rather than just using "straight.empty()" directly as the while condition? Does that somehow circumvent errors or something? Should I use a lambda expression instead of using "it->astronaut.end()" directly in my program?
• June 16th, 2018, 11:25 PM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by Kingdominth4
What is the benefit of using a lambda expression that returns "straight.empty()" as the while condition rather than just using "straight.empty()" directly as the while condition? Does that somehow circumvent errors or something? Should I use a lambda expression instead of using "it->astronaut.end()" directly in my program?

Several of my lambdas aren't strictly necessary. For example also pop_stack() and remove_pair() are both called from one place only. I do this for the reason of abstraction. If I were to tidy up the code (which I certainly would if it was for production) I probably would introduce a couple of classes to hide certain data structures and these functions would then most likely appear as methods of those classes. There's no reason to refrain from "unnecessary" lambdas for performance reasons, the compiler will see to that. I'm also quite fond of using the using keyword for the same purpose, namely abstraction.

Anyway I got these results,

(100 70) = 3984
(10 7) = 23
(10 20) = 0
(10000 2) = 49994998

Are they correct?

For the (10000 2) case I had to comment out the printing of the urns because the list became too long to fit in my output window. Here's the test program I used,

Code:

```void test() {                 // sample 0 from problem description         PairList pairs_sample_0 = { //                {5, 3}, // not a pair, 5 astronauts                 {0, 1},                 {2, 3},                 {0, 4}         };         int result_0 = journeyToMoon2(5, pairs_sample_0);         std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should         std::cout << "----------" << std::endl; // 5 as it should                 // sample 1 from problem description         PairList pairs_sample_1 = { //                {4, 1}, // not a pair, 4 astronauts                 {0, 2}         };         int result_1 = journeyToMoon2(4, pairs_sample_1);         std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should         std::cout << "----------" << std::endl; // 5 as it should         PairList pairs_sample_2 = { //                {100, 70},                 {0, 11},                 {2, 4},                 {2, 95},                 {3, 48},                 {4, 85},                 {4, 95},                 {5, 67},                 {5, 83},                 {5, 42},                 {6, 76},                 {9, 31},                 {9, 22},                 {9, 55},                 {10, 61},                 {10, 38},                 {11, 96},                 {11, 41},                 {12, 60},                 {12, 69},                 {14, 80},                 {14, 99},                 {14, 46},                 {15, 42},                 {15, 75},                 {16, 87},                 {16, 71},                 {18, 99},                 {18, 44},                 {19, 26},                 {19, 59},                 {19, 60},                 {20, 89},                 {21, 69},                 {22, 96},                 {22, 60},                 {23, 88},                 {24, 73},                 {27, 29},                 {30, 32},                 {31, 62},                 {32, 71},                 {33, 43},                 {33, 47},                 {35, 51},                 {35, 75},                 {37, 89},                 {37, 95},                 {38, 83},                 {39, 53},                 {41, 84},                 {42, 76},                 {44, 85},                 {45, 47},                 {46, 65},                 {47, 49},                 {47, 94},                 {50, 55},                 {51, 99},                 {53, 99},                 {56, 78},                 {66, 99},                 {71, 78},                 {73, 98},                 {76, 88},                 {78, 97},                 {80, 90},                 {83, 95},                 {85, 92},                 {88, 99},                 {88, 94}         };         int result_2 = journeyToMoon2(100, pairs_sample_2);         std::cout << "Result 2 = " << result_2 << std::endl;         std::cout << "----------" << std::endl;         PairList pairs_sample_3 = {                 //{10, 7},                 {0, 2},                 {1, 8},                 {1, 4},                 {2, 8},                 {2, 6},                 {3, 5},                 {6, 9}         };         int result_3 = journeyToMoon2(10, pairs_sample_3);         std::cout << "Result 3 = " << result_3 << std::endl;         std::cout << "----------" << std::endl;         PairList pairs_sample_4 = { //                {10, 20},                 {0, 1},                 {0, 3},                 {0, 4},                 {1, 2},                 {1, 3},                 {1, 5},                 {1, 7},                 {1, 8},                 {1, 9},                 {2, 8},                 {2, 7},                 {3, 5},                 {3, 8},                 {3, 7},                 {4, 9},                 {4, 5},                 {4, 6},                 {4, 7},                 {6, 8},                 {6, 7}         };         int result_4 = journeyToMoon2(10, pairs_sample_4);         std::cout << "Result 4 = " << result_4 << std::endl;         std::cout << "----------" << std::endl;         PairList pairs_sample_5 = { //                {10000, 2},                 {1, 2},                 {3, 4}         };         int result_5 = journeyToMoon2(10000, pairs_sample_5);         std::cout << "Result 5 = " << result_5 << std::endl;         std::cout << "----------" << std::endl; }```
• June 30th, 2018, 03:15 AM
wolle
Re: How exactly does recursion work with iterators?
Quote:

Originally Posted by wolle
I've come up with a solution now according to the strategy in my post #4.

I've cleaned up my solution in #10. It turns out that the second part of the solution strategy isn't necessary. Once it's known how many astronauts there are in an urn it's possible to calculate how much they contribute to the total pairs of astronauts from different countries. The contribution from astronauts that aren't in any urn can be calculated once the total number of astronauts that are in urns is known. This observation greatly simplifies the code.

Code:

```#include <iostream> #include <vector> #include <utility> #include <unordered_set> #include <functional> #include <algorithm> #include <stack> namespace tomoon {         using Astro = int;         using Pair = std::pair<Astro,Astro>;         using PairList = std::vector<Pair>;         class PairBase { // pair storage         public:                 PairBase(const PairList& pairs) {                         for (Pair p : pairs) {                                 storage.emplace(p); // store all pairs                                 storage.emplace(reverse_pair(p)); // and reversed pairs                         }                 }                 void remove_pair(Pair p) { // remove pair                         const auto rem = [&] (const Pair p) {                                 const auto range = storage.equal_range(p); // here equal is on first of pair (as defined for Pairs in the storage hashtable)                                 const auto iterator = std::find(range.first, range.second, p); // here equal is on both first and second (standard for an std::pair)                                 if (iterator != range.second) storage.erase(iterator);                         };                         rem(p);                         rem(reverse_pair(p));                 };                 Pair any_pair() const { // pick any pair (for example the first)                         return *storage.begin();                 };                 bool no_pairs() const { // no more pairs ?                         return storage.empty();                 };                 PairList linked_pairs(Pair p) const {        // identify all pairs that are linked (share an astronout) with this pair                         PairList pairList;                         const auto add = [&] (const Pair p) {                                 const auto range = storage.equal_range(p);                                 pairList.insert(pairList.end(), range.first, range.second);                         };                         add(p);                         add(reverse_pair(p));                         return pairList;                 }         private:                 struct Hash {                         std::size_t operator() (Pair p) const { return std::hash<Astro>{}(p.first); }                 };                 struct Equal {                         bool operator() (Pair l,Pair r) const { return l.first == r.first; };                 };                     // hash table for pairs, equal relation and hashing is on first astronaut of a pair                 std::unordered_multiset<Pair,Hash,Equal> storage; // pair storage                 Pair reverse_pair(Pair p) const { // switch first with second in pair                         return Pair(p.second,p.first);                 };         }; // PairBase         inline int journey(const int astros,const PairList& pairs) {                 PairBase pairBase(pairs); // pair storage                 int comb_sum = 0; // total sum of astronaut not from same country combinations                 int urn_sum = 0; // sum of austronauts in urns                 while (!pairBase.no_pairs()) { // as long as there are pairs                         std::stack<Pair> stack; // stack of pairs                         std::unordered_set<Astro> urn; // urn of austronauts                         stack.push(pairBase.any_pair()); // push any pair                         while (!stack.empty()) { // when empty all astronouts from a common country have been identified                                 const Pair p = stack.top(); // pop a pair                                 stack.pop();                                 pairBase.remove_pair(p); // remove pair                                 urn.insert({p.first,p.second}); // store both astronauts of pair                                 for(const Pair q : pairBase.linked_pairs(p)) stack.push(q); // push all linked pairs on stack                         }                         const int n = int(urn.size()); // number of astros in this urn                         urn_sum += n; // add to total urn sum                         comb_sum += n * (astros - n); // multiply astros inside this urn with all other astros and add up total sum                 }                 comb_sum += (astros - urn_sum) * (astros - 1); // consider astros outside any urn                 comb_sum /= 2; // all combinations have been counted twice                 return comb_sum; //comb_sum;         } } // tomoon void test() {         // sample 0 from problem description         tomoon::PairList pairs_sample_0 ={                 //                {5, 3}, // not a pair, 5 astronauts                                 {0,1},                                 {2,3},                                 {0,4}         };         int result_0 = tomoon::journey(5,pairs_sample_0);         std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should         std::cout << "----------" << std::endl; // 5 as it should                                                                                         // sample 1 from problem description         tomoon::PairList pairs_sample_1 ={                 //                {4, 1}, // not a pair, 4 astronauts                                 {0,2}         };         int result_1 = tomoon::journey(4,pairs_sample_1);         std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should         std::cout << "----------" << std::endl; // 5 as it should         tomoon::PairList pairs_sample_2 ={                 //                {100, 70},                                 {0,11},                                 {2,4},                                 {2,95},                                 {3,48},                                 {4,85},                                 {4,95},                                 {5,67},                                 {5,83},                                 {5,42},                                 {6,76},                                 {9,31},                                 {9,22},                                 {9,55},                                 {10,61},                                 {10,38},                                 {11,96},                                 {11,41},                                 {12,60},                                 {12,69},                                 {14,80},                                 {14,99},                                 {14,46},                                 {15,42},                                 {15,75},                                 {16,87},                                 {16,71},                                 {18,99},                                 {18,44},                                 {19,26},                                 {19,59},                                 {19,60},                                 {20,89},                                 {21,69},                                 {22,96},                                 {22,60},                                 {23,88},                                 {24,73},                                 {27,29},                                 {30,32},                                 {31,62},                                 {32,71},                                 {33,43},                                 {33,47},                                 {35,51},                                 {35,75},                                 {37,89},                                 {37,95},                                 {38,83},                                 {39,53},                                 {41,84},                                 {42,76},                                 {44,85},                                 {45,47},                                 {46,65},                                 {47,49},                                 {47,94},                                 {50,55},                                 {51,99},                                 {53,99},                                 {56,78},                                 {66,99},                                 {71,78},                                 {73,98},                                 {76,88},                                 {78,97},                                 {80,90},                                 {83,95},                                 {85,92},                                 {88,99},                                 {88,94}         };         int result_2 = tomoon::journey(100,pairs_sample_2);         std::cout << "Result 2 = " << result_2 << std::endl;         std::cout << "----------" << std::endl;         tomoon::PairList pairs_sample_3 ={                 //{10, 7},                 {0,2},                 {1,8},                 {1,4},                 {2,8},                 {2,6},                 {3,5},                 {6,9}         };         int result_3 = tomoon::journey(10,pairs_sample_3);         std::cout << "Result 3 = " << result_3 << std::endl;         std::cout << "----------" << std::endl;         tomoon::PairList pairs_sample_4 ={                 //                {10, 20},                 {0,1},                 {0,3},                 {0,4},                 {1,2},                 {1,3},                 {1,5},                 {1,7},                 {1,8},                 {1,9},                 {2,8},                 {2,7},                 {3,5},                 {3,8},                 {3,7},                 {4,9},                 {4,5},                 {4,6},                 {4,7},                 {6,8},                 {6,7}         };         int result_4 = tomoon::journey(10,pairs_sample_4);         std::cout << "Result 4 = " << result_4 << std::endl;         std::cout << "----------" << std::endl;         tomoon::PairList pairs_sample_5 ={                 //                {10000, 2},                 {1,2},                 {3,4}         };         int result_5 = tomoon::journey(10000,pairs_sample_5);         std::cout << "Result 5 = " << result_5 << std::endl;         std::cout << "----------" << std::endl; }```
Show 50 post(s) from this thread on one page
Page 1 of 2 12 Last