Steam Matching Tiles

Question

Recently, in a coding contest, I came across this issue.

We have 1000 tiles, where each tile is a 3x3 matrix. Each cell in the matrix has an integer value from 0 to 9, which means the height of the cell. The problem was to find the maximum pairs of tiles, such as that they fit perfectly. Tiles can be rotated to fit. in it means for tile A and tile B

A [i] + B [i] = const for i = 0 to 8

The approach I solved for this problem was that I could maintain a hash value corresponding to each tile. Then I will find possible combinations of tiles that would be a possible fit and search in the hash table.

Ex. For the tiles below

5 3 2 4 6 7 5 7 8 4 8 9 matches with 5 1 0 for const = 9 & with 6 2 1 for const=10 1 4 5 8 5 4 9 6 5 

for this snippet, "const" will range from 9 (adding 0 to the maximum element) to 10 (adding 9 to the minimum element). Therefore, I would get two possible combinations for tiles, which I would look in the table.

But this method is greedy and does not give the desired answer, and also I could not think of the correct hash function, which would take into account all possible rotations.

So, what would be a good approach to solve this problem?

I am sure that there is a problem with brute force to solve this problem, but I really wondered if there is a viable solution to the problem in the line of the problem "in pairs equal to k ".

Answer 1

For n = 1000, I would stick to the brute force solution O (n ^ 2). However, the O (n log n) algorithm is described below.

Lexicographic ordering is defined by the following less operator:

For two matrices M1, M2 define M1' as M1 if M1[1] positive, and -M1 if M1[1] negative, or also M2'. We say that M1<M2 if M1'[1]<M2'[1], or if M1'[1] == M2'[1] and M1'[2] < M2'[2], or if M1'[1] == M2'[1] and M1'[2] == M2'[2] and M1'[3] < M2'[3] , etc.

• Subtract the middle element of each matrix from the remaining elements of the matrix, i.e. A'[5] = A[5] and A'[i] = A[i] - A[5]. Then A 'corresponds to B' if A'[i] +B'[i] = 0 for i!=5 , and the height is A'[5] + B'[5].

• Create an array of matrices and a dictionary. Rotate each matrix so that the upper left corner has a minimum absolute value before adding it to the array. If there are several angles with the same absolute value, duplicate the matrix and save both rotations in an array.

  If some rotation of the matrix coincides with itself and i,j are the rotation indices of this matrix, add value-word pairs (i,j) and (j, i) to the dictionary.

• Create an array of S indices 1,2 ... and sort S using lexicographic ordering.

• Instead of performing operations O (n ^ 2) to check all possible pairs of matrices, it is only necessary to verify that all pairs of matrices with indices S_i and S_(i+1). If a pair of matrices is suitable, use a dictionary to verify that the two matrices are not rotations of the same source matrix before calculating the elevation of the pair.

Answer 2

Not sure if this is the most efficient way to do this, but it works.

What would I do:

• Go through all the tiles and check the maximum and minimum value of each tile and save it in another array.
• Check all possible pairs.
  • If min(A) + max(B) == min(B) + max(A) , then check if any rotation of B by A is suitable. If so, add 1 to your account.
  • Otherwise, this does not work, so you can skip checking this pair.

Note. . The reason for saving the maximum and minimum values ​​for each tile is that it can save us unnecessary calculations and check the rotation, as in O(1) , we can check if it suits.