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

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