[SOLVED] 'Circle of Squares' programming challenge

dogpatch · 05-10-2021, 01:22 PM

Quote:

Originally Posted by GazL

Yes, these totals exclude mirrored results, which the latest version of my program no longer finds. Also, I don't believe that it was possible for my code to return a non-mirrored duplicate result, even before I changed it.

My code has always found the mirrored results, but can now recognize and not count them. If launched with option -a, it shows all results, including mirrors. If option -ao, it orders the ring data and culls the mirrors. Would be interested to know how your code doesnt even find them in the first place. Will have to study your code a bit more.

dogpatch · 05-10-2021, 02:17 PM

Have uploaded my latest code to its own directory on my personal website. I think you can download it via this hyperlink:

WonderRing_1.3.patch.txt

As suggested by the filename, am calling this version 1.3. If you can download it, you should be able to then unpack it into the current directory thus:

Code:

patch -p1 < WonderRing_1.3.patch.txt

(Thanks to GazL for tips on using diff and patch)

I think the header file inclusions should now work for newer compilers. Cannot test to be sure.

GazL · 05-10-2021, 02:35 PM

Quote:

Originally Posted by dogpatch

... Would be interested to know how your code doesnt even find them in the first place. Will have to study your code a bit more.

In the new version (which I haven't posted yet), I pick a seed value, and use that to find all possible permutations of before/seed/after, while ensuring the same candidate pair(before/after) is not used again in reverse. As candidate pairs only appear in one orientation, you now avoid mirrored results.

Each of the above permutations is then passed to the solver as a separate job, splitting the problem space.

Example run for 32 number circle, using seed 1.

Code:

$ ./circle -va
Calculating sequence(s), please wait...

Candidates Table:
1: 24 15 8 3
2: 23 14 7
3: 22 13 6 1
4: 32 21 12 5
5: 31 20 11 4
6: 30 19 10 3
7: 29 18 9 2
8: 28 17 1
9: 27 16 7
10: 26 15 6
11: 25 14 5
12: 24 13 4
13: 23 12 3
14: 22 11 2
15: 21 10 1
16: 20 9
17: 32 19 8
18: 31 7
19: 30 17 6
20: 29 16 5
21: 28 15 4
22: 27 14 3
23: 26 13 2
24: 25 12 1
25: 24 11
26: 23 10
27: 22 9
28: 21 8
29: 20 7
30: 19 6
31: 18 5
32: 17 4
Using Seed value: 1
Jobs to submit to solver (seeded result buffers):
24 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
24 1 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
24 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 1 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Result(s):
15 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10

1 results returned.

You'll see that there are 6 separate jobs (pre-seeded buffers) queued to be solved, which it currently processes sequentially.

What got me excited about this approach is that it shouldn't be hard to make it use multiple solver threads and process them in parallel. I've already done much of the prep work for that, I just need to read up a little on pthreads for the final bit of the puzzle.

The longer the circle, the more possible permutations,the more jobs the problem space will be split into. So, it looks like it will scale pretty well.

So, that's where I am right now.

igadoter · 05-10-2021, 02:51 PM

We owe @dogpatch for to make this programming challenge. As every good problem it grows and feeds itself - what @GazL posted is very advanced level of programming - people who want to learn something are greatly invited to follow.

mimorek · 05-10-2021, 04:30 PM

Quote:

Originally Posted by GazL

Here's some timings on my latest WIP version:

Code:

$ time ./circle -va 40 |grep results
64 results returned.

real	0m0.814s
user	0m0.817s
sys	0m0.000s

For those of you running your own code, do those "results returned" numbers agree with what you get?

No, I get different results:

Code:

circleofsquares_v03.py 40 | uniqueCycles.py | grep -i "input\|unique"
Paths in input:  1180
Unique cycles: 1116

Quote:

Originally Posted by GazL

P.S. I don't have enough experience with python to contribute on that thread of the discussion, but I'm still watching with interest.

I don't have enough experience with C, and I took an interest in Python a few months back. So that's what I can work with, sort of. I did compile and ran your program. I'm looking forward to your current version.
Indeed interesting to see one problem solved different ways.

mimorek · 05-10-2021, 04:48 PM

Quote:

Originally Posted by dogpatch

WonderRing_1.3.patch.txt
...
...
I think the header file inclusions should now work for newer compilers. Cannot test to be sure.

I tried compiling your program dogpatch, but ran into errors which I don't understand.

Code:

$ ls
WonderRing_1.3.patch.txt
$ patch -p1 < WonderRing_1.3.patch.txt
patching file README.txt
patching file makefile
patching file DataRing.h
patching file WonderRing.cpp
patching file WRpairs.h
patching file SquareTarget_1.3.h
patching file PrimeTarget.h
patching file TriangularTarget.h

$ make SquareRing
g++ -Wall WonderRing.cpp -include SquareTarget_1.3.h -o SquareRing
In file included from WonderRing.cpp:9:
DataRing.h: In member function ‘bool Ring::rInit(int)’:
DataRing.h:39:54: error: lvalue required as left operand of assignment
  if (!((void*)rElement = malloc(AllocSz*sizeof(rType))))
                                                      ^
DataRing.h: In member function ‘int Ring::rSeek(int, bool)’:
DataRing.h:114:18: warning: comparison of constant ‘2’ with boolean expression is always false [-Wbool-compare]
  else if (whence == rSEEK_END) rCurr = rTail;
                  ^
In file included from WonderRing.cpp:43:
WRpairs.h: In function ‘int YourBasicPairsArray()’:
WRpairs.h:155:45: warning: operation on ‘i4’ may be undefined [-Wsequence-point]
       parray[i3].pair[i4] = parray[i3].pair[++i4];
                                             ^~~~
In file included from WonderRing.cpp:43:
WRpairs.h: In function ‘int BuildPairsArray()’:
WRpairs.h:239:60: error: lvalue required as left operand of assignment
  if (!((void*)gWkArray = malloc((gRingSize+1)*sizeof(rType)))) { // allocate extra element
                                                            ^
WRpairs.h:243:62: error: lvalue required as left operand of assignment
  if (!((void*)gBestArray = malloc((gRingSize+1)*sizeof(rType)))) {
                                                              ^
WonderRing.cpp: In function ‘void Initialize(int, char**)’:
WonderRing.cpp:116:16: error: ‘getopt’ was not declared in this scope
  while ((opt = getopt( argc, argv, "haoq")) != -1) {
                ^~~~~~
WonderRing.cpp:116:16: note: suggested alternative: ‘getpt’
  while ((opt = getopt( argc, argv, "haoq")) != -1) {
                ^~~~~~
                getpt
WonderRing.cpp:137:6: error: ‘optind’ was not declared in this scope
  if (optind < argc) {
      ^~~~~~
WonderRing.cpp:137:6: note: suggested alternative: ‘options’
  if (optind < argc) {
      ^~~~~~
      options
WonderRing.cpp:157:6: error: ‘optind’ was not declared in this scope
  if (optind < argc) {
      ^~~~~~
WonderRing.cpp:157:6: note: suggested alternative: ‘options’
  if (optind < argc) {
      ^~~~~~
      options
WonderRing.cpp: In function ‘void Terminate()’:
WonderRing.cpp:178:2: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  if (!ring0.rClockwise) printf("Counter-"); printf("Clockwise");
  ^~
WonderRing.cpp:178:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  if (!ring0.rClockwise) printf("Counter-"); printf("Clockwise");
                                             ^~~~~~
make: *** [makefile:2: SquareRing] Error 1

dogpatch · 05-10-2021, 06:13 PM

Quote:

Originally Posted by mimorek

I tried compiling your program dogpatch, but ran into errors which I don't understand.

Code:

                                                      ^
DataRing.h: In member function ‘int Ring::rSeek(int, bool)’:
DataRing.h:114:18: warning: comparison of constant ‘2’ with boolean expression is always false [-Wbool-compare]
  else if (whence == rSEEK_END) rCurr = rTail;

Nor do i understand, with the exception of the newbie mistake of testing a bool variable for equation to '2'. That has now been corrected, but will not upload anything new, since the function Ring::rSeek() is never used by the SquareRing program, anyway.

As for the remaining errors and warnings, my old gcc compiles everything just fine, and the resulting code seems to work fine. I suppose this is yet another example of changes to compiler requirements that i cannot test for with my old gcc compiler and libraries.

Has malloc() changed its parameter requirements? I honestly don't know what your compiler is complaining about, nor how i could correct it and still have it work for my old gcc.

As for the many warnings, what's the deal with 'misleading indentation'? That sounds like a Cobol norm, not C. And the ++i4 operation is now cautioned against? Yikes!

(sigh) Well, thanks for pointing these things out to me, but i don't honestly know what i can do to correct things. Has anyone else downloaded my code? Do you get the same kinds of compiler errors and warnings?

Now that we've proven that i can share files with you using my own website, perhaps i could upload my compiled binary? Compiled on a 32 bit Pentium, but maybe it would run ok on any Linux computer?

GazL · 05-10-2021, 06:28 PM

Quote:

Originally Posted by mimorek

No, I get different results:

Code:

circleofsquares_v03.py 40 | uniqueCycles.py | grep -i "input\|unique"
Paths in input:  1180
Unique cycles: 1116

Have you fixed the wraparound yet? You v02 didn't check that the first num + last num also makes a square. That might explain where the extra results your getting are coming from.

GazL · 05-10-2021, 06:33 PM

Quote:

Workaround LQ's new upload security restrictions

BTW, did I miss something? What new restrictions?

mimorek · 05-10-2021, 08:12 PM

Quote:

Originally Posted by GazL

Have you fixed the wraparound yet?

What are you talking about???

Quote:

Originally Posted by GazL

You v02 didn't check that the first num + last num also makes a square. That might explain where the extra results your getting are coming from.

Hahaha
You are right!

Thanks for pointing that out.

mimorek · 05-10-2021, 08:44 PM

Fixed the wraparound. Now it finds actual circles.

Code:

$ time ./circleofsquares_v04.py 40 | ./uniqueCycles.py
 1  3  6 19 30 34  2  7 18 31 33 16  9 40 24 25 39 10 15 21 28 36 13 23 26 38 11  5 20 29 35 14 22 27 37 12  4 32 17  8 
...
...
 1 24 40  9 27 37 12 13 36 28  8 17 32  4 21 15 34 30 19  6 10 39 25 11 38 26 23  2 14 22  3 33 16 20  5 31 18  7 29 35 
Paths in input:  128
Unique cycles: 64

real    2m4.918s
user    2m4.766s
sys     0m0.009s

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

Quote:

Originally Posted by GazL

BTW, did I miss something? What new restrictions?

When i tried to upload my code as an LQ attachment, i got a new little window of some kind of Captcha mechanism to prove i was human. But it never gave me any photos or funky text to look at. I suppose my browsers are too old.

Anyway, am now putting my uploads onto my own very simple and 'insecure' site, and just inserting the hyperlink here in my post. I think you may have to right-click on the hyperlink to download the file.

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

Here's my version 1.31, with some fixes per Mimorek's compiler messages. This is a complete upload; you don't need previous version.

WonderRing_1.31.patch.txt

Some notes:
1. Fixed my dumb boof where i was declaring a bool variable which could contain values other than 0 or 1. But this was not impacting the SquareRing program, anyway.
2. The malloc error may be because i was using the negate '!' rather than specifically comparing against NULL, so corrected that.
3. The getopt and optind errors may be from not including the unistd.h header which my old compiler doesn't need, so now including that.
4. Made the ++ incrementation less ambiguous, though i still don't see why that was a problem.
5. Didn't do anything about the 'misleading indentation' complaint. Screw it, this ain't Cobol. It was just a warning message, so ignore it.
6. All this is done blindly, without testing, especially 2 & 3 above, which didn't alter my binary program at all. Anyway, try this, it might work

, remembering to ignore warning messages, especially about 'misleading indentation'.

mimorek · 05-10-2021, 09:43 PM

I've got it to compile with a few adjustments dogpatch.
I don't understand all of them nor if they are correct, but the program runs.

Quote:

Originally Posted by dogpatch

As for the remaining errors and warnings, my old gcc compiles everything just fine, and the resulting code seems to work fine. I suppose this is yet another example of changes to compiler requirements that i cannot test for with my old gcc compiler and libraries.

The adjustments I have made:

Code:

In WonderRing.cpp add:
#include <unistd.h>

WRpairs.h line 239:
  if (!((void*)gWkArray = malloc((gRingSize+1)*sizeof(rType))))
changed to:
  if (!(gWkArray = (rType*) malloc((gRingSize+1)*sizeof(rType))))

WRpairs.h line 243
  if (!((void*)gBestArray = malloc((gRingSize+1)*sizeof(rType))))
changed to:
  if (!(gBestArray = (rType*) malloc((gRingSize+1)*sizeof(rType))))

DataRing.h line 39
  if (!((void*)rElement = malloc(AllocSz*sizeof(rType))))
changed to:
  if (!(rElement = (rType*) malloc(AllocSz*sizeof(rType))))

Quote:

Originally Posted by dogpatch

Has malloc() changed its parameter requirements? I honestly don't know what your compiler is complaining about, nor how i could correct it and still have it work for my old gcc.

I don't understand much of it. Some information here.

Quote:

"In C++, we must explicitly typecast return value of malloc to (int *)."

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

Quote:

Originally Posted by GazL

In the new version (which I haven't posted yet), I pick a seed value, and use that to find all possible permutations of before/seed/after, while ensuring the same candidate pair(before/after) is not used again in reverse. As candidate pairs only appear in one orientation, you now avoid mirrored results.

Each of the above permutations is then passed to the solver as a separate job, splitting the problem space.

Example run for 32 number circle, using seed 1.

Code:

$ ./circle -va
Calculating sequence(s), please wait...

Candidates Table:
1: 24 15 8 3
2: 23 14 7
3: 22 13 6 1
4: 32 21 12 5
5: 31 20 11 4
6: 30 19 10 3
7: 29 18 9 2
8: 28 17 1
9: 27 16 7
10: 26 15 6
11: 25 14 5
12: 24 13 4
13: 23 12 3
14: 22 11 2
15: 21 10 1
16: 20 9
17: 32 19 8
18: 31 7
19: 30 17 6
20: 29 16 5
21: 28 15 4
22: 27 14 3
23: 26 13 2
24: 25 12 1
25: 24 11
26: 23 10
27: 22 9
28: 21 8
29: 20 7
30: 19 6
31: 18 5
32: 17 4
Using Seed value: 1
Jobs to submit to solver (seeded result buffers):
24 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
24 1 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
24 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 1 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Result(s):
15 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10

1 results returned.

You'll see that there are 6 separate jobs (pre-seeded buffers) queued to be solved, which it currently processes sequentially.

What got me excited about this approach is that it shouldn't be hard to make it use multiple solver threads and process them in parallel. I've already done much of the prep work for that, I just need to read up a little on pthreads for the final bit of the puzzle.

The longer the circle, the more possible permutations,the more jobs the problem space will be split into. So, it looks like it will scale pretty well.

So, that's where I am right now.

Excellent!. The idea of pre-seeded buffers is much simpler than my approach, and so probably more effective. As for pthreads and processing in parallel, that may be beyond my skill level. Am definitiely interested, but am up against some local issues here that may not leave me with much computer time for awhile. Maybe something to work on rainy days, which season is almost upon us.

Quote:

Originally Posted by igadoter

what @GazL posted is very advanced level of programming. .

No kidding.