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
|
|||
|
|||
RE: Challenge: sum of squares. Let's break 299
NewRpl (recursive (and naive) approach) :
Code: Bk299 : 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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
RE: Challenge: sum of squares. Let's break 299
** deleted **
|
|||
01-24-2018, 09:18 PM
Post: #27
|
|||
|
|||
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
|
|||
|
|||
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. 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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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:
Then create a dictionary of sets to store the edges. Code:
{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
|
|||
|
|||
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
|
|||
|
|||
RE: Challenge: sum of squares. Let's break 299
The scoring function is simply the count of the edge list:
Code:
{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:
(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:
Then I check to see if there is a tuple of length equal to the goal length and quit. Code:
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
|
|||
|
|||
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:
17bii | 32s | 32sii | 41c | 41cv | 41cx | 42s | 48g | 48g+ | 48gx | 50g | 30b |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)