Challenge: sum of squares. Let's break 299

[Allen]

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)