[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.
In his Amazing Circle thread, igadoter presented us with a circle of data consisting of the numbers 1 thru 32. The amazing part was that each adjacent pair of numbers when summed yielded a perfect square. He asked for a programmatic way to verify that the conditions were met for the particular sequence of 32 numbers that he supplied, which program was offered by danielbmartin. Others, including myself, have wondered about the possibility of programmatically generating such an amazing circle of numbers, so I hereby issue the programming challenge. Here are the rules:
1. The data must be a logical circle or ring of data, in which there is no defined first and last element, and no defined direction or flow (can be clockwise or counter-clockwise);
2. Each element in the ring must be within the defined limits. In this case, between 1 and 32, with each number occurring exactly once (in any order).
3. Each adjacent pair of numbers must sum to a perfect square. [1, 4, 9, etc] 'Adjacent pair' is defined per rule #1 above. That is, if you define the ring as a linear array, the array must 'wrap around' so that the first and last elements are considered logically adjacent.
Let's have a little fun with this, and, as others have suggested, maybe carry it further than limits of 1 to 32.
Last edited by dogpatch; 04-07-2021 at 06:51 PM.
Reason: last note
To start things off, I offer the following data ring class definition, FWIW. This has probably been done before and better, but it's where I'm beginning, as a C++ header, to help me to define and work with a specific ring of data.
Code:
/** Ring class: define Ring (circular array) data type */
typedef char rType;
class Ring {
public:
int rSize;
int rHead; // arbitrary start point in ring
bool rClockwise; // true=Clockwise, false=Counter-clockwise
rType *rElement; // store ring as linear array
bool rInit(int AllocSz) { // Alloc ring dynamically
if (!((void*)rElement = malloc(AllocSz*sizeof(rType))))
return false;
rSize = AllocSz;
srand(time(0));
Randomize();
return true;
};
void Randomize() {
rHead = rand()%rSize; // randomize rHead offset
rClockwise = rand()%2; // and direction of flow
return;
};
int AdvanceIndex(int Index) {
// Step index clockwise or counter, wrapping as needed
if (rClockwise) { // clockwise (normal order)
Index++;
if (Index == rSize)
Index = 0; // wrap to 0 in linear array
}
else { // counter-clockwise (descending order)
if (!Index)
Index = rSize; // wrap to end of linear array
Index--;
}
return (Index);
}
};
I would define a check like function which will return true if the sum of the given adjacent pair of numbers is square. But we can have different conditions, later....
Code:
Ring r;
....
bool check(int ix) {
int s = r[ix] + r[ix+1];
float f = sqrt((double)s);
int i = f;
return i == f;
}
First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.
P.S. I left the result in an array. It would be trivial to create a linklist from it and then point the last entry back to the first to make it circular, but it seemed kind of pointless, and I was more interested in doing the sequence generation functions.
update:
attached program now takes start value as first arg .
First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.
I created my list of pairs manually. Otherwise, this is precisely what i've been trying since early yesterday. But so far, it dead ends every time.
If i suspend randomness, it seems to make a big difference what digit i start with, which intuitively should not be. In at least two cases, i've gotten as far as a 31 byte array:
which, as you can see, does indeed wrap around to form a ring of squares, and is a different order than the original amazing circle. But there are only 31, not 32 digits. The missing digit is 2, which does not fit into any point in the 31 byte circle. There are a number of other circles of fewer than 32 digits; that doesn't meet the challenge.
I haven't yet figured out why i can't get the above sequence if i start with, say, '21' or some other digit. Perhaps my backtracking logic need some tweaking. Or perhaps a completely different approach. If you get a full 32 byte circle, I'd love to see your code.
I have not yet had a chance to write any code, or even decide what I want to write! But I did write on paper a list of all the possible pairings which sum to perfect squares and thinking about what I see in that list leads to a set of constraints for generating a complete ordering, as well as placing limits on the number of integers in the ring (32 may represent a limit!).
I'll defer posting my own observations but offer the following helpful hints:
* There aren't really a great number of choices - the possible pairs are tightly constrained in "families" of number of choices
* Each choice, where there is a choice, further constrains the next choice
* Using the clues suggested by the above list, think in terms of segments (arcs) of one or more pairs, then join the segments
On paper I was able to find (generate) a 32 number solution quickly (or perhaps accidentally!)
Last edited by astrogeek; 04-08-2021 at 12:29 PM.
Reason: arcs
I did not check all of them, but they look identical (just the first number is different, but the order is the same).
My routine is deterministic with no random element, so one should expect to see common sequences of varying length reoccurring when it is possible. It will only diverge when an already used number forces a different path. Look closer and you'll see this to be true.
I have written a C routine which implements my thoughts on building the circle from segments (refined pencil and paper method). Instead of trying all possible combinations as Gazl has done, I successively pair everything that is fully deterministic and then test for any left overs.
The segments are doubly linked lists and the strategy is:
1. Connect all deterministic pairings into segments (those integers with only two possible pairing partners)
2. Connect all deterministic segment end pairs (segment ends with only one possible partner)
3. If the result is a ring then there is only one solution and its mirror, it is fully deterministic.
When run it produces the result below. The numbers in parenthesis are the sum of leading and trailing pairs. I set the circle entry to 4 only to orient the result with the original post's example, but it is a doubly linked ring of integers.
My routine is deterministic with no random element, so one should expect to see common sequences of varying length reoccurring when it is possible. It will only diverge when an already used number forces a different path. Look closer and you'll see this to be true.
First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.
P.S. I left the result in an array. It would be trivial to create a linklist from it and then point the last entry back to the first to make it circular, but it seemed kind of pointless, and I was more interested in doing the sequence generation functions.
update:
attached program now takes start value as first arg .
not identical. there is reversal on some sequences. I never claimed it would find multiple sequences, only that it would generate a valid result given any start point.
Look carefully. All these above sequences are in fact the same up to mirror. It is not difficult to create up to test that the above sequences are the same up to mirroring. The first starts with 1 reaches 2 - now read backward from this point and compare with sequence starting with 2 - they are the same.
Edit: For me it looks like all these sequences are the same - and the same as original sequence. So seems tha GazL showed us - computer proof - there is only one such sequence. If there are no other possibilities. Congrats! But if it is true - challenge is finished.
Edit: here what is more challenging #n - number of different sequences with the property as amazing circle for given n - seems that #32 = 1 - only one sequence. What about #123? Reasonable sequence is when there is algorithm to compute it - say Fibonacci - there is page on internet with "all" up to date known sequences - if you will find new one - fame awaits you.
Have to credit Gazl with first meeting the challenge of generating a valid 32 element circle of squares. But, with his own caveat:
Quote:
Originally Posted by GazL
This may not be all possible sequences, my code just returns the first complete valid sequence it finds for each start point.
I will try to study Gazl's code to understand why my (similar) approach didn't work. Meanwhile will try to employ something more like Astrogeek's:
Quote:
Originally Posted by astrogeek
* There aren't really a great number of choices - the possible pairs are tightly constrained in "families" of number of choices
* Each choice, where there is a choice, further constrains the next choice
* Using the clues suggested by the above list, think in terms of segments (arcs) of one or more pairs, then join the segments
Quote:
Originally Posted by astrogeek
1. Connect all deterministic pairings into segments (those integers with only two possible pairing partners)
2. Connect all deterministic segment end pairs (segment ends with only one possible partner)
3. If the result is a ring then there is only one solution and its mirror, it is fully deterministic.
This approach sounds more likely to generate multiple sequences, if such multiple sequences exist, or to definitively prove that there is only one valid 32 element Ring. Keeping in mind that every valid Ring can be expressed as an array of 64 permutations, for 32 head points * 2 directions.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.
