Challenge: sum of squares. Let's break 299
01-21-2018, 10:44 PM (This post was last modified: 01-21-2018 11:32 PM by Gilles59.)
Post: #21
 Gilles59 Member Posts: 136 Joined: Jan 2017
RE: Challenge: sum of squares. Let's break 299
NewRpl (recursive (and naive) approach) :

Code:
Bk299 : «   → L a    « 1 L SIZE FOR 'n'        L n GET 'b' LSTO        IF a b + √ FP NOT a NOT OR THEN        L 1 n 1 - SUB L n 1 + 299 SUB ADD         IF DUP SIZE THEN         1 CF          b Bk299          IF 1 FS? THEN Sol b ADD 'Sol' STO EXIT END        ELSE         DROP Sol b ADD 'Sol' STO 1 SF         END       END     NEXT   » » Search : «   →  lg    «      {}  'Sol' STO      1 Lg FOR 'n' n NEXT     Lg →LIST      0 Bk299      Sol    » »

Example :

15 Search
{ 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8 }

Simulator : 0,012sec
Real Calc : (I 've a problem with the USB connexion... will try tomorrow

16 -> { 16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8 }

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

Simulator : 0.282 s
Real calc : ?

Could be easily improved by changing the square root with a table of of all the square numbers and a POS command... But i ve to go at bed now ;D And for a 299 search we need another way...
01-22-2018, 01:40 AM
Post: #22
 Thomas Okken Senior Member Posts: 1,058 Joined: Feb 2014
RE: Challenge: sum of squares. Let's break 299
I took another look at those videos, and the description box of the second one has a link to Charlie Turner's code that verified N <= 299: https://github.com/charlieturner/square-sum-sequences

If I understand this correctly (not a Python expert myself), this is a Jupyter workbook containing Python code which in turn uses SageMath. Jupyter is a system that creates Mathematica-like workbooks for interactive Python-based math work.

So, the actual Python code is buried in certain sections of the workbook, and in turn may be hard to understand if you don't know SageMath. I won't claim to know any of this except basic Python and having had Jupyter demoed to me once; I just thought I'd pass it on.
01-22-2018, 11:54 AM
Post: #23
 TheKaneB Member Posts: 175 Joined: Jul 2014
RE: Challenge: sum of squares. Let's break 299
The key part is this function:
http://doc.sagemath.org/html/en/referenc...onian_path

And here it is the basic algorithm for finding hamiltonian paths:
https://github.com/sagemath/sage/blob/07...ph_pyx.pyx

The function is called find_hamiltonian

Software Failure: Guru Meditation

--
Antonio
IU2KIY
01-22-2018, 01:11 PM (This post was last modified: 01-22-2018 01:13 PM by Thomas Okken.)
Post: #24
 Thomas Okken Senior Member Posts: 1,058 Joined: Feb 2014
RE: Challenge: sum of squares. Let's break 299
According to the main comment, that function does perform simple backtracking, but with two important twists: it is randomized, and it gives up and restarts after a certain number of steps with no solution.

I had a moment of déjà vu reading that, because years ago, I wrote a FreeCell solver that was able to find solutions, through backtracking (with a bunch of FreeCell-specific optimizations), by giving up when it got stuck and trying again, randomized, until it found a solution. It was surprisingly effective (as in: it solved every starting position I threw at it, and quickly), but I had totally forgotten about it and it never occurred to me to try that approach here.
01-22-2018, 03:19 PM
Post: #25
 TheKaneB Member Posts: 175 Joined: Jul 2014
RE: Challenge: sum of squares. Let's break 299
yep, it reminds me of a technique of Monte Carlo sampling used in linear optimization programming, simulated annealing and others. Random sampling is also used in many AI applications as well.

Software Failure: Guru Meditation

--
Antonio
IU2KIY
01-22-2018, 08:49 PM (This post was last modified: 01-22-2018 10:41 PM by Gilles59.)
Post: #26
 Gilles59 Member Posts: 136 Joined: Jan 2017
RE: Challenge: sum of squares. Let's break 299
** deleted **
01-24-2018, 09:18 PM
Post: #27
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
I think I may have found a general solution to this problem.
As a test case I picked 4 numbers over 299 and got solutions for all 4: 300,310, 400,487

The un-optimized code is than 30 lines of python and finishes in a few min on a single CPU, near-linear time, lear linear memory requirements.

Before I post code and comments, I would be grateful if someone could verify my solution #487.

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

01-24-2018, 09:43 PM
Post: #28
 Thomas Okken Senior Member Posts: 1,058 Joined: Feb 2014
RE: Challenge: sum of squares. Let's break 299
(01-24-2018 09:18 PM)Allen Wrote:  I think I may have found a general solution to this problem.
As a test case I picked 4 numbers over 299 and got solutions for all 4: 300,310, 400,487

The un-optimized code is than 30 lines of python and finishes in a few min on a single CPU, near-linear time, lear linear memory requirements.

Nice!

(01-24-2018 09:18 PM)Allen Wrote:  Before I post code and comments, I would be grateful if someone could verify my solution #487.

I'd be happy to, but you'll have to post that solution first.
01-24-2018, 10:03 PM (This post was last modified: 01-24-2018 10:04 PM by Allen.)
Post: #29
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
Here's one for 300:

(264, 265, 219, 181, 260, 269, 172, 228, 256, 273, 211, 230, 170, 271, 258, 226, 174, 267, 262, 179, 221, 263, 266, 175, 225, 259, 270, 214, 227, 257, 272, 128, 196, 288, 241, 200, 284, 292, 237, 204, 280, 296, 233, 208, 276, 300, 229, 255, 274, 210, 231, 298, 278, 206, 235, 294, 282, 202, 198, 243, 286, 290, 151, 173, 268, 261, 180, 144, 297, 279, 205, 236, 293, 283, 201, 240, 289, 287, 242, 199, 162, 238, 291, 285, 244, 197, 203, 281, 295, 234, 207, 277, 252, 232, 209, 275, 254, 187, 213, 148, 176, 224, 217, 183, 178, 222, 139, 185, 299, 142, 182, 218, 223, 177, 147, 253, 188, 212, 112, 249, 192, 169, 155, 245, 239, 161, 163, 126, 130, 194, 247, 153, 171, 190, 251, 149, 140, 184, 216, 145, 111, 250, 191, 98, 127, 129, 195, 246, 154, 135, 121, 168, 156, 133, 123, 166, 158, 131, 125, 164, 160, 96, 193, 248, 152, 137, 119, 50, 146, 215, 109, 87, 138, 186, 103, 122, 134, 91, 105, 120, 136, 89, 167, 157, 132, 124, 72, 97, 159, 165, 60, 84, 141, 220, 69, 100, 189, 67, 102, 94, 75, 150, 106, 90, 79, 117, 108, 88, 81, 115, 110, 86, 83, 113, 143, 82, 114, 55, 66, 78, 118, 51, 93, 76, 68, 53, 116, 80, 64, 57, 43, 101, 95, 74, 70, 99, 45, 36, 85, 59, 41, 40, 104, 92, 52, 48, 73, 71, 29, 35, 65, 56, 44, 77, 23, 26, 38, 62, 107, 37, 63, 58, 42, 39, 61, 20, 16, 33, 31, 18, 46, 54, 10, 6, 19, 30, 34, 47, 17, 32, 49, 15, 1, 8, 28, 21, 4, 5, 11, 14, 2, 7, 9, 27, 22, 3, 13, 12, 24, 25)

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

01-24-2018, 10:08 PM (This post was last modified: 01-24-2018 10:09 PM by Allen.)
Post: #30
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
(Note: I beilive these are not unique solutions)
for len 310:
(288, 241, 200, 284, 292, 237, 204, 280, 296, 233, 208, 276, 300, 229, 255, 274, 302, 227, 257, 272, 304, 225, 259, 270, 306, 178, 263, 266, 310, 219, 265, 264, 220, 309, 267, 262, 222, 307, 269, 260, 224, 305, 271, 258, 226, 303, 273, 256, 228, 301, 275, 209, 232, 297, 279, 205, 236, 293, 283, 201, 240, 289, 287, 242, 199, 162, 238, 291, 285, 244, 197, 203, 281, 295, 234, 207, 277, 299, 185, 176, 308, 268, 173, 151, 210, 231, 298, 278, 206, 235, 294, 282, 202, 198, 243, 286, 155, 245, 196, 128, 161, 239, 290, 194, 247, 153, 171, 190, 251, 149, 212, 188, 253, 147, 177, 223, 261, 180, 144, 217, 107, 254, 230, 211, 189, 252, 148, 213, 187, 174, 150, 250, 191, 170, 154, 246, 195, 166, 123, 133, 156, 168, 193, 248, 152, 172, 84, 112, 249, 192, 169, 87, 109, 215, 146, 110, 214, 186, 103, 221, 179, 145, 216, 184, 72, 124, 165, 159, 130, 126, 163, 93, 132, 157, 167, 122, 74, 182, 218, 71, 125, 164, 160, 129, 127, 98, 158, 131, 94, 50, 175, 81, 115, 141, 183, 106, 119, 137, 88, 108, 117, 139, 86, 83, 142, 114, 111, 85, 140, 116, 80, 89, 136, 120, 105, 39, 82, 143, 181, 75, 69, 100, 96, 73, 48, 121, 135, 90, 79, 65, 104, 92, 77, 67, 102, 42, 58, 138, 118, 78, 66, 55, 45, 76, 68, 101, 95, 49, 51, 70, 99, 97, 47, 53, 91, 134, 62, 38, 43, 57, 64, 36, 28, 8, 113, 56, 44, 20, 61, 60, 40, 41, 59, 5, 31, 18, 63, 37, 27, 54, 46, 35, 29, 52, 12, 13, 23, 26, 10, 6, 30, 19, 17, 32, 4, 21, 15, 34, 2, 7, 9, 16, 33, 3, 22, 14, 11, 25, 24, 1)

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

01-24-2018, 10:14 PM
Post: #31
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
solution for 400
(the time stamps for my postings are how long it took my 7-year-old computer to calculate each one)

len 400:(383, 346, 330, 295, 381, 348, 328, 297, 379, 350, 326, 299, 377, 352, 324, 301, 375, 354, 271, 258, 367, 362, 314, 311, 365, 364, 312, 264, 361, 368, 257, 319, 357, 372, 304, 272, 353, 376, 300, 325, 351, 378, 298, 327, 349, 380, 296, 329, 347, 382, 294, 331, 345, 384, 400, 225, 259, 366, 363, 262, 267, 309, 316, 260, 269, 307, 318, 358, 371, 305, 320, 356, 373, 303, 273, 256, 369, 360, 216, 268, 308, 317, 359, 370, 306, 270, 355, 374, 302, 227, 398, 386, 290, 335, 394, 390, 339, 337, 392, 284, 341, 388, 396, 333, 343, 233, 128, 313, 263, 266, 310, 174, 226, 399, 385, 291, 334, 242, 287, 338, 391, 393, 336, 289, 387, 397, 332, 293, 236, 340, 389, 395, 230, 254, 275, 209, 232, 344, 281, 203, 197, 244, 240, 201, 283, 342, 234, 250, 279, 162, 322, 207, 277, 252, 148, 176, 265, 219, 222, 139, 261, 315, 169, 231, 210, 274, 255, 321, 208, 276, 253, 323, 206, 235, 249, 192, 292, 237, 247, 282, 202, 239, 245, 196, 288, 241, 200, 161, 280, 204, 157, 243, 286, 198, 126, 163, 278, 251, 190, 171, 229, 212, 149, 175, 186, 214, 147, 177, 223, 218, 182, 179, 221, 220, 180, 144, 217, 224, 137, 187, 213, 228, 172, 152, 248, 193, 168, 156, 205, 195, 166, 123, 238, 246, 154, 170, 191, 98, 127, 129, 160, 164, 125, 199, 285, 115, 141, 183, 178, 146, 215, 185, 104, 121, 135, 189, 211, 113, 83, 173, 188, 101, 155, 134, 122, 167, 194, 130, 159, 165, 124, 132, 93, 103, 153, 72, 184, 140, 116, 109, 87, 138, 151, 105, 120, 136, 89, 80, 145, 111, 114, 82, 143, 181, 108, 88, 81, 63, 106, 150, 75, 94, 102, 67, 158, 131, 65, 79, 117, 52, 69, 100, 96, 73, 71, 50, 119, 77, 92, 133, 36, 64, 57, 112, 84, 85, 59, 62, 107, 118, 78, 91, 53, 47, 97, 99, 70, 74, 95, 49, 32, 68, 76, 45, 55, 66, 34, 110, 86, 58, 42, 39, 25, 56, 44, 37, 27, 142, 54, 90, 31, 18, 46, 35, 29, 20, 61, 60, 40, 41, 23, 13, 51, 30, 19, 17, 8, 28, 21, 15, 10, 26, 38, 43, 6, 3, 22, 14, 11, 5, 4, 12, 24, 1, 48, 33, 16, 9, 7, 2)

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

01-24-2018, 10:16 PM (This post was last modified: 01-24-2018 10:18 PM by Thomas Okken.)
Post: #32
 Thomas Okken Senior Member Posts: 1,058 Joined: Feb 2014
RE: Challenge: sum of squares. Let's break 299
They are both correct.

(I checked that all the numbers occurred exactly once by looking at the output from "sort -un", and checked that all consecutive pairs sum to perfect squares by pasting the numbers into Free42 and running a simple program there.)

EDIT: Solution for 400, also verified.
01-24-2018, 10:22 PM
Post: #33
 TheKaneB Member Posts: 175 Joined: Jul 2014
RE: Challenge: sum of squares. Let's break 299
Now we want the code!

Software Failure: Guru Meditation

--
Antonio
IU2KIY
01-24-2018, 10:29 PM (This post was last modified: 01-24-2018 10:32 PM by Allen.)
Post: #34
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
Thomas,
Thank you for verifying those solutions! It's always nice to have a second set of eyes. I have an important event in less than an hour, but generally speaking, I think the hamiltonian approach is good for random-walk kind of graphs, but these "square" graphs have some interesting properties we can exploit.

Namely, there are bottlenecks in the graph. For N=71 ( and numbers around there) the bottleneck is 50. There is only 1 or 2 ways to include 50 in the string.

By sorting the nodes of the graph according to how many outgoing edges there are, one can write a penalty/reward scoring to promote those strings that contain the most bottlenecks. Make a population of possible strings, and sort them according to their score, decimating to only keeping a portion of the resulting population.

I'm still trying to find the optimal settings for decimation, and growth rates to ensure the population does not collapse, while still finishing reasonably quickly. Will post more as soon as I'm able.

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

01-24-2018, 10:32 PM
Post: #35
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
len 487:(461, 439, 402, 327, 457, 443, 398, 331, 453, 447, 337, 392, 449, 451, 333, 396, 445, 455, 329, 400, 441, 459, 325, 404, 437, 463, 378, 406, 435, 465, 376, 408, 433, 467, 374, 410, 431, 469, 372, 412, 429, 471, 258, 226, 450, 391, 338, 446, 454, 387, 342, 442, 458, 326, 403, 438, 462, 379, 405, 324, 460, 440, 401, 328, 456, 444, 340, 336, 393, 448, 452, 332, 293, 436, 464, 377, 407, 434, 466, 375, 409, 432, 468, 373, 411, 430, 470, 371, 413, 428, 472, 369, 415, 485, 476, 365, 364, 477, 484, 416, 368, 473, 427, 414, 486, 475, 366, 363, 421, 420, 480, 361, 423, 418, 482, 479, 362, 422, 478, 483, 417, 367, 474, 487, 242, 383, 346, 330, 295, 381, 348, 277, 399, 385, 291, 334, 395, 389, 236, 248, 481, 419, 257, 227, 349, 380, 296, 280, 345, 384, 241, 288, 388, 341, 335, 290, 386, 343, 282, 294, 382, 347, 278, 298, 231, 394, 390, 339, 237, 292, 284, 200, 425, 304, 272, 353, 323, 302, 274, 351, 225, 259, 270, 306, 370, 359, 266, 263, 313, 312, 264, 265, 360, 424, 305, 320, 356, 269, 307, 318, 358, 426, 303, 273, 352, 224, 260, 316, 309, 267, 262, 179, 350, 275, 301, 228, 397, 279, 297, 232, 344, 281, 203, 197, 287, 289, 240, 201, 283, 246, 238, 162, 322, 354, 271, 170, 314, 311, 173, 268, 308, 317, 212, 229, 300, 276, 208, 321, 355, 221, 220, 180, 261, 315, 310, 174, 187, 254, 230, 299, 185, 256, 144, 217, 183, 178, 222, 219, 357, 319, 210, 151, 249, 235, 206, 155, 245, 239, 202, 198, 286, 243, 157, 204, 196, 128, 233, 251, 149, 175, 186, 255, 145, 216, 184, 177, 223, 218, 106, 150, 250, 234, 207, 193, 131, 125, 199, 285, 244, 156, 205, 195, 166, 123, 133, 191, 209, 152, 172, 189, 211, 113, 176, 148, 252, 109, 215, 146, 110, 214, 147, 253, 188, 136, 120, 169, 192, 132, 124, 165, 159, 130, 126, 163, 161, 95, 194, 167, 122, 134, 190, 171, 153, 247, 114, 82, 143, 181, 108, 88, 168, 121, 104, 92, 164, 160, 129, 127, 98, 158, 67, 102, 154, 135, 90, 79, 117, 139, 86, 83, 142, 182, 107, 89, 80, 116, 140, 85, 111, 213, 76, 93, 103, 66, 78, 118, 138, 87, 57, 112, 84, 141, 115, 54, 27, 94, 75, 69, 100, 96, 73, 71, 50, 119, 137, 32, 49, 72, 97, 99, 70, 51, 30, 91, 105, 64, 36, 28, 53, 68, 101, 43, 38, 62, 59, 41, 40, 81, 63, 37, 44, 77, 23, 58, 42, 39, 25, 56, 65, 35, 46, 18, 31, 33, 16, 48, 52, 29, 20, 61, 60, 21, 15, 10, 26, 74, 47, 34, 2, 7, 9, 55, 45, 4, 5, 11, 14, 22, 3, 13, 12, 24, 1, 8, 17, 19, 6)

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

01-24-2018, 10:33 PM (This post was last modified: 01-24-2018 10:35 PM by Thomas Okken.)
Post: #36
 Thomas Okken Senior Member Posts: 1,058 Joined: Feb 2014
RE: Challenge: sum of squares. Let's break 299
Sounds very interesting. I'm looking forward to seeing it!

EDIT: Solution for 487, also verified.
01-25-2018, 01:47 AM
Post: #37
 Allen Member Posts: 113 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

01-25-2018, 01:49 AM
Post: #38
 Allen Member Posts: 113 Joined: Aug 2014
RE: Challenge: sum of squares. Let's break 299
Here's a len 999 to prove it does not blow up too much in size as N increases.

len 999:(936, 913, 851, 830, 934, 915, 849, 832, 932, 917, 847, 834, 930, 919, 845, 836, 928, 921, 843, 838, 926, 923, 841, 840, 924, 925, 839, 842, 922, 927, 837, 844, 920, 929, 835, 846, 918, 931, 833, 848, 916, 933, 831, 850, 999, 937, 912, 852, 997, 939, 910, 854, 995, 941, 908, 856, 993, 943, 906, 858, 991, 945, 904, 860, 989, 947, 902, 862, 987, 949, 900, 864, 985, 951, 730, 791, 973, 963, 801, 880, 969, 967, 882, 799, 965, 971, 878, 803, 961, 975, 874, 890, 959, 977, 872, 809, 955, 981, 868, 896, 785, 979, 870, 811, 953, 983, 698, 746, 935, 914, 686, 683, 998, 938, 911, 853, 996, 940, 909, 855, 994, 942, 907, 857, 992, 944, 905, 859, 990, 946, 903, 861, 988, 948, 901, 863, 986, 950, 731, 790, 974, 962, 802, 798, 966, 970, 879, 885, 796, 968, 881, 800, 964, 972, 877, 804, 960, 976, 788, 812, 869, 980, 784, 897, 867, 982, 954, 810, 871, 978, 958, 891, 873, 648, 952, 984, 865, 816, 628, 893, 956, 808, 792, 889, 875, 806, 794, 887, 634, 735, 786, 895, 626, 818, 782, 899, 701, 743, 778, 822, 699, 745, 776, 824, 697, 747, 774, 826, 695, 749, 772, 828, 693, 676, 768, 753, 691, 678, 766, 755, 689, 680, 764, 757, 687, 402, 894, 787, 734, 635, 886, 795, 805, 876, 888, 793, 807, 957, 892, 789, 732, 637, 884, 797, 647, 578, 866, 898, 702, 742, 779, 821, 700, 744, 625, 819, 781, 740, 629, 815, 706, 663, 633, 736, 708, 813, 631, 738, 783, 817, 627, 669, 775, 825, 696, 748, 773, 827, 694, 750, 771, 829, 692, 677, 767, 754, 690, 679, 765, 756, 688, 681, 763, 758, 611, 685, 759, 762, 607, 549, 820, 780, 741, 703, 666, 630, 814, 707, 737, 632, 664, 705, 739, 486, 883, 638, 587, 709, 660, 636, 733, 711, 585, 640, 729, 715, 654, 642, 583, 713, 512, 577, 579, 646, 650, 719, 725, 644, 652, 717, 727, 362, 599, 770, 751, 545, 544, 612, 684, 760, 761, 608, 617, 752, 769, 675, 621, 823, 777, 592, 497, 659, 710, 586, 639, 657, 712, 584, 641, 728, 716, 580, 576, 649, 720, 724, 645, 651, 718, 726, 643, 653, 503, 722, 574, 582, 714, 655, 501, 588, 568, 521, 704, 665, 491, 598, 558, 667, 489, 600, 556, 533, 623, 673, 416, 484, 605, 551, 674, 622, 603, 553, 672, 624, 601, 488, 668, 557, 532, 492, 597, 559, 530, 494, 662, 563, 593, 431, 658, 567, 589, 500, 656, 569, 520, 504, 721, 575, 581, 508, 516, 573, 723, 502, 459, 565, 591, 498, 463, 561, 595, 366, 534, 555, 670, 419, 542, 614, 682, 543, 418, 671, 485, 539, 550, 606, 619, 537, 487, 602, 554, 535, 365, 596, 560, 529, 495, 661, 564, 525, 499, 590, 566, 458, 442, 519, 505, 456, 444, 517, 572, 452, 509, 515, 446, 338, 562, 594, 430, 411, 613, 476, 548, 541, 615, 610, 546, 415, 369, 531, 493, 468, 432, 409, 552, 604, 420, 421, 540, 616, 609, 547, 294, 435, 406, 618, 538, 423, 477, 364, 536, 620, 341, 443, 518, 506, 335, 449, 451, 510, 514, 447, 453, 571, 329, 400, 441, 288, 496, 528, 433, 467, 374, 410, 490, 471, 370, 414, 427, 473, 368, 361, 480, 481, 360, 424, 417, 367, 474, 426, 199, 330, 511, 450, 391, 570, 454, 507, 393, 448, 513, 328, 401, 440, 460, 381, 403, 438, 462, 379, 405, 436, 464, 377, 407, 434, 527, 257, 472, 428, 413, 371, 358, 483, 478, 363, 262, 522, 439, 461, 268, 408, 376, 524, 437, 292, 284, 392, 337, 339, 445, 455, 386, 398, 331, 345, 384, 457, 327, 349, 380, 404, 325, 300, 429, 412, 372, 469, 315, 526, 258, 318, 466, 375, 354, 271, 305, 479, 482, 359, 425, 475, 254, 422, 203, 281, 344, 332, 293, 383, 346, 279, 397, 387, 342, 334, 395, 389, 287, 289, 336, 340, 285, 291, 385, 399, 277, 299, 326, 350, 275, 301, 324, 352, 273, 211, 465, 264, 265, 311, 314, 470, 259, 270, 355, 321, 304, 225, 351, 378, 298, 278, 347, 382, 243, 333, 396, 280, 296, 233, 343, 282, 394, 390, 235, 206, 523, 261, 223, 353, 323, 302, 274, 210, 319, 357, 219, 310, 266, 263, 313, 312, 217, 267, 309, 316, 260, 269, 356, 373, 252, 189, 295, 234, 207, 322, 303, 181, 348, 228, 256, 320, 209, 232, 297, 144, 180, 220, 221, 308, 317, 212, 272, 169, 231, 253, 276, 208, 192, 249, 151, 290, 286, 198, 202, 239, 245, 196, 204, 237, 388, 188, 173, 227, 214, 147, 177, 307, 222, 178, 306, 135, 154, 246, 283, 201, 240, 244, 156, 205, 236, 248, 193, 131, 230, 170, 191, 250, 150, 174, 226, 215, 146, 143, 218, 182, 179, 145, 255, 229, 132, 124, 200, 241, 159, 130, 194, 247, 153, 171, 190, 251, 149, 140, 184, 216, 108, 117, 172, 152, 137, 224, 176, 148, 213, 187, 102, 123, 238, 162, 127, 197, 164, 160, 129, 195, 166, 158, 242, 119, 106, 183, 141, 115, 110, 86, 139, 185, 104, 121, 168, 88, 81, 175, 186, 103, 122, 134, 155, 101, 68, 128, 161, 163, 126, 99, 157, 167, 58, 111, 85, 84, 112, 113, 83, 142, 114, 82, 62, 107, 118, 138, 87, 109, 116, 80, 89, 136, 120, 105, 91, 165, 31, 69, 75, 94, 50, 71, 73, 96, 100, 125, 44, 56, 65, 79, 90, 54, 67, 77, 92, 133, 36, 64, 57, 43, 78, 66, 55, 45, 76, 93, 51, 70, 74, 95, 49, 72, 97, 47, 53, 28, 21, 60, 61, 39, 42, 22, 27, 37, 63, 18, 46, 98, 23, 41, 59, 5, 20, 29, 52, 48, 33, 16, 9, 40, 24, 25, 11, 38, 26, 10, 15, 34, 30, 19, 6, 3, 13, 12, 4, 32, 17, 8, 1, 35, 14, 2, 7)

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

01-25-2018, 01:55 AM
Post: #39
 Allen Member Posts: 113 Joined: Aug 2014
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

01-25-2018, 02:04 AM (This post was last modified: 01-25-2018 02:12 AM by Allen.)
Post: #40
 Allen Member Posts: 113 Joined: Aug 2014
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 )

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