LinuxQuestions.org [SOLVED] 'Circle of Squares' programming challenge
 User Name Remember Me? Password
 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-09-2021, 02:01 PM #16 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: Let's try sequences of squares Code: ```4 4 1 3 1 - circle is closed ....... 4 9 .. 1 3 6 ... ...... 4 16 ... 1 3 13 ... ...``` extend by next square as long as there is no repetition. Last edited by igadoter; 04-09-2021 at 02:36 PM.
 04-09-2021, 02:22 PM #17 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1} Posts: 6,004 Blog Entries: 23 Rep: Sorry to delay posting the code - it was after 3AM when finished and needed a little cleanup - here it is (and apologies if I broke anything during housekeeping!) circle.txt I have commented the header file with more complete details of the basis of my strategy, and the source code with hints where the implementation may be obscure, hope it is readable. What I refer to as "bottom-up" pairings has a few subtleties but I have explored it in some detail and reduced the logic to only what is necessary, and am confident it is sound. If anyone thinks otherwise I would appreciate an example of an actual exception within the range of values under test. Indeed, I am confident this may be taken as proof that there is a single solution and its mirror. In addition, it suggests answers to a few earlier questions: Code: ```* Can there be such circles of more than 32 integers? Maybe not (but see Gazl's post #20 below!) - An unavoidable gap is produced by 33, and higher numbers (also evident in shape of listing in header) * Can you remove any single number and have the circle remain valid? Probably not - the sequence is fully deterministic and it is difficult to see how to remove anything and close the circle``` It will accept arguments for list starting point and listing direction, for example: Code: ```./circle 17 rev 17 (49, 36) 32 (36, 49) 4 (25, 36) 21 (49, 25) 28 (36, 49) 8 (9, 36) 1 (16, 9) 15 (25, 16) 10 (36, 25) 26 (49, 36) 23 (25, 49) 2 (16, 25) 14 (36, 16) 22 (49, 36) 27 (36, 49) 9 (25, 36) 16 (36, 25) 20 (49, 36) 29 (36, 49) 7 (25, 36) 18 (49, 25) 31 (36, 49) 5 (16, 36) 11 (36, 16) 25 (49, 36) 24 (36, 49) 12 (25, 36) 13 (16, 25) 3 (9, 16) 6 (36, 9) 30 (49, 36) 19 (36, 49)``` Last edited by astrogeek; 04-09-2021 at 08:05 PM. Reason: tpoys, shameless face saving! 1 members found this post helpful.
04-09-2021, 03:03 PM   #18
dogpatch
Member

Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490

Original Poster
Blog Entries: 4

Rep:
Thanks, astrogeek. Will study your code.
Quote:
 Originally Posted by astrogeek * Can you remove any single number and have the circle remain valid? Probably not - the sequence is fully deterministic and it is difficult to see how to remove anything and close the circle
I have (accidentally?) produced some valid circles of squares with some digits missing, e.g
Code:
```
25 24 12 13 23 26 10 15 21 28 8 17 32 4 5 31 18 7 29 20 16 9 27 22 14 11```
and at least one 32 element linear array that doesn't wrap around to form a ring (first and last elements don't sum to a square):
Code:
```
1 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15 21 28 8 17 32 4 12 13 3 6 30 19```
Of course, neither of these meet the challenge of a valid 32 element ring, and both involve completely different sequences, not the removal of digits from a (the?) valid ring

I think there were one or more valid rings of 31 digits. The missing digit was 2, if i remember correctly. If i can reproduce it, will post it here.

Last edited by dogpatch; 04-09-2021 at 03:15 PM. Reason: add thanks and caveat

1 members found this post helpful.
04-09-2021, 03:22 PM   #19
astrogeek
Moderator

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

Rep:
Quote:
 Originally Posted by dogpatch I have (accidentally?) produced some valid circles of squares with some digits missing, e.g Code: ``` 25 24 12 13 23 26 10 15 21 28 8 17 32 4 5 31 18 7 29 20 16 9 27 22 14 11```
Indeed! I had typed a third question to the effect...

Code:
```* Can there be other valid circles of fewer numbers?
Almost certainly. While it is difficult to see a way to remove any single number and rejoin the ends,
it is easy to see smaller rings, or removal of larger segments and be able to rejoin the ends.```
But I had not fully explored it and decided it was too vague... but here now for what it is worth!

One inportant aspect of "with a few numbers missing" is whether they are missing from the end, leaving the list complete in some sense, or missing from within leaving gaps. Sets of numbers with internal discontinuities seem much easier to join into rings ad hoc whereas a continuous list imposes a more difficult constraint I think.

Quote:
 Originally Posted by dogpatch and at least one 32 element linear array that doesn't wrap around to form a ring (first and last elements don't sum to a square): Code: ``` 1 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15 21 28 8 17 32 4 12 13 3 6 30 19```
That one doesn't count!

Quote:
 Originally Posted by dogpatch I think there were one or more valid rings of 31 digits. The missing digit was 2, if i remember correctly. If i can reproduce it, will post it here.
I'd be interested to see that one!

1 members found this post helpful.
 04-09-2021, 03:24 PM #20 GazL LQ Veteran   Registered: May 2008 Distribution: CRUX 3.7 Posts: 6,592 Rep: Here's the amazing_circle sequence for 1-50: Code: `1, 3, 6, 10, 15, 49, 32, 4, 5, 11, 14, 50, 31, 18, 46, 35, 29, 7, 9, 27, 22, 42, 39, 25, 24, 40, 41, 8, 17, 47, 2, 34, 30, 19, 45, 36, 28, 21, 43, 38, 26, 23, 13, 12, 37, 44, 20, 16, 33, 48.` This one took over 6 mins cpu time to calculate using my sequence finding routine. I've found many other lengths generate a valid sequence, though not all (1-31 being one of the ones that fails to solve). Last edited by GazL; 04-09-2021 at 03:29 PM. 2 members found this post helpful.
04-09-2021, 03:40 PM   #21
astrogeek
Moderator

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

Rep:
Quote:
 Originally Posted by GazL Here's the amazing_circle sequence for 1-50: Code: `1, 3, 6, 10, 15, 49, 32, 4, 5, 11, 14, 50, 31, 18, 46, 35, 29, 7, 9, 27, 22, 42, 39, 25, 24, 40, 41, 8, 17, 47, 2, 34, 30, 19, 45, 36, 28, 21, 43, 38, 26, 23, 13, 12, 37, 44, 20, 16, 33, 48.` This one took over 6 mins cpu time to calculate using my sequence finding routine. I've found many other lengths generate a valid sequence, though not all (1-31 being one of the ones that fails to solve).
So some longer sequences are possible, very interesting!

I have been so preoccupied with my own code in limited free time and have not had a chance to look into yours, but will do so over weekend. Thanks!

2 members found this post helpful.
 04-09-2021, 06:43 PM #22 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 490 Original Poster Blog Entries: 4 Rep: Here's a 31 element ring of squares: Code: `30 19 17 32 4 5 31 18 7 29 20 16 9 27 22 14 11 25 24 12 13 23 26 10 15 21 28 8 1 3 6` but neither this nor the 26 element ring in post #18 above meet the challenge, because, although they wrap around as a ring of data, they still include values 1 thru 32, beyond their proper range. The 31 element ring is missing a 2, not a 32. And astrogeek is right, of course; the missing digits are outside the ring. The 2 could not be validly inserted in any location without completely re-arranging the sequence, and so could not be described as being removed from inside a valid 32 element ring. 1 members found this post helpful.
 04-09-2021, 07:20 PM #23 GazL LQ Veteran   Registered: May 2008 Distribution: CRUX 3.7 Posts: 6,592 Rep: Here's an updated version of my program. It now takes number of elements and start value as arg1 and arg2 respectively to aid experimentation. It runs much faster when compiled -O3, and this version has replaced the O(n) value_used() function in the original with an O(1) lookup which also helped speed it up significantly. Running ./amazing_circle 51 takes about two minutes here. Running ./amazing_circle 52 takes over six minutes, and calculation time starts to get significant as the sequence size gets larger. Last edited by GazL; 04-15-2021 at 08:05 AM. 1 members found this post helpful.
 04-10-2021, 06:50 AM #24 GazL LQ Veteran   Registered: May 2008 Distribution: CRUX 3.7 Posts: 6,592 Rep: And a final version. Purely performance improvements this time: generating an index of the pairs by value rather than doing a sequential search in find_next() brings the 1-52 calculation time down from 6 minutes to 33 seconds. Last edited by GazL; 04-15-2021 at 08:05 AM.
 04-10-2021, 08:19 AM #25 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: Thanks, this Code: `% time for i in `seq 52` ; do echo -n "\$i "; ./a.out \$i >/dev/null && echo 1 || echo 0 ; done` says starting from 32 there is always such sequence, here is my timing Code: ``` real 2m2.535s user 2m2.336s sys 0m0.056s``` on Code: ```% lscpu | grep name Model name: Intel(R) Core(TM) i5-3320M CPU @ 2.60GHz``` essentially I see drop of performance at 52, say the same as above but up to 51, gives Code: ```real 0m54.465s user 0m54.285s sys 0m0.046s``` so to calculate ./a.out 52 took almost the same time as to calculate all earlier sequences. At the end I can assure that if there is only one sequence starting with 1 then there are no other sequences.
 04-10-2021, 08:33 AM #26 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: Where beauty lies? Genetic modification. Let see hot looks like sequences for 32 and 33 Code: ``` 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 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 33 16 9 27 22 14 2 23 26 10 15``` as you see these sequences share very large common prefix start from 1 up to 5, notice Code: ```31 18 7 29 20 20 29 7 18 31``` they are reverse of each other -now 33 in new insertion and the rest is the same as in the first sequence. Why we slice the first sequence at 31 and 16? It's evident 31+33= 64 is a square, 16+33=49 is a square! So it seems it is possible to create new sequence from existing one through slicing, reversing and insertion. It is pure bio-technology . I really deserve for this good beer. Nope, doctor's say can't drink, think chocolate be enough sigh. 2 members found this post helpful.
04-10-2021, 09:55 AM   #27
dogpatch
Member

Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 490

Original Poster
Blog Entries: 4

Rep:
As expected, you fellows are leaving me in the dust, even though i had a head start.

Quote:
 Originally Posted by igadoter Genetic modification. Let see hot looks like sequences for 32 and 33 Code: ``` 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 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 33 16 9 27 22 14 2 23 26 10 15``` as you see these sequences share very large common prefix start from 1 up to 5, notice Code: ```31 18 7 29 20 20 29 7 18 31``` they are reverse of each other -now 33 in new insertion and the rest is the same as in the first sequence. Why we slice the first sequence at 31 and 16? It's evident 31+33= 64 is a square, 16+33=49 is a square! So it seems it is possible to create new sequence from existing one through slicing, reversing and insertion. It is pure bio-technology . I really deserve for this good beer. Nope, doctor's say can't drink, think chocolate be enough sigh.
This sounds exactly like what astrogeek has been saying about deterministic sequences, series that must exist, or their mirrors. His logic makes it possible to identify such sequences before starting any recursive looping. Such sequences then remain valid and deterministic in ever larger rings. Not only that, but new deterministic sequences may then be identified as longer rings are developed.

I predict that combining this with Gazl's enhanced performance could greatly reduce run time and make larger rings and, possibly, reveal multiple valid rings for some ring sizes.

Last edited by dogpatch; 04-10-2021 at 10:04 AM.

1 members found this post helpful.
 04-11-2021, 03:25 PM #28 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: 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.
 04-12-2021, 03:17 AM #29 pan64 LQ Addict   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 19,532 Rep: I tried to improve [speed up] that amazing_circle_v2.1.c, but was not that easy. Actually [for 51] the find_next function was called 507 343 990 times.
 04-12-2021, 05:10 AM #30 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: Ok let me explain what I'm thinking of in more details. The program (or procedure) takes as input amazing circle and extends it by one. As input let take circle of 32 number (1.. 32). Now Code: ```33+3=36 33+16=49 33+31=64``` now we need to find numbers 3, 16, 31 in input circle. Each pair (3,16), (3,31), (16,31) divides circle into two "arcs" [3,16] - the first one reaches 16 going forward - second backward. This [3,16) means the arc without 16, (3,16] - arc without 3. Let reverse [3,16). then 3 and 16 will be adjacent and I can insert 33 between them. But reverse may not give new amazing circle. Condition must be satisfied. Ok some picture Code: `1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15` this is circle of 32 numbers let's look for pair 3,16 one of arcs [3, 16] is Code: `3 13 12 24 25 11 5 31 18 7 29 20 16` and [3,16) is Code: `3 13 12 24 25 11 5 31 18 7 29 20` reverse is Code: `20 29 7 18 31 5 11 25 24 12 13 3` this reversing is operation did on circle so output is Code: `1 8 28 21 4 32 17 19 30 6 20 29 7 18 31 5 11 25 24 12 13 3 16 9 27 22 14 2 23 26 10 15` now 3 and 16 are adjacent and I can put between them 33. But construction fails: there are two consecutive numbers 6 20 which do not sum up to square 6+20=26. Verifying all pairs and all arcs finally we succed with 31 and 16.

 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 04:36 PM icyfire Linux - Software 4 09-18-2003 05:22 PM bongo.hickup Linux - Hardware 0 06-13-2003 04:51 AM

LinuxQuestions.org

All times are GMT -5. The time now is 09:54 AM.

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