Ndtyjky

I have tried this question and I am able to get the answer as 149 by the principle of inclusion and exclusion but a standard book solutions gave it as 147. I want to confirm whether I am wrong or right. I am expecting a detailed answer as my question and clear and from a standard book.strong text

The correct answer seems to be 147.
I did exhaustive search by constructing a binary tree with nodes that have as values 0 or 1 whose paths from the root to the leaves correspond to all possible 8-bit strings (that is, we start from the root with two branches that lead to two level-1 nodes with values 0 and 1. From each such node we draw another two branches that lead to two level-2 nodes with values 0 and 1. We go like this until we build all possible paths). Some pruning applies here: when one of the paths has three consecutive 0's or four consecutive 1's we stop right there. Likewise, if the path built so far does not allow for the possibility to contain a sequence of three 0's or four 1's we stop right there too.

Below there is a simple piece of python code with an implementation (not optimized, only some pruning is performed).

def pruning_pos(lst):

    '''Pruning function over a list ('lst')'''

    if len(lst) >= 3:

        # if there are three consecutive 0's...

        if lst[-3:] == [0, 0, 0]:       

            return True

        else:

            if len(lst) >= 4:

                # if there are four consecutive 1's...

                if lst[-4:] == [1,1,1,1]: 

                    return True

    return False



paths = [[0], [1]]                              

count = 0

for i in xrange(7):

    new_paths =                               # candidate paths

    for c in paths:

        for elem in [c+[1], c+[0]]:

            if pruning_pos(elem):               # if it contains sequence of interest...

                count += 2**(8-len(elem))       # count all subpaths we are pruning 

            else:       

                new_paths.append(elem)          

    paths = new_paths[:]



print count