import pickle
class SumProductPuzzle:
def __init__(self, lb=2, rb=98):
self.nodes = [(i, j) for i in range(lb, rb) for j in range(lb, rb) if i < j]
edgesP = [(tup1, tup2, tup1[0] * tup1[1]) for tup1 in self.nodes for tup2 in self.nodes
if (tup1[0] * tup1[1] == tup2[0] * tup2[1]
and tup1[0] <= tup2[0])]
edgesS = [(tup1, tup2, sum(tup1)) for tup1 in self.nodes for tup2 in self.nodes
if (tup1[0] + tup1[1] == tup2[0] + tup2[1]
and tup1[0] <= tup2[0])]
self.primes = []
g = gen_primes()
p = next(g)
while p < rb:
self.primes.append(p)
p = next(g)
self.adjListP = {}
self.adjListS = {}
createAdjList(edgesP, self.adjListP)
createAdjList(edgesS, self.adjListS)
def writeAsPrime(self, num):
for i in self.primes:
for j in self.primes:
if i + j == num or i + i ** 2 == num:
return True
return False
def cond1(self, u):
# validates first condition
for v in self.adjListS[u]:
if len(self.adjListP[v]) == 1:
return False
return True
def cond2(self, u):
# validates second condition
for v in self.adjListP[u]:
if u != v and not self.writeAsPrime(sum(v)):
return False
return True
def cond3(self, u):
# validates third condition
for v in self.adjListS[u]:
if v != u and self.cond2(v):
return False
return True
def getSolution(self):
# returns puzzle solution
return [node for node in self.nodes if self.cond3(node) and self.cond2(node) and self.cond1(node)]
# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while True:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
def createAdjList(edgeList, adjList):
# creates adjacency lists as a dictionary
for i in edgeList:
if not adjList.get(i[0]):
adjList[i[0]] = list([i[1]])
elif i[1] not in adjList[i[0]]:
adjList[i[0]].append(i[1])
if not adjList.get(i[1]):
adjList[i[1]] = list([i[0]])
elif i[0] not in adjList[i[1]]:
adjList[i[1]].append(i[0])
def dumpObject(obj, filename="sumProductObj"):
# dumps an object in a file
with open(filename, "wb") as out:
pickle.dump(obj, out, pickle.HIGHEST_PROTOCOL)
if __name__ == "__main__":
try:
with open("sumProductObj", "rb") as obj:
testInstance = pickle.load(obj)
except FileNotFoundError as e:
print("File Not Found! Creating new puzzle instance!")
testInstance = SumProductPuzzle()
dumpObject(testInstance)
print("Puzzle's solution between %d nodes is %s"
% (len(testInstance.nodes), testInstance.getSolution()))