Fixing this recursive function

[kimchiboy03]

Hello, I am currently trying to solve a programming problem. However, I cannot get this recursive function to work:

void mergeData(vector<int> data)
{
	for (int i = 0; i < data.size() - 1; i++)
	{
		for (int j = i + 1; j < data.size(); j++)
		{
			if (data.at(i) == data.at(j))
			{
				data.at(i)++;
				
				data.erase(data.begin() + j);
				
				mergeData(data);
			}
		}
	}
}

Can someone please tell me how to fix this recursive function? Thanks in advance.

[kimchiboy03]

More specifically, I am currently trying to solve this problem:
https://www.codechef.com/problems/WEAPONS

Here is my full code:

#include <iostream>
#include <vector>

using namespace std;

//Finds maximum element in array
int findMax(vector<int> data)
{
	int max = data.at(0);
	for (int i = 1; i < data.size(); i++)
	{
		if (max < data.at(i))
		{
			max = data.at(i);
		}
	}

	return max;
}

//Merges duplicates in array
void mergeData(vector<int> data)
{
	for (int i = 0; i < data.size() - 1; i++)
	{
		for (int j = i + 1; j < data.size(); j++)
		{
			if (data.at(i) == data.at(j))
			{
				data.at(i)++;
				
				data.erase(data.begin() + j);
				
				mergeData(data);
			}
		}
	}
}

//Main function
int main()
{
	int numSets;
	cin >> numSets;

	vector<vector<int> > data;
	for (int i = 0; i < numSets; i++)
	{
		int len;
		cin >> len;

		vector<int> temp;
		for (int j = 0; j < len; j++)
		{
			int element;
			cin >> element;
			
			temp.push_back(element);
		}

		data.push_back(temp);
		temp.clear();
	}

	for (int i = 0; i < numSets; i++)
	{
		mergeData(data.at(i));
		cout << findMax(data.at(i)) << endl;
	}
	
	return 0;
}

[JLBorges]

#include <iostream>
#include <vector>
#include <algorithm>

#ifndef NDEBUG

    // debugging scaffold (writing one tends to be much more productive in the long run than
    //                     unprincipled, non-repeatable hacking using a debugger)
    #include <cassert>

    void show_sorted_levels( const std::vector<int>& levels )
    {
            std::cout << "[ " ;
            for( int v : levels ) std::cout << v << ' ' ;
            std::cout << "]\n" ;
            // assert the invariant
            assert( !levels.empty() && std::is_sorted( std::begin(levels), std::end(levels) ) ) ;
    }
#else // #if defined NDEBUG
    void show( const std::vector<int>& ) {} // do nothing; our code is already debugged
#endif // NDEBUG

std::vector<int>& fuse( std::vector<int>& levels ) // invariant: levels are sorted
{
    show_sorted_levels(levels) ;

    // try to find the first two adjacent levels which are equal (in the reverse direction)
    // http://en.cppreference.com/w/cpp/algorithm/adjacent_find
    // note: fusing the first two adjacent values in the reverse direction maintains the sorted order
    //       (because the fused value is just one greater than the original value)
    const auto rev_iter = std::adjacent_find( std::rbegin(levels), std::rend(levels) ) ;
    if( rev_iter == std::rend(levels) ) return levels ; // no equal levels, nothing more to fuse

    // fuse the two equal levels into a single weapon
    // get an iterator to the first weapon (the earlier one in the forward direction)
    // http://en.cppreference.com/w/cpp/iterator/reverse_iterator/base
    const auto iter = rev_iter.base() - 2 ;
    ++*iter ; // increment the level of that weapon
    levels.erase( iter+1 ) ; // and remove the next weapon

    return fuse(levels) ; // repeat the fuse operation
}

int max_fused_level( std::vector<int> levels ) // return the max level after fusing weapons
{
    if( levels.empty() ) return 0 ; // sanity check

    std::sort( std::begin(levels), std::end(levels) ) ; // sort the levels
    return fuse(levels).back() ; // the max fused level is at the back of the sorted vector
}

int main() // minimal test driver (the first two test cases are the ones from codechef)
{
    std::cout << max_fused_level( { 3, 3, 1, 4 } ) << "\n-------------\n"
              << max_fused_level( { 2, 3, 3, 3, 1, 1 } ) << "\n-------------\n"
              << max_fused_level( { 2, 3, 3, 3, 1, 1, 2, 3, 3, 3, 1, 1, 4, 4, 5, 3, 3 } ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/269ff9ff4b7a1691

[kimchiboy03]

I'm sorry but your code doesn't seem to work on my computer.

So, I was wondering if I could modify the below code (which removes duplicates from a vector) to fuse the weapons?

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Is this possible?

@JLBorges Thanks you for your reply though :)

[kimchiboy03]

I have tried testing my code with the sample test cases. Although my code succeeded those sample test cases, it didn't seem to pass through the online judge.

What's wrong with this code??? I really want to solve this problem...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int> > output;

void sortOutput(vector<int> &output)
{
	while (unique(output.begin(), output.end()) != output.end())
	{
		for (int i = 0; i < output.size() - 1; i++)
		{
			if (output.at(i) == output.at(i + 1))
			{
				output.erase(output.begin() + i);
				output.at(i)++;
			}
		}

		sort(output.begin(), output.end());
	}
}

//Finds maximum element in array
int findMax(vector<int> data)
{
	int max = data.at(0);
	for (int i = 1; i < data.size(); i++)
	{
		if (max < data.at(i))
		{
			max = data.at(i);
		}
	}

	return max;
}

//Main function
int main()
{
	int numSets;
	cin >> numSets;

	vector<vector<int> > data;

	for (int i = 0; i < numSets; i++)
	{
		int len;
		cin >> len;

		vector<int> temp;
		for (int j = 0; j < len; j++)
		{
			int element;
			cin >> element;

			temp.push_back(element);
		}

		data.push_back(temp);
		temp.clear();
	}

	for (int i = 0; i < numSets; i++)
	{
		sort(data.at(i).begin(), data.at(i).end());
		sortOutput(data.at(i));

		cout << findMax(data.at(i)) << endl;
	}

	return 0;
}

[benhart]

Using recursion this way might hurt you sometimes as it leads to high complexity within the code. It might generate some bugs and errors that are hard to be detected. Unless you're using some program as checkmarx as help, I'd recommend you go slow with he coding and detect your vulnerabilities among the code.
Good luck