Algorithms – Fastest Way to Check if Two Square 2D Arrays Are Rotationally and Reflectively Distinct

algorithmsmath

The best idea I have so far is to rotate first array by {0, 90, 180, 270} degrees and reflect it horizontally or/and vertically. We basically get 16 variations [1] of first array and compare them with second array. if none of them matches the two arrays are rotationally and reflectively distinct.

I am wondering if there is more optimal solution than this brute-force approach?

[1]

0deg, no reflection
0deg, reflect over x
0deg, reflect over y
0deg, reflect over x and y
90deg, no reflection
...

Best Answer

Break this into two problems:

How would you compare two square arrays - I'll call these matrices - that cannot be rotated or reflected, and
How would you compare an item that can be rotated and reflect against another item

Implementing the first problem with a naive approach gives a very simple answer - walk the matrices in parallel, stopping once you find non-equal values. If you walk the entire matrix without non-equal values then the matrices are equal. To walk the matrix, loop through columns, inner loop through each row, and compare values. Note that walking the matrix allows us to enumerate over all items in the matrix as if they were a single linear collection.

For the second problem, there are eight different ways to rotate and reflect a matrix. There are four corners to be used as a starting point, and an algorithm can walk from each corner in two directions (i.e. horizontally or vertically). Thus we will need to perform 'problem 1' over each of the eight perspectives of the original matrix.

How would I implement this? We can walk the eight matrices in parallel or sequentially; I'll implement this sequentially as potentially faster (if the first matrix checked is a match, no other checks are required) but more importantly it will be simpler.

Each of the eight matrices to check should be represented by a walking function f(x) to retrieve the xth value. For instance, in an n by n square array A,

f1(x) = A[x % n, x / n]; // walking rows first, then columns
f2(x) = A[x / n, x % n]; // walking columns first, then rows

// using a different starting point
f3(x) = A[n - (x / n), x % n];
f4(x) = A[n - (x % n), x / n];

and so on. Now simply,

foreach walking function
    foreach value in walking function
        if value not equal to corresponding value in target 
            next walking function
    return true // not non-equal values found
return false // none of the functions matched

Related Solutions

Are suffix trees and suffix arrays identical? What are the differences

A suffix array is a space-efficient datastructure, which, if stored together with the original string, provides the same functions as a suffix tree.

So yes, you can think of a suffix array as a storage mechanism for suffix trees. Depending on the details, there may be performance costs to using arrays over full-blown trees, which typically are outweighed by the space-use benefits. I believe the arrays are constructed almost identically to the way trees are constructed, and, in practice, suffix arrays are the preferred method for storing/representing a suffix tree.

Array Multiplication and Division

Ruby’s model is provided more for convenience than correctness, and is inconsistent:

array + array is array concatenation, allowing duplicates, but array - array is set difference, removing duplicates: [1, 1] - [1] is [], not [1].
- is not the inverse of +, because it’s not the case that a + b - c == a for all Array instances a, b, and c: take [1] + [1] - [1].
array * fixnum is defined as iterated array concatenation, but fixnum * array is not defined at all.

For purely array-based operations, I would expect + and - to be inverses:

[1, 2] + [3, 1] == [1, 2, 3, 1]
[1, 2, 3, 1] - [3, 1] == [1, 2]

- would remove elements from the tail just as + added them. Similarly for * and /:

[1, 2] * 3 == [1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2] / 3 == [1, 2]
[5, 1, 2, 1, 2] / 2 == [1, 2]

/ would first discard elements from the left until a.size % b == 0. Why from the left? Well, I would expect an array modulus operator to satisfy the law:

a % b == a - (b * (a / b))

And that rule seems to work if you go through a few examples:

[1, 1] % 2 == [1, 1] - (2 * ([1, 1] / 2)) == []
[5, 1, 1] % 2 == [5, 1, 1] - (2 * ([5, 1, 1] / 2)) == [5]

This is basically defining division as iterated subtraction.

There are a couple of consistent and reasonably intuitive interpretations of array ♦ array:

Cartesian product: [1, 2] ♦ [3, 4] == [1 ♦ 3, 1 ♦ 4, 2 ♦ 3, 2 ♦ 4]
Pairwise product: [1, 2] ♦ [3, 4] == [1 ♦ 3, 2 ♦ 4]

With a Cartesian product, the size of the result is the product of the size of the inputs. This is how list comprehensions and the list monad work in Haskell:

[x ♦ y | x <- [1, 2], y <- [3, 4]]

do
  x <- [1, 2]
  y <- [3, 4]
  return (x ♦ y)

A pairwise product also makes sense, in that ([x1, y1, z1] * [x2, y2, z2]).reduce(:+) would be the dot product of the vectors [x1, y1, z1] and [x2, y2, z2]. Of course, you would need to define the result when the inputs are of different lengths; in Haskell, the zipWith function takes the shorter of the two input lists:

   zipWith (♦) [1, 2] [3, 4, 5]
== zipWith (♦) [1, 2] [3, 4]

So the answer is that there are several possible interpretations, the choice of which is up to the designers of languages and libraries. As long as they’re self-consistent, none of them is strictly more “right” or “intuitive” than any other. The established convention in array languages is for array * array to refer to pairwise product, because this generalises well to higher dimensions of array, and from promoting scalars to arrays of appropriate dimension.