How to find three consecutive ones using bit logic?

Question

JavaScript

What is the way and or algorithm to find three consecutive ones using bitwise logic? If possible, then taking into account both the horizontal and vertical rows.

var Map = [
  [0, 0, 1, 1, 1, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0]
];

Answer 1

Apparently, the task is educational, the task, most likely, was compiled by a specialist in algorithms. Therefore, I will not give a ready-made solution to the problem, but I will give hints.
1. The Map array can be converted to an array of bytes, or simply treat each row as an array of bit values ​​corresponding to a byte.
The outer loop at this stage will be iterating over the rows.
In this case, you can use bit logic:
Where idxis the number of the line being checked by the loop. By the way, for completely kosher programming, it would be more correct to calculate byteValalso in a loop, replacing the fixed values ​​​​in the second square brackets with a different index (position), and the multiplier is all numbers that can be represented by a power of two using only one byte with one bit set on all possible positions.
How to get such numbers in a loop using bit operations, see the code example below.
2. now, sequentially compare byteValwith numbers containing 3 units in a row in a bit expression. There will be only 6 such numbers (!) - play around with the calculator to make sure.
This can be written in one operation (there are a small number of numbers for comparison, they are easy to prepare with a calculator and assign to constants), or use the shift operation, taking as a basis the number 7, which is 7 and the same 7 in 8 and 10, and in 16-bit records - all the same: 7 = 0x7 = 0o7, and all the other values ​​needed for testing are obtained in a cycle using a bit shift.
Those. inside the loop iterating over the lines, after calculating the value of the byte:

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: it may surprise someone, but where is the shift optimization? The fact is that the principle is necessary and sufficient, no one has canceled. For strings that are too long, this method is indispensable - the Javascript shift size limit is 32.
To calculate the actual shift size, you need MUCH more operations than an extra couple of bitwise comparison loops. This is true even for assembler, and for any implementation of Javascript in particular - 100500 times more. We already save a couple of cycles at each iteration of the outer loop in this step.
The code is aligned with the ECMA262 (ES5) standards, there are no new ES6 (ES2015) chips in it.
3. The outer loop, unlike the previous step, would be better done - for the test value. Internal loop - for the line number that starts the comparison block, consisting of 3 adjacent lines - for viewing, vertical matches, we loop through the lines 6 (!) Times, calculate byteValfor each of the 3 lines of the comparison block, we will check the values ​​​​for a match of one bit , i.e. initial value testVal = 1, shift to the left, we will also be 1 bit.
To optimize the algorithm, we will compare first byteValfor the 1st tested string, if it does not match, immediately increase the index of the initial string by 1 and go to the next step, otherwise - (if the 1st comparison== profit) comparison of the second line of the comparison set, if unsuccessful - add 2 to the index, and if the comparison is unsuccessful only on the 3rd line - 3, and accordingly - the next step of comparisons.
The optimization lies in the fact that we skip combinations of strings where there will certainly not be consecutive values. Those. if, when checking the 3rd line, we found out that there is no profit, then we start the check from the next line, but consider it the first line of the set being checked, i.e. we shift the pointer of the beginning of the checked block by 3 positions at once, because successive checking of blocks with an offset of +1 and +2 - obviously will not give a profit, because. we already know for sure that on this site with a profit - a bummer.
4. The second solution for finding matches in columns is to transpose ("expand" the array, making rows columns) the Map array, and apply steps 1 and 2 to it. positions, then when calculating byteVal, replace each Map[idx][x] with Map[x][idx].
Read more about bit operations on DevDocs.io and on Javascript.ru (in Russian)
For search algorithms, on the basis of which search optimization is built, I advise you to read Donald Knuth "Sorting and Search", or Thomas Korman et al. "Algorithms. Construction and analysis".
PS: To be honest, it took me 20 (!) times less time and 5 times less text to write a working solution. Appreciate lazy ignoramuses, I tried for you, otherwise the old guard will die and your jobs will be taken by diligent Indians and meticulous Chinese!
UPD2: in the literature on graphics, pattern recognition and some other analyzers, such tasks are found, as parts, only data arrays are wider, and much more authentic.

Answer 2

And what's stopping you "on the forehead" to compare three consecutive elements in the array and move to the next one?

Answer 3

var l = Map.length;
var l2 = Map[0].length;
for(var i = 0; i < l; i++) {
  var el = Map[i];
  for(var i2 = 0; i2 < l2; i2++) {
    if(el[i2] != 0) {
      if(el[i2 + 1] != 0 && el[i2 + 2] != 0); //Нашли
      if(Map[i + 1][i2] != 0 && Map[i + 2][i2] != 0;); //Нашли
    }
  }
}

The logic, I think, is clear: we are looking for units only if we have found a unit.
PS You can optimize even more, but my eyes already hurt)

Answer 4

My bike in PHP (with optimized search algorithm):

<?php
error_reporting	(E_ALL); // включаем лог ошибок

function array_flatten($array) {
   $return = array();
   foreach ($array as $key => $value) {
       if (is_array($value)){ $return = array_merge($return, array_flatten($value));}
       else {$return[$key] = $value;}
   }
   return $return;
}

function rotate90($array) {
  array_unshift($array, null);
  $array = call_user_func_array('array_map', $array);
  $array = array_map('array_reverse', $array);
  return $array;
}

$Map = [
  [0, 1, 1, 1, 0, 0, 1, 1],
  [0, 0, 0, 1, 0, 1, 0, 0],
  [1, 0, 1, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 1],
  [0, 1, 0, 0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 1, 1]
];

$Map90 = array_flatten(rotate90($Map));
$Map = array_flatten($Map);

$s='';
$s90='';
foreach ($Map as $k=>$i) {
  $s.=$i;
  $s90.=$Map90[$k];
}

echo $s.'<br>';
echo $s90.'<br>';

 //убрать переносы на след.строку
$i=0;
do {
   $n=strpos($s,'111',$i++);
   if ($n) {
      if($n%8>5) $i=8*(1+floor($n/8));
      else break; //найдено! :)
   } else break; //не найдено :(
} while (-1);

 //убрать переносы на след.строку
$i=0;
do {
   $n90=strpos($s90,'111',$i++);
   if ($n90) {
         if($n90%8>5) $i=8*(1+floor($n90/8));
        else break; //найдено! :)
   } else break; //не найдено :(
} while (-1);

if ($n90!==false) {
   $n90=(8-$n90%8-3)*8+floor($n90/8); //конвертим в верный индекс
   if(!$n||$n&&$n90<$n) $n=$n90; //берём минимальный ближайший к началу.
}

//OUT
if ($n!==false) {
 echo "Позиция в массиве (начиная с 0): ".$n.'<br>'; //позиция первого элемента совпадения в "плоском" массиве.
 echo "Координаты по X*Y в двумерном массиве: ".($n%8).'x'.floor($n/8); //COLxROW
} else echo "не найдено!";
?>

Answer 5

The statement of the problem is not clear, or rather, what do you mean by bit logic if it is true / false then the sign of 3 consecutive units horizontally = x[i] AND x[i+1] AND x[i+2] (x=bit)
if consider the array string as a byte, then the expressions (x AND 0x07) OR (x AND 0x0E) OR (x AND 0x1C ) OR (x AND 0x38) OR (x AND 0x70) OR (x AND 0xE0) x[i] AND x[i+1] AND x[i+2] (х=byte and more) a sign of the presence of 3 single bits vertically.

Answer 6

In any high-level language, your "bit logic" will be slower and look uglier than primitive integer summation.
i := 0;
j := 0;
repeat
repeat
s := 0;
for k := 0 to 2 do
s := s + arr[j, i +k];
inc(i);
until (i < 5) and (s > 0) ;
inc(j);
until (j <= High(arr)) and (s > 0) ;