Challenge: sum of squares. Let's break 299
01-25-2018, 01:47 AM
Post: #37
 Allen Member Posts: 117 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
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?)

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

 « Next Oldest | Next Newest »

 Messages In This Thread Challenge: sum of squares. Let's break 299 - pier4r - 01-18-2018, 09:32 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-18-2018, 10:58 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:08 AM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:15 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 05:43 PM RE: Challenge: sum of squares. Let's break 299 - John Keith - 01-20-2018, 08:19 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-20-2018, 10:13 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 10:31 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:17 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 06:31 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 06:48 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-19-2018, 12:40 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:47 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:26 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:33 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:56 PM RE: Challenge: sum of squares. Let's break 299 - ggauny@live.fr - 01-20-2018, 06:15 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 09:08 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-21-2018, 05:41 AM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-21-2018, 10:44 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 11:54 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:11 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 03:19 PM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-22-2018, 08:49 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 09:18 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 09:43 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:03 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:08 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:14 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:16 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-24-2018, 10:22 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:29 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-25-2018, 05:54 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:32 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:33 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018 01:47 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:49 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:55 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:04 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 03:25 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 04:19 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-25-2018, 09:33 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 10:53 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 11:10 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-26-2018, 12:29 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-26-2018, 08:15 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-26-2018, 10:01 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-27-2018, 01:23 PM RE: Challenge: sum of squares. Let's break 299 - Massimo Gnerucci - 01-27-2018, 02:14 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-28-2018, 04:14 PM RE: Challenge: sum of squares. Let's break 299 - brickviking - 01-29-2018, 07:13 PM RE: Challenge: sum of squares. Let's break 299 - peacecalc - 01-30-2018, 02:51 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:38 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 02-01-2018, 10:54 AM

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