Post Reply 
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
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 Smile )

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
Edit: fix a code section I was editing while writing, add comment

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

Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018 02:04 AM



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