there is this problem in CodeWars that involves searching algorithms and since i'm still a beginner i had some difficulties trying to optimize my code, it's working correctly but i want it to be faster. This is the problem if you would like to check it out : Light Switch
# n is the number of lights
# corresponding_lights_list is the array representing relationships between lights and switches
# returns a boolean, represents whether it is possible to turn all the lights on.
def light_switch(n, corresponding_lights_list):
lights = [0]*n
oldlights = []
queue = []
while True:
for s in corresponding_lights_list :
newlights = [1 - lights[l] if l in s else lights[l] for l in range(n)]
if newlights == [1]*n :
return True
if not (newlights in oldlights or newlights in queue) :
queue.append(newlights)
oldlights.append(lights)
lights = queue.pop(0)
if len(queue) == 0 :
return False
from collections import deque
def light_switch(n, corresponding_lights_list):
lights1 = [0]*n
lights2 = [1]*n
oldlights1 = []
oldlights2 = []
queue1 = deque()
queue2 = deque()
while True:
oldlights1.append(lights1)
oldlights2.append(lights2)
for s in corresponding_lights_list :
newlights1 = [1 - lights1[l] if l in s else lights1[l] for l in range(n)]
newlights2 = [1 - lights2[l] if l in s else lights2[l] for l in range(n)]
if not (newlights1 in oldlights1 or newlights1 in queue1) :
queue1.append(newlights1)
if not (newlights2 in oldlights2 or newlights2 in queue2) :
queue2.append(newlights2)
if newlights2 in queue1 :#or newlights2 in oldlights1 or newlights1 in queue2 or newlights1 in oldlights2 :
return True
lights1 = queue1.popleft()
lights2 = queue2.popleft()
if len(queue1) == 0 :
return False
I would like from you guys to help me improve my code or even suggest a new approach, but please keep it as general as possible because i still want to solve this problem myself.
You could perform Gaussian elimination, where each switch is an unknown (variable), and for each light you can formulate a constraint that essential says that the sum of activated switches that toggle that light must be odd (or otherwise put: the XOR of them should be 1).
For example, for this input:
[
[0, 1, 2], # switch 0 controls light 0, 1, 2
[1, 2], # switch 1 controls light 1, 2
[1, 2, 3, 4], # switch 2 controls light 1, 2, 3, 4
[1, 4] # switch 3 controls light 1, 4
]
...we can define 𝑠𝑖 as the state of the switch with index 𝑖, and then write these XOR equations (one per light), which must be satisfied:
This can be represented as an extended matrix:
1 0 0 0 | 1
1 1 1 1 | 1
1 1 1 0 | 1
0 0 1 0 | 1
0 0 1 1 | 1
As these are booleans, you can also represent this matrix as a list of sets:
{0, 4}
{0, 1, 2, 3, 4}
{0, 1, 2, 4}
{2, 4}
{2, 3, 4}
The values in each set represent switches, except for the value 4, which is a separate value to represent the last column in the extended matrix.
Then perform Gaussian elimination by XOR-ing rows (sets) with each other, to end up with a matrix where a switch is member of at most one row (set). Then there should be no other rows (sets) that are non-empty (as they may still contain 4): this represents an inconsistency and False should be returned in that case.
If you cannot make it work, here is a spoiler:
def light_switch(num_lights, corresponding_lights_list): num_switches = len(corresponding_lights_list) # Build extended matrix for Gaussian elimination. As the variables (switch states) # are booleans, a matrix row can be represented with a set (of switches) # The num_switches value represents the desired outcome by xoring the states # of the relevant switches (i.e. the light should be ON) gauss = [{num_switches} for _ in range(num_lights)] # Populate the matrix: for switch, lights in enumerate(corresponding_lights_list): for light in lights: gauss[light].add(switch) # Perform Gaussian elimination light = 0 for switch in range(num_switches): # iterate columns (switches) # Find a constraint that involves this switch i = next((i for i in range(light, num_lights) if switch in gauss[i]), -1) if i == -1: # No constraint found for this switch: it is irrelevant continue # Swap constraint gauss[light], gauss[i] = gauss[i], gauss[light] selected = gauss[light] # Make this the only constraint that involves the current switch for other_light in gauss: if switch in other_light and other_light is not selected: # Redefine constraint as a XOR of itself with the selected constraint other_light.symmetric_difference_update(selected) light += 1 # Confirm there are no constraints without switches that must produce light return not any(rule for rule in gauss[light:])
Finally, there are Python modules that can perform Gaussian elimination for you, and if they are implemented in C, they will certainly do the job faster.