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?
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?Originally Posted by neeraj87
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.
Last edited by quzah; 08-27-2011 at 03:06 AM.
Hope is the first step on the road to disappointment.
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.
That's a good one, Quzah! Describes someone's economic plan, perfectly.Hope is the first step on the road to disappointment.
Last edited by Adak; 08-27-2011 at 03:27 AM.
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?Code:char fromstream( void ) { static char bits[] = { ... }; static size_t here; return bits[ here++ % sizeof( bits ) ]; }
Quzah.
Hope is the first step on the road to disappointment.
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
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
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.
@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 ?
