12
\$\begingroup\$

A Latin square is a square that has no repeated symbols in either the X or Y columns. For example:

ABCD    
DABC
CDAB
BCDA

is one such square. Notice how every column and row contains a permutation of the same 4 letters.

However, our Latin square has a problem: If I were to rotate the second row (DABC) 1 to the left, I'd end up with ABCD, which is identical to the permutation above it. If it is impossible to rotate any 1 column/row and obtain another column/row, then we consider the square to be rotation safe.

For example:

ABCD
BDAC
CADB
DCBA

is rotation safe. The grid has the following properties:

  1. Point [0,N] uses the Nth symbol
  2. Point [0,N] and [N,0] are always the same symbol. (I'd like to also say that [x,y] and [y,x] are also always the same letter, but I can't prove it)

Your task is to print out 1 rotation-safe Latin square, when passed N. I don't care if you output letters, numbers, a list, or a 2D array. If you use numbers, the top column and row must be 0,1,2,3,... (in that order). If you use letters, then it must be A,B,C,D,....

For example, if your input was 4, you should either print:

0,1,2,3            0,1,2,3
1,3,0,2     or     1,0,3,2
2,0,3,1            2,3,1,0
3,2,1,0            3,2,0,1

There are no rotation-safe Latin squares of size less than 4. I don't care what your program does if N is less than 4. For the curious, the number of rotation-safe squares is (starting at 4): 2,5,5906,(too long to calculate)

This is a , so try to make answers as short as possible in your favorite language!

\$\endgroup\$
  • \$\begingroup\$ Is there a time limit? (Related: Are Monte Carlo methods allowed if they are technically not guaranteed to terminate for high values of N due to insufficient random number quality?) \$\endgroup\$ – Doorknob May 9 '16 at 21:58
  • \$\begingroup\$ No time limit, but your solution should be guaranteed to terminate. \$\endgroup\$ – Nathan Merrill May 9 '16 at 22:01
  • 1
    \$\begingroup\$ For 1-indexed languages, can the first row be 1,2,3,...? \$\endgroup\$ – miles May 9 '16 at 22:09
  • \$\begingroup\$ related,related \$\endgroup\$ – Abr001am May 9 '16 at 22:44
  • \$\begingroup\$ @miles yes, that is fine \$\endgroup\$ – Nathan Merrill May 9 '16 at 22:45
3
\$\begingroup\$

Pyth - 29 bytes

Brute force.

hf&!@JsCBTsm.>RdJStQ.A{IMJ^.p

Does not finish online even for n=4, but you can try it out locally, or run this modified version online for one more byte.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Sqlserver 2012 - 918 bytes

On my box this runs for @k = 5, although it takes 16 seconds.

This is code building code(watch out Skynet, you have competition)

Is there a price for the longest script?

DECLARE @k int = 4;

DECLARE @t VARCHAR(max)='WITH C as(SELECT
top '+left(@k,1)+'row_number()over(order by 1/0)n
FROM sys.messages),D(nÆ)as(SELECT
concat(~),~
FROM Ø
WHERE |)SELECT top 1~ FROM Å
WHERE 1=1',@
varchar(999)=''SELECT @+=','+CHAR(x+65)FROM(values(0),(1),(2),(3),(4),(5))x(x)WHERE x<@k
SELECT
@t=REPLACE(REPLACE(REPLACE(REPLACE(@t,'Æ',@),'Ø',STUFF(REPLACE(@,',',',C '),1,1,'')),'Å',STUFF(REPLACE(@,',',',D
'),1,1,'')),'~',STUFF(REPLACE(@,',','.n,'),1,3,'')+'.n'),@='';WITH C as(SELECT top(@k)x
FROM(values(0),(1),(2),(3),(4),(5))x(x))SELECT @+=' AND
'+char(65+C.x)+'.n<>'+char(65+D.x)+'.n'FROM c,c d WHERE C.x<D.x
SELECT @t=REPLACE(@t,'|',STUFF(@,1,4,''));WITH A
as(SELECT top(@k)x
FROM(values(65),(66),(67),(68),(69),(70))x(x))SELECT @t+='AND
'+char(A.x)+'.'+char(C.x)+'<>'+CHAR(B.x)+'.'+char(C.x)+' AND
'+char(A.x)+'.n+'+char(A.x)+'.n'+'
not like''%''+'+char(B.x)+'.n+''%'''FROM A,A B,A C
WHERE A.x<>B.x and C.x<>B.x
EXEC(@t)

Try online!

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.