I have a set of constraints over modular domains e.g. $\exists a \in A_i : x \equiv a \pmod{n_i}$ for all $i=0,\ldots,k$
The question is, does such an $x$ exist? I've been pointed to method of successive substitution which ended up with me implementing the following python code.
import fractions
def exist(ruleList, acc = [0,1]): # currentCandidate , currentDomain
if len(ruleList) == 0:
return True
else:
rule = ruleList[0]
n = rule[1]/fractions.gcd(rule[1], acc[1])
newDomain = acc[1] * n
for candidate in (acc[0] + acc[1] * i for i in xrange(n)):
if candidate % rule[1] in rule[0]:
if exist(ruleList[1:], [candidate, newDomain]):
return True
return False
rules = [([0,1,2],5), # A_1,n_1
([4,5,6],9), # A_2,n_2
([0,3,6],10)] # A_3,n_3
print (exists(rules),) # True
rules = [([0,2,3],5), # A_1,n_1
([1,2,8],9), # A_2,n_2
([4,6,9],10)] # A_3,n_3
print (exist(rules),) # False
Is their a better way of implementing this or better algorithmic approach?