Post Reply 
Challenge: sum of squares. Let's break 299
01-25-2018, 01:55 AM
Post: #39
RE: Challenge: sum of squares. Let's break 299
The scoring function is simply the count of the edge list:

Code:

scoring={j:len(edges[j]) for j in range(1,goal+1)}

{1: {3, 8, 15, 24}, -> 4
2: {7, 14, 23}, -> 3
8: {1, 17}, -> 2
18: {7}, -> 1
}

Then, starting with the bare edge list (each of length 2) I extend them 1 character at a time, sorting the results by MINIMUM score.

Code:

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(a[:lim],edges,scoring,goal)
        else:
            b=extend(set(a[:2*len(f)]+a[-2*len(f):]),edges,scoring,goal)

(I've added some stuff in here to make it run faster by limiting the choices available at different times, but the basic concept is still in there.)

Where the extend function only allows it to grow if there are valid solutions:
Code:

def extend(inputs,edges, scoring,goal):
    output=[]
    top=set(range(goal+1))
    if len(list(inputs)[0])<goal/3:          # these three lines are optimizations.. still tweaking
        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]))

Then I check to see if there is a tuple of length equal to the goal length and quit.
Code:

if len(b)>0:
            a=list(b)
            if len(b[0])==goal:
                print 'Success for len {}:{}'.format(goal,b[0])
                return b
                break

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 01:55 AM



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