Need help to slove this bit pattern problem

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?

Correcting spelling: Need help to solve this bit pattern problem

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.

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

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! :D

What consists of a repeated pattern?

101010101010 <-- that is your input

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

Quote:

---

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.

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!

@ 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.

Quote:

---

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.

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.

@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).

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.

Quote:

---

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.

@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.

@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

So if the streams has 99 bits in it, for example, you don't need to check for any even number length of pattern, because they can't fit into 99 evenly, correct?

If so, then only the numbers that divide evenly into the number of bits in the stream, need to be even considered, right?

Quote:

---

Originally Posted by neeraj87

@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

---

So you are looking for what then? Can you put it into actual words? Are you trying to find the longest repeating pattern? The shortest repeating pattern? The pattern that repeats the most amount of times?

If you are looking for the longest repeating pattern, then 460 bits is the longest repeating pattern, and it repeats three times.
If you are looking for the one that repeats the most times, then it is 92 bits, repeating 15 times (unless you can find a sub-section of that repeating more than 15 times).

110111011101110111011101110111011101110100

Repeat the red through blue block a total of 8 more times. What's your answer? The red through blue occurring 9 times, or the red block occurring 10 times?

I'm just trying to see what your actual rules are for solving this problem.

Edit - Adak brings up a good point, and another question: Are you to assume that you don't know when the stream ends? You just keep reading to try to find the pattern, or do you know when it stops?


Quzah.

I'm hazy on the characteristics of the stream. Can you run that by me, one more time?

On the answer that you seek, I also need another round of explanation. Just can't nail it down yet.

Quote:

---

Hope is the first step on the road to disappointment.

---

That's a good one, Quzah! Describes someone's economic plan, perfectly.

Quote:

---

Originally Posted by Adak

I'm hazy on the characteristics of the stream. Can you run that by me, one more time?

On the answer that you seek, I also need another round of explanation. Just can't nail it down yet.

---

Code:

---

char fromstream( void )
{
    static char bits[] = { ... };
    static size_t here;

    return bits[ here++ % sizeof( bits ) ];
}

---

I was wondering if he knew how many bits there were in the stream, or, if for example, the only thing he could do was call fromstream, and be handed a "bit" from it, without knowing what the state of the stream was. Does he get to know anything about the stream (ie: the length), or is it up to him to figure out when it starts to repeat itself?


Quzah.

I understand the confusion. It's late, and there seems more questions than answers, at the moment. I'll catch up tomorrow.

Seems like something like this would do:

Code:

---

initial pattern = ""+ getNext()
while( (next = getNext() )
  if(pattern[streamindex %patternLength] != next)
    pattern = steam up to this point including next

---

Do an autocorrelation of the input signal, varying the lag from 1 to num_inputs. When the result of the autocorrelation equals that of lag 0, you've found your how often the signal repeats.

thanx all for luking into this problem.... i have solved this problem.

Quote:

---

Originally Posted by neeraj87

thanx all for luking into this problem.... i have solved this problem.

---

@neeraj: I am trying to understand below description from you @ this problem

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

Not understanding exact logic behind this. Could you explain in more detail ?