Need help to slove this bit pattern problem

**neeraj87** · 08-27-2011

Hi,
My question: "Write a C program to find out the repeating "bit pattern" in the stream of bits given as the input. The continuous stream of bits is given in the attached text file, 'BitStream.txt'. Bits are given in a continuous fashion in a single line. It can be assumed that the stream is made by repeating a particular pattern n times."

The following is expected as the output

- Length of bit pattern

- Exact bit pattern

- How many times the bit pattern is repeated in the given BitStream.

Ex: Consider a bit stream below

0011001100110011001100110011

The outputs expected are

- Length: 4

- BitPattern: 0011

- Number of times its repeated: 7

BitStream.txt File Contains(manually i found that stream in Bold letters is continously repeating):
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010

If anybody can help?

**neeraj87** · 08-27-2011

Correcting spelling: Need help to solve this bit pattern problem

**Salem** · 08-27-2011

So what have you tried so far?

Like for example, can you read the file into memory?

You need to show us what you can do, and what you tried, so we can help you with what you're really stuck on.

What isn't going to happen is a complete answer on a plate for you to hand in.

**Jimmy** · 08-27-2011

Please explain what you are having trouble with? At the moment it looks like you are asking for a complete solution to something that looks a lot like a homework assignment. Please read http://cboard.cprogramming.com/c-programming/announcement-homework.html

**Adak** · 08-27-2011

Well, well! A fun problem.

I see a lot more repeating bit patterns:

00
01
11
10
001
011
110
and
0110

Maybe the problem only wants the longest repeated bit pattern?

Unless I knew the correct length of the bit pattern, (or a minimum solution length to the pattern), I would use the same (shorter to longer) pattern to search for the longest pattern, while setting up the program - then switch it to work from a length of (strlen(totalPattern)) / 2 +1, down to the first pattern that repeated - that would be the longest one you could find.

If you can't seem to get started, I recommend working it through with paper and pencil several times, and note the steps you use, to solve the problem. Put those (small) steps down into order, and that's your pseudo code to start your program from.

Post up your pseudo code, if you need help with that.

And Welcome to the forum, Neeraj!

**quzah** · 08-27-2011

What consists of a repeated pattern?

101010101010 <-- that is your input

Is 10 the pattern?
Is 1010 the pattern?
Is 101010 the pattern?

Originally Posted by Adak

work from a length of (strlen(totalPattern)) / 2 +1, down to the first pattern that repeated - that would be the longest one you could find.

Is 1010101010 the pattern? (It's there, think about it.)

Quzah.

**Adak** · 08-27-2011

We'll have to wait on Neeraj to give us the info on just what the problem specifies - but it is an interesting problem, at least. Not something that's already covered in Chapter N of some tutorial. Thank you, Neeraj!

**neeraj87** · 08-27-2011

@ adah ... 00,01,11 .. etc are not repeating patterns since they are not continuously repeating..... only the bit pattern ( in bold -first 92 approx bits) is repeating 15 times and it makes full stream.

**quzah** · 08-27-2011

Originally Posted by neeraj87

@ adah ... 00,01,11 .. etc are not repeating patterns since they are not continuously repeating..... only the bit pattern ( in bold -first 92 approx bits) is repeating 15 times and it makes full stream.

I say that your pattern is actually what you think your pattern is, times five, and it only repeats three times.

Quzah.

**neeraj87** · 08-27-2011

and about my work...... I am reading one digit at a time and comapring with the previous digits( for comaprison) if they are equal than i m updating my bit pattern.
For example:
at the start 0 is comapared with next 0, so bitpattern=0.
and after that read next digit , since next is one i m updating only pointer to next at 00110 since 0 is compared with first 0 , continue nxt digit with 2nd digit from start.
similarly 0011 will be compared with 0011 and after that i will update my Bitpattern=0011,
same way i m continuing to search, but i think it is very time comsuimg. that's why i asked your help.

**neeraj87** · 08-27-2011

@quzah .... my input from file is:
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010
00110011001100011110111001111011110100011010111110 1001100001011000001011111111111001111001010

and i have to search bit pattern in this stream which is continuously repeating and making full stream.

and what i have analysed that first 92 or 94 digits are repeating in whole stream ( 15 times).

**quzah** · 08-27-2011

Are you to assume that everything is part of some pattern, or are their junk values?

Code:

01110011100100110001

For example, every 4th bit is 1, and the rest doesn't matter.

Quzah.

**quzah** · 08-27-2011

Originally Posted by neeraj87

@quzah .... my input from file is:
...
and i have to search bit pattern in this stream which is continuously repeating and making full stream.

and what i have analysed that first 92 or 94 digits are repeating in whole stream ( 15 times).

Like I said, I could see it as the first 460 bits are the pattern, and the pattern repeats 3 times. What is it they want you to turn in for your answer? 92 * 15, or 460 * 3? Do they want the longest pattern? The one that repeats the most? Or something different? Is it possible that there is more than one right answer?

Quzah.

**neeraj87** · 08-27-2011

@quzah....
example: 001100110011 : in this 0011 is repeating and making one stream

110011001100: in this 1100 is repeating and making one stream

1101110111011101: 1101 is repeating and making one stream

but if:
0111011101110000: in this case no repeating pattern (since 0111 is repeating for 3 times but at the end 0000 is present) , we have to search one pattern which is continuously repeating.

The Input for the question is also a stream of 0 and 1's.

**neeraj87** · 08-27-2011

@quzah.... in case of 460 bits ( same 92 bits pattern is repeating 5 times ) so usually it means same 92 bits pattern is again repeating. so we have max. unique bit pattern of 92 bits not 460 bits

Thread: Need help to slove this bit pattern problem

Thread Tools

Search Thread

Display

Need help to slove this bit pattern problem

Similar Threads

bit pattern

Pattern matching problem with fscanf. Any suggestions?

string pattern search problem

problem with pointers and strings (replace pattern program)

I don't know how to slove these simple questions