LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-07-2021, 06:49 PM   #1
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
'Circle of Squares' programming challenge


In his Amazing Circle thread, igadoter presented us with a circle of data consisting of the numbers 1 thru 32. The amazing part was that each adjacent pair of numbers when summed yielded a perfect square. He asked for a programmatic way to verify that the conditions were met for the particular sequence of 32 numbers that he supplied, which program was offered by danielbmartin. Others, including myself, have wondered about the possibility of programmatically generating such an amazing circle of numbers, so I hereby issue the programming challenge. Here are the rules:

1. The data must be a logical circle or ring of data, in which there is no defined first and last element, and no defined direction or flow (can be clockwise or counter-clockwise);

2. Each element in the ring must be within the defined limits. In this case, between 1 and 32, with each number occurring exactly once (in any order).

3. Each adjacent pair of numbers must sum to a perfect square. [1, 4, 9, etc] 'Adjacent pair' is defined per rule #1 above. That is, if you define the ring as a linear array, the array must 'wrap around' so that the first and last elements are considered logically adjacent.

Let's have a little fun with this, and, as others have suggested, maybe carry it further than limits of 1 to 32.

Last edited by dogpatch; 04-07-2021 at 06:51 PM. Reason: last note
 
Old 04-07-2021, 07:14 PM   #2
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
To start things off, I offer the following data ring class definition, FWIW. This has probably been done before and better, but it's where I'm beginning, as a C++ header, to help me to define and work with a specific ring of data.
Code:
/** Ring class: define Ring (circular array) data type */
typedef char rType;
class Ring {
public:
 int rSize;
 int rHead;			// arbitrary start point in ring
 bool rClockwise;		// true=Clockwise, false=Counter-clockwise
 rType *rElement;		// store ring as linear array

bool rInit(int AllocSz) {	// Alloc ring dynamically
 if (!((void*)rElement = malloc(AllocSz*sizeof(rType))))
  return false;
 rSize = AllocSz;
 srand(time(0));
 Randomize();
 return true;
 };

void Randomize() {
 rHead = rand()%rSize;		// randomize rHead offset
 rClockwise = rand()%2;		// and direction of flow
 return;
 };

int AdvanceIndex(int Index) {
// Step index clockwise or counter, wrapping as needed
 if (rClockwise) {		// clockwise (normal order)
  Index++;
  if (Index == rSize)
   Index = 0;			// wrap to 0 in linear array
  }
 else {				// counter-clockwise (descending order)
  if (!Index)
   Index = rSize;		// wrap to end of linear array
  Index--;
  }
 return (Index);
 }
};
 
2 members found this post helpful.
Old 04-08-2021, 01:10 AM   #3
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,488

Rep: Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530
I would define a check like function which will return true if the sum of the given adjacent pair of numbers is square. But we can have different conditions, later....
Code:
Ring r;
....
bool check(int ix) {
   int s = r[ix] + r[ix+1];
   float f = sqrt((double)s);
   int i = f;
   return i == f;
}
https://www.includehelp.com/c-progra...re-or-not.aspx
 
2 members found this post helpful.
Old 04-08-2021, 06:56 AM   #4
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,921

Rep: Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896
Code:
$ !cc
cc -Wall -Wextra -O2 amazing.c
$ ./a.out 
92 possible pairs that sum to a square:
  1, 3
  1, 8
  1, 15
  1, 24
  2, 7
  2, 14
  2, 23
  3, 1
  3, 6
  3, 13
  3, 22
  4, 5
  4, 12
  4, 21
  4, 32
  5, 4
  5, 11
  5, 20
  5, 31
  6, 3
  6, 10
  6, 19
  6, 30
  7, 2
  7, 9
  7, 18
  7, 29
  8, 1
  8, 17
  8, 28
  9, 7
  9, 16
  9, 27
  10, 6
  10, 15
  10, 26
  11, 5
  11, 14
  11, 25
  12, 4
  12, 13
  12, 24
  13, 3
  13, 12
  13, 23
  14, 2
  14, 11
  14, 22
  15, 1
  15, 10
  15, 21
  16, 9
  16, 20
  17, 8
  17, 19
  17, 32
  18, 7
  18, 31
  19, 6
  19, 17
  19, 30
  20, 5
  20, 16
  20, 29
  21, 4
  21, 15
  21, 28
  22, 3
  22, 14
  22, 27
  23, 2
  23, 13
  23, 26
  24, 1
  24, 12
  24, 25
  25, 11
  25, 24
  26, 10
  26, 23
  27, 9
  27, 22
  28, 8
  28, 21
  29, 7
  29, 20
  30, 6
  30, 19
  31, 5
  31, 18
  32, 4
  32, 17
Sequence:
 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, 15
$
First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.

P.S. I left the result in an array. It would be trivial to create a linklist from it and then point the last entry back to the first to make it circular, but it seemed kind of pointless, and I was more interested in doing the sequence generation functions.

update:
attached program now takes start value as first arg .

Last edited by GazL; 04-15-2021 at 07:05 AM.
 
2 members found this post helpful.
Old 04-08-2021, 07:54 AM   #5
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Quote:
Originally Posted by GazL View Post
First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.
I created my list of pairs manually. Otherwise, this is precisely what i've been trying since early yesterday. But so far, it dead ends every time.

If i suspend randomness, it seems to make a big difference what digit i start with, which intuitively should not be. In at least two cases, i've gotten as far as a 31 byte array:
Code:
 
8 28 21 15 10 26 23 13 12 24 25 11 14 22 27 9 16 20 29 7 18 31 5 4 32 17 19 30 6 3 1
28 21 15 10 26 23 13 12 24 25 11 14 22 27 9 16 20 29 7 18 31 5 4 32 17 19 30 6 3 1 8
which, as you can see, does indeed wrap around to form a ring of squares, and is a different order than the original amazing circle. But there are only 31, not 32 digits. The missing digit is 2, which does not fit into any point in the 31 byte circle. There are a number of other circles of fewer than 32 digits; that doesn't meet the challenge.

I haven't yet figured out why i can't get the above sequence if i start with, say, '21' or some other digit. Perhaps my backtracking logic need some tweaking. Or perhaps a completely different approach. If you get a full 32 byte circle, I'd love to see your code.
 
1 members found this post helpful.
Old 04-08-2021, 11:13 AM   #6
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,921

Rep: Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896
Quote:
Originally Posted by dogpatch View Post
If you get a full 32 byte circle, I'd love to see your code.
Attached to post #4 (now updated to take a start arg).

Code:
$ cc -Wall -Wextra -O2 amazing_circle.c 
$ for i in {1..32}
> do 
>   ./a.out $i | tail -2 
> done
Sequence:
 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, 15
Sequence:
 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23
Sequence:
 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13
Sequence:
 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32
Sequence:
 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31
Sequence:
 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30
Sequence:
 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29
Sequence:
 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28
Sequence:
 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27
Sequence:
 10, 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
Sequence:
 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25
Sequence:
 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24
Sequence:
 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12
Sequence:
 14, 2, 23, 26, 10, 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
Sequence:
 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
Sequence:
 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20
Sequence:
 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, 15, 1, 8, 28, 21, 4, 32
Sequence:
 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31
Sequence:
 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30
Sequence:
 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29
Sequence:
 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, 15, 1, 8, 28
Sequence:
 22, 14, 2, 23, 26, 10, 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
Sequence:
 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26
Sequence:
 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25
Sequence:
 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24
Sequence:
 26, 10, 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
Sequence:
 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22
Sequence:
 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21
Sequence:
 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20
Sequence:
 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19
Sequence:
 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18
Sequence:
 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17
$
This may not be all possible sequences, my code just returns the first complete valid sequence it finds for each start point.

I'll look forward to seeing other approaches.
 
2 members found this post helpful.
Old 04-08-2021, 12:06 PM   #7
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,488

Rep: Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530
I did not check all of them, but they look identical (just the first number is different, but the order is the same).
 
Old 04-08-2021, 12:23 PM   #8
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
I have not yet had a chance to write any code, or even decide what I want to write! But I did write on paper a list of all the possible pairings which sum to perfect squares and thinking about what I see in that list leads to a set of constraints for generating a complete ordering, as well as placing limits on the number of integers in the ring (32 may represent a limit!).

I'll defer posting my own observations but offer the following helpful hints:

* There aren't really a great number of choices - the possible pairs are tightly constrained in "families" of number of choices
* Each choice, where there is a choice, further constrains the next choice
* Using the clues suggested by the above list, think in terms of segments (arcs) of one or more pairs, then join the segments

On paper I was able to find (generate) a 32 number solution quickly (or perhaps accidentally!)

Last edited by astrogeek; 04-08-2021 at 12:29 PM. Reason: arcs
 
1 members found this post helpful.
Old 04-08-2021, 12:41 PM   #9
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,921

Rep: Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896
Quote:
Originally Posted by pan64 View Post
I did not check all of them, but they look identical (just the first number is different, but the order is the same).
My routine is deterministic with no random element, so one should expect to see common sequences of varying length reoccurring when it is possible. It will only diverge when an already used number forces a different path. Look closer and you'll see this to be true.
 
Old 04-09-2021, 04:11 AM   #10
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
I have written a C routine which implements my thoughts on building the circle from segments (refined pencil and paper method). Instead of trying all possible combinations as Gazl has done, I successively pair everything that is fully deterministic and then test for any left overs.

The segments are doubly linked lists and the strategy is:

1. Connect all deterministic pairings into segments (those integers with only two possible pairing partners)
2. Connect all deterministic segment end pairs (segment ends with only one possible partner)
3. If the result is a ring then there is only one solution and its mirror, it is fully deterministic.

When run it produces the result below. The numbers in parenthesis are the sum of leading and trailing pairs. I set the circle entry to 4 only to orient the result with the original post's example, but it is a doubly linked ring of integers.

Code to follow after sleep!

Code:
./circle
4   (25, 36)
32  (36, 49)
17  (49, 36)
19  (36, 49)
30  (49, 36)
6   (36, 9)
3   (9, 16)
13  (16, 25)
12  (25, 36)
24  (36, 49)
25  (49, 36)
11  (36, 16)
5   (16, 36)
31  (36, 49)
18  (49, 25)
7   (25, 36)
29  (36, 49)
20  (49, 36)
16  (36, 25)
9   (25, 36)
27  (36, 49)
22  (49, 36)
14  (36, 16)
2   (16, 25)
23  (25, 49)
26  (49, 36)
10  (36, 25)
15  (25, 16)
1   (16, 9)
8   (9, 36)
28  (36, 49)
21  (49, 25)

Last edited by astrogeek; 04-09-2021 at 04:37 AM.
 
1 members found this post helpful.
Old 04-09-2021, 05:41 AM   #11
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,488

Rep: Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530Reputation: 5530
Quote:
Originally Posted by GazL View Post
My routine is deterministic with no random element, so one should expect to see common sequences of varying length reoccurring when it is possible. It will only diverge when an already used number forces a different path. Look closer and you'll see this to be true.
those are all identical:
http://paste.ubuntu.com/p/SPtYcSByZd/
 
Old 04-09-2021, 07:24 AM   #12
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,234
Blog Entries: 1

Rep: Reputation: Disabled
Quote:
Originally Posted by GazL View Post
First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.

P.S. I left the result in an array. It would be trivial to create a linklist from it and then point the last entry back to the first to make it circular, but it seemed kind of pointless, and I was more interested in doing the sequence generation functions.

update:
attached program now takes start value as first arg .
I disabled pairs printing. Just here what I got
Code:
% for i in `seq 7` ; do ./a.out $i >> sequences ; done 
% cat sequences 
Sequence:
 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, 15,
Sequence:
 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23,
Sequence:
 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13,
Sequence:
 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32,
Sequence:
 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31,
Sequence:
 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15, 1, 8, 28, 21, 4, 32, 17, 19, 30,
Sequence:
 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29,
Above 32 it doesn't work. So all sequences by your program are
Code:
% for i in `seq 32` ; do ./a.out $i ; done
so there are only up to 32 all of them? Program is deterministic.

edit: but they are essentially the same - it's circle - if sequences differ only by left/right shift.

edit: so the question is about two sequences being the same - say 1,2,3,1,2,3,1,...should be considered the same as 2,3,1,2,3,1,...

oh men look at this
Code:
1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3,
3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1,
they are mirrors! Read forward, read backward gives the same.

Last edited by igadoter; 04-09-2021 at 07:42 AM.
 
Old 04-09-2021, 07:42 AM   #13
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,921

Rep: Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896Reputation: 3896
not identical. there is reversal on some sequences. I never claimed it would find multiple sequences, only that it would generate a valid result given any start point.
 
Old 04-09-2021, 07:53 AM   #14
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,234
Blog Entries: 1

Rep: Reputation: Disabled
Look carefully. All these above sequences are in fact the same up to mirror. It is not difficult to create up to test that the above sequences are the same up to mirroring. The first starts with 1 reaches 2 - now read backward from this point and compare with sequence starting with 2 - they are the same.

Edit: For me it looks like all these sequences are the same - and the same as original sequence. So seems tha GazL showed us - computer proof - there is only one such sequence. If there are no other possibilities. Congrats! But if it is true - challenge is finished.

Edit: here what is more challenging #n - number of different sequences with the property as amazing circle for given n - seems that #32 = 1 - only one sequence. What about #123? Reasonable sequence is when there is algorithm to compute it - say Fibonacci - there is page on internet with "all" up to date known sequences - if you will find new one - fame awaits you.

Last edited by igadoter; 04-09-2021 at 08:09 AM.
 
Old 04-09-2021, 12:44 PM   #15
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Have to credit Gazl with first meeting the challenge of generating a valid 32 element circle of squares. But, with his own caveat:
Quote:
Originally Posted by GazL View Post
This may not be all possible sequences, my code just returns the first complete valid sequence it finds for each start point.
I will try to study Gazl's code to understand why my (similar) approach didn't work. Meanwhile will try to employ something more like Astrogeek's:

Quote:
Originally Posted by astrogeek View Post
* There aren't really a great number of choices - the possible pairs are tightly constrained in "families" of number of choices
* Each choice, where there is a choice, further constrains the next choice
* Using the clues suggested by the above list, think in terms of segments (arcs) of one or more pairs, then join the segments
Quote:
Originally Posted by astrogeek View Post
1. Connect all deterministic pairings into segments (those integers with only two possible pairing partners)
2. Connect all deterministic segment end pairs (segment ends with only one possible partner)
3. If the result is a ring then there is only one solution and its mirror, it is fully deterministic.
This approach sounds more likely to generate multiple sequences, if such multiple sequences exist, or to definitively prove that there is only one valid 32 element Ring. Keeping in mind that every valid Ring can be expressed as an array of 64 permutations, for 32 head points * 2 directions.

Quote:
Originally Posted by astrogeek View Post
Code to follow after sleep!
Yes, please let us see your code!
 
  


Reply

Tags
circle, perfect square, programming challenge, ring, ring data type


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
damnit!!! i cant see what im typing.. fonts are squares iLLuSionZ Linux - Newbie 22 11-18-2003 03:36 PM
characters as squares in mozilla icyfire Linux - Software 4 09-18-2003 04:22 PM
white squares appear on screen saver? bongo.hickup Linux - Hardware 0 06-13-2003 03:51 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 02:46 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration