Closed Thread Icon

Topic awaiting preservation: Latin Squares and XOR (Page 1 of 1) Pages that link to <a href="https://ozoneasylum.com/backlink?for=33315" title="Pages that link to Topic awaiting preservation: Latin Squares and XOR (Page 1 of 1)" rel="nofollow" >Topic awaiting preservation: Latin Squares and XOR <span class="small">(Page 1 of 1)</span>\
 
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 10-07-2017 04:34

Nugget of joy that I started some time ago, but got put on hold just tad.

I found myself in need of orthogonal latin squares of size 16. Turns out
that it is ridiculously simple when using XOR as the base. There are a
lot of amazing patterns in XOR, and this following code in Python makes
use of some of them.

I started out with some brute force using XOR with a size of 8, but terminated
early because I just needed a few working samples as oppossed to the whole
data set. Then I played with the samples until I found the patterns governing
the whole. The patterns governing XOR size=8 hold true for XOR size=16...
and on up for higher powers of 2.

Once I had the patterns down in a certain sub-arena, things went pretty damn
quick. Imagine trying to brute force 16!*16!*16!. No thanks. I'll find the
patterns and go from there.

This first chunk of code is brute force, but only 14!/11!=2184. And it will
spit out 416 valid solutions to screen and to pickled file.

A few things to note:
- All solutions are a permutations of the XOR grid.
- The permutations of the XOR grid are 1d rows only.

There are some interesting things that go on with re-mapped values and
redundancy, but too much to talk about right now.


code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import pickle
import itertools


def ndlist(s, v):
   # http://stackoverflow.com/questions/13447882/python-2-7-creating-a-multidimensional-list
   # by pterodragon
   return [ndlist(s[1:], v) for i in range(s[0])] if s else v


def remap(rgrid,rseq):

   ngrid=[]

   for i in rseq:
      ngrid.append(rgrid[i])

   return ngrid


def is_ortho(agrid,bgrid):

   isbit=0
   tsize=len(agrid)
   olist=[]

   for j in range(tsize):
      for i in range(tsize):
         olist.append(tsize*agrid[j][i]+bgrid[j][i])

   t=set(olist)

   if len(t)==(tsize*tsize):
      isbit=1

   return isbit


ss=16
tgrid=ndlist([ss,ss],0)
for j in range(ss):
   for i in range(ss):
      tgrid[j][i]=j^i

pseq=[1,3,4,5,6,7,8,9,10,11,12,13,14,15]
fseq=[]
tcount=0

for x in itertools.permutations( pseq, 3):

      s=[0]

      y=[2]
      y.extend(x)

      for i in y:
         t=[]
         for v in s:
            t.append(i^v)
         s.extend(t)

      ts=set(s)

      if len(ts)==ss:
         rmgrid=remap(tgrid,s)
         obit=is_ortho(tgrid,rmgrid)
         if obit:
            fseq.append(y)
            print('{} --> {}').format(y,s)
            tcount=tcount+1

print('tcount={}').format(tcount)

output = open('xor16_orthoseq.pkl', 'wb')
pickle.dump(fseq, output,-1)
output.close()




This second chunk of code will load the solutions from the pickled file,
pick one at random, expand into a latin square, double-check that it is
still orthogonal to the base XOR grid, and dump it screen.


code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import pickle
import random


def ndlist(s, v):
   # http://stackoverflow.com/questions/13447882/python-2-7-creating-a-multidimensional-list
   # by pterodragon
   return [ndlist(s[1:], v) for i in range(s[0])] if s else v


def cout_2dgrid(cgrid):

   ll=len(cgrid)

   cmap=['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']

   for row in range(ll):
      pme=' '
      for col in range(ll):
         pme=pme+' '+cmap[ cgrid[row][col] ]
      print(pme)
   print('')

   return


def remap(rgrid,rseq):

   ngrid=[]

   for i in rseq:
      ngrid.append(rgrid[i])

   return ngrid


def is_ortho(agrid,bgrid):

   isbit=0
   tsize=len(agrid)
   olist=[]

   for j in range(tsize):
      for i in range(tsize):
         olist.append(tsize*agrid[j][i]+bgrid[j][i])

   t=set(olist)

   if len(t)==(tsize*tsize):
      isbit=1

   return isbit


ss=16
tgrid=ndlist([ss,ss],0)
for j in range(ss):
   for i in range(ss):
      tgrid[j][i]=j^i

pkl_file = open('xor16_orthoseq.pkl', 'rb')
xseq = pickle.load(pkl_file)

y=random.choice(xseq)
s=[random.choice( range(ss) )]
for i in y:
   t=[]
   for v in s:
      t.append(i^v)
   s.extend(t)

print('s={}\n').format(s)

ogrid=remap(tgrid,s)
cout_2dgrid(ogrid)

fcheck=is_ortho(tgrid,ogrid)
if fcheck:
   print('yes, ortho')
else:
   print('fail')




On one hand, it is a bit boring because it doesn't really dig into slews
of combinations and permutations. On the other hand, it is pretty amazing
to see what can be done with patterns.

16!*16!*16!

vs.

14!/11!

heh
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 10-11-2017 13:42

T + XOR = F!

Transversals, yo.

code:
0 1 2 3       0 . . .   . 1 . .   . . 2 .   . . . 3
1 0 3 2  -->  . . 3 .   . . . 2   1 . . .   . 0 . .  ---+
2 3 0 1       . . . 1   . . 0 .   . 3 . .   2 . . .     |
3 2 1 0       . 2 . .   3 . . .   . . . 0   . . 1 .     |
                                                        |
0 1 2 3       0 . . .   . 1 . .   . . 2 .   . . . 3     |
2 3 0 1  <--  . . 0 .   . . . 1   2 . . .   . 3 . .  <--+
3 2 1 0       . . . 0   . . 1 .   . 2 . .   3 . . .
1 0 3 2       . 0 . .   1 . . .   . . . 2   . . 3 .




Find a bunch of transversals.
Play a rousing game of cover-all.
Flatten each trans to a single symbol.
Put it back together.
Boom. Orthogonal mate.

Try to find a transversal in this:

code:
0 1 2 3
1 0 3 2
2 3 1 0
3 2 0 1



Let's try some brute force on that little guy:

code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def cout_trans(cgrid,inds):

   ll=len(cgrid)

   bseq=['0','1','2','3','4','5','6','7',
         '8','9','A','B','C','D','E','F']

   for trow in range(ll):
      cme=' '
      for tcol in range(ll):
         if inds[trow]==tcol:
            cme=cme+' '+bseq[cgrid[trow][tcol]]
         else:
            cme=cme+' .'
      print(cme)
   print('')

   return


tgrid=[[0,1,2,3],
       [1,0,3,2],
       [2,3,1,0],
       [3,2,0,1]]

dr=len(tgrid)
tcount=0

for p in itertools.permutations(range(dr)):
   tset=set()
   for c in range(dr):
      tset.add( tgrid[c][p[c]]  )
   if len(tset)==dr:
      tcount=tcount+1
      cout_trans(tgrid,p)

print('tcount={}').format(tcount)



Toss other tgrids in there and see what it spits out
to screen.

When it comes to transversals and XOR, orthogonal mates
pop out all over the place. In most cases, brute force
the whole solution. Not the case with XOR. With XOR, one
transversal holds enough information for a complete orthogonal
mate solution.

With XOR, just one trans is all you need.

Here is a transversal using XOR=8 and the associated data:

code:
. . . . . 5 . .
  . . . . . . 7 .
  . . 0 . . . . .
  . 2 . . . . . .
  . . . . . . . 3
  . . . . 1 . . .
  6 . . . . . . .
  . . . 4 . . . .

  row=[0,1,2,3,4,5,6,7]
  col=[5,6,2,1,7,4,0,3]
  val=[5,7,0,2,3,1,6,4]



Try swapping that data around to make a permutation.
Something like:

code:
nrow=col
ncol=val
nval=row



You might be surprised (or not surprised) as to what
gets spit out.

One day I was playing with re-indexing transversal data
to the diagonal in the XOR grid. And I got some variables
mixed around. But I didn't think anything about it at
the time because I was still getting a valid orthogonal
mate. That was a real mind-bender. Once I realized, I
started mixing things up intentionally. More mind-bending.

Once you have a single transversal in an XOR grid, getting
a full orthogonal is wicked easy.

But how easy, or not easy, is it to get a transversal in
the first place? Well, when you are dealing with an XOR
grid base, not that hard at all. Depending on a few things.
Like your sense of humour.
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 10-13-2017 00:20

Okay, let's do some 2d reduction kind of stuff to find
a transversal in this little guy:

code:
0 1 2 3
  +--------
0 | 0 1 2 3
1 | 1 0 3 2
2 | 2 3 0 1
3 | 3 2 1 0



We are going to look for (0,1,2,3) each in turn, add them
to lists, and remove them from the grid.

First we find 0 and do like so:

code:
val=[0]
row=[0]
col=[0]

    1 2 3
  +------
1 | 0 3 2
2 | 3 0 1
3 | 2 1 0



Now we pick a 1.

code:
val=[0,1]
row=[0,2]
col=[0,3]

    1 2
  +----
1 | 0 3
3 | 2 1



Now for 2.

code:
val=[0,1,2]
row=[0,2,3]
col=[0,3,1]

    2
  +--
1 | 3



And the last one left is 3, so the final data set
for a transversal looks like this:

code:
val=[0,1,2,3]
row=[0,2,3,1]
col=[0,3,1,2]

0 . . .
. . 3 .
. . . 1
. 2 . .



Re-arrange a few things. In this case, the rows so
that [0,2,3,1] is along the one diagonal:

code:
0 . . .
. 2 . .
. . 3 .
. . . 1

0 1 2 3
3 2 1 0
1 0 3 2
2 3 0 1



Boom. We now have an orthogonal to the original XOR=4 grid.
Pretty sweet, yes?

And, as near as I can tell, that will always work for XOR=4. I've
done it tons of times and it has never locked-out. If you stare
at it long enough, you should be able to see how the diagonals
play an important part in why it never locks-out.

When you start playing around with doing the same trick with
XOR=8, you are going to have to start getting a little bit
smarter. I look at it as a game of distribution. Where can I
pick from so that I still have options as I get further down
the road? I don't want to get too greedy in one spot or else
I will run out of possibilities and lock-out.

code:
0 1 2 3 4 5 6 7
  +----------------
0 | 0 1 2 3 4 5 6 7
1 | 1 0 3 2 5 4 7 6
2 | 2 3 0 1 6 7 4 5
3 | 3 2 1 0 7 6 5 4
4 | 4 5 6 7 0 1 2 3
5 | 5 4 7 6 1 0 3 2
6 | 6 7 4 5 2 3 0 1
7 | 7 6 5 4 3 2 1 0



Going to look at it in quadrants. The upper-left has the
digits [0,1,2,3], as does the lower-right. And the other two
quadrants have [4,5,6,7].

In the upper-left quad, going to pick 0 and 1. Append
the data and reduce the grid.

code:
val=[0,1]
row=[1,2]
col=[1,3]

    0 2 4 5 6 7
  +------------
0 | 0 2 4 5 6 7
3 | 3 1 7 6 5 4
4 | 4 6 0 1 2 3
5 | 5 7 1 0 3 2
6 | 6 4 2 3 0 1
7 | 7 5 3 2 1 0



Now going to pick 2 and 3 from the lower-right.

code:
val=[0,1,2,3]
row=[1,2,5,6]
col=[1,3,7,5]

    0 2 4 6
  +--------
0 | 0 2 4 6
3 | 3 1 7 5
4 | 4 6 0 2
7 | 7 5 3 1



From here, everthing falls into place very nicely.
Pick 4 and 5:

code:
val=[0,1,2,3,4,5]
row=[1,2,5,6,0,3]
col=[1,3,7,5,4,6]

    0 2
  +----
4 | 4 6
7 | 7 5



After 6 and 7, left with this data set:

code:
val=[0,1,2,3,4,5,6,7]
row=[1,2,5,6,0,3,4,7]
col=[1,3,7,5,4,6,2,0]



Our transversal looks like this:

code:
val=[0,1,2,3,4,5,6,7]
row=[1,2,5,6,0,3,4,7]
col=[1,3,7,5,4,6,2,0]

 . . . . 4 . . .
 . 0 . . . . . .
 . . . 1 . . . .
 . . . . . . 5 .
 . . 6 . . . . .
 . . . . . . . 2
 . . . . . 3 . .
 7 . . . . . . .



Just for fun, going to re-arrange to the other diagonal.

code:
. . . . . . . 2
 . . . . . . 5 .
 . . . . . 3 . .
 . . . . 4 . . .
 . . . 1 . . . .
 . . 6 . . . . .
 . 0 . . . . . .
 7 . . . . . . .


 5 4 7 6 1 0 3 2
 3 2 1 0 7 6 5 4
 6 7 4 5 2 3 0 1
 0 1 2 3 4 5 6 7
 2 3 0 1 6 7 4 5
 4 5 6 7 0 1 2 3
 1 0 3 2 5 4 7 6
 7 6 5 4 3 2 1 0




Tada.

Fun or boring? Depends on what you are after. As for me, I'm
have a lot of fun exploring the patterns. Other than playing
with patterns, not a lot of insight into latin squares and
orthogonals in general. Just playing with patterns.


! BONUS ROUND !

I have been playing with sizing things up. Well, to the size
of XOR=16. I'm going to stop at that size for awhile because
that's the size that I need for my purposes.

So I started playing with XOR=16. Tackling it like a distribution
problem to find transversals in a hurry. Once I got it down, I
started getting little blocks of numbers like this:

code:
2 5 B C
7 0 E 9
8 F 1 6
D A 4 3



Just by looking at that I can very easily see that finding transversals
in XOR=16 is wicked easy and fast. Ah, but there is a little bit
more to it than that.

You see, those numbers are in base16. Now watch what happens when you
convert it to base4 and pull the bits apart:

code:
02 11 23 30   0 1 2 3   2 1 3 0
13 00 32 21   1 0 3 2   3 0 2 1
20 33 01 12   2 3 0 1   0 3 1 2
31 22 10 03   3 2 1 0   1 2 0 3



Not only did it spit out an XOR pattern, but it spit out a corresponding
orthogonal.
Everytime.
Seriously, how cool is that?

edit:
formating issues in a few spots
i'm sure you'll figure it out

(Edited by warjournal on 10-13-2017 00:23)

(Edited by warjournal on 10-13-2017 00:24)
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 11-04-2018 00:11

Started writing again. Going to go over what I was talking about in the first again using
a different slant.

First, this ol' boy:

code:
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0



Then brute force perm the rows and columns. If it is orthogonal, spit it out. It went
a lot faster than I was expecting.

Time to stare at something like this:

code:
0 2 4 6 3 1 7 5
1 3 5 7 2 0 6 4
2 0 6 4 1 3 5 7
3 1 7 5 0 2 4 6
4 6 0 2 7 5 3 1
5 7 1 3 6 4 2 0
6 4 2 0 5 7 1 3
7 5 3 1 4 6 0 2



That is orthogonal to the XOR square of size 8. Bunches of those I was doing the Zen
stare thing looking for any pattern that I could take advantage of.

When I started lookinig at 1d groups in a recursive manner, the basic XOR pattern popped-
out. Which makes total sense because it is XOR after all. Right?

Using the above square, I extracted the sequence [2,4,3].

How do you use that 3-digit sequence and XOR to get an orthogonal? Well, that 3-digit
example will give you a transversal, and the transversal will give you the orthogonal.
As it turns out, any transversal in XOR will give you an orthogonal. So, 3 digits
to transversal, transversal to orthogonal. Boom. Done.

We are going to take those 3 digits and the starting number 0. XOR the first digit with
0 and extend. Xor that with the second digit, and extend again. One more time with the
third digit.

code:
[0,[2,4,3]] # starting number and XOR extend sequence

[0]^2=[2] # xor with first
[0,2]     # extend
[0,2]^4=[4,6] # xor with second
[0,2,4,6]     # extend
[0,2,4,6]^3=[3,1,7,5] # xor with third
[0,2,4,6,3,1,7,5]     # extend



That final 8-digit sequence is a transversal in the original XOR square. And there are
quite a few ways to use it to generate a complete orthogonal square. The easiest way,
in Python, is to re-index the rows:

code:
# re-index rows using [0,2,4,6,3,1,7,5]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
3 2 1 0 7 6 5 4
1 0 3 2 5 4 7 6
7 6 5 4 3 2 1 0
5 4 7 6 1 0 3 2



Just to give you a start on seeing other ways, here are two alternatives to getting a transversal
from the same 8-digit sequence:

code:
#   by index          by value
0 . . . . . . .   0 . . . . . . .
. . 3 . . . . .   . . . 2 . . . .
. . . . 6 . . .   . . . . . . 4 .
. . . . . . 5 .   . . . . . 6 . .
. . . 7 . . . .   . . . . . . . 3
. 4 . . . . . .   . . . . 1 . . .
. . . . . . . 1   . 7 . . . . . .
. . . . . 2 . .   . . 5 . . . . .



Then play around with ways to use that to get a complete ortho square. I tried all sorts of ways, some
wicked easy and some seriously convoluted, and they all worked.

Back to some brute force. I went through and spit out all of the 3-digit sequences that worked. Here
they are:

code:
243 341 413 512 612 713
245 345 416 516 615 715
251 352 432 532 631 731
256 357 436 537 637 736
261 361 452 543 641 751
265 367 457 547 647 756
273 372 463 573 672 763
276 375 467 576 675 765



There are 48 3-digit sequences that can be used to wicked quickly create an XOR orthogonal. Pick a
starting number in the range[0...7], pick one of those sequences, and XOR extend it.

In those 3-digit sequences, notice that none of them is a 0. Notice that the first digit is never
1. Notice that the second digit is never 2. Finally, notice that the third digit is never 4. If you
think about it and how XOR works, this makes perfect sense.

One more quick example. I'm going to take the sequence [2,4,3] and feed it [0...7]. The resulting
square is the exact same as the first ortho that I showed above.

code:
(0, [2, 4, 3], [0, 2, 4, 6, 3, 1, 7, 5])
(1, [2, 4, 3], [1, 3, 5, 7, 2, 0, 6, 4])
(2, [2, 4, 3], [2, 0, 6, 4, 1, 3, 5, 7])
(3, [2, 4, 3], [3, 1, 7, 5, 0, 2, 4, 6])
(4, [2, 4, 3], [4, 6, 0, 2, 7, 5, 3, 1])
(5, [2, 4, 3], [5, 7, 1, 3, 6, 4, 2, 0])
(6, [2, 4, 3], [6, 4, 2, 0, 5, 7, 1, 3])
(7, [2, 4, 3], [7, 5, 3, 1, 4, 6, 0, 2])



Seriously, how wicked cool is that?

I also went through and did the same thing for XOR=16. Here is the first batch of 4-digit squences:

code:
238C  2483  2581  2681  2783  2815  2914  2A14  2B15  2C14  2D15  2E15  2F14
238D  2485  2586  2685  2786  2816  2917  2A17  2B16  2C17  2D16  2E16  2F17
238E  2489  2589  2689  2789  281C  291C  2A1C  2B1C  2C19  2D19  2E19  2F19
238F  248F  258E  268D  278C  281F  291F  2A1F  2B1F  2C1A  2D1A  2E1A  2F1A
239C  2491  2593  2693  2791  2834  2935  2A35  2B34  2C34  2D35  2E35  2F34
239D  2497  2594  2697  2794  2837  2936  2A36  2B37  2C37  2D36  2E36  2F37
239E  249A  259A  269A  279A  283D  293D  2A3D  2B3D  2C39  2D39  2E39  2F39
239F  249C  259D  269E  279F  283E  293E  2A3E  2B3E  2C3A  2D3A  2E3A  2F3A
23AC  24A1  25A3  26A3  27A1  2854  2954  2A54  2B54  2C51  2D51  2E51  2F51
23AD  24A7  25A4  26A7  27A4  2856  2956  2A56  2B56  2C53  2D53  2E53  2F53
23AE  24A9  25A9  26A9  27A9  285C  295D  2A5C  2B5D  2C5D  2D5C  2E5D  2F5C
23AF  24AF  25AE  26AD  27AC  285E  295F  2A5E  2B5F  2C5F  2D5E  2E5F  2F5E
23BC  24B3  25B1  26B1  27B3  2865  2965  2A65  2B65  2C61  2D61  2E61  2F61
23BD  24B5  25B6  26B5  27B6  2867  2967  2A67  2B67  2C63  2D63  2E63  2F63
23BE  24BA  25BA  26BA  27BA  286D  296C  2A6D  2B6C  2C6D  2D6C  2E6D  2F6C
23BF  24BC  25BD  26BE  27BF  286F  296E  2A6F  2B6E  2C6F  2D6E  2E6F  2F6E
23C4  24C1  25C1  26C1  27C1  2894  2985  2A94  2B85  2C81  2D91  2E91  2F81
23C5  24C7  25C6  26C5  27C4  2897  2986  2A97  2B86  2C83  2D93  2E93  2F83
23C6  24C9  25CA  26C9  27CA  289D  298D  2A9C  2B8C  2C8D  2D9C  2E9D  2F8C
23C7  24CF  25CD  26CD  27CF  289E  298E  2A9F  2B8F  2C8F  2D9E  2E9F  2F8E
23D4  24D3  25D3  26D3  27D3  28B5  29A4  2AB5  2BA4  2CB1  2DA1  2EA1  2FB1
23D5  24D5  25D4  26D7  27D6  28B6  29A7  2AB6  2BA7  2CB3  2DA3  2EA3  2FB3
23D6  24DA  25D9  26DA  27D9  28BC  29AC  2ABD  2BAD  2CBD  2DAC  2EAD  2FBC
23D7  24DC  25DE  26DE  27DC  28BF  29AF  2ABE  2BAE  2CBF  2DAE  2EAF  2FBE
23E4  24E3  25E3  26E3  27E3  28C5  29D5  2AD4  2BC4  2CD4  2DC5  2ED5  2FC4
23E5  24E5  25E4  26E7  27E6  28C7  29D7  2AD6  2BC6  2CD7  2DC6  2ED6  2FC7
23E6  24E9  25EA  26E9  27EA  28CD  29DC  2ADC  2BCD  2CD9  2DC9  2ED9  2FC9
23E7  24EF  25ED  26ED  27EF  28CF  29DE  2ADE  2BCF  2CDA  2DCA  2EDA  2FCA
23F4  24F1  25F1  26F1  27F1  28F4  29E4  2AE5  2BF5  2CF4  2DE5  2EF5  2FE4
23F5  24F7  25F6  26F5  27F4  28F6  29E6  2AE7  2BF7  2CF7  2DE6  2EF6  2FE7
23F6  24FA  25F9  26FA  27F9  28FC  29ED  2AED  2BFC  2CF9  2DE9  2EF9  2FE9
23F7  24FC  25FE  26FE  27FC  28FE  29EF  2AEF  2BFE  2CFA  2DEA  2EFA  2FEA



Truly a thing of beauty. Brings a smile to my face. And that's just the first 416 sequences.
There are 5,408 more to go. Heh.

That is as big as I have gone using this particular pattern. The next size up that I have an
interest in is 256. But I wouldn't use this method for creating XOR orthos of size 256. For size
256, I would use the fractal/distribution pattern in XOR. This is what I was talking about in
the second post. I've since refined that particular fractal/distribution technique considerably.
Arthurio
Paranoid (IV) Inmate

From: cell 3736
Insane since: Jul 2003

 posted posted 11-04-2018 16:35

Warjournals adventures into the wonderful world of mathematical patterns.
I wanted to comment something so that you'll know that at least one person has been reading these posts.

What do you do with these things besides making weird sudoku puzzles and sort of meditating to a wall of numbers?
Try as I might I just can't get as excited about these things. However I do find fascinating the energy and determination with which you have been exploring this subject. It feels as though a scientific discovery might be just around the corner here that will solve a problem no one knew they had. And then you'll be celebrated as the genius who solved subatomic MRI and teleportation or something. Or it could be that you are actually genuinely insane and you have tricked me into believing that all of this should make sense if I just took more time to dive into it. So ... yeah ... keep it up! I wanna see which way it goes

warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 11-07-2018 13:37

I always assume that someone somewhere is listening. But it is good to hear for sure, Arthurio. Thank you.
Don't worry about being excited. I recognize that people have different passions. It's all good.

What do I do with all of this stuff? Honestly, not much. I'm just following my passion is all. I've got so many
tricks up my sleeve that I could easily get a few software patents or write a few books. But for now, it all
just sits in my brain and in my notes.

I'm in the middle of a 55 hour work week. However, I am planning on posting some code that will show
the distribution and reduction thing. I've got it working 100%, but I still have to make one little part
parametric and switch it all over to numpy. I think it was Ty that whispered numpy in my ear.
I was hesitant at first, but it is good stuff. Thanks, Ty.
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 11-07-2018 17:11

I got the important parts converted to numpy.
I got the last little bit converted to parametric.
And the damn thing works like a charm 100%.
Some polish here and there is all that is left.

Wanna see something beautiful?

code:
F G g r 1 U a x 2 T d u C J f s
U 1 x a G F r g J C s f T 2 u d
j o 8 N Z y 6 P W / 5 Q k n B K
y Z P 6 o j N 8 n k K B / W Q 5
B K k n 5 Q W / 6 P Z y 8 N j o
Q 5 / W K B n k N 8 o j P 6 y Z
f s C J d u 2 T a x 1 U g r F G
u d T 2 s f J C r g G F x a U 1
7 O Y z 9 M i p A L l m 4 R X +
M 9 p i O 7 z Y R 4 + X L A m l
b w 0 V h q E H e t D I c v 3 S
q h H E w b V 0 v c S 3 t e I D
3 S c v D I e t E H h q 0 V b w
I D t e S 3 v c V 0 w b H E q h
X + 4 R l m A L i p 9 M Y z 7 O
m l L A + X R 4 z Y O 7 p i M 9



That right there is a mini-grid in an XOR=256.
Unfortunately I don't have 256 symbols, so I did Base(64)%64.
So, each symbol in there appears four times.
But still beautiful. Absolutely gorgeous.
Solvable every single time.

Soon.

(Edited by warjournal on 11-07-2018 17:11)
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 11-10-2018 22:50

The first thing we are going to look at is two very particular latin
squares of size 4. Both of those being:

code:
0 1 2 3   0 1 2 3
1 0 3 2   1 0 3 2
2 3 0 1   2 3 1 0
3 2 1 0   3 2 0 1



Why those two? Because those are the only two that exist. You can perm
one all you want and you will never get the other one. They are reduced
to complete uniqueness with regards to perming.

The first one is the XOR pattern. Fairly easy. Ah, but the second one
is very different from the first in a very different way other than perming.
The second square does not any orothogonal latin mates. None. Do the
perms and check for yourself. Shouldn't take any coder too long to try it.

The second square does not have any orthogonal mates, but the first one does.
And there is a funny little trick to finding them. There is a cute little
series of swaps that does it.

Let's look at that first one in groups like this:

code:
..C C D D
A 0 1 2 3
A 1 0 3 2
B 2 3 0 1
B 3 2 1 0


'A' is a group of two rows. 'B' is a group of two rows.
'C' is a group of two columns. 'D' is a group of two columns.

Step 1: Swap any group with itself.
- swap one A and the other A
- swap one B and the other B
- swap one C and the other C
- swap one D and the other D

Step 2: Swap one from one group with another group in the same vert or horz.
- Swap either A with either B
- Swap either C with either D

Or you can do Step 2 first and then Step 1. It doesn't matter. If you do those swaps,
you will always get an orthogonal to the first XOR grid above. Again, try it for
yourself. Not that hard to code. I originally did it with a pencil and graph paper
before moving on to code. I'm low-tech like that sometimes. Heh.

Now, this is where it gets into distribution. We want a very particular kind of even
distribution that can be found in latin squares, and no place better than in a
latin square. Or rather, in this case, orthogonal latin squares.

If you can create this distribution with small orthogonals, you can expand it to find
more orthogonals in larger squares.

code:
0 1 2 3   0 3 2 1
1 0 3 2   1 2 3 0
2 3 0 1   3 0 1 2
3 2 1 0   2 1 0 3

First latin square flattened for rows:
0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0

Second latin square flattened for cols:
0 3 2 1 1 2 3 0 3 0 1 2 2 1 0 3



Once they are flattened, notice how they pair-up:

code:
0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0
0 3 2 1 1 2 3 0 3 0 1 2 2 1 0 3

00 13 22 31 11 02 33 20 23 30 01 12 32 21 10 03
 0  6  A  D  5  2  F  8  B  C  1  6  E  9  4  3



Pretty sweet, huh? As a matter of fact, using that kind of pairing making is easy to check
to see if two grids are orthogonal. In that example, it would be 2 bits in base(4) producing
16 unique numbers. Not that hard to code.

So, use those two flattened lines of othogonals to cull a larger square. Since 4x4=16, those two
can be used to cull an XOR=16 grid. Lay it out, pick a number, squish, and solve.

code:
|0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0
--+-------------------------------
0 |0 1 2 3 4 5 6 7 8 9 A B C D E F
3 |1 0 3 2 5 4 7 6 9 8 B A D C F E
2 |2 3 0 1 6 7 4 5 A B 8 9 E F C D
1 |3 2 1 0 7 6 5 4 B A 9 8 F E D C
1 |4 5 6 7 0 1 2 3 C D E F 8 9 A B
2 |5 4 7 6 1 0 3 2 D C F E 9 8 B A
3 |6 7 4 5 2 3 0 1 E F C D A B 8 9
0 |7 6 5 4 3 2 1 0 F E D C B A 9 8
3 |8 9 A B C D E F 0 1 2 3 4 5 6 7
0 |9 8 B A D C F E 1 0 3 2 5 4 7 6
1 |A B 8 9 E F C D 2 3 0 1 6 7 4 5
2 |B A 9 8 F E D C 3 2 1 0 7 6 5 4
2 |C D E F 8 9 A B 4 5 6 7 0 1 2 3
1 |D C F E 9 8 B A 5 4 7 6 1 0 3 2
0 |E F C D A B 8 9 6 7 4 5 2 3 0 1
3 |F E D C B A 9 8 7 6 5 4 3 2 1 0


0 |0 0 0 0   1 |1 1 1 1
--+-------   --+-------
0 |0 5 A F   1 |2 7 8 D
0 |7 2 D 8   1 |5 0 F A
0 |9 C 3 6   1 |B E 1 4
0 |E B 4 1   1 |C 9 6 3

2 |2 2 2 2   3 |3 3 3 3
--+-------   --+-------
2 |0 5 A F   3 |2 7 8 D
2 |7 2 D 8   3 |5 0 F A
2 |9 C 3 6   3 |B E 1 4
2 |E B 4 1   3 |C 9 6 3



Just for fun, let's take a look at all 4 of those mini-grids in the big square. You know, just the
intersetions that we are after:

code:
|0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0
--+-------------------------------
0 |0 . . . . 5 . . . . A . . . . F
3 |. . . 2 . . 7 . . 8 . . D . . .
2 |. . 0 . . . . 5 A . . . . F . .
1 |. 2 . . 7 . . . . . . 8 . . D .
1 |. 5 . . 0 . . . . . . F . . A .
2 |. . 7 . . . . 2 D . . . . 8 . .
3 |. . . 5 . . 0 . . F . . A . . .
0 |7 . . . . 2 . . . . D . . . . 8
3 |. . . B . . E . . 1 . . 4 . . .
0 |9 . . . . C . . . . 3 . . . . 6
1 |. B . . E . . . . . . 1 . . 4 .
2 |. . 9 . . . . C 3 . . . . 6 . .
2 |. . E . . . . B 4 . . . . 1 . .
1 |. C . . 9 . . . . . . 6 . . 3 .
0 |E . . . . B . . . . 4 . . . . 1
3 |. . . C . . 9 . . 6 . . 3 . . .



In that whole grid, those are the only parts that we are interested in looking at. In those points, there
is a very easy to find transversal that will lead to a full-on orthogonal.

How do we do that? Let's look at mini-grid(0) and solve for (0,1,2,3) and their indices in the big grid.

code:
0 |0 0 0 0
--+-------
0 |0 5 A F
0 |7 2 D 8
0 |9 C 3 6
0 |E B 4 1

0=(0,0)
1=(0,15)
2=(7,5)
3=(9,10)



Then you do mini_grid(1) and solve for (4,5,6,7). And so-on for the other mini-grids. Once you get all of
that, you will have a transversal. And that transversal can easily be turned into an orthogonal to the
XOR=16 grid.

Start with easy orthos of size 4, and get orthos of size 16. Boom. Done. Not bad.

Here is an example (not the above data) of doing such a thing:

code:
0 1 2 3 4 5 6 7 8 9 A B C D E F
F E D C B A 9 8 7 6 5 4 3 2 1 0
5 4 7 6 1 0 3 2 D C F E 9 8 B A
A B 8 9 E F C D 2 3 0 1 6 7 4 5
E F C D A B 8 9 6 7 4 5 2 3 0 1
1 0 3 2 5 4 7 6 9 8 B A D C F E
B A 9 8 F E D C 3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3 C D E F 8 9 A B
D C F E 9 8 B A 5 4 7 6 1 0 3 2
2 3 0 1 6 7 4 5 A B 8 9 E F C D
8 9 A B C D E F 0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0 F E D C B A 9 8
3 2 1 0 7 6 5 4 B A 9 8 F E D C
C D E F 8 9 A B 4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1 E F C D A B 8 9
9 8 B A D C F E 1 0 3 2 5 4 7 6



But you can take it further. Since 16x16=256, you can do all of that again to get an ortho of size 256.
And so on.

As a whole, it may seem a bit complex to understand and code. But it's not. Doing all of this is wicked
easy. The only part that was difficult was understanding the bits and putting them together in a new way
for the first time. Once you do that, you will be all like, "Damn, that was easy. Why didn't I think
of that sooner?" You know, something along those lines. Yes, I fought hard to get there, but now that I'm
there it's all like whatever - because the bits that make up the whole and how to put them together really
is that easy.

Fucking genius.

Now, if you'll excuse me, I have some lager to down and come code to clean.

ugh... formatting

(Edited by warjournal on 11-10-2018 22:53)
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 11-13-2018 14:25

My Bamboo Fun was rendered useless several months ago. But, several days ago, my Intuos Art arrived.
So I kind of hurried through this just a tad so I can play with Krita and Blender.

Python 2.7.
I did try Python 3.5.2 and it doesn't like print().format(). I'm not sure what else it doesn't like.

But I'm okay with that because I use 2.7 and ya'll are free to fix it for 3.whateveryouuse.
Yeah, play with it and all that.

If you know anything about coding in any language, you should be able to see how ridiculously
simple the defs are. It really is that simple.

It uses a simple method to create 4x4 orthos. Then uses those to create 16x16 orthos. Then
uses those to create 256x256 orthos. But it is very limited because of the small space that
it starts in: 4x4. If you used another method to create a larger variety of 16x16, like the
XOR extend method, then you will get more 256x256 orthos - by more than a few magnitudes.

But... still a bit boring on one front in particular. This whole thing is based on XOR patterns, and
those patterns will still be there. Cool as shit as-is, but it doesn't really introduce anything new.
But maybe, just maybe... I have a few more tricks up my sleeve. Heh.


code:
#!/usr/bin/env python
import random
import numpy as np


def cout_2d(pme):

    bseq=['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F', #00
          'G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V', #10
          'W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','l', #20
          'm','n','o','p','q','r','s','t','u','v','w','x','y','z','+','/'] #30

    for row in pme:
        c=''
        for col in row:
            c=c+' '+bseq[col%64] # testing bigger grids
        print(c)
    print('')


    return

def cout_1d(pme):

    bseq=['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']

    c=''

    for i in pme:
        c=c+' '+bseq[i]

    print(c)
    print('')

    return

def cout_mini(lgrid,lrow,lcol,lval):

    bseq=['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F', #00
          'G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V', #10
          'W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','l', #20
          'm','n','o','p','q','r','s','t','u','v','w','x','y','z','+','/'] #30

    for tr in range(len(lrow)):
        c=''
        if lrow[tr]==lval:
            for tc in range(len(lcol)):
                if lcol[tc]==lval:
                    c=c+' '+bseq[lgrid[tr][tc]%64] # testing bigger mini-grids
            print(c)
    print('')




    return

def gen_xor(n):

    # using uint8 because I don't plan on going
    # beyond 0-255 anytime soon

    fx=np.zeros((n,n),dtype=np.uint8)

    for row in range(n):
        for col in range(n):
            fx[row,col]=row^col

    return fx

def gen_ls_ortho4():

    # hardcoded to 4
    # this works 100%
    # but this implementation
    # has some oddities that iron-out

    ls=gen_xor(4)
    ortho=gen_xor(4)


    if random.choice([0,1]):

        n=random.choice(range(4))
        if n==0: ortho[0,:],ortho[1,:]=ortho[1,:].copy(),ortho[0,:].copy()
        if n==1: ortho[2,:],ortho[3,:]=ortho[3,:].copy(),ortho[2,:].copy()
        if n==2: ortho[:,0],ortho[:,1]=ortho[:,1].copy(),ortho[:,0].copy()
        if n==3: ortho[:,2],ortho[:,3]=ortho[:,3].copy(),ortho[:,2].copy()

        n=random.choice(range(8))
        if n==0: ortho[0,:],ortho[2,:]=ortho[2,:].copy(),ortho[0,:].copy()
        if n==1: ortho[0,:],ortho[3,:]=ortho[3,:].copy(),ortho[0,:].copy()
        if n==2: ortho[1,:],ortho[2,:]=ortho[2,:].copy(),ortho[1,:].copy()
        if n==3: ortho[1,:],ortho[3,:]=ortho[3,:].copy(),ortho[1,:].copy()

        if n==4: ortho[:,0],ortho[:,2]=ortho[:,2].copy(),ortho[:,0].copy()
        if n==5: ortho[:,0],ortho[:,3]=ortho[:,3].copy(),ortho[:,0].copy()
        if n==6: ortho[:,1],ortho[:,2]=ortho[:,2].copy(),ortho[:,1].copy()
        if n==7: ortho[:,1],ortho[:,3]=ortho[:,3].copy(),ortho[:,1].copy()

    else:

        n=random.choice(range(8))
        if n==0: ortho[0,:],ortho[2,:]=ortho[2,:].copy(),ortho[0,:].copy()
        if n==1: ortho[0,:],ortho[3,:]=ortho[3,:].copy(),ortho[0,:].copy()
        if n==2: ortho[1,:],ortho[2,:]=ortho[2,:].copy(),ortho[1,:].copy()
        if n==3: ortho[1,:],ortho[3,:]=ortho[3,:].copy(),ortho[1,:].copy()

        if n==4: ortho[:,0],ortho[:,2]=ortho[:,2].copy(),ortho[:,0].copy()
        if n==5: ortho[:,0],ortho[:,3]=ortho[:,3].copy(),ortho[:,0].copy()
        if n==6: ortho[:,1],ortho[:,2]=ortho[:,2].copy(),ortho[:,1].copy()
        if n==7: ortho[:,1],ortho[:,3]=ortho[:,3].copy(),ortho[:,1].copy()

        n=random.choice(range(4))
        if n==0: ortho[0,:],ortho[1,:]=ortho[1,:].copy(),ortho[0,:].copy()
        if n==1: ortho[2,:],ortho[3,:]=ortho[3,:].copy(),ortho[2,:].copy()
        if n==2: ortho[:,0],ortho[:,1]=ortho[:,1].copy(),ortho[:,0].copy()
        if n==3: ortho[:,2],ortho[:,3]=ortho[:,3].copy(),ortho[:,2].copy()

    return ls,ortho

def flatten2d(fme):

    # not numpy, but seems to work just fine

    fl=[]

    for i in fme:
        fl.extend(i)

    return fl

def solve_mini(mgrid,mrow,mcol,mval):

    # this will solve for a mini-grid
    # should add some breaks in there to speed things up

    msolve=[]

    sqmult=int(np.sqrt(len(mgrid)))

    for val in range(mval*sqmult,mval*sqmult+sqmult):
        for row in range(len(mrow)):
            for col in range(len(mcol)):
                if mrow[row]==mval:
                    if mcol[col]==mval:
                        if mgrid[row][col]==val:
                            msolve.append([row,col,val])

    return msolve

def shuffle_tandem(a,b):

    # i don't normally randomize the values (rvals)
    # but going to because it will shuffle
    # the solver later down the road
    # does not return a numpy array

    ll=len(a)

    rrows=random.shuffle(range(ll))
    rcols=random.shuffle(range(ll))
    rvals=random.shuffle(range(ll))

    m=[];n=[]

    for row in rrows:
        tline=[]
        sline=[]
        for col in rcols:
            tline.append(rvals[a[row][col]])
            sline.append(rvals[b[row][col]])
        m.append(tline)
        n.append(sline)

    return m,n

def is_ortho(grid0,grid1):

    # this checks to see if two grids are orthogonal
    # it does this by treating each grid as bit
    # in a base(n) manner
    # then counts the unique numbers
    # that is, eaching pairing of numbers in
    # the same position in each grid
    # should be unique

    ll=len(grid0)
    fcheck=set()

    for i in range(ll):
        for j in range(ll):
            fcheck.add(grid0[i][j]*ll+grid1[i][j])

    print('len(fcheck)={}').format(len(fcheck))

    return

def main(args):

    ls0,ls1=gen_ls_ortho4()
    #ls0,ls1=shuffle_tandem(ls0,ls1)
    srow=flatten2d(ls0)
    scol=flatten2d(ls1)

    ls16=gen_xor(16)

    print('The first latin square, XOR size=4:')
    cout_2d(ls0)
    print('The orthogonal to the first latin square:')
    cout_2d(ls1)
    print('First latin square flattened for rows:')
    cout_1d(srow)
    print('Second latin square flattened for cols:')
    cout_1d(scol)
    print('XOR size=16:')
    cout_2d(ls16)

    print('mini grid 0, solve for 0,1,2,3')
    cout_mini(ls16,srow,scol,0) # 0 1 2 3
    print('mini grid 1, solve for 4,5,6,7')
    cout_mini(ls16,srow,scol,1) # 4 5 6 7
    print('mini grid 2, solve for 8,9,A,B')
    cout_mini(ls16,srow,scol,2) # 8 9 A B
    print('mini grid 3, solve for C,D,E,F')
    cout_mini(ls16,srow,scol,3) # C D E F

    #cout_2d(ls16)

    fsolve=[]
    for i in range(4):
        fsolve.extend(solve_mini(ls16,srow,scol,i))
    print('Final solve data, fsolve[i][row,col,val]:')
    for i in fsolve:print(i)
    print('')

    lt16=gen_xor(16)
    for i in range(16):
        lt16[i]=ls16[fsolve[i][0]]

    print('Orthogonal using final solve data to permutate the rows:')
    cout_2d(lt16)

    print('Check to make sure that it is orthogonal, should be 256:')
    is_ortho(ls16,lt16)



    # the BIG jump
    print('')
    print('Time to make the big jump to 256.')
    gsolve=[]
    big256a=gen_xor(256)
    br=flatten2d(ls16)
    bs=flatten2d(lt16)

    print('')
    print('Previous 16x16 flattend for rows and columns.')
    print('Uncomment lines in code to print.')
    #print('br={}').format(br)
    #print('bs={}').format(bs)

    print('')
    print('Here is a mini-grid:')
    cout_mini(big256a,br,bs,0)
    print('Not completely accurate because of the lack of 256 symbols.')
    print('Uses 64 symbols with %64.')
    print('')

    print('Begin the countdown!')
    for i in range(16):
        print(15-i)
        gsolve.extend(solve_mini(big256a,br,bs,i))
    print('Solve data is done.')
    print('Uncomment line in code to print.')
    #print('gsolve={}').format(gsolve)

    b256b=np.zeros([256,256],dtype=np.uint8)
    for i in range(256):
        b256b[i]=big256a[ gsolve[i][0] ]
    print('')
    print('256x256={}').format(256*256)
    fs=is_ortho(big256a,b256b)
    print('If the above number is 65536, then you have orthogonal')
    print('latin squares of size 256 in a numpy array dtype=uint8.')

    return 0

if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))
Tyberius Prime
Maniac (V) Mad Scientist with Finglongers

From: Germany
Insane since: Sep 2001

 posted posted 11-13-2018 16:34

Regarding the print().format() - Python3, print is a function and returns None,
so you can't call .format on it.

You're looking to format a string and print that.
So you need to do print('something {}'.format(...))

I have no clue why print().format() works in ptyhon 2.7 - it must be a weird quirk of the grammar...
Tyberius Prime
Maniac (V) Mad Scientist with Finglongers

From: Germany
Insane since: Sep 2001

 posted posted 11-13-2018 16:36

(so what I think is happening is that the future-compability of 'print()' as a function is implemented
by a parser rule removing the braces -> print('shu').format() becomes print 'shu'.format()...)
warjournal
Maniac (V) Mad Scientist

From:
Insane since: Aug 2000

 posted posted 11-20-2018 01:36

I did do some looking into that, Ty. Thank you. Statement vs. Function.
Now I am that much more apprehensive about making the jump to Python3.
I'm such a wuss like that. "I don't wanna!" ~crosses arms~

Going to be my last post awhile. Holiday season and lots of work to do.

I'm not entirely sure just yet, but I think I can solve orthogonal latin
squares of size 2n. Actually, more like take known orthos and x2.

Here is 4x4 that I expanded into 8x8:

code:
0 1 7 6 5 4 3 2
2 3 0 1 6 7 5 4
4 5 3 2 1 0 7 6
6 7 4 5 2 3 1 0
3 2 5 4 7 6 0 1
5 4 6 7 0 1 2 3
7 6 1 0 3 2 4 5
1 0 2 3 4 5 6 7

3 4 5 7 1 2 6 0
2 5 4 6 0 3 7 1
7 0 1 3 5 6 2 4
6 1 0 2 4 7 3 5
4 7 3 5 6 1 0 2
5 6 2 4 7 0 1 3
0 3 7 1 2 5 4 6
1 2 6 0 3 4 5 7



While I did break a lot of the XOR patterns, there is still a very specific
structure in there.

Take a closer look at the top two rows of both of them like this:

code:
0 1  7 6  5 4  3 2
2 3  0 1  6 7  5 4
...
3 4  5 7  1 2  6 0
2 5  4 6  0 3  7 1



I call it "stair-stepping". To me, it looks like over-lapping stairs. I can
see it in those groupings. I can also see it in various ways in the vert
and horz. (When I see these kinds of things in sudoku, it looks like
scaffolding to me.) Because of the way that I see the stairs, I think that
there may be a way to use a path-finding algorithm to do this.

Now, I don't like reading the works of others very much. This usually does me
more harm that good. However, I did do some cursory research into creating
orthogonal latin squares. I do believe that Euler found this grouped structure.
But I'm not sure because I haven't found the reference again just yet.

I'm off for awhile.
Thanks for listening.

« Backwards — Onwards »

Show Forum Drop Down Menu