Search code examples
algorithmcomputer-sciencetraveling-salesman

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

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

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: Picture 2

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

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

For this example, the correct answer is these blocks: Picture 5

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!

Solution

  • 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.

    Pic

    Additional note:

    Given that you only have 3 colours, the running time of brute force will be O(n3), which is quite a lot less than the O(n!) or O(2n) 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(n1n2n3) where ni is the amount of blocks with the i-th colour.