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

在CodeWars中有一个涉及搜索算法的问题，由于我仍然是一个初学者，我在尝试优化我的代码时遇到了一些困难，它工作正常，但我希望它更快。如果你想了解一下，这就是问题所在：电灯开关

This is my first attempt using breadth-first search.

# 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

I also tried searching in the two directions, so instead of reaching a final state you need to find a common state in the middle reached by both sides.

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

您可以执行高斯消去法，其中每个开关都是未知的(变量)，并且对于每个灯，您可以制定一个约束条件，即触发该灯的激活开关的总和必须是奇数(或者放在其他位置：它们的XOR应该是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:

...我们可以将𝑠𝑖定义为具有索引𝑖的开关的状态，然后写出这些异或方程(每光一个)，这必须满足：

• 𝑠₀ = 1


• 𝑠₀ ⊕ 𝑠₁ ⊕ 𝑠₂ ⊕ 𝑠₃ = 1


• 𝑠₁ ⊕ 𝑠₂ ⊕ 𝑠₃ = 1


• 𝑠₂ = 1


• 𝑠₂ ⊕ 𝑠₃ = 1

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.

除了值4之外，每个集合中的值都表示开关，值4是表示扩展矩阵中最后一列的单独值。

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.

然后通过将行(集)彼此异或来执行高斯消去，以得到一个矩阵，其中开关至多是一行(集)的成员。那么不应该有其他非空的行(集)(因为它们可能仍然包含4)：这表示不一致，在这种情况下应该返回FALSE。

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.

最后，还有一些可以为您执行高斯消除的Python模块，如果用C实现它们，它们肯定会更快地完成这项工作。