Playing with light switches

Question

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

#include <iostream>
#include <vector>
#include <stdexcept>

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<bool> 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;
}

Answer 1

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 [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 crossed

The time complexity is down to \$O(N + R\log R)\$, including output (took less than 2 seconds on my system).

Answer 2

• ifBiggerSwitch() also sounds like a bool function, yet it's void. It doesn't quite convey the purpose, either. Perhaps a name such as swapIfBiggerLight() would be better.

  Also, you can replace the entire if body with a call to std::swap():

  std::swap(num1, num2);
  

• In order to maintain consistent use of curly braces, you should also apply them to the range-based for loop in print().

  Also, why not make this an operator<< overload instead? Print functions are usually void and take no arguments. You can even have both if you'd like.

  Moreover, the light parameter should be a const&.

Answer 3

I think sortIndices or orderIndices is a better function name than ifBiggerSwitch. When the function returns, the input indices are sorted/ordered.