[SOLVED] 'Circle of Squares' programming challenge

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.

Exclusive for LQ members, get up to 45% off per month. Click here for more info.

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

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:

* 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

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

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

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

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!

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.

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.

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.

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

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.

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.

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.

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

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.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.