Latest LQ Deal: Latest LQ Deals
 LinuxQuestions.org [SOLVED] 'Circle of Squares' programming challenge
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

 04-23-2021, 01:22 PM #61 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 488 Original Poster Blog Entries: 4 Rep: 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.)
 04-23-2021, 03:02 PM #62 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,475 Blog Entries: 1 Rep: 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.
04-23-2021, 03:42 PM   #63
dogpatch
Member

Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep:
Quote:
 Originally Posted by pan64 I was thinking about an algorithm to find out the "best" starting point.
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.

Quote:
 Originally Posted by pan64 Right now I think we can calculate the number of pairs for every number in the circle and I think we need to find the one with the lowest number of pairs (and probably we can go further to find the number of second/third/... neighbors). But probably this is not really useful.
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.

Last edited by dogpatch; 04-23-2021 at 03:51 PM. Reason: typos

 04-23-2021, 05:20 PM #64 ntubski Senior Member   Registered: Nov 2005 Distribution: Debian, Arch Posts: 3,604 Rep: 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.
 04-23-2021, 08:25 PM #65 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 488 Original Poster Blog Entries: 4 Rep: 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.
 04-26-2021, 09:50 AM #67 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,475 Blog Entries: 1 Rep: Great thanks.
 04-27-2021, 09:03 PM #68 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,475 Blog Entries: 1 Rep: Can someone would post amazing_circle_v2.c code, please? Can't find attachment anywhere in thread. Removed?
 04-28-2021, 04:20 PM #69 GazL LQ Veteran   Registered: May 2008 Posts: 5,961 Rep: 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. Last edited by GazL; 04-28-2021 at 04:27 PM. 1 members found this post helpful.
 04-28-2021, 07:12 PM #70 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 488 Original Poster Blog Entries: 4 Rep: 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: Code: ```char *fragment[MaxElement] = {"ar","ch","e","ear","in","it","s","t","th","on","ru","f","n","o"}``` and this array of words: Code: ```char *TargetWord[TargetCount] = {"arch","char","sear","near","ears","earn","on","no","inch","chin","ins","sin","art","tar","far","arf","its","sit","itch","chit","are","ear","son","ons","one","eon","of","fo","int","tin","eth","the","earth","thear","inth","thin","tear","eart","ruth","thru","ruin","inru","rue","eru"};``` 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: Code: `WordRing 9` might dump the folowing ring Code: `ch, it, s, ear, th, e, ar, t, in,` 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. Code: `WordRing 14` might dump the folowing Code: `it, ch, in, t, ar, f, o, n, ear, th, ru, e, on, s,` 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. Last edited by dogpatch; 04-28-2021 at 07:27 PM. Reason: correct code tags y español
 04-28-2021, 07:16 PM #71 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,475 Blog Entries: 1 Rep: 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?
 04-28-2021, 07:33 PM #72 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 488 Original Poster Blog Entries: 4 Rep: As others have done, i've included all text in a single .txt file, and marked each piece with start and end lines, as Code: ```/*************************** Start makefile ***********************/ . . . /*************************** End makefile ***********************/``` 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.
 04-28-2021, 07:51 PM #73 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,475 Blog Entries: 1 Rep: 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.
 04-28-2021, 07:59 PM #74 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 488 Original Poster Blog Entries: 4 Rep: 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.
 04-28-2021, 08:28 PM #75 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,475 Blog Entries: 1 Rep: 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. Last edited by igadoter; 04-28-2021 at 09:02 PM.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post iLLuSionZ Linux - Newbie 22 11-18-2003 03:36 PM icyfire Linux - Software 4 09-18-2003 04:22 PM bongo.hickup Linux - Hardware 0 06-13-2003 03:51 AM

LinuxQuestions.org

All times are GMT -5. The time now is 11:54 PM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -