algorithm - 解决来自 Kattis 的编程挑战 : Apparatus,

Question

我正在尝试解决描述的设备问题here .我有一个解决方案，但它需要超过 2 秒的时间限制。我试图优化我的代码以提高速度，但无法在 2 秒的限制内完成。

import sys
import math

for line in sys.stdin:

    line = line.strip("\n").split(" ")
    numSwitches = int(line[0])
    numPics = int(line[1])

    wiring = {}
    inValid = False
    for i in range(numPics):
        if (inValid):
            break
        x = sys.stdin.readline().strip("\n")
        f_x = sys.stdin.readline().strip("\n")

        x_ones = 0
        f_x_ones = 0

        digit = 0
        for i in range(numSwitches):
            if f_x[i]=='1':
                digit += 2**(numSwitches-i-1)
                f_x_ones += 1

        for switch in range(numSwitches):
            if (x[switch]=='1'):
                x_ones += 1
                if not (switch in wiring.keys()):
                    wiring[switch] = digit
                else:
                    wiring[switch] &= digit

        if x_ones != f_x_ones:
            inValid = True
            break

    if not inValid:
        for i in wiring.values():
            if i==0:
                inValid = True
                break

    for possibilities in set(wiring.values()):
        frequency = wiring.values().count(possibilities)
        if frequency>1:
            oneBits = 0
            while (possibilities>0):
                oneBits += (possibilities%2==1)
                possibilities /= 2
            if oneBits < frequency:
                inValid = True
                break

    if not inValid:
        print math.factorial(numSwitches-numPics)%1000003
    else:
        print 0

我正在寻找解决问题的方法的建议或关于如何优化当前代码的意见。

注意:考虑以下测试用例:

3 2
110
011
011
011

我的代码通过以下方式发现无效。首先，遇到第一张照片 (110, 011)。 wiring 字典被分配了以下键和值:

wiring[0] = 011
wiring[1] = 011

这意味着第一个和第二个开关可以点亮第二个或第三个灯。遇到第二张照片 (011, 011)。 布线更新如下:

wiring[1] = 011 & 011 = 011
wiring[2] = 011

现在观察接线的状态表明所有三个开关都可以点亮第二个和第三个灯。这是一个不一致，因为 3 个开关必须点亮三个灯，这里我们有三个开关点亮 2 个灯。

Answer 1

我认为这可能是一个解决方案，但我不确定，明天我可以解释更多

import numpy as np
from operator import mul

def apparatus(n, m, x, y):
    if not m:
        return np.math.factorial(n) % 1000003
    result = 1
    tmp = np.matrix([False] * x.shape[1])

    for i in xrange(x.shape[1]):
        if tmp[0, i]:
            continue
        tmp0 = np.prod(x[:, i] == x, 0)
        tmp1 = np.prod(x[:, i] == y, 0)
        if np.sum(tmp1) != np.sum(tmp0):
            return 0
        result *= np.math.factorial(np.sum(tmp1))
        result %= 1000003
        tmp += tmp1

    return result

x = np.matrix([[True, True, False]])
y = np.matrix([[False, True, True]])
print apparatus(3, 1, x, y)

x = np.matrix([[True, False, False, False], [False, False, False, False]])
y = np.matrix([[True, False, False, False], [False, False, True, False]])
print apparatus(4, 2, x, y)

print apparatus(1000, 0, [], [])