Search code examples
algorithmbit-manipulationpermutationdivide-and-conquer

Fair Attraction Algorithm

Fair Attraction Problem

What I've Tried
I tried thinking about the switches as bits of a bit string. Basically, no matter the state, I need to get them all to zero. And since this question is in a chapter about decrease-and-conquer I tried to solve for n=1. But, I can't even come up with a brute force solution to ensure that one switch is off.

If you have any ideas or hints, please help, thank you.

Solution

  • Since the only feedback we get is when we're in the goal state, the problem is to explore all possible states as efficiently as possible. The relevant mathematical object is called a Gray code. Since you're looking for a recursive construction, the algorithm is:

    • If there are no switches, then there's one state, and we're in it.
    • Otherwise, pick a switch. Recursively explore all configurations of the other switches. Flip the held-out switch and then recursively explore the others again.