[SOLVED] 'Circle of Squares' programming challenge

mimorek · 05-01-2021, 09:44 PM

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')

GazL · 05-02-2021, 03:43 AM

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

pan64 · 05-02-2021, 10:19 AM

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

mimorek · 05-02-2021, 10:32 AM

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

mimorek · 05-02-2021, 11:43 AM

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.

GazL · 05-02-2021, 01:30 PM

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.

pan64 · 05-03-2021, 11:21 AM

here is it: https://pastebin.com/icWqtYR5
Memory and error handling was not fine tuned, but hopefully it will work....

GazL · 05-03-2021, 12:22 PM

Nice. thanks for sharing.

BTW, firefox downloaded this as *.c.c for some reason. Not sure what that's all about.

pan64 · 05-03-2021, 12:42 PM

probably because I clicked on "c source file", so a .c was automatically added. Unfortunately I cannot change it any more.

GazL · 05-03-2021, 01:32 PM

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

dogpatch · 05-04-2021, 10:09 PM

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.

mimorek · 05-05-2021, 08:56 AM

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.

igadoter · 05-07-2021, 12:04 PM

Don't know what do you mean by 'all'.

mimorek · 05-07-2021, 12:15 PM

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.

igadoter · 05-07-2021, 12:30 PM

No matter starting point? I mean shift left/right? In circle 1,2,3 and 2,3,1 are the same.