Challenge: sum of squares. Let's break 299
02-01-2018, 03:40 AM
Post: #57
 Allen Member Posts: 117 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
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)

17bii | 32s | 32sii | 41c | 41cv | 41cx | 42s | 48g | 48g+ | 48gx | 50g | 30b

 « Next Oldest | Next Newest »

 Messages In This Thread Challenge: sum of squares. Let's break 299 - pier4r - 01-18-2018, 09:32 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-18-2018, 10:58 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:08 AM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:15 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 05:43 PM RE: Challenge: sum of squares. Let's break 299 - John Keith - 01-20-2018, 08:19 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-20-2018, 10:13 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 10:31 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:17 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 06:31 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 06:48 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-19-2018, 12:40 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:47 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:26 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:33 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:56 PM RE: Challenge: sum of squares. Let's break 299 - ggauny@live.fr - 01-20-2018, 06:15 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 09:08 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-21-2018, 05:41 AM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-21-2018, 10:44 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 11:54 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:11 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 03:19 PM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-22-2018, 08:49 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 09:18 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 09:43 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:03 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:08 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:14 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:16 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-24-2018, 10:22 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:29 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-25-2018, 05:54 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:32 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:33 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:47 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:49 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:55 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:04 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 03:25 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 04:19 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-25-2018, 09:33 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 10:53 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 11:10 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-26-2018, 12:29 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-26-2018, 08:15 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-26-2018, 10:01 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-27-2018, 01:23 PM RE: Challenge: sum of squares. Let's break 299 - Massimo Gnerucci - 01-27-2018, 02:14 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-28-2018, 04:14 PM RE: Challenge: sum of squares. Let's break 299 - brickviking - 01-29-2018, 07:13 PM RE: Challenge: sum of squares. Let's break 299 - peacecalc - 01-30-2018, 02:51 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:38 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018 03:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 02-01-2018, 10:54 AM

User(s) browsing this thread: 1 Guest(s)