[SOLVED] 'Circle of Squares' programming challenge

igadoter · 04-09-2021, 01:01 PM

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.

astrogeek · 04-09-2021, 01:22 PM

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)

dogpatch · 04-09-2021, 02:03 PM

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.

astrogeek · 04-09-2021, 02:22 PM

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!

GazL · 04-09-2021, 02:24 PM

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

astrogeek · 04-09-2021, 02:40 PM

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!

dogpatch · 04-09-2021, 05:43 PM

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.

GazL · 04-09-2021, 06:20 PM

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.

GazL · 04-10-2021, 05:50 AM

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.

igadoter · 04-10-2021, 07:19 AM

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.

igadoter · 04-10-2021, 07:33 AM

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.

dogpatch · 04-10-2021, 08:55 AM

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.

igadoter · 04-11-2021, 02:25 PM

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.

pan64 · 04-12-2021, 02:17 AM

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.

igadoter · 04-12-2021, 04:10 AM

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.