Nearest blocks, one of each color, but on different rows

Question

Let's say that I have a room with 3 different colors of blocks, labelled A, B, and C:

My goal is to find the three blocks closest to Lolo such that I have one A, one B, and one C. Additionally, each block and Lolo himself must be on different rows:

For example, no block on Row 1 may be used, since Lolo is on that row:

If we pick the A block above Lolo, no other block from Row 0 can be used:

For this example, the correct answer is these blocks:

I can easily find the closest three blocks to Lolo; however, I'm having a hard time applying the additional constraints (one of each letter, not on same row). This feels like a variation of the travelling salesman problem.

What is an efficient way of figuring out these blocks? (Even a point in the right direction would be greatly appreciated!) Thanks!

Answer 1

Greedy solution:

All picking of blocks below should be done such that it adheres to the row constraints.

1. Pick the closest block not already picked (say this is an A).
2. Pick the closest non-A block (say this is an B).
3. Pick the closest non-A, non-B (thus C) block.
4. Record this distance.
5. If there was a closer C in the same row as B, pick that C, along with the next closest B and record the distance.
   • For more than 3 colors, you'd want to just pick the next closest B in a different row.
6. Stop if the closest unpicked block is further than bestDistanceSoFar/3, otherwise repeat from 1.
7. Return the best distance.

For this I'd suggest having a sorted list for each colour.

I believe this is optimal, but why it would be requires some thought.

Preprocess:

You can remove all blocks in the same row as Lolo, as you mentioned, but also all blocks further from Lolo than another block of the same type in the same row, which is not a lot in this case, but still.

Additional note:

Given that you only have 3 colours, the running time of brute force will be O(n³), which is quite a lot less than the O(n!) or O(2ⁿ) of the TSP.

The obvious optimization to the brute force is to separate all the colours, which will result in a running time of O(n₁n₂n₃) where n_i is the amount of blocks with the i-th colour.

Answer 2

I think you should use DFS

You build the G in the next way :

1. Lolo is the root
2. Choose available block that is not have color that already visit, add to G with weight is the distance from Lolo
3. Make all block on the same row as un-available
4. If there are more available blocks Go to 2
5. If no available blocks go back Lolo, and choose block that is not direct son of Lolo

After you build the graph you can run DFS with depth 3 and choose the lowest cost path.

This will give you the lowest distance.

There are other constrains ? how fast does it need to run ?