Algorithm - How to pair blocks efficiently

Question

lets say, we have two cubes of 3X3 with different heights in cell. Each cell value represents the height of that cell. For example in below block 1, cell (1,1) has height of 1, cell(1,2) has height of 2 and so on.

block-1,

1 2 3
1 3 2
3 1 2

block-2,

4 3 2
4 2 3
2 4 3

Giver two such blocks how to check efficiently whether two blocks can be connected in such a way that there would be no cell mismatched and both blocks together produce a cuboid.

For example, above block-1 + block-2 can be connected and resultant block will be a perfect cuboid height 5. Resultant cuboid will be,

5 5 5
5 5 5
5 5 5

Extension of the problem: Given a set (size >= 50K) of such 4X4 blocks how to connect pair of blocks and produce maximum height sum of resultant cuboid? You can take only matched blocks full height to maximise total height sum. Non matched blocks will be ignored. Each cell height can be up to 20 unit.

Further extension of the problem: Blocks can be given in such a way that might be rotated to make pair with other to maximise resultant cuboids height sum.

Any clue?

Answer 1

You could solve the problem in two steps (1) find all pairs of blocks that connect (build a cuboid) and (2) find the best pairing that maximizes the total height.

Find connecting pairs

For this I would (a) build a surface representation for each block, (b) hash the blocks by their surface representation and (c) search for each block all connecting blocks by looking for the connecting surface models.

(a) Building the surface model

The basic idea is to represent each block by its surface. For this you just subtract the minimum entry in the matrix from every entry in the matrix

surface representation of block-1 will be

1 2 3   -1   0 1 2       
1 3 2   -->  0 2 1
3 1 2        2 0 2

and surface representation of block-2 will be

4 3 2   -2    2 1 0
4 2 3   -->   2 0 1
2 4 3         0 2 1

(b) hash the blocks

Now you hash the blocks by their surface representation

(c) Finding connecting pairs

For each block you then compute the connecting surface model, by taking the maximum value in the surface representation and subtracting the entries in the matrix from it,

for block-1 this will yield

    0 1 2     2 1 0     
2 - 0 2 1  =  2 0 1   
    2 0 2     0 2 0

the blocks with this surface representation can be found using the hash table (note that the surface representation of block-2 will match).

Note: when you allow for rotation then you will have to perform 4 queries on the hash table with all possible rotations.

Finding the best pairing

To find the best pairing (maximizing the sum of connected blocks) I would use the Hungarian Algorithm. In order to do this you will have to build a matrix where the entry (i, j) contains the height of the block when the two blocks i and j connect and 0 otherwise.

Edit

I think the second step (finding best pairing) can be done more efficiently, by connecting pairs of matching blocks greedily (connecting pairs resulting in highest blocks first).

The intuition for this is: When you have two blocks a and b and they both have the same surface model. Then they will either both connect to another block c or they both won't connect to c. With this in mind, after the "find connecting pairs" step you will end up with pairs of groups of blocks (X_i, Y_i) where each block of X_i connects to each block of Y_i. If the two groups X_i and Y_i are of equal size, then we can connect in any way we want and will always get the same sum of height of resulting cuboids. If one of the groups (wlog Y_i) contains less elements then we want to avoid connecting to the smallest blocks in X_i. Thus we can greedily connect starting with the largest blocks and in doing so avoid connecting to the smallest blocks.

So the algorithm could work as follows:

1. (Hash each block according to its surface representation. Sort blocks with the same surface representation descending according to their offset (height of block minus surface representation)

2. Process blocks in order of descending offset, for each block: Search for connecting block cBlock with highest offset, connect the two blocks, remove cBlock from the hash table and the processing pipeline.

Overall this should be doable in O(n log n)