[SOLVED] 'Circle of Squares' programming challenge

astrogeek · 04-12-2021, 05:53 PM

@GazL - I had some time to explore your code over the weekend. What a pleasure to read well considered code!

I really like your backtracking method, elegant simplicity!

I also had a chance to better understand the nature of the problem, which I should have done much earlier!

I made two incorrect assumptions (you know what they say!):

1. Looking at the shape of possible pairings in the 32 number case, from which my own method of finding the deterministic solution grew, I reached the quick conclusion that the higher end of the range would always be limited to one or two possible pairs... that is blindingly obviously incorrect!

2. From the name given to the problem and the deterministic nature of the (special) case of 32 numbers, I assumed the case itself was known to be unique or at least rare, i.e. "amazing", and did not explore the more general question of how many other series of numbers could be so arranged even though I asked the question.

Even so, the deterministic soloution in the case of the series 1 through 32 is in fact correct, and from what I have now seen, unique.

But as it turns out, the "circle of square pairs" is not so amazing after all, but there are numerous ranges with such solutions! That being the case, your general solver is much more useful!

I did observe a couple of things while writing my deterministic solver which can improve the performance of your own code in some cases (there are some exceptions which I have not yet fully explored).

First, you can get a small but consistent gain from changing your is_a_square() function to require fewer iterations. We can always know what the greatest perfect square and its root will be as that is determined by the max end of the range. It will be the greatest perfect square less than or equal to max*2-1. So if we set that in the initial conditions and iterate only the possible roots we can make a small but useful improvement. To do that I modified your amazing_circle_v2.1.c as follows:

Code:

struct state
{
    int max ;
    int maxroot ;
    int *result ;
    int *seen_values ;
    int pair_count ;
    struct pair * pairs_head ;
    struct pair * pairs_tail ;
    struct pair ** pairs_value_index ;
};

struct state *init_state(struct state *state, int max )
{
    state->max = max ;
    for(state->maxroot=2; (state->maxroot*state->maxroot)<=(state->max*2-1); state->maxroot++)
      ;
    state->maxroot--;
    ...
}

int is_a_square(int x, struct state *state)
{
   int i;
   for(i = state->maxroot; i>1; i--)
      if(x == i*i)
         break;
   return (i>1);
}

Modify callers of is_a_square() to pass state pointer, two places.

That made a change of about 1/2 second out of 12 seconds in the 51 series test case on my old AMD Phenom machine, but it was consistent and affected all results.

The second observation from the detereministic code is that there are always fewer ways to reach the higher squares, so fewer possible pairs for numbers in the high end of the range. By testing those first you eliminate an ever increasing number of possibilities to test from the lower end of the range.

I modified your pair generating/indexing function to index the higher pair possibilities first, with dramatic results:

Code:

int generate_pairs( struct state *state )
{
    struct pair *pairs_head = state->pairs_head ;
    struct pair *pairs_tail = state->pairs_tail ;

    for ( int i = 1 ; i <= state->max ; i++ )
    /*    for ( int j = 1 ; j <= state->max ; j++)*/
        for ( int j = state->max ; j >=1 ; j--)
    ...
}

These results follow from those changes, comparing the revised code to the original:

Code:

./revised 53 1
...
Sequence:
 1, 48, 52, 29, 35, 46, 18, 31, 50, 14, 22, 42, 39, 25, 24, 40, 41, 23, 26, 38, 43, 21, 28, 53, 11, 5, 44, 20, 16, 33, 3, 13, 36, 45, 19, 6, 10, 15, 49, 51, 30, 34, 47, 2, 7, 9, 27, 37, 12, 4, 32, 17, 8.

real    0m0.011s
user    0m0.009s
sys     0m0.001s

./amazing_circle 53 1
Sequence:
 1, 3, 6, 10, 15, 21, 43, 38, 26, 23, 2, 7, 9, 16, 33, 48, 52, 12, 4, 45, 19, 30, 34, 47, 17, 32, 49, 51, 13, 36, 28, 53, 11, 14, 50, 31, 18, 46, 35, 29, 20, 5, 44, 37, 27, 22, 42, 39, 25, 24, 40, 41, 8.

real    1m52.386s
user    1m52.343s
sys     0m0.016s

They find different solutions which I have not tried to compare in detail for common sequences, but the time difference is more than a little dramatic!

I see similar but less dramatic results for nearby cases, and even an increase in time for some smaller cases. It will be interesting to see how that holds up, or not, over a larger range.

Code:

amazing 52,   real    0m40.898s
revised 52,   real    0m0.041s

amazing 51,   real    0m12.360s
revised 51,   real    0m11.424s

amazing 48,   real    0m2.563s
revised 48,   real    0m4.374s

astrogeek · 04-12-2021, 05:58 PM

Quote:

Originally Posted by igadoter

In this place story started https://m.facebook.com/story.php?sto...cus_composer=0 I really hope we will finish this. My idea of "genetic" modifications is good starting point to create more efficient program.

I cannot access that site, it is blocked at the genetic level from here.

Could you summarize for us what you think is applicable to this thread. That would also help keep the discussion complete here on LQ without dependence on outside content which may disappear over time. Thanks!

igadoter · 04-12-2021, 07:29 PM

It is facebook page where one of my facebook friends posted the picture with amazing circle. He is mathematician. Just I want to emphasize that I am not the author of original circle. That's it Maybe try address starting with facebook not m.facebook. I blocked JavaScript and Facebook redirects here to mobile version m.facebook. Mobile version is supported mostly by php. Maybe you can't acess my timeline on facebook. I click on link I provided and it opens. I verified this before posting. From that post on facebook I copied the picture and posted it here.

astrogeek · 04-12-2021, 07:40 PM

It is not a routing matter. When I said it is "blocked at the genetic level" I meant that it is a personal choice to block anything with facebook in the domain name from my field of view and from access to my network.

Sorry if my choice of expression obscured rather than clarified my meaning.

Even so, my personal choices aside, it is always preferable to post relevant information in thread here on LQ so that it will remain available to future visitors and not require others to follow off site links, which may disappear over time, to get info. It just keeps everything complete here. Thanks!

igadoter · 04-12-2021, 08:06 PM

Thanks, I will remember that.

astrogeek · 04-12-2021, 11:35 PM

I had a little time to play this evening...

Code:

Max   Revised     Amazing
56    0m3.488s   24m46.152s
55    1m37.103s   8m0.734s
54    26.528s     3m22.459s

I suspect the rise and fall of the spread will be cyclic, or periodic in some way related to the distance between the max number and the reachable squares. That distance between each square and the one before increases twice as fast as the max number (or roots) and is root*2-1.

pan64 · 04-13-2021, 01:31 AM

Code:

int sq[10000];

int is_a_square(int x)
{
    return sq[x];
}

void fill_sq()
{
    for (int i=0; i<10000; i++)
        sq[i]=0;
    for (int i=0; i<100; i++)
        sq[i*i]=1;
}

main ()
{
    ....
    fill_sq()
    ...

theoretically this should work faster and also quite simple, but (as I wrote) gave no any speed improvement, because the time spent in this function is negligible.
find_next was invoked more than 500 M times and is_a_square was only invoked [less than] 3000 times.

@astrogeek: with your modification (still using 51 numbers) the number of calls (to find_next) was 436M, therefore the full execution time was almost the same.
But using 52 numbers there was a dramatic change, there were only 1.4M calls and obviously the execution time was less than a second.

GazL · 04-13-2021, 06:29 AM

Quote:

Originally Posted by astrogeek

@GazL - I had some time to explore your code over the weekend. What a pleasure to read well considered code!

Thanks for the kind words.

Your observation about reversing the generated pairs list for efficiency is very interesting. Thanks for that.

As for is_a_square(), I suspected there were more efficient ways of doing it, but it's only called in find_next() when it thinks it has a full sequence and just needs to check it wraps correctly, so I didn't worry about optimising it. Combining your and pan's observations, I'm wondering if generating a lookup array of root values for numbers from 4 to max + max - 1 would be the most efficient process, though I suspect gains will still be minor due to the relatively small number of calls made.

I'll look into both.

GazL · 04-13-2021, 09:32 AM

Using astrogeeks suggestion of changing the order of pairs, along with a sqrt lookup table, and changing the default start of sequence value to be sequence_max, speeds things up significantly. v2.2 attached.

Code:

$ time ./amazing_circle 99 | tail -2
Sequence:
 99, 97, 72, 49, 95, 74, 70, 51, 93, 76, 68, 53, 91, 78, 66, 55, 89, 80, 64, 57, 87, 82, 62, 59, 85, 84, 60, 61, 83, 86, 58, 63, 81, 88, 56, 65, 79, 90, 54, 67, 77, 92, 52, 69, 75, 94, 50, 71, 98, 46, 35, 29, 20, 44, 37, 27, 73, 96, 48, 33, 16, 9, 40, 41, 23, 26, 38, 43, 21, 28, 36, 45, 19, 30, 6, 10, 39, 42, 7, 18, 31, 5, 4, 32, 17, 8, 1, 15, 34, 47, 2, 14, 11, 25, 24, 12, 13, 3, 22.

real	0m7.889s
user	0m7.888s
sys	0m0.003s
$

Thanks to all involved in this thread. Was a lot of fun!

P.S. And as astrogeek pointed out, not quite as "amazing" as we originally thought, but still cool!

pan64 · 04-13-2021, 10:44 AM

yes, now comes the next step: find all the different solutions. (or the number of different circles)

GazL · 04-13-2021, 12:05 PM

Quote:

Originally Posted by pan64

yes, now comes the next step: find all the different solutions. (or the number of different circles)

That's pretty easy to do with my code, but it's going to be cpu intensive for the larger numbers.

proof of concept diff (needs cleaning up):

Code:

--- amazing_circle_v2.2.c	2021-04-13 15:26:50.737773927 +0100
+++ amazing_all.c	2021-04-13 17:32:12.057721526 +0100
@@ -167,6 +167,23 @@
 
     return state ;
 }
+void print_sequence( struct state *state )
+{
+    if ( ! state->result )
+    {
+        printf("No sequence calculated.\n");
+        return ;
+    }
+
+    printf("Sequence:\n") ;
+
+    for ( int i = 0 ; i < state->max ; i++ )
+        printf(" %d,", state->result[i]);
+
+    printf("\b.\n");
+
+    return ;
+}
 
 int find_next( int depth, int value, struct state *state )
 {
@@ -175,8 +192,10 @@
     if ( depth == state->max )
     {
         if ( state->sqrt_table[state->result[0] + state->result[state->max - 1]] )
-            return 1 ;
-        else
+        {
+            print_sequence( state ) ;
+            return 0 ;
+        } else
             return 0 ;
     }
 
@@ -220,24 +239,6 @@
     return find_next(0, sequence_start, state) ;
 }
 
-void print_sequence( struct state *state )
-{
-    if ( ! state->result )
-    {
-        printf("No sequence calculated.\n");
-        return ;
-    }
-
-    printf("Sequence:\n") ;
-
-    for ( int i = 0 ; i < state->max ; i++ )
-        printf(" %d,", state->result[i]);
-
-    printf("\b.\n");
-
-    return ;
-}
-
 int main( int argc, char *argv[] )
 {
     int sequence_max = 0 ;
@@ -267,13 +268,7 @@
 
     printf("\nCalculating sequence, please wait...\n");
 
-    if ( calculate_sequence(sequence_start, &state) )
-    {
-        print_sequence( &state ) ;
-        return 0;
-    }
-
-    printf("Could not calculate sequence.\n");
+    calculate_sequence(sequence_start, &state) ;
 
     return 1;
 }

output:

Code:

98 possible pairs that sum to a square:
  1, 24
  1, 15
  1, 8
  1, 3
  2, 23
  2, 14
  2, 7
  3, 33
  3, 22
  3, 13
  3, 6
  3, 1
  4, 32
  4, 21
  4, 12
  4, 5
  5, 31
  5, 20
  5, 11
  5, 4
  6, 30
  6, 19
  6, 10
  6, 3
  7, 29
  7, 18
  7, 9
  7, 2
  8, 28
  8, 17
  8, 1
  9, 27
  9, 16
  9, 7
  10, 26
  10, 15
  10, 6
  11, 25
  11, 14
  11, 5
  12, 24
  12, 13
  12, 4
  13, 23
  13, 12
  13, 3
  14, 22
  14, 11
  14, 2
  15, 21
  15, 10
  15, 1
  16, 33
  16, 20
  16, 9
  17, 32
  17, 19
  17, 8
  18, 31
  18, 7
  19, 30
  19, 17
  19, 6
  20, 29
  20, 16
  20, 5
  21, 28
  21, 15
  21, 4
  22, 27
  22, 14
  22, 3
  23, 26
  23, 13
  23, 2
  24, 25
  24, 12
  24, 1
  25, 24
  25, 11
  26, 23
  26, 10
  27, 22
  27, 9
  28, 21
  28, 8
  29, 20
  29, 7
  30, 19
  30, 6
  31, 33
  31, 18
  31, 5
  32, 17
  32, 4
  33, 31
  33, 16
  33, 3

Calculating sequence, please wait...
Sequence:
 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16,.
Sequence:
 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31,.
Sequence:
 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16,.
Sequence:
 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31,.
Sequence:
 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16,.
Sequence:
 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31,.

... works by pretending that a completed circle isn't. Each possible sequence will be reported twice, once in each direction. When I've had time to look at it a little more I might add an --all option to the cli.

GazL · 04-15-2021, 07:00 AM

Here we go, final tarted-up version, with -a and -v options.

edit:
oops, just spotted a duplication issue, and a few other tweaks.
version 2.5 (just reuploaded and hopefully really,really final this time)

igadoter · 04-15-2021, 10:21 AM

Downloaded but from 41 up largest number in sequence is duplicated and there are missing numbers, for n = 41 number 37 is missing.

Code:

% ./a.out 41 | grep -v result | wc -w 
41
% ./a.out 41 | grep -v result | tr ' ' '\n' | sort -n 
.
33
34
35
36
38
39
40
41
41

GazL · 04-15-2021, 10:45 AM

Yep, I forgot to set seen_values[] for the first value in v2.4 when I fixed the duplicate results issue. Should be fixed now in the reupload v2.5

dogpatch · 04-15-2021, 10:19 PM

Well, i've finally (huff! puff!) gotten a working program, one that generates valid rings of squares, and the results seem to be the same as code already posted here. I have no clean code to upload yet, and hope to spend the weekend (and probably beyond) cleaning my code, adding options, and, possible speeding it up a bit. At present it's much slower than GazL's and others.

Throughout, i have retained the concept of a ring of data, with no arbitrary starting point and direction of flow. Have found that these arbitray factors can have a big impact upon process time, especially for generating the first valid ring. Perhaps this can lead to some performance gains.