I am trying to solve apparatus problem described here. And I have a solution but it takes longer than 2 seconds which the time limit. I've tried to optimize my code for speed but can't get it with in the 2 second limit.
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
I'm looking for suggestions of ways I should have approached the problem or input on how I can optimize my current code.
Note: Consider the following test case:
3 2
110
011
011
011
My code finds that is invalid in the following manner. First, upon encountering the first photograph (110, 011). The wiring dictionary gets assigned the following keys and values:
wiring[0] = 011
wiring[1] = 011
This means that the first and second switch can light up either the second or third lights. Upon encountering the second photograph (011, 011). wiring is updated as follows:
wiring[1] = 011 & 011 = 011
wiring[2] = 011
Now observe that the state of wiring indicates that all three switches can light up either the second and third lights. This is an inconsistency since 3 switches have to light up three lights, here we have three switches lighting up 2 lights.
I think this could be a solution, but I'm not sure, I can explain more tomorrow
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, [], [])