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

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

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

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!

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.

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!

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.

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.

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

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.

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

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.

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