Судя по всему задание - учебное, задание, скорее всего, составлял спец по алгоритмам. Поэтому готового решения задачи приводить не буду, а дам подсказки.
1. Массив
Map можно конвертировать в массив байтов или просто рассматривать каждую строку, как массив битовых значений, соответствующих байту.
Внешним циклом на этом этапе, будет перебор строк.
В таком случае можно применять битовую логику:
byteVal = Map[idx][0]*128+ Map[idx][1]*64+ Map[idx][2]*32+ Map[idx][3]*16+ Map[idx][4]*8+ Map[idx][5]*4+ Map[idx][6]*2+Map[idx][7]*1;
Где
idx
- это номер проверяемой циклом строки. Кстати, для совсем кошерного программирования, правильнее будет вычислять
byteVal
также в цикле, заменив фиксированные значения во вторых квадратных скобках на другой индекс (позиции), а множитель - это все числа, которые можно представить степенью двойки, используя лишь один байт с одним установленным битом на всех возможных позициях.
Как с помощью битовых операций получать в цикле такие числа, смотри в примере кода ниже.
2. теперь, последовательно сравним
byteVal
с числами, содержащими подряд 3 единицы в битовом выражении. Таких чисел, будет всего 6(!) - поиграйтесь с калькулятором, чтобы убедиться.
Это можно записать в одну операцию (чисел для сравнения небольшое количество, их легко подготовить с помощью калькулятора и назначить константам), либо использовать операцию сдвига, взяв за основу число 7, которое есть 7 и одинаково 7 и в 8ми, и в 10ти, и в 16ти разрядных записях - все-равно: 7 = 0x7 = 0o7, и все остальные, нужные для тестирования значения получать в цикле используя побитовый сдвиг.
Т.е. внутри цикла перебора строк, после вычисления значения байта:
var testVal = 7;
for (var i = 0; i < 6 OR ; i++) {
if ( profit = byteVal & testVal === testVal )
console.log('Profit найден в позиции %i', 6-i);
testVal <<= 1; // то же, что и возведение 2 в следующую степень
}
UPD: кого-то может удивить, а где оптимизация сдвига? дело в том, что принцип необходимо и достаточно, никто не отменял. Для слишком длинных строк, такой способ непременим - ограничение размера сдвига для Javascript - 32.
Для вычисления актуального размера сдвига нужно ГОРАЗДО больше операций, чем лишние пару циклов с побитовым сравнением. Это справедливо даже для ассемблера, а для любой реализации Javascript в частности - ваабче в 100500 раз. Мы уже на каждой итерации внешнего цикла в данном шаге экономим пару циклов.
Код приведен в соответствие со стандартами ECMA262 (ES5), новых фишек ES6 (ES2015) в нем нет.
3. Внешний цикл, в отличие от предыдущего шага, лучше будет сделать - для тестового значения. Внутренний цикл - для номера строки, начинающей блок сравнения, состоящий из 3 смежных строк - для просмотра, совпадений по вертикали, проходим циклом по строкам 6(!) раз, вычисляем
byteVal
для каждой из 3х строк блока сравнения, будем проверять значения на совпадение одного бита, т.е. начальное значение
testVal = 1
, сдвигать влево, тоже будем на 1 бит.
Для оптимизации алгоритма, будем сравнивать сначала
byteVal
для 1й тестируемой строки, если не совпадает, сразу увеличиваем индекс начальной строки на 1 и уходим на следующий шаг, иначе - (если 1е сравнение
== profit
) сравнение второй строки набора сравнения, если неудачно - прибавляем к индексу 2, а если сравнение неудачно только на 3й строке - 3, и соответственно - следующий шаг сравнений.
Оптимизация заключается в том, что мы пропускаем комбинации строк, где заведомо не будет подряд значений. Т.е. если при проверке 3й строки мы выяснили, что профита не светит, то мы начинаем проверку, со следующей строки, но считаем ее первой строкой проверяемого набора, т.е. сдвигаем указатель начала проверяемого блока сразу на 3 позиции, т.к. последовательная проверка блоков со смещением +1 и +2 - заведомо не дадут профита, т.к. мы уже точно знаем, что на этом участке с профитом - облом.
4. Второй вариант решения по нахождению совпадений по столбцам - это транспонировать ("развернуть" массив, сделав строки столбцами) массив Map, и к нему применить шаги 1 и 2. Либо относиться к нему как к заведомо транспонированному, заменив перебор строк, на перебор позиций, тогда при вычислении byteVal, каждое Map[idx][x], заменить на Map[x][idx].
Подробнее о битовых операциях на
DevDocs.io и на
Javascript.ru (по-русски)
По алгоритмам поиска, на основе которого построена оптимизация поиска, советую почитать Дональд Кнут "Сортировка и поиск", либо Томас Кормэн и др. "Алгоритмы. Построение и анализ".
P.S.: Честно говоря, на написание рабочего решения, мне понадобилось, в 20(!) раз меньше времени и раз в 5 меньше текста. Цените ленивые неучи, для вас старался, а то помрет старая гвардия и ваши рабочие места займут старательные индусы и дотошные китайцы!
UPD2: в литературе по графике, распознаванию образов и еще каким-то анализаторами, такие задачи встречаются, как части, только массивы данных дец поширше, и знаааачительно подлиннее.