Detecting cycles

Question

This is a challenge question from codeeval.com:

Given a sequence, write a program to detect cycles within it. Input sample:

Your program should accept as its first argument a path to a filename containing a sequence of numbers (space delimited). The file can have multiple such lines. E.g

2 0 6 3 1 6 3 1 6 3 1

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

1 2 3 1 2 3 1 2 3

Output sample:

Print to stdout the first cycle you find in each sequence. Ensure that there are no trailing empty spaces on each line you print. E.g:

6 3 1

49

1 2 3

The cycle detection problem is explained more widely on wiki Constrains: The elements of the sequence are integers in range [0, 99] The length of the sequence is in range [0, 50]

Please let me know any improvements on this implementation.

#include<algorithm>
#include<unordered_map>
#include<iostream>
#include<set>
#include<fstream>
#include<sstream>
template<typename T>
class cyclicKeeper
{
 public:
 void push( T val)
 {
 cycles.push_back(val);
 cycleSet.emplace(val);
 }
 void clear()
 {
 for ( auto & x : cycles)
 {
 --counter[x];
 }
 cycles.clear();
 cycleSet.clear();
 }
 void incrementCounter(T val)
 {
 ++counter[val];
 }
 T counterValue(T val)
 {
 return counter[val];
 }
 void print()
 {
 std::vector<int> order( cycleSet.size());
 for( auto & x : cycleSet)
 {
 auto pos= std::find(std::begin(cycles), std::end(cycles),x);
 order[pos- std::begin(cycles)]=x;
 }
 for( auto &x : order)
 {
 std::cout<< x << " ";
 }
 std::cout<<"\n";
 }
 private:
 std::unordered_map<T,T> counter;
 std::vector<T> cycles;
 std::set<T> cycleSet; 
};
void processInputRecord(std::vector<int>& vec)
{
 cyclicKeeper<int> ck;
 for( auto & x : vec )
 {
 ck.incrementCounter(x);
 }
 int prev = 0;
 for( auto & x : vec )
 {
 if( ck.counterValue(x) > 1 )
 {
 if ( prev == 0)
 {
 prev = ck.counterValue(x);
 ck.push(x);
 }
 else if( prev == ck.counterValue(x) )
 {
 ck.push(x);
 }
 else
 {
 ck.clear();
 prev= ck.counterValue(x);
 ck.push(x);
 }
 }
 else
 {
 ck.clear();
 prev = 0;
 }
 }
 ck.print();
}
void readInputFile( std::string fileName )
{
 std::ifstream infile( fileName );
 std::vector<int> vec;
 std::string record;
 while( std::getline( infile, record ) )
 {
 std::istringstream iss(record);
 int temp = 0;
 while( iss >> temp )
 {
 vec.push_back(temp);
 }
 processInputRecord(vec);
 vec.clear();
 }
 infile.close();
}
int main( int argc, char* argv[] )
{
 if( argc < 2 )
 {
 std::cout << "Error: input file is missing " << "\n";
 exit( 0 );
 }
 std::ios_base::sync_with_stdio( false );
 readInputFile( argv[ 1 ]);
 return 0;
}

• Veedrac: As I mention in the comments to JS1, the question is woefully underspecified. Is this all you have to go on?
• Steephen: @Veedrac Yes, Veedrac this is all.

Answer 1

Too complex

With the problem constrained to:

The elements of the sequence are integers in range [0, 99]
The length of the sequence is in range [0, 50]

the program should be very simple. Instead, you use an unordered_map, a vector, and a set, which is overkill. The problem could be solved with only a vector of size 50.

(Note: answer modified to find the cycle as clarified by the comments)

The vector of size 50 holds the input sequence. Starting at the end of the sequence, you only need to search backwards until you find a match for the last number of the sequence. This is because any cycle must end the sequence.

Simplified example

Here is the simplified code:

#define MAX_INPUT_LENGTH 50
void readInputFile( std::string fileName )
{
 std::ifstream infile( fileName );
 std::vector<int> inputValues(MAX_INPUT_LENGTH);
 std::string record;
 while( std::getline( infile, record ) )
 {
 std::istringstream iss(record);
 int i = 0;
 int value = 0;
 while( iss >> value )
 inputValues[i++] = value;
 int lastValue = inputValues[i-1];
 for (int j = i-2; j >= 0; j--) {
 if (inputValues[j] == lastValue) {
 // Found a cycle.
 for (j = j+1; j < i; j++)
 std::cout << inputValues[j] << " ";
 std::cout << "\n";
 break;
 }
 }
 }
 infile.close();
}

• Veedrac: What about 1 2 3 1 4 2 3 1 4 (although the Wiki link suggests the sequence is made from an iterated function, so maybe not)?
• JS1: @Veedrac What about your sequence? The code I wrote outputs 1 2 3 for it. Is that not correct? Also, I edited my answer to show that your program could not find a cycle in 3 2 1 3.
• Veedrac: 1 2 3 is not a cycle in 1 2 3 1 4 2 3 1 4 - the cycle is 2 3 1 4. There's also a strong implication that cycles must contain at least two "copies"; else 2 0 6 3 1 6 3 1 6 3 1 would be a cycle in 2 0 6 3 1 6 3 1 6 3 1. I'll admit the question is badly-formed, but I'm not sold on your reading of it.
• JS1: @Veedrac So if I use your interpretation of a cycle, then I think the sequence should be infinite. I don't think the question is well formed. For example, is there a cycle in: 1 2 3 1 2 3 4? If we assume that the sequence doesn't have to be infinite, then it should at least end in the cycle. In which case, you can start at the back end and look for the first repeat of the last number of the sequence to find the cycle.
• JS1: @Veedrac According to the wikipedia article linked by the question, the series of numbers is a sequence of iterated function values. This means that a sequence such as 1 2 3 1 4 is not allowed because 1 must always be followed by the same number (in this case 2). So I believe my original solution holds, although the new solution I added also works and is even shorter.