A shared house has a smart hub with n switches (0 to n - 1), each on or off. The residents
have filed m rules, and each rule is a list of wishes such as "switch 3 on, or switch 17 off,
or switch 8 on". A rule is kept when at least one of its wishes comes true, and broken
otherwise. The rules contradict each other, so some will be broken; each rule has a weight from 1
to 9 (how many residents signed it). Break as little weight as possible.
Write set_switches(n, rules) that returns a list on of n booleans (True = on). Each rule is
a pair (weight, wishes), and wishes is a list of 2 to 4 (switch, state) pairs with different
switches, where state is True (on) or False (off).
The tests build their rules with house_rules(n, m, seed), and broken_weight(rules, on) adds up
the weight of the broken rules. Both are available in your code.
How this problem is scored
The checker makes its own setting: every switch is set the way the larger total weight of wishes
wants it (on for a tie); then, switch 0, 1, 2, ... in turn, it flips a switch whenever that lowers
the broken weight, repeating the passes until none does. Your setting passes if it breaks no
more weight than that one. Its quality (0 to 100) says how much of the gap between that setting
and the best one we know you close.
Examples
Input: n = 30, rules = house_rules(30, 180, 2)
Output: a list of 30 booleans
the checker's setting breaks weight 24; the best known breaks 14
Constraints
30 <= n <= 400,180 <= m <= 2000- Each test must finish in well under a second in your browser. Limit your loops by a number of
flips, not by the clock, and use
random(the tests seed it) for random choices.
Goals
- Satisfy as much weight of conflicting either-or rules as possible
- Mix greedy moves with random ones so the search never gets stuck
- Track which rules are broken incrementally so every flip is cheap