[SOLVED] 'Circle of Squares' programming challenge

shruggy · 04-29-2021, 01:53 AM

Quote:

Originally Posted by igadoter

How do I split the file into separate files?

Code:

csplit WonderRing.1.2.txt /Start/ '{*}'

igadoter · 04-29-2021, 04:12 AM

I knew there must be solution. It would be a shame to have to by hand cut the file into pieces. With LibreOffice.

GazL · 04-29-2021, 05:23 AM

Just a hint on sharing multi-file code in one file.

Assuming your source is in a subdir called 'myproject' in the current directory, you can use a unified diff against /var/empty to pack it up into one patch file.
e.g.
diff -Nur --strip-trailing-cr /var/empty/ myproject/ > project.patch.txt

Which could then be unpacked into the current directory with
patch -p1 < project.patch.txt

To make it slightly easier for your recipients to unpack (patch has some weird rules about choosing target files), one can replace /var/empty in the patch file with the target directory.

I wrote a bash function to make life easier:

Code:

diff_bundle()
{
  local olddir=/var/empty
  local newdir=${1:-.}

  diff -Nur --strip-trailing-cr "$olddir" "$newdir" \
    | sed "/^--- / s:$olddir:${newdir%/}:"
}

Bundles up current directory by default, with diff to stdout.

I wasn't aware of csplit. I'll have to investigate that.

igadoter · 04-29-2021, 08:21 PM

Ok hold fast - I posted about amazing circle from 101 numbers. And what about amazing circle from - wait - 24348 numbers? I compiled circle.c - played a little - is fast as light

Code:

$ time ./a.out 24348 43 > /dev/null

real	0m39.165s
user	0m39.121s
sys	0m0.022s

I tested output for amazing circle from 10456 numbers

Code:

$ ./a.out 10456 11

- looks ok. Can't build @dogpatch programm. I got compilation errors about missing #include <cstring> and some other errors.

pan64 · 04-30-2021, 12:28 AM

Quote:

Originally Posted by igadoter

Ok hold fast - I posted about amazing circle from 101 numbers. And what about amazing circle from - wait - 24348 numbers? I compiled circle.c - played a little - is fast as light

Code:

$ time ./a.out 24348 43 > /dev/null

real	0m39.165s
user	0m39.121s
sys	0m0.022s

I tested output for amazing circle from 10456 numbers

Code:

$ ./a.out 10456 11

- looks ok.

The problem is not really to find the first solution, because it is relatively easy [and fast]. But to find all the different circles.

It looks like we always have a solution if the number [of numbers] is big enough. And what is the smallest circle?

dogpatch · 04-30-2021, 10:57 AM

Quote:

Originally Posted by shruggy

Code:

csplit WonderRing.1.2.txt /Start/ '{*}'

Thank you, shruggy! The best part of this solution is that it seems to be part of basic Linux, even in my old system, without downloading a nifty utility, and without writing a clever bash script.

I will remember this next time I upload multiple files, and will use something other than 'Start' in the separator lines. Fortunately in this case, none of my code nor comments used the word 'Start' with upper case 'S'.

dogpatch · 04-30-2021, 10:58 AM

Quote:

Originally Posted by pan64

And what is the smallest circle?

32 is the smallest valid ring of data for square numbers. Other data rings, such as for prime numbers or triangular numbers are quite different (of course).

dogpatch · 04-30-2021, 11:12 AM

Quote:

Originally Posted by igadoter

Can't build @dogpatch programm. I got compilation errors about missing #include <cstring> and some other errors.

Yes, as noted above, you may have to add (or remove?) some header files. My GCC compiler is very old, and the header file requirements have changed since then.

Try removing

Code:

#include malloc.h

from DataRing.h, and add

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

to WonderRing.cpp.

Maybe replace <string> with <string.h>??

These are guesses; impossible for me to test with my old system. Sorry.

shruggy · 04-30-2021, 11:13 AM

Quote:

Originally Posted by dogpatch

Fortunately in this case, none of my code nor comments used the word 'Start' with upper case 'S'.

Well, the part between slashes is a regular expression, so '/\* Start /' would also do, but was unnecessary in this case. Actually, more correct splitting would be achieved with

Code:

csplit WonderRing.1.2.txt %Start% /Start/ {\*}

as this would exclude the first part.

And yes, as igadoter said above doing this with awk is fun and gives you more control:

Code:

#!/usr/bin/awk -f
/\* Start /{f=$3; next}
/\* End /{f=0; next}
f{print >f}

or in one line

Code:

awk '/\* End /{f=0}f{print>f}/\* Start /{f=$3}' WonderRing.1.2.txt

GazL · 05-01-2021, 05:33 AM

I spent a little time yesterday evening reworking my circle program.
As part of that I added a routine to try and guess a good seed value based on finding a seed with the lowest number of neighbour candidates. I wondered whether it would speed it up, but the results weren't what I expected, so I started to investigate (really should have done that before writing the code

).

These are the cpu times for a circle of 50, for each seed.

Code:

Seed 1::::::::::::::::::::::::::::::
user 3.12
Seed 2::::::::::::::::::::::::::::::
user 0.00
Seed 3::::::::::::::::::::::::::::::
user 0.00
Seed 4::::::::::::::::::::::::::::::
user 0.02
Seed 5::::::::::::::::::::::::::::::
user 0.00
Seed 6::::::::::::::::::::::::::::::
user 0.15
Seed 7::::::::::::::::::::::::::::::
user 0.03
Seed 8::::::::::::::::::::::::::::::
user 0.01
Seed 9::::::::::::::::::::::::::::::
user 0.14
Seed 10::::::::::::::::::::::::::::::
user 0.61
Seed 11::::::::::::::::::::::::::::::
user 0.74
Seed 12::::::::::::::::::::::::::::::
user 1.76
Seed 13::::::::::::::::::::::::::::::
user 2.56
Seed 14::::::::::::::::::::::::::::::
user 6.35
Seed 15::::::::::::::::::::::::::::::
user 0.23
Seed 16::::::::::::::::::::::::::::::
user 4.83
Seed 17::::::::::::::::::::::::::::::
user 0.16
Seed 18::::::::::::::::::::::::::::::
user 0.00
Seed 19::::::::::::::::::::::::::::::
user 0.00
Seed 20::::::::::::::::::::::::::::::
user 0.00
Seed 21::::::::::::::::::::::::::::::
user 0.00
Seed 22::::::::::::::::::::::::::::::
user 0.02
Seed 23::::::::::::::::::::::::::::::
user 0.01
Seed 24::::::::::::::::::::::::::::::
user 0.11
Seed 25::::::::::::::::::::::::::::::
user 0.41
Seed 26::::::::::::::::::::::::::::::
user 0.93
Seed 27::::::::::::::::::::::::::::::
user 0.01
Seed 28::::::::::::::::::::::::::::::
user 0.02
Seed 29::::::::::::::::::::::::::::::
user 0.06
Seed 30::::::::::::::::::::::::::::::
user 0.16
Seed 31::::::::::::::::::::::::::::::
user 43.35
Seed 32::::::::::::::::::::::::::::::
user 97.73
Seed 33::::::::::::::::::::::::::::::
user 1.23
Seed 34::::::::::::::::::::::::::::::
user 0.07
Seed 35::::::::::::::::::::::::::::::
user 0.11
Seed 36::::::::::::::::::::::::::::::
user 0.02
Seed 37::::::::::::::::::::::::::::::
user 0.01
Seed 38::::::::::::::::::::::::::::::
user 1.41
Seed 39::::::::::::::::::::::::::::::
user 0.75
Seed 40::::::::::::::::::::::::::::::
user 0.33
Seed 41::::::::::::::::::::::::::::::
user 0.06
Seed 42::::::::::::::::::::::::::::::
user 0.05
Seed 43::::::::::::::::::::::::::::::
user 0.00
Seed 44::::::::::::::::::::::::::::::
user 0.00
Seed 45::::::::::::::::::::::::::::::
user 0.00
Seed 46::::::::::::::::::::::::::::::
user 0.00
Seed 47::::::::::::::::::::::::::::::
user 0.00
Seed 48::::::::::::::::::::::::::::::
user 10.20
Seed 49::::::::::::::::::::::::::::::
user 0.34
Seed 50::::::::::::::::::::::::::::::
user 28.93

Seeds 31, 32, 48 and 50 stand out, with 32 being the worst of all, while seeds 2 and 5 are so fast they don't even register cpu-time.
So, lets look at their possible neighbours:

Code:

2: 47 34 23 14 7
5: 44 31 20 11 4
31: 50 33 18 5
32: 49 17 4
48: 33 16 1
50: 31 14

My seed guessing code would pick 50 in this case as it only has two candidates, but apparently, less neighbours doesn't necessarily mean a faster result. Back to the drawing board.

I wonder what makes 32 so bad, and 2 and 5 so good.

Changes in this version:

Refactored, and split into modules.
Uses a bucket structure to hold neighbour candidates rather than the link list of pairs plus an index. (Doesn't have much effect on runtime as it's essentially the same in operation, but code is tidier).
seed is now specified with an option: -s
Includes suggest_seed() function: which it turns out doesn't help any, but if we can come up with a scheme that does work, there's a function to slap it in.

To disable the useless seed guessing code I added, set DEFAULT_SEED_VALUE in circle.c to 1 rather than 0.

New reworked version of circle is attached in diff format for anyone that wants it. Unpack with
patch -p0 < circle-3.1.diff.txt

pan64 · 05-01-2021, 05:39 AM

Quote:

Originally Posted by GazL

Seeds 31, 32, 48 and 50 stand out, with 32 being the worst of all, while seeds 2 and 5 are so fast they don't even register cpu-time.
So, lets look at their possible neighbours:

Code:

2: 47 34 23 14 7
5: 44 31 20 11 4
31: 50 33 18 5
32: 49 17 4
48: 33 16 1
50: 31 14

My seed guessing code would pick 50 in this case as it only has two candidates, but apparently, less neighbours doesn't necessarily mean a faster result. Back to the drawing board.

I wonder what makes 32 so bad, and 2 and 5 so good.

Good work!
I guess we need to take into account [not only the first but] the second and/or third neighbours too.

dogpatch · 05-01-2021, 08:56 AM

Quote:

Originally Posted by GazL

I added a routine to try and guess a good seed value. . .

This looks very much like what i tried to do a few days ago. May you have better success! I tried various algorithms, some similar to yours, but failed to find a way to predict the optimal seed for any given ring size. So i finally concluded that the best algorithm was to simply try to generate the first ring for every ring size, and dump the results. Anyway, here is my list of pairs, optimized as best as i can, for ring size 50, which seems to be the size you are concentrating on:

Code:

order change for '1': '15'<->'8'
order change for '31': '33'<->'18'
order change for '46': '35'<->'18'
186 pairs generated
 1: 48 35 24 8 15 3
 2: 47 34 23 14 7
 3: 46 33 22 13 6 1
 4: 45 32 21 12 5
 5: 44 31 20 11 4
 6: 43 30 19 10 3
 7: 42 29 18 9 2
 8: 41 28 17 1
 9: 40 27 16 7
10: 39 26 15 6
11: 38 25 14 5
12: 37 24 13 4
13: 36 23 12 3
14: 50 35 22 11 2
15: 49 34 21 10 1
16: 48 33 20 9
17: 47 32 19 8
18: 46 31 7
19: 45 30 17 6
20: 44 29 16 5
21: 43 28 15 4
22: 42 27 14 3
23: 41 26 13 2
24: 40 25 12 1
25: 39 24 11
26: 38 23 10
27: 37 22 9
28: 36 21 8
29: 35 20 7
30: 34 19 6
31: 50 18 33 5
32: 49 17 4
33: 48 31 16 3
34: 47 30 15 2
35: 46 29 14 1
36: 45 28 13
37: 44 27 12
38: 43 26 11
39: 42 25 10
40: 41 24 9
41: 40 23 8
42: 39 22 7
43: 38 21 6
44: 37 20 5
45: 36 19 4
46: 18 35 3
47: 34 17 2
48: 33 16 1
49: 32 15
50: 31 14

... and the result of my brute force speed test for ring size 50:

Code:

050 000000Begin
050 0000217 002
050 0000233 047
050 0000480 014
050 0001046 050
050 0002447 019
050 0003431 018
050 0006920 045
050 0033371 021
050 0051589 020
050 0084151 003
050 0084155 043
050 0096164 005
050 0166748 044
050 0458607 027
050 0479123 046
050 0480074 037
050 0815690 008
050 0820156 023
050 1008194 022
050 1210275 028
050 1222623 004
050 1259218 036
050 1367831 007
050 2530394 042
050 2739107 041
050 3229208 029
050 999999*End*

The first column is the ring size, the second column is the number of recursions to generate the first ring, and the third column the seed number. So, seed 2 is the fastest, then 47, 14, etc. I set an arbitrary limit of 3400000 recursions, beyond which the speed test abandoned that seed and tried the next. If you can find an algorithm which will connect the spped test results to the array of pairs, an algorithm that works for every ring size, and thus predict the optimal seed(s) without doing a similar brute force run, i'll buy you a beer. See post #61 above for more details, and download WonderRing.1.1.txt from post #60 to get, among other things, SRopt.array, the condensed single-column array of best seeds for ring sizes 43 through 130. If you're interested, and if i have coinnection minutes later, i may try to assemble and upload the uncondensed 3-column array for ring sizes 43 through 130, which, like the above, includes the recursion value, the reliable indicator of relative speed to generate the first ring for a given ring size.

dogpatch · 05-01-2021, 09:15 AM

This whole exercise reminds me of my work of a couple years ago to make my sudoku analyzer run more efficiently. It's very easy and fast to generate the first possible solution for a sudoku grids with none or very few solved cells, and for one that has many solved cells. The tough sudoku to analyze is one with between about 15 to 20 cells solved. In these cases, it makes a huge difference which unsolved cell you start with, and the order in which you work from cell to cell. Working out an acceptable way to get a decent response time took me several weeks and resulted in some fairly complex code. Turns out, i had to try my best algorithm, then, if it failed within a prescribed number of processing loops, try the second algorithm, then a third...

GazL · 05-01-2021, 10:53 AM

Yeah, I think finding a formula for this is going to be beyond my abilities, so I guess I'll be staying thirsty.

I tried some of the obvious approaches and non of them really worked out. I don't really see the point in using an array of pre-determined seed values as one may as well have a array of full results rather than calculate them if you do that. So, to be honest, I think I'm dead-ended at this point.

astrogeek · 05-01-2021, 02:49 PM

Interesting discussion!

I too have been working on this problem but with no result worth posting so far...

At some point I too, realized that trying to pick a "best" starting point based on possible pairings was not going to be always successful (though starting at the highest end, fewer pairs end of the range is weighted in your favor most often I think).

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.