Challenge: sum of squares. Let's break 299

[Allen]

Code to find these super nodes:

Code:


def super_nodes(goal,length=3):
    import itertools
    squares=set([x**2 for x in range(2*goal)])
    increasing=[(i,x) for i in range(1,goal+1) for x in range(i+1,goal+1) if i+x in squares]
    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)}
    
    for l in range(length-2):
        output=[]
        for i in f:
            next1=edges[i[-1]]-set(i)
            output+=[i+(x,) for x in next1]
        f=set(output)
    
    found=0
    perms=[]
    done=set()
    print 'precalculation complete.. looking for super nodes among {} items starting with {}'.format(len(f),sorted(f,key=lambda x:x[0])[0])
    for j in sorted(f,key=lambda x:x[0]):
        this_perm=set(itertools.permutations(list(j)))
        done=done.union(this_perm)
        if this_perm.issubset(f):
            found+=1
            perms+=[j]
            print 'subset:{} remaining {} found {}'.format(j,len(f),found)
            f=f-done
            done=set()
        if len(done)>1000:
            f=f-done
            done=set()
    return sorted(perms,key=lambda x:max(x))

Edit-fixing code bugs/ speedup to remove searched items as you go..