2
$\begingroup$

There is a network of connected electric bulbs each with a unique id. Each bulb has a switch. When the switch is clicked, the colour of the bulb changes and also the colours of connected bulbs change. The order in which the colour-change occurs is green-yellow-red-green. The network of bulbs is a connected graph (but not necesarily a complete graph). I want to find a way by which I can convert all bulbs to green. This could be represnted by sequence of ids of bulbs whose switches can be clicked to get the final outcome.

I tried to solve this by converting the problem to a graph. Each node of the graph representing a state of the network so that two states are different if there is at least one unique bulb which has different colour in those two states. Then by using Dijkstra's shortest path algorithm I tried to find a path to the final state where all bulbs have green colour. (Although in my problem I don't need a shortest path. But this is also one valid solution.) This worked fine for small networks (number of nodes less than 12). But as the number of nodes increased the number of states increased so much that my program was running forever.

  • 0
    Thanks for the pointer, @Ilmari Karonen2012-07-02

1 Answers 1

2

If the bulbs initially have different colors, and the only possible colors are green, yellow and red, there can be at most 3 nodes in the graph. There are only 4 possible connected graphs with at most 3 nodes, do it seems to be feasible simply to consult a precomputed table of solutions for each possible instance of the problem. (Especially since the answer is always "no" for three of the four possible graphs).

On the other hand, if some of the bulbs are allowed to have the same color initially, then the problem becomes more interesting. The key to improving your search algorithm is to notice that the order in which the buttons are pressed does not matter; the final state of each bulb depends only on its initial color and the number of times some button connected to it was pressed.

Given this (and the lucky coincidence that the number of colors in the cycle is prime), the simplest way to approach the problem is linear algebra: Represent each color an element of $\mathbb F_3$ (the field of integers modulo 3), and a state of the entire network as a vector with entries in $\mathbb F_3$. The actions of each button is another fixed vector (containing only 0's and 1's) that is added to the state vector, and the problem is then to find whether the difference between the initial state and the all-green state is a sum of multiples of button vectors. That is simply a system of $n$ linear equations in $n$ unknowns, where the unknowns are the number of times each button is pressed. This can be solved in $O(n^3)$ time using standard techniques such as Gaussian elimination.

  • 0
    oh! I see it now. Thanks for the explanation @Henning Makholm.2012-07-02