My code is still slow compared with GazL's and astrogeek's (& others?), but have spent alot of time on this, so will post it for what it's worth:

My first and best strategy for reducing processing time was to make the RecursFind() function as simple as possible, and then to reduce the number of its recursive cycles.

From the beginning, i've employed an array of potential 'mates' for each element, similar to GazL and astrogeek. Following astrogeek's idea of deterministic sequences, i saw that i could easily identify in these arrays necessary 3-element chains, and then eliminate the middle element from any other element's list of potential 'mates', because if a given value is the middle element of a deterministic chain, it can never be usefully attached to elements other than the two outer elements in the deterministic chain.

Next, i could arrange each element's array of mates in reverse order of their 'popularity' within the array of mate arrays. That is, elements with fewer potential mates (generally, but not always, larger numbers) should have priority over those with more potential mates. This leads to less iteration within RecursFind(), and fewer recursions as well.

The first measure, of eliminating useless mates, nicely improves performance both for generating a single ring and for generating all rings of a given size. The second one, the ordering of mates according to 'popularity', improves the speed of generating the first ring, but has little or no effect on generating all rings. Code and comments can be seen in WRopt.h.
---------------

Secondly, as some of you have already pointed out, i noticed that, especially for larger ring sizes, the starting or 'seed' number made a huge difference in the number of recursive cycles, and, therefore, in processing time. This was especially true when just the initial ring was requested (no option -a). Even large ring sizes could sometimes generate the first ring after only a few cycles, while the same ring size with a different seed value would grind on seemingly forever without generating a single ring. Moreover, for some intermediate sizes, a given seed number might generate a single ring quickly but grind unceasingly in generating all rings, while a different seed might take longer to generate the first ring, but might generate all rings relatively more quickly.

I tried valiantly, but unsuccessfully, to discern a pattern to this, and to code some kind of logic to address it. I soon gave up on the idea of making the all_rings option fast by playing with the seed value. Also, mustn't alter the seed value if it was specified on the command line. So, focusing only upon the initial ring generation, and only when the seed is not specified, i still couldn't find a way to programmatically optimize the selection of a seed, nor even to discern a hint of a pattern. Perhaps astrogeek can explain it, or perhaps it's just an example of chaos.

At any rate, i finally decided that the only way to determine the best seed values for a given size was via trial and error. So i temporarily altered the program for a series of speed tests, and via a recursive bash script dumped to a text file the output for various seeds for various ring sizes, and awked it into another include file SRopt.h, which see in the uploaded WonderRing.cpp.txt. It's an ugly and shameful kludge, but it does have a dramatic effect, so am using it, for now at least. Here are the limitations and caveats:
- Only ring sizes 43 thru 125 are affected. No need in the smaller rings, and i didn't have time or patience to go beyond 125.
- Only employed for generating a single valid ring (option -a ignores this logic)
- Only employed if the seed value is NOT specified on the command line.
- It randomly selects from those seeds that passed the bash script test, with preference for the quickest seeds.
- Have retained the original bash output, which has more detailed info. Perhaps may take a gander at this data some day, and try again to discern a pattern. Or if one of you are interested, please let me know. Each ring size seems to have its own favorite starting seeds, with no apparent relation to other ring sizes.
- All this seems only to apply to a target of squares. Primes, or other target types, will, i think, show a completely different pattern or lack therof. So the ugly include file SRopt.h is only included and used for the SquareRing program, not for PrimeRing (nor FibonacciRing, etc.)

Great thanks @dogpatch. I will test as soon as I fix laptop - damaged hard drive due to too high temperature. I switched off too soon laptop. Was tired - people stop thinking when tired. I am posting this to assure I am all the time interested in this. Myself I tried to implement this idea of mine of modifications. But it appeared my knowledge of C is not enough. But I will be working on this.

I never came up with an algorithm, but used brute force, as noted in my last post. And this 'best' point seems to matter much only for finding the first valid ring, not for generating all rings of a given size.

Yes, i have found this technique to be quite useful, for reducing excess iterations and recursions, and it improves processing time both for the first valid ring and for subsequent rings.

And don't neglect to completely eliminate useless pairs (or 'mates' as i name them), as noted above.

I think nobody pointed out yet that this find-a-circle-problem is equivalent to finding a Hamiltonian cycle in a graph (where each number is a node, and there is an edge between nodes if two numbers sum to a square). This is an NP-complete problem in the general case, although for some classes of graph there are polynomial algorithms (I'm not which type of graph the circle of squares map to, could be different for different sets of numbers). https://en.wikipedia.org/wiki/Hamiltonian_path_problem

1 members found this post helpful.

I think i've corrected the occasional floating point bug, but it was a minor thing and am still not positive i've corrected it. So haven't uploaded any updated code.

Meanwhile, have played a bit with alternate target numbers. Armstrong numbers only work for the first 9 numbers, which are simply integers 1 thru 9. With that as a target array, the program can generate valid rings of up to 7. (yawn)

Fibonacci numbers are a bit more interesting. The fibonacci sequence is such that, no matter the ring size, at least one number will have only one possible mate, and so it is impossible to form a valid ring, no matter how far along the fibonacci sequence you go. This one was fun to play with, but no valid rings to show you.

Here is my latest code. Am calling this version 1.1 (my earlier upload didn't have a version number).

WonderRing.1.1.txt

This upload contains all the pieces you need, minus DataRing.h, attached a few posts ago in its own separate upload, which is unchanged. There are a couple minor bug fixes, a little cleaning of code here & there, version number, 5 new ring sizes in the seed optimization array SR_opt.array (now optimizes seeds for rings of squares sizes 43 through 130). Again, you may have to tweak the use of header files per your newer development environment.

Also, in accord with most other contributors here, i now refer to the coupling together of two numbers as 'pairs', not 'mates', as i had been doing. That is, i changed structures and variable names, as well as a few display literals from 'mate' to 'pair'. This, of course, does not affect the binary logic. But reflected upon the fact that the ring logic doesn't work unless each number in the ring has at least two other numbers to which it can be added to form a square (or prime or triangular) number. My earlier nomenclature in calling these coupled numbers 'mates' was demanding promiscuity, and prohibiting monogamy, hardly a civilized system. Anyway, the unfortunate nomenclature is now corrected.

Plus: a new target include file TriangularTarget.h for making the TriangularRing program ('Triangular' number sequence 1, 3, 6, 10, etc.) Had a little fun with it, runs faster than SquareRing, but not as fast as PrimeRing. There are places where it would need its own seed optimization, which i haven't done.

2 members found this post helpful.

Great thanks.

Can someone would post amazing_circle_v2.c code, please? Can't find attachment anywhere in thread. Removed?

You can find the source in this post:

https://www.linuxquestions.org/quest...ml#post6241335

It got renamed to just circle as I went along, but its fundamentally the same program, cleaned up, with some minor speed enhancements and a bugfix.

I'm afraid I didn't keep a copy of the older versions, and yes, I deleted the attachments after they were superceded as I didn't think anyone would want the older ones.

1 members found this post helpful.

WonderRing.1.2.txt

Version 1.2 of my code introduces the idea of a ring of textual data, as opposed to numbers, first suggested by igadoter back in his "Amazing Circle" thread. I haven't (yet) enhanced DataRing.h to handle rings of strings or rings of pointers to strings. Rather, this version maintains a ring of integers as before, which are then used to index static character arrays. I only had to change the building of the array of pairs in WRopt.h, and the DumpRing() function in WonderRing.cpp. Also eliminated the command line -o and Seed options. These changes only affect the new logic. The previous programs SquareRing, PrimeRing, and TriangularRing should remain unaffected, save for a new version number.

WordRing works by building rings of string fragments. Each adjacent pair of fragments when concatenated together, forms a word found in the target array of words. So, starting with this array of fragments:
and this array of words:
WordRing assembles rings of fragments in such a way that each adjacent pair of fragments forms a word, regardless of the direction of flow. E.g, fragments "in" & "ch" are a valid pair because they form words "inch" and "chin", both of which are in the TargetWord array. This is to conform to the logic already in place for numeric data rings, where adjacent pairs are added together. Addition is a commutative operation; string concatenation is not, so the logic is a bit different.

The trick is to think of fragment pairs that form words regardless of which fragment is the 'head'. Plus, each fragment must form a pair with at least one other fragment, and most fragments should have 3 or more pairs, so the WordRing program can generate valid rings in which each fragment occurs exactly once, just like SquareRing.

Currently, WordRing can generate ring sizes of 9, 10, 11, and 14 elements. A couple examples:
might dump the folowing ring
Reading forward, this would form words "chit, its, sear, earth, the, ear, art, tin, inch"
and backward, "int, tar, are . . . itch, chin"
all of which are in the TargetWord array.

might dump the folowing
Caveat: Yes, i know that some of the 'words' in WordArray would never pass the Scrabble test. They tell me "thear" is a real word, but "eru", "eth", "inth" & others, are questionable, to say the least. Well, OK, this is mostly to test the concept. I leave it to one of you to come up with a better WordTarget.h

Last of all, just for fun, incluí también código en makefile y PalabraTarget.h para hacer PalabraRing, anillos de datos de palabras en español. Actualmente, puede generar anillos de 13, 14, 16 y 18 elementos.

How do I split the file into separate files? file utility says it is CRLF line terminated text file - awk has capability to create archives (bundle) - does it something similar?

As others have done, i've included all text in a single .txt file, and marked each piece with start and end lines, as
Just cut and paste the stuff in between to a file named 'makefile'. Same with the other pieces.

Upload 1.2 is not complete; just what changed from 1.1. First download version 1.1, a few posts back, then 1.2 to get the stuff that's changed.

You will find in classic book about awk (original) that awk can do bundle - and unbundle - documents. File with examples from book is one text file containing all examples. There is about eighty of them all. The only problem I had to solve was to add header to each file #!/usr/bin/awk -f. To make files scripts. The book is the first book about awk - I don't want to mess now with authors.

Trouble is, LQ only accepts certain file types. Text files with .txt extension are one, and have been employed by myself and others here as the generic way to share programming code. Plus, i am not familiar enough with awk to use the awk bundle technique. Sorry.

Just try yourself. Here direct download link for examples https://www.cs.princeton.edu/~bwk/bt...or/awkcode.zip . Bundle/unbundle works as well with gnu awk. Awk is really fun. Good to learn in spare time.

Edit: One more thing. fromdos utility converts dos files into unix files.