[SOLVED] 'Circle of Squares' programming challenge

dogpatch · 04-15-2021, 10:29 PM

@igadoter: (re. your signature and dislike of rep points)
I'll buy you a beer for your 'amazing circle' thread that started this whole thing.

Gotta come to Jinotega, Nicaragua to claim your reward.

igadoter · 04-16-2021, 01:49 AM

Great thanks, you made my day, sun is shining more brightly

.

GazL · 04-16-2021, 04:15 AM

Quote:

Originally Posted by dogpatch

@igadoter: (re. your signature and dislike of rep points)
I'll buy you a beer for your 'amazing circle' thread that started this whole thing.

Gotta come to Jinotega, Nicaragua to claim your reward.

Agreed, thanks for bringing this to our attention. Was just as interesting as the "Armstrong numbers" thread we had a while back.

dogpatch · 04-16-2021, 08:36 AM

Quote:

Originally Posted by GazL

. . . Was just as interesting as the "Armstrong numbers" thread we had a while back.

. . . or the 2019 New year puzzle thread.

@GazL: Is this the Armstrong numbers thread to which you referred?. That was resurrected after 11 years? And is now 4 years older? I missed it the first two times, but may take a look at it sometime myself. Thanks for the tip.

GazL · 04-16-2021, 09:26 AM

Yep, that's the one.

pan64 · 04-17-2021, 09:50 AM

I downloaded the code from post #42. Is this the last one?
This is the top of the profile (for 56):

Code:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 34.35    337.33   337.33                             find_next (a.c:240 @ 1979)
 10.79    443.35   106.02                             find_next (a.c:236 @ 1a3b)
 10.66    548.04   104.69                             find_next (a.c:242 @ 199c)
  8.09    627.54    79.50                             find_next (a.c:250 @ 1a10)
  6.04    686.88    59.33                             find_next (a.c:253 @ 1a2f)
  6.00    745.80    58.92                             find_next (a.c:238 @ 196f)
  5.03    795.18    49.38                             find_next (a.c:243 @ 19b6)
  3.65    831.03    35.85                             find_next (a.c:255 @ 1a51)
  3.23    862.74    31.70                             find_next (a.c:249 @ 19f5)
  3.05    892.69    29.95                             find_next (a.c:234 @ 194a)
  2.76    919.76    27.07 243738122   111.05   111.05  find_next (a.c:217 @ 188e)
...

What does it mean? the statement "state->seen_values[candidate - 1]" is the most expensive part of this code (line 240, 243, 250).

GazL · 04-17-2021, 10:46 AM

It should be the latest. To confirm, If you have the one tagged "version 2.5" on line 1, then it's the latest.

The statement you highlight replaced a for loop that did a sequential search of an array in earlier versions, It's now a single memory access using a pointer and offset so I don't know how one could make it any faster. If you have a faster way of keeping track of what values have been used I'm all ears.

BTW, what profiling tool are you using?

floppy_stuttgart · 04-17-2021, 11:23 AM

a bit mathematic does it ? https://math.stackexchange.com/quest...-of-two-number

pan64 · 04-17-2021, 11:43 AM

that is the default gcc/gprof toolset.
That line is not a single memory access, or at least quite difficult to calculate that address.

Code:

    int *ip = state->seen_values;
    int *rd = &(state->result[depth]);

    while( p && (p->value == value) )
    {
        int candidate = p->adjacent ;

        if ( ! ip[candidate - 1] )
        {
            *rd = candidate ;
            ip[candidate - 1] = candidate ;

            if ( find_next(depth + 1, candidate, state) )
            {
                return 1 ;
            } else {
                *rd = 0 ;
                ip[candidate - 1] = 0;
            }
        }
        p = p->next ;
    }
    return 0;

it looks (for me) using this ip and rd will speed up the execution (more than 10%)

GazL · 04-17-2021, 12:22 PM

I would have expected the optimizer to have dealt with some of that, but perhaps I was giving gcc too much credit. Thanks, I'll look into it.

igadoter · 04-17-2021, 01:35 PM

Miracle happens. As it was time consuming to count amazing circle for 56 and higher number it is relatively fast

Code:

% gcc amazing_circle_v2.1.c
% time a.out 59
1, 3, 6, 10, 15, 21, 4, 5, 11, 14, 50, 31, 18, 7, 2, 23, 58, 42, 39, 25, 56, 8, 17, 32, 49, 51, 13, 36, 28, 53, 47, 34, 30, 19, 45, 55, 26, 38, 43, 57, 24, 12, 37, 44, 20, 29, 52, 48, 33, 16, 9, 40, 41, 59, 22, 27, 54, 46, 35.

real	0m47.545s
user	0m47.543s
sys	0m0.000s

now

Code:

% time a.out 65 1 

real - didn't wait to finish 

% time a.out 65 2
 2, 7, 9, 16, 20, 5, 4, 12, 13, 3, 1, 8, 17, 32, 49, 51, 30, 6, 10, 15, 21, 28, 36, 64, 57, 43, 38, 26, 55, 45, 19, 62, 59, 41, 23, 58, 63, 18, 46, 54, 27, 37, 44, 56, 65, 35, 29, 52, 48, 33, 31, 50, 14, 22, 42, 39, 61, 60, 40, 24, 25, 11, 53, 47, 34.

real	0m37.535s
user	0m37.528s
sys	0m0.001s

so it is not as difficult to find sequence but starting point seems to be important. It is not difficult cause must be a lot of such sequences - deterministic algorithm is just pure lack. If there are many such sequences there is great chance to find one.

Edit: My small addition to is_square test

Code:

// is_square logical table 
char *p;
p = (char *) malloc((MAXSIZE*MAXSIZE+1)*sizeof(char));

for (int i = 1; i < MAXSIZE + 1; i++)
	    *(p+i*i) = 'A';

it test all squares up to MAXSIZE*MAXSIZE. For n test is satisfied if *(p+n) == 'A', fails if
*(p+n) == '\0'. The last this dependency from starting point gives me following idea

Code:

% a.out N $(($RANDOM % N))

say with N = 76 the third run gave almost immediate answer. So put time limit execution up to 1 minut and execute that command.

pan64 · 04-17-2021, 01:49 PM

Quote:

Originally Posted by igadoter

Miracle happens.
...
so it is not as difficult to find sequence but starting point seems to be important. It is not difficult cause must be a lot of such sequences - deterministic algorithm is just pure lack. If there are many such sequences there is great chance to find one.

I was thinking about an algorithm to find out the "best" starting point.
Right now I think we can calculate the number of pairs for every number in the circle and I think we need to find the one with the lowest number of pairs (and probably we can go further to find the number of second/third/... neighbors). But probably this is not really useful.

igadoter · 04-17-2021, 04:28 PM

With randomization and timeout 60 seconds it took me 6 min to find sequence of 97 numbers (1 .. 97). But it seems some numbers are more lucky. Timeout 60 sec means that program found sequence in period of time shorter than 60 sec.

igadoter · 04-18-2021, 04:04 AM

I think that improvement will be if program would accept starting sequence - you can think about first number as 0-level randomization Providing longer starting sequence is higher randomization. Just pick starting sequence randomly.

Code:

% amazing_circle 127 1 3 13 23

Edit: I ma^T uploading amazing circles for 97, 98, 99 - they can be computed relatively fast - below 6 min.

dogpatch · 04-23-2021, 01:15 PM

Here at last is something to upload; have included the latest DataRing.h.txt include file as a separate upload, as more general use code. The other WonderRing.cpp.txt contains several pieces specific to this Ring of Squares challenge, as noted within the txt file. You may have to change some include file specs; my gcc compiler is pretty old.

DataRing.h.txt
WonderRing.cpp.txt

A few notes on what i've been doing off-line. Forgive me if i'm treating of things that you folks have long since conquered.

1. From the beginning, i've treated the sequences as rings, with indeterminate start, end, and flow direction. In fact, rings of data strike me as a concept with practical applications elsewhere. Probably it's already been done, and probably better than my amateurish C++ code. See DataRing.h.txt and comments.

2. Rather than code functions to calculate squares and square roots, i always simply used a static array of squares. It then occurred to me that this array could be any series of target numbers, say Fibonacci or Armstrong. To try this idea, i made an array of prime numbers and was able to easily generate rings of primes with pretty much the same code. (Caveat: you can't generate a ring of primes with an odd number of elements. Think about it.) The output of rings of primes was very fast but grew in number VERY quickly when the -a (all_rings) option was employed. For example, the command

Code:

PrimeRing 16 -a

displays 81024 valid rings of 16 elements, while recursing through RecursFind() for only 1016063 cycles (depending upon the starting, or seed number - see below).

3. With rings of data, it was a simple matter to include an option (-o) to order the elements of the rings before dumping to the screen. This did not involve any sorting or rearranging of the elements; simply alter the head, tail, and flow direction to give the desired order. This, along with the -a option, allowed the program to identify and discard any mirror (duplicate) rings. So, for example

Code:

 SquareRing 34 6 -a

yields

Code:

22 valid rings generated
670991 cycles of RecursFind()

while

Code:

SquareRing 34 6 -ao

gives

Code:

11 valid rings generated and ordered
670991 cycles of RecursFind()

Note that no processing time is saved, since all rings are still generated, just that not all are accepted and displayed.

4. Speaking of processing time, most of my computer time since my last LQ visit was spent trying to get my program to run more efficiently and faster. That deserves a separate post, below.

Caveat: Am still getting an occasional floating point error; haven't yet tracked it down.