Challenge: sum of squares. Let's break 299

[Gilles59]

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...

[Thomas Okken]

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.

[TheKaneB]

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

[Thomas Okken]

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.

[TheKaneB]

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.

[Gilles59]

** deleted **

[Allen]

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.

[Thomas Okken]

(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.

[Allen]

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)

[Allen]

(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)

[Allen]

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)

[Thomas Okken]

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.

[TheKaneB]

Now we want the code!

[Allen]

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.

[Allen]

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)

[Thomas Okken]

Sounds very interesting. I'm looking forward to seeing it!

EDIT: Solution for 487, also verified.

[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?)

[Allen]

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)

[Allen]

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

[Allen]

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

Edit: fix a code section I was editing while writing, add comment