Detecting Cycles

Ankit Gupta

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

A file 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

Ensure to account for numbers that have more than one digit eg. 12. If there is no sequence, ignore that line.
Print to stdout the first sequence you find in each line. Ensure that there are no trailing empty spaces on each line you print. e.g.

6 3 1

help me please.....!!

5 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes14y ago
The regular expression, regexp, matches any sequence of numbers, separated by single spaces, which repeats at least once.

If you're not familiar with regular expressions, then \d matches any digit (0 to 9), \s matches whitepace and + means that what immediately precedes it occurs at least once.

So \d+ means at least one digit.

The construct (?'cycle' ...) means that everything within the parentheses should be considered to be a group with a name of 'cycle'.

\k'cycle' means match the group named 'cycle' that was previously captured.

If the Regex.Match method succeeds in finding such a sequence of numbers, the sequence - represented by m.Groups["cycle"] - is printed to the console.

Notice that this approach only looks for the first cycle - in general, there could be others. For example, there are two (1 2 3 and 4 5 6) in the following line:

1 2 3 1 2 3 4 5 6 4 5 6
Ankit Gupta14y ago
Can you please explain what this code is doing??

string regexp = @"(?'cycle'(\d+\s)+(\d+))\s\k'cycle'";
Match m = Regex.Match(sequence, regexp);

if (m.Success)
{ Console.WriteLine(m.Groups["cycle"]);
}
Vulpes14y ago
The question is asking you to detect a sequence of numbers which is repeated (at least once) in a given line of numbers. Such a sequence is often called a cycle.

So, in this line:

2 0 6 3 1 6 3 1 6 3 1

the sequence 6 3 1 is repeated three times and that's what my program should give you.
Ankit Gupta14y ago
hello sir i am unable to understand the question can you please explain what question is saying?
Vulpes14y ago
This can be done quite easily using regular expressions:

using System;
using System.Text.RegularExpressions;

class Cycle
{
static void Main()
{
string sequence = "2 0 6 3 1 6 3 1 6 3 1";
string regexp = @"(?'cycle'(\d+\s)+(\d+))\s\k'cycle'";
Match m = Regex.Match(sequence, regexp);
if (m.Success)
{
Console.WriteLine(m.Groups["cycle"]);
}
Console.ReadKey();
}
}

I'll leave you to insert the bit about reading the sequences from a file.