Правильный ответ, кажется, 147.
Я провел исчерпывающий поиск, построив двоичное дерево с узлами, имеющими значения 0 или 1, чьи пути от корня к листьям соответствуют всем возможным 8-битным строкам (то есть мы начинаем с корня с двумя ветвями, которые ведут к двум узлы уровня 1 со значениями 0 и 1. Из каждого такого узла мы рисуем еще две ветви, которые ведут к двум узлам уровня 2 со значениями 0 и 1. Мы будем идти так, пока не построим все возможные пути). Здесь применяется некоторое сокращение: когда один из путей имеет три последовательных 0 или четыре последовательных 1, мы останавливаемся прямо здесь. Аналогично, если путь, построенный до сих пор, не допускает возможности содержать последовательность из трех нулей или четырех единиц, мы также останавливаемся здесь.
Ниже приведен простой фрагмент кода python с реализацией (не оптимизирован, выполняется только некоторое сокращение).
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