Numbers question

[jared181]

Hi,
I got a numeric question

You get a streaming of 1's and 0's.

You need to detect when the streaming satisfies the following sequence:
1. at least six 1's
2. the 1's form over 50% of the sequence

For example, you get the following stream


0 -- 0 -- 0 -- 1 -- 0 -- 1 -- 0 -- 0 -- 0 -- 1 -- 1 -- 1 -- 1 -- 1-- 0 -- 1

At the 13th Cycle (counting from 1), you should raise a flag the the #4-#13 Sequence satisfied the requirements.

I know it's not necessarily C++ question, but i'd still love to hear your idea how to detect it.

Thank you very much.

[JLBorges]

Use a sliding window.
Minimum window size: 6 (at least six 1's)
Maximum window size: 11 (1's form over 50% of the sequence)

[jared181]

Hi JLBorges,

Thank you very much.

This is a wonderful idea!

I got a question please.

--EDIT--

How do you know when to clear the window size and start it all over again?

[JLBorges]

> How do you know when to clear the window size and start it all over again?

It is a Markov chain; we don't completely clear the window size and start it all over again.
Instead, we keep history of up to a maximum of the window size.

Something like this:

#include <iostream>
#include <deque>

int main()
{
    const std::size_t ONES_REQUIRED = 6 ; // minimum six ones
    const std::size_t WINDOW_SIZE = ONES_REQUIRED*2 - 1 ; // more than 50% ones

    std::deque<bool> window ;
    std::size_t cnt_of_ones = 0 ;

    bool bit ;
    while( cnt_of_ones < ONES_REQUIRED && std::cin >> bit )
    {

        if(bit) ++cnt_of_ones ;

        window.push_back(bit) ;

        if( window.size() > WINDOW_SIZE )
        {
             cnt_of_ones -= window.front() ;
             window.pop_front() ;
          
             // leading zeroes can be discarded (this may be omitted)
             while( !window.empty() && window.front() == false ) window.pop_front() ;
        }
    }
}

[jared181]

Hi JLBorges

Thank you very much again!

instead of the the Deque,

I'd be possible to simply allocate a 11-element circular array, with two points - pstart, pend, that will move circularly across the array, right?

[JLBorges]

Yes.

If the bit stream is arriving at a rapid rate (say, a million bits a second), we would get better performance with a ring buffer (in-cache access).

[jared181]

Thank you very much JLBorges.

The Ring Buffer, unlike other Ring Buffers, should be with Two Pointers, one to its start and one to its End.

When the Window Size is Max, the Start and End Pointers will differ by 1.

When the Window Size is less than Max, they will differ by more than 1.

[JLBorges]

> When the Window Size is Max, the Start and End Pointers will differ by 1.

If we visualise it as a ring.
If we visualize it as linear (the underlying array), if the end pointer is at the end of the array, the start pointer would be at the begin of the array.

.............................................
|   |   |   |   |   |   |   |   |   |   |   | 
.............................................
^                                           ^
|                                           |
start                                       end

Using boost::circular_buffer<> with the example input in the first post:

#include <iostream>
#include <boost/circular_buffer.hpp>
#include <algorithm>

int main()
{
    const int ONES_REQUIRED = 6 ; // minimum six ones
    const int MAX_WINDOW_SIZE = ONES_REQUIRED*2 - 1 ; // more than 50% ones

    boost::circular_buffer<bool> window(MAX_WINDOW_SIZE) ; // ring buffer
    int nbits = 0 ; // count of total bits seen
    
    std::cout << "input bit stream: " ;
    bool bit ;
    while( std::count( window.begin(), window.end(), true ) < ONES_REQUIRED && std::cin >> bit ) 
    {
        ++nbits ;
        window.push_back(bit) ;
        std::cout << bit << ' ' ;
    }
    
    while( window.front() == false ) window.pop_front() ; // knock off leading zeroes
    
    std::cout << "\n  found sequence: " ;
    for( int bit : window ) std::cout << bit << ' ' ;
    // **** alert: unusual **** : bit count starts at one, not zero
    std::cout << "(bits #" << nbits - window.size() + 1 << " to #" << nbits << " in the input stream)\n" ;
}

http://coliru.stacked-crooked.com/a/8563c0e163e2db4e

Note: you may want to avoid std::count() each time through the loop by keeping manual counts.