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

#!/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')

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

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.

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

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.

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

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