Latest LQ Deal: Latest LQ Deals
 LinuxQuestions.org [SOLVED] 'Circle of Squares' programming challenge
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

 04-12-2021, 05:53 PM #31 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1} Posts: 6,292 Blog Entries: 24 Rep: @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 Last edited by astrogeek; 04-13-2021 at 12:06 AM. 3 members found this post helpful.
04-12-2021, 05:58 PM   #32
astrogeek
Moderator

Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,292
Blog Entries: 24

Rep:
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!

 04-12-2021, 07:29 PM #33 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: 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. 2 members found this post helpful.
 04-12-2021, 07:40 PM #34 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1} Posts: 6,292 Blog Entries: 24 Rep: 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! Last edited by astrogeek; 04-12-2021 at 07:57 PM.
 04-12-2021, 08:06 PM #35 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: Thanks, I will remember that.
 04-12-2021, 11:35 PM #36 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1} Posts: 6,292 Blog Entries: 24 Rep: 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. 1 members found this post helpful.
 04-13-2021, 01:31 AM #37 pan64 LQ Addict   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 22,589 Rep: 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. Last edited by pan64; 04-13-2021 at 01:33 AM. 3 members found this post helpful.
04-13-2021, 06:29 AM   #38
GazL
LQ Veteran

Registered: May 2008
Posts: 6,997

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

Last edited by GazL; 04-13-2021 at 06:33 AM.

 04-13-2021, 09:32 AM #39 GazL LQ Veteran   Registered: May 2008 Posts: 6,997 Rep: 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! Last edited by GazL; 04-15-2021 at 07:05 AM. 2 members found this post helpful.
 04-13-2021, 10:44 AM #40 pan64 LQ Addict   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 22,589 Rep: yes, now comes the next step: find all the different solutions. (or the number of different circles)
04-13-2021, 12:05 PM   #41
GazL
LQ Veteran

Registered: May 2008
Posts: 6,997

Rep:
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 @@

-    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

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.

Last edited by GazL; 04-13-2021 at 12:07 PM.

1 members found this post helpful.
 04-15-2021, 07:00 AM #42 GazL LQ Veteran   Registered: May 2008 Posts: 6,997 Rep: 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) Last edited by GazL; 08-13-2024 at 11:25 AM. 2 members found this post helpful.
 04-15-2021, 10:21 AM #43 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: 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
 04-15-2021, 10:45 AM #44 GazL LQ Veteran   Registered: May 2008 Posts: 6,997 Rep: 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 2 members found this post helpful.
 04-15-2021, 10:19 PM #45 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 490 Original Poster Blog Entries: 4 Rep: 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. 1 members found this post helpful.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post iLLuSionZ Linux - Newbie 22 11-18-2003 03:36 PM icyfire Linux - Software 4 09-18-2003 04:22 PM bongo.hickup Linux - Hardware 0 06-13-2003 03:51 AM

LinuxQuestions.org

All times are GMT -5. The time now is 08:34 AM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -