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.

 05-01-2021, 09:44 PM #91 mimorek Member   Registered: Feb 2013 Distribution: Debian (jessie) Posts: 42 Rep: Here's my python version. Took me ages. Code: ```#!/usr/bin/python3 # Usage: First commandline argument is maximum number. import sys high = int( sys.argv[1] ) ring = [ x+1 for x in range(high) ] squares = [ x**2 for x in range(1, high) if x**2 < 2*high ] final = [] # Function to find circle of squares. def findPath(x, circle): for i in possq[x]: if i not in circle: findPath(i, circle[:] + [i]) if circle[-1] in possq[1] and len(circle) == high: final.append(circle) return # Create dict of possible squares. possq = dict() for base in ring: possq[base] = [] for num in ring: if num + base in squares and num != base: possq[base].append(num) # Print dictionary with possible squares. #for i, j in possq.items(): # print(i, j) # Find circle path = [1] findPath(1, path[:]) # Print result Final = [] [ Final.append(i) for i in final if i not in Final ] print(*Final, sep='\n')``` 2 members found this post helpful.
 05-02-2021, 03:43 AM #92 GazL LQ Veteran   Registered: May 2008 Posts: 6,998 Rep: Nice! That really demonstrates the difference in brevity of code between a high-level language and something like C. Though it also demonstrates the cost one pays in performance. python3 circle.py 40: real 127.58 user 126.98 sys 0.00 ./circle -as 1 40: real 1.03 user 1.03 sys 0.00 1 members found this post helpful.
05-02-2021, 10:19 AM   #93
pan64

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 22,614

Rep:
Quote:
 Originally Posted by ntubski 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
Yes, exactly. I don't really know if the other members ignored (or recognized) this post or not, but actually implemented a solution (finding a cycle in the graph). There are two ways: using linked list or using matrix.
I tried the second one (matrix based) and works a bit differently, but the implementation is mainly identical to the one what was made by GazL (ok, let we say: quite similar).
I have also added an algorithm to calculate and use an ordered list of neighbors (based on the number of their non-used neighbors), and looks like that will dramatically increase the speed.
I will try to post it soon, but the code is quite ugly at this moment, I want to make it more readable.
based on: https://www.tutorialspoint.com/Hamiltonian-Cycle

Last edited by pan64; 05-02-2021 at 10:32 AM.

2 members found this post helpful.
05-02-2021, 10:32 AM   #94
mimorek
Member

Registered: Feb 2013
Distribution: Debian (jessie)
Posts: 42

Rep:
Quote:
 Originally Posted by GazL Nice! That really demonstrates the difference in brevity of code between a high-level language and something like C. Though it also demonstrates the cost one pays in performance.
And I didn't save it on programming time either

05-02-2021, 11:43 AM   #95
mimorek
Member

Registered: Feb 2013
Distribution: Debian (jessie)
Posts: 42

Rep:
Quote:
 Originally Posted by pan64 I don't really know if the other members ignored (or recognized) this post or not,
I noticed the post, read about it, but it took me too long understand.

05-02-2021, 01:30 PM   #96
GazL
LQ Veteran

Registered: May 2008
Posts: 6,998

Rep:
Quote:
 Originally Posted by pan64 I don't really know if the other members ignored (or recognized) this post or not, but actually implemented a solution (finding a cycle in the graph).
Yes, I did go read up on that too, but it looked like in my original program the pairs were essentially "edges" and my code seemed very similar to the backtracking solutions described. To be honest, the other more involved algorithms mentioned were a little beyond me.

 05-03-2021, 11:21 AM #97 pan64 LQ Addict   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 22,614 Rep: here is it: https://pastebin.com/icWqtYR5 Memory and error handling was not fine tuned, but hopefully it will work.... 1 members found this post helpful.
 05-03-2021, 12:22 PM #98 GazL LQ Veteran   Registered: May 2008 Posts: 6,998 Rep: Nice. thanks for sharing. BTW, firefox downloaded this as *.c.c for some reason. Not sure what that's all about.
 05-03-2021, 12:42 PM #99 pan64 LQ Addict   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 22,614 Rep: probably because I clicked on "c source file", so a .c was automatically added. Unfortunately I cannot change it any more. 1 members found this post helpful.
 05-03-2021, 01:32 PM #100 GazL LQ Veteran   Registered: May 2008 Posts: 6,998 Rep: No worries, not complaining. I just wondered if my firefox, or pastebin were broken. I've seen this sort of stuff before when web servers send the wrong content type. It came down with DOS line endings too, so this may save someone a little effort grabbing it. curl "https://pastebin.com/raw/icWqtYR5" | sed 's/\r\$//' > hamiltonian.c
05-04-2021, 10:09 PM   #101
dogpatch
Member

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

Original Poster
Blog Entries: 4

Rep:
Have done two things since my last post to boost performance. First, followed GazL's lead in maintaining a 'seen' value for each number in the ring, much more efficient to reference this seen array rather than slog through the ring every iteration looking for a previous occurence of the candidate. This greatly enhances performance both for generating that first valid ring and for generating all rings for a given size.

Secondly, in generating the first ring, am now thinking that trying to find the best seed number is not the best approach. Whether the seed number is specified on the command line, or chosen by the program, have been trying to optimize the pairs array for the given seed. So have abandoned my ugly list of favorite seed numbers, and abandoned as well other attempts to programmatically select a 'good' seed value.

The list of valid pairs for each number in the ring is what counts. Have discovered that some methods of ordering the pairs works for some seed numbers, but other seed numbers do better with a different ordering method. Still haven't figured out why this is so, nor how to determine ahead of time the best way to order the pairs array for a given seed. So, am now following my own previous work in my sudoku analyzer (see post #88) in simply trying first one method, then another, etc. Right now am using 3 methods of ordering the pairs. The first, suggested by astrogeek way back, is to order the pairs in reverse, larger pair numbers first, since the larger numbers will generally have fewer pairs associated with them. The second method is the opposite, favoring smaller pair numbers first. The third method is what i'm calling a folded order, favoring numbers next in line larger than the base number. In all cases, the lists are visited a second time to bump up those numbers that have fewer associated pairs. (There is a lot more such reordering for the second and third methods.)

Just to give one example, the folded order method generates a valid ring for that troublesome ring size 50, seed 32, in just 2658 recursion cycles, blindingly fast even on my old Dell. My program is not clever enough to know ahead of time to start with the folded order method. It tries the 1st method for a million cycles or so, then the 2nd method for another million cycles, then the folded order method. Ends up with more tha 2658 overall recursion cycles - 2002694 to be exact - which is still pretty fast compared with 4597467774 cycles when it was just using the first pair ordering method. If no method generates a ring after the initial small recursion limit, it tries the same 3 methods with a larger limit. If that fails, it goes back to the first method with no recursion limit.

This whole exercise is only for generating the first valid ring. The ordering of pairs doesn't seem to appreciably affect the run time for generating all rings of a given size.

I'm sure there are some ring size and seed combinations that will still bog the program down. So far, randomly testing just a few cases, the worst case i've had is SquareRing 180 126, which went through all 3 methods twice, reverted to the first method with no recursion limit, and finally generated the first valid ring after 1128238914 recursion cycles, which is still about 4 times more efficient and almost 3 times faster than SquareRing 50 32 used to be.

Have to do more testing (and possibly look for other methods to try?), and code cleaning, etc. The next few days look to be quite busy with personal stuff, but hope to have some new code to upload soon.
Quote:
 Originally Posted by astrogeek My thoughts have been to try to add an intermediate test condition to attempt earliest detection of dead end conditions rather than having to wait until the dead ended number appears for evaluation. For a contrived example, suppose the left neighbor of your seed has five possible pair partners, and successive evaluation proceeds to the right. Then suppose within a few iterations of the pairing selection you pair each of those five possibilities with other partners, never using the left-of-seed neighbor. The left neighbor is now dead ended but you will not detect that condition until some point later in the process. Surely we can manage to detect that earlier, possibly when it occurs... but my limited attempts to turn that into code based on Gazl's 2.x base have not been successful so far.
Interesting thought; may take a look at this as well.

2 members found this post helpful.
 05-05-2021, 08:56 AM #102 mimorek Member   Registered: Feb 2013 Distribution: Debian (jessie) Posts: 42 Rep: I've adjusted my initial python script so now it finds all possible circles. I've also made a script that checks if the list of circles contains any duplicates or mirrors; and prints the unique ones. The sad thing is that PathFinderCircleOfSquares.py takes a lot of time to find all circles. PathFinderCircleOfSquares.py 36 takes like twice as long as PathFinderCircleOfSquares.py 35. But it finds all circles PathFinderCircleOfSquares.py : https://pastebin.com/pSnAdJm4 uniqueCycles.py : https://pastebin.com/bW2S8RZV Code: ```for i in {32..40}; \ do \ echo -n "Path 1..\$i :: "; PathFinderCircleOfSquares.py \$i | uniqueCycles.py | grep cycles; \ done Path 1..32 :: Unique cycles: 21 Path 1..33 :: Unique cycles: 30 Path 1..34 :: Unique cycles: 267 Path 1..35 :: Unique cycles: 670 Path 1..36 :: Unique cycles: 437 Path 1..37 :: Unique cycles: 308 Path 1..38 :: Unique cycles: 418 Path 1..39 :: Unique cycles: 679 Path 1..40 :: Unique cycles: 1116``` This takes more than 20 minutes to run. Last edited by mimorek; 05-05-2021 at 09:21 AM.
 05-07-2021, 12:04 PM #103 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: Don't know what do you mean by 'all'.
 05-07-2021, 12:15 PM #104 mimorek Member   Registered: Feb 2013 Distribution: Debian (jessie) Posts: 42 Rep: PathFinderCircleOfSquares.py N finds all valid paths of sequence 1..N. uniqueCycles.py tests all found paths for uniqueness and prints the unique circles. It removes duplicates and mirrors.
 05-07-2021, 12:30 PM #105 igadoter Senior Member   Registered: Sep 2006 Location: wroclaw, poland Distribution: many, primary Slackware Posts: 2,717 Blog Entries: 1 Rep: No matter starting point? I mean shift left/right? In circle 1,2,3 and 2,3,1 are the same.

 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 08:22 PM.

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