patterncppMinor
Playing with light switches
Viewed 0 times
playingswitcheswithlight
Problem
When you were a little kid, was indiscriminately flicking light switches super fun? I know it was for me. Let's tap into that and try to recall that feeling with today's challenge.
Imagine a row of N light switches, each attached to a light bulb. All the bulbs are off to start with. You are going to release your inner child so they can run back and forth along this row of light switches, flipping bunches of switches from on to off or vice versa. The challenge will be to figure out the state of the lights after this fun happens.
The input will have two parts. First, the number of switches/bulbs (N) is specified. On the remaining lines, there will be pairs of integers indicating ranges of switches that your inner child toggles as they run back and forth. These ranges are inclusive (both their end points, along with everything between them is included), and the positions of switches are zero-indexed (so the possible positions range from 0 to N-1).
Imagine a row of N light switches, each attached to a light bulb. All the bulbs are off to start with. You are going to release your inner child so they can run back and forth along this row of light switches, flipping bunches of switches from on to off or vice versa. The challenge will be to figure out the state of the lights after this fun happens.
The input will have two parts. First, the number of switches/bulbs (N) is specified. On the remaining lines, there will be pairs of integers indicating ranges of switches that your inner child toggles as they run back and forth. These ranges are inclusive (both their end points, along with everything between them is included), and the positions of switches are zero-indexed (so the possible positions range from 0 to N-1).
#include
#include
#include
class lights;
void ifBiggerSwitch(unsigned&, unsigned&);
std::ostream &print(std::ostream&, lights&);
class lights {
public:
friend std::ostream &print(std::ostream&, lights&);
lights() = default;
lights(unsigned ammount) { setLights(ammount); }
void setLights(unsigned ammount) { lightsOn.assign(ammount, false); }
void switchLights(unsigned num1, unsigned num2);
private:
std::vector lightsOn;
};
void lights::switchLights(unsigned num1, unsigned num2) {
ifBiggerSwitch(num1, num2);
++num2;
for (auto beg = lightsOn.begin() + num1; beg != lightsOn.begin() + num2; ++beg) {
*beg = !*beg;
}
}
// Non member functions
void ifBiggerSwitch(unsigned &num1, unsigned &num2) {
if (num1 > num2) {
unsigned tempNum1 = num1;
num1 = num2;
num2 = tempNum1;
}
}
std::ostream &print(std::ostream &os, lights &light) {
for (auto c : light.lightsOn)
os << c << " ";
return os;
}Solution
Algorithm
The solution is brute force. It has a time complexity of \$O(N R)\$ (where \$N\$ is a number of bulbs and \$R\$ a number of ranges) and I expect to take forever on a bonus input (I gave up after 5 minutes).
To get the correct solution you should first realize that flipping switches in
Which brings the correct solution, in pseudocode:
The time complexity is down to \$O(N + R\log R)\$, including output (took less than 2 seconds on my system).
The solution is brute force. It has a time complexity of \$O(N R)\$ (where \$N\$ is a number of bulbs and \$R\$ a number of ranges) and I expect to take forever on a bonus input (I gave up after 5 minutes).
To get the correct solution you should first realize that flipping switches in
[x, y] range has the same net result as flipping switches in [x, N) range followed by flipping switches in [y+1, N) range. Next, since the flippings commute, it doesn't matter in which order they are performed. Each flipping is an edge changing state of all switches to the right of it.Which brings the correct solution, in pseudocode:
set up a vector of integers representing edges
for each input range (x, y)
push min(x, y)
push max(x, y) + 1
sort the vector
scan integers from 0 to N toggling state when the edge is crossedThe time complexity is down to \$O(N + R\log R)\$, including output (took less than 2 seconds on my system).
Code Snippets
set up a vector of integers representing edges
for each input range (x, y)
push min(x, y)
push max(x, y) + 1
sort the vector
scan integers from 0 to N toggling state when the edge is crossedContext
StackExchange Code Review Q#120916, answer score: 4
Revisions (0)
No revisions yet.