Best algorithm for checking 5 in a / col row in a matrix

Question

Is there a good algorithm for checking for the presence of 5 identical elements in a row or column or diagonally taking into account a square matrix, say, 6x6?

There is, of course, a naive algorithm for iterating through each spot, and then for each point in the matrix, iterating along this line, col, and then diagonally. I am wondering if there is a better way to do this.

Answer 1

You can check if there are identical elements in the matrix of integers in one pass .

Suppose n is the size of the matrix and m is the largest element. We have n columns, n rows and 1 diagonal. In the column "column", row or diagonal, we have no more than n different elements.

Now we can create a histogram containing the (n + n + 1) * (2 * m + 1) element. representing rows, columns, and a diagonal, each of which contains no more than n different elements.

size = (n + n + 1) * (2 * m + 1) histogram = zeros(size, Int) 

Now the tricky part is how to update this histogram?

Consider this function in pseudo-code:

 updateHistogram(i, j, element) if (element < 0) element = m - element; rowIndex = i * m + element columnIndex = n * m + j * m + element diagonalIndex = 2 * n * m + element histogram[rowIndex] = histogram[rowIndex] + 1 histogram[columnIndex] = histogram[columnIndex] + 1 if (i = j) histogram[diagonalIndex] = histogram[diagonalIndex] + 1 

Now all you have to do is iterate over the histogram and check if there is an element> k

Answer 2

You can save the histogram in the dictionary (display element type → int). And then you histogram[element] over a row or column or diagonal and increase the histogram[element] , and also check at the end to see if you have 5s in the histogram or if you can allow more than 5 copies, you can just stop once you reach 5 for any item.

A simple, one-dimensional example:

 m = ['A', 'A', 'A', 'A', 'B', 'A'] h = {} for x in m: if x in h: h[x] += 1 else: h[x] = 1 print "Histogram:", h for k in h: if h[k]>=5: print "%s appears %d times." % (k,h[k]) 

Output:

 Histogram: {'A': 5, 'B': 1} A appears 5 times. 

Essentially, h[x] will store the number of times the element x appears in the array (in your case, it will be the current row or column or diagonal). Elements should not appear sequentially, but the count will be reset every time you start looking at a new row / column / diagonal.

Answer 3

For rows, you can save a counter that indicates how many of the same elements in the row you currently have. To do this, iterate over the line and

• If the current item matches the previous item, increment the counter by one. If the counter is 5, you found 5 items that you wanted.
• If the current item does not match the previous item, set the counter to 1.

The same principle can be applied to columns and diagonals. You will probably want to use an array of counters for columns (one element for each column) and diagonals so that you can iterate over the matrix sequentially.

I made a small example for a smaller size, but you can easily change it:

 n = 3 matrix = [[1, 2, 3, 4], [1, 2, 3, 1], [2, 3, 1, 3], [2, 1, 4, 2]] col_counter = [1, 1, 1, 1] for row in range(0, len(matrix)): row_counter = 1 for col in range(0, len(matrix[row])): current_element = matrix[row][col] # check elements in a same row if col > 0: previous_element = matrix[row][col - 1] if current_element == previous_element: row_counter = row_counter + 1 if row_counter == n: print n, 'in a row at:', row, col - n + 1 else: row_counter = 1 # check elements in a same column if row > 0: previous_element = matrix[row - 1][col] if current_element == previous_element: col_counter[col] = col_counter[col] + 1; if col_counter[col] == n: print n, 'in a column at:', row - n + 1, col else: col_counter[col] = 1 

I left the diagonals to make the example short and simple, but for diagonals you can use the same principle as in the columns. The previous element would be one of the following (depending on the direction of the diagonal):

 matrix[row - 1][col - 1] matrix[row - 1][col + 1] 

Please note that in the second case, you will need a little more effort. For example, cross a row in the inner loop from right to left.

Answer 4

Your best approach may depend on whether you control the placement of elements.

For example, if you were building a game and simply placing the last element in the grid, you could capture in four lines the vertical, horizontal and diagonal stripes that intersected this point, and use the same algorithm on each strip, counting each element and evaluating the results . The algorithm may vary slightly depending on whether you count five contiguous elements out of six or allow spaces until the total number is five.

Answer 5

I do not think that you can avoid iteration, but you can at least make XOR of all elements, and if the result of this is 0 =>, they are all equal, then you do not need to make any comparisons.

Answer 6

You can try to improve your method with the help of several heuristics: use the knowledge of the matrix size to exclude sequences of elements that are not suitable and to suspend unnecessary calculations. If the given vector size is 6, you want to find 5 equal elements, and the first 3 elements are different, further calculation does not make any sense.

This approach can give you a significant advantage if 5 equal elements in a row are rare enough.

Answer 7

If you encode rows / columns / diagonals as bitmaps, "five in a row" means "mask% 31 == 0 && mask / 31 == power_of_two"

• 00011111: = 0x1f 31 (five lines in a row)
• 00111110: = 0x3e 62 (five in a row)
• 00111111: = 0x3f 63 (six in a row)

If you want to consider the case with six in a row as well as five in a row, the simplest way is probably the following:

 for ( ; !(mask & 1) ; mask >>= 1 ) {;} return (mask & 0x1f == 0x1f) ? 1 : 0; 

Maybe the Stanford bit tuning department has a better solution or suggestion that doesn't require a loop?