Code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 24 16:26:01 2018
@author: allen_thomson
"""
#!/usr/bin/env python
import time
from math import sqrt as sqrt
import argparse
import random
def is_square(l,goal):
squares=set([x**2 for x in range(2,int(sqrt(goal+goal-1))+1)])
pairs=set([sum(x) for x in zip(l,l[1:])])
return len(pairs-squares)==0
def extend(inputs,edges, scoring,goal,clip):
output=[]
for j in inputs:
rev=random.choice([True,False])
score,i=j
left=set(i)
next1=sorted(edges[i[-1]]-left,key=lambda x:-scoring[x])
if clip==1 and len(next1)>1:
if random.random()>.95:
scoring={w:len(edges[w]-left) for w in range(1,goal+1)}
#next1=sorted(edges[i[-1]]-left,key=lambda x:-scoring[x])
output=[(score+scoring[next1[-1]],i+(next1[-1],))]
else:
scoring={w:len(edges[w]-left) for w in range(1,goal+1)}
if rev:
next1=edges[i[0]]-left
output+=[(score+scoring[x],(x,)+i) for x in next1]
else:
next1=edges[i[-1]]-left
output+=[(score+scoring[x],i+(x,)) for x in next1]
return sorted(set(output),key=lambda x: -x[0])
def bottlenecks(goal,max_clip=100,min_clip=1):
start_time=time.time()
squares=set([x**2 for x in range(2,int(sqrt(goal+goal-1))+1)])
edges={j:{x-j for x in [y for y in squares if y>j] if x-j<=goal} for j in range(1,goal+1)}
scoring={j:len(edges[j]) for j in range(1,goal+1)}
a=sorted([(scoring[y],(y,)) for y in edges.keys()],key=lambda x:-x[0])
b=list(a)
while len(b)>0:
if len(set(b[0][1]))<1 or len(set(b[0][1]))+10>goal:
clip=max_clip
else:
clip=min_clip
print 'length {} : extending {} items with {} grams clip:{}'.format(len(set(b[0][1])),len(b),len(edges.keys()),clip)
b=extend(set(a[-clip:]),edges,scoring,goal,clip)
if len(b)>0:
if len(b[0][1])==goal:
print 'Success for len {}:{}'.format(goal,b[0])
print 'Unique solutions found for len {}: {}'.format(goal,len(set(b+[x[::-1] for x in b])))
return b
a=list(b)
print 'Runtime: {}'.format(time.time()-start_time)
if len(a)>0:
print 'Goal:{}'.format(goal)
for i,j in enumerate(a):
print 'sol {}: len {} unique {} is_square:{} Success:{}'.format(i,len(j[1]),len(set(j[1])),is_square(j[1],goal),is_square(j[1],goal) and len(set(j[1]))==goal)
return a
if __name__ == "__main__":
import argparse
parser = argparse.ArgumentParser(description='Calculate a sum-squares graph walk')
parser.add_argument('N', type=int, help='number of nodes on the graph')
parser.add_argument('min_clip', type=int, default=1, help='Smaller=Faster, Larger=more solutions')
parser.add_argument('max_clip', type=int, default=100, help='Smaller=Faster, Larger=more solutions')
args = parser.parse_args()
b=bottlenecks(args.N,args.max_clip,args.min_clip)