Challenge: sum of squares. Let's break 299

[Allen]

In trying to make the code faster, I fear I may have rendered it harder to read. Sorry about that. This is based on a variation of genetic algorithms applied to graph paths but without mutation.

I'll use the solution for length 25 as an example since it's small enough to fit on a screen.
First generate your square numbers and use those to calculate edges and nodes:

Code:


    #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])

here f(25)=set([(17, 8), (1, 3), (16, 9), (10, 6), (5, 4), (25, 11), (1, 15), (10, 15), (20, 5), (4, 12), (11, 14), (18, 7), (22, 14), (7, 2), (14, 22), (6, 3), (13, 12), (3, 1), (14, 11), (19, 17), (13, 3), (12, 13), (23, 13), (6, 10), (1, 8), (23, 2), (12, 24), (2, 23), (3, 6), (24, 1), (5, 11), (9, 7), (22, 3), (6, 19), (1, 24), (17, 19), (19, 6), (3, 13), (4, 5), (24, 12), (7, 18), (9, 16), (21, 15), (15, 10), (8, 17), (2, 14), (7, 9), (2, 7), (20, 16), (13, 23), (3, 22), (25, 24), (15, 21), (21, 4), (24, 25), (8, 1), (5, 20), (12, 4), (16, 20), (4, 21), (11, 5), (11, 25), (15, 1), (14, 2)])

Then create a dictionary of sets to store the edges.

Code:


edges={j:{x[1] for x in f if x[0]==j} for j in range(1,goal+1)}

{1: {3, 8, 15, 24},
2: {7, 14, 23},
3: {1, 6, 13, 22},
4: {5, 12, 21},
5: {4, 11, 20},
6: {3, 10, 19},
7: {2, 9, 18},
8: {1, 17},
9: {7, 16},
10: {6, 15},
11: {5, 14, 25},
12: {4, 13, 24},
13: {3, 12, 23},
14: {2, 11, 22},
15: {1, 10, 21},
16: {9, 20},
17: {8, 19},
18: {7},
19: {6, 17},
20: {5, 16},
21: {4, 15},
22: {3, 14},
23: {2, 13},
24: {1, 12, 25},
25: {11, 24}}

(see the bottleneck at 18?)