Challenge: sum of squares. Let's break 299
01-25-2018, 02:04 AM (This post was last modified: 01-25-2018 02:12 AM by Allen.)
Post: #40
 Allen Member Posts: 117 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
Given the way it decimates and limits options, there is trade off between speed and accuracy. The settings that will guarantee a solution for small N are very slow for large N, but i have not had to run the same test case more than a few times to "tweak" the decimation to get it through the bottlenecks.

(NOTE: The code below was used to solve N=1000, and may decimate too aggressively for smaller N.. adjust as necessary, or come up with a clever way to auto-adjust )

No doubt some one else here can make a clever hack and speed this up ten fold. You'll see in the solutions above that it tends to satisfy all the higher square values (with the most constraints) first then move on to smaller and smaller numbers. My challenge to the group would be to have a program that can calculate N=1000 in just a few seconds.

My only request is that if this is mapped to a more general solution ( and I think one exists), cite my work here or wherever it lands. Deal?

Here is the whole code. No fancy imports or packages.. just straight python 2.7*

Code:
 def extend(inputs,edges, scoring,goal):     output=[]     top=set(range(goal+1))     if len(list(inputs)[0])<goal/3:         top=set(range(goal/2,goal+1))     for i in inputs:         next1=edges[i[-1]]-set(i)         output+=[i+(x,) for x in next1 if x in top]     return sorted(set(output),key=lambda x: -sum([scoring[y] for y in x])) def bottlenecks(goal):     #calculate squares     squares=set([x**2 for x in range(2*goal)])     #only keep those that add to a square     increasing=[(i,x) for i in range(1,goal+1) for x in range(i+1,goal+1) if i+x in squares]     #take the pairs and combine them with revserd versions of the same to get all pairs     f=set(increasing+[x[::-1] for x in increasing])          edges={j:{x[1] for x in f if x[0]==j} for j in range(1,goal+1)}          scoring={j:len(edges[j]) for j in range(1,goal+1)}     a,b=list(f),list(f)     generation=0     while len(b)>0:         generation+=1         print 'gen {} : extending {} items with {} grams'.format(generation,len(b),len(f))         if generation>goal/5:             lim=max(len(f)/2,1000)             #b=extend(set(a[:lim]+a[-lim:]),edges,scoring,goal)             b=extend(set(a[:lim]+a[-lim:]),edges,scoring,goal)         else:             b=extend(set(a[:2*len(f)]+a[-2*len(f):]),edges,scoring,goal)         #b=extend(a,edges,scoring)         if len(b)>0:             a=list(b)             if len(b[0])==goal:                 print 'Success for len {}:{}'.format(goal,b[0])                 return b                 break     return a