dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 21

Thread: How exactly does recursion work with iterators?

  1. #1
    Join Date
    Jun 2018
    Posts
    8

    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;
    }

  2. #2
    Join Date
    Feb 2017
    Posts
    325

    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.

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,366

    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.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.8.1)

  4. #4
    Join Date
    Feb 2017
    Posts
    325

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by Kingdominth4 View Post
    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.
    Last edited by wolle; June 16th, 2018 at 09:39 AM.

  5. #5
    Join Date
    Jun 2018
    Posts
    8

    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;
    }

  6. #6
    Join Date
    Jun 2018
    Posts
    8

    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?

  7. #7
    Join Date
    Jun 2018
    Posts
    8

    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.

  8. #8
    Join Date
    Feb 2017
    Posts
    325

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by Kingdominth4 View Post
    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.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,366

    Re: How exactly does recursion work with iterators?

    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;
    Last edited by 2kaud; June 16th, 2018 at 06:12 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.8.1)

  10. #10
    Join Date
    Feb 2017
    Posts
    325

    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
    
    }
    Last edited by wolle; June 19th, 2018 at 01:24 AM.

  11. #11
    Join Date
    Jun 2018
    Posts
    8

    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

  12. #12
    Join Date
    Jun 2018
    Posts
    8

    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.

  13. #13
    Join Date
    Jun 2018
    Posts
    8

    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?

  14. #14
    Join Date
    Feb 2017
    Posts
    325

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by Kingdominth4 View Post
    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; 
    }
    Last edited by wolle; June 17th, 2018 at 12:31 PM.

  15. #15
    Join Date
    Feb 2017
    Posts
    325

    Re: How exactly does recursion work with iterators?

    Quote Originally Posted by wolle View Post
    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;
    }
    Last edited by wolle; June 30th, 2018 at 04:12 AM.

Page 1 of 2 12 LastLast

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)