Like Tree1Likes

Need help to slove this bit pattern problem

This is a discussion on Need help to slove this bit pattern problem within the C Programming forums, part of the General Programming Boards category; Hi, My question: "Write a C program to find out the repeating "bit pattern" in the stream of bits given ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    8

    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?

  2. #2
    Registered User
    Join Date
    Aug 2011
    Posts
    8
    Correcting spelling: Need help to solve this bit pattern problem

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,338
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Dec 2004
    Posts
    48
    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

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!
    Last edited by Adak; 08-27-2011 at 02:17 AM.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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 View Post
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

  8. #8
    Registered User
    Join Date
    Aug 2011
    Posts
    8
    @ 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.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by neeraj87 View Post
    @ 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.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Aug 2011
    Posts
    8
    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.

  11. #11
    Registered User
    Join Date
    Aug 2011
    Posts
    8
    @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).

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by neeraj87 View Post
    @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.
    Hope is the first step on the road to disappointment.

  14. #14
    Registered User
    Join Date
    Aug 2011
    Posts
    8
    @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.

  15. #15
    Registered User
    Join Date
    Aug 2011
    Posts
    8
    @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

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bit pattern
    By hell0 in forum C Programming
    Replies: 3
    Last Post: 07-25-2011, 08:38 AM
  2. Replies: 4
    Last Post: 01-10-2006, 12:23 PM
  3. string pattern search problem
    By goron350 in forum C Programming
    Replies: 6
    Last Post: 11-25-2004, 07:50 AM
  4. Replies: 5
    Last Post: 05-25-2004, 04:36 PM
  5. I don't know how to slove these simple questions
    By zaki in forum C Programming
    Replies: 9
    Last Post: 10-03-2003, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21