# Latin square compression

A Latin square is a square that has no repeated symbols in the rows or columns:.

13420
21304
32041
04213
40132


And as many Sudoku players know, you don't need all of the numbers to deduce the remaining numbers.

Your challenge is to compress a Latin square into as few bytes as possible. You need to provide one or two program(s) that compresses/decompresses.

Various info:

• The numbers used will always be 0..N-1, where N is the length of the square's edge, and N<=25
• On decompression, the latin square must be identical to the input.
• Your program(s) should be able to (de)compress any latin square (within the maximum square size), not just the ones I've provided. Compression ratios should be similar as well.
• You must actually run the compression and decompressor to obtain your score (No end-of-universe runtimes)

The test cases can be found on github. Your score is total size of compressed test cases.

EDIT: As of 20:07 on July 7th, I updated the test cases (in order to fix a generation issue). Please rerun your program on the new test cases. Thanks Anders Kaseorg.

• Well, by definition, any symbol could be used, but my test cases just happen to use 0 though n-1 :) – Nathan Merrill Jul 12 '16 at 12:51
• – feersum Jul 12 '16 at 12:54
• @NathanMerrill well, the point was only being allowed to use n different symbols. :P – Martin Ender Jul 12 '16 at 12:57
• @DavidC It shouldn't matter, as the size is measured in bytes. – flawr Jul 12 '16 at 13:39
• 19 of your 25 test cases (all those except 4, 6, 8, 10, 12, 14) were generated by permuting the rows and columns of the trivial Latin square whose (i, j) entry is i + j mod n. This makes them very easy to compress much more than a random Latin square. Although your rules say we should have similar compression ratios for all Latin squares, this might be easy to break by accident. The test cases should be more representative. – Anders Kaseorg Jul 12 '16 at 19:55

# Python, 1281.375 1268.625 bytes

We encode the Latin square one “decision” at a time, where each decision is of one of these three forms:

• which number goes in row i, column j;
• in row i, which column the number k goes in;
• in column j, which row the number k goes in.

At each step, we make all the logical inferences we can based on previous decisions, then pick the decision with the smallest number of possible choices, which therefore take the smallest number of bits to represent.

The choices are provided by a simple arithmetic decoder (div/mod by the number of choices). But that leaves some redundancy in the encoding: if k decodes to a square where the product of all the numbers of choices was m, then k + m, k + 2⋅m, k + 3⋅m, … decode to the same square with some leftover state at the end.

We take advantage of this redundancy to avoid explicitly encoding the size of the square. The decompressor starts by trying to decode a square of size 1. Whenever the decoder finishes with leftover state, it throws out that result, subtracts m from the original number, increases the size by 1, and tries again.

import numpy as np

class Latin(object):
def __init__(self, size):
self.size = size
self.possible = np.full((size, size, size), True, dtype=bool)
self.count = np.full((3, size, size), size, dtype=int)
self.chosen = np.full((3, size, size), -1, dtype=int)

def decision(self):
axis, u, v = np.unravel_index(np.where(self.chosen == -1, self.count, self.size).argmin(), self.count.shape)
if self.chosen[axis, u, v] == -1:
ws, = np.rollaxis(self.possible, axis)[:, u, v].nonzero()
return axis, u, v, list(ws)
else:
return None, None, None, None

def choose(self, axis, u, v, w):
t = [u, v]
t[axis:axis] = [w]
i, j, k = t
assert self.possible[i, j, k]
assert self.chosen[0, j, k] == self.chosen[1, i, k] == self.chosen[2, i, j] == -1

self.count[1, :, k] -= self.possible[:, j, k]
self.count[2, :, j] -= self.possible[:, j, k]
self.count[0, :, k] -= self.possible[i, :, k]
self.count[2, i, :] -= self.possible[i, :, k]
self.count[0, j, :] -= self.possible[i, j, :]
self.count[1, i, :] -= self.possible[i, j, :]
self.count[0, j, k] = self.count[1, i, k] = self.count[2, i, j] = 1
self.possible[i, j, :] = self.possible[i, :, k] = self.possible[:, j, k] = False
self.possible[i, j, k] = True
self.chosen[0, j, k] = i
self.chosen[1, i, k] = j
self.chosen[2, i, j] = k

def encode_sized(size, square):
square = np.array(square, dtype=int)
latin = Latin(size)
chosen = np.array([np.argmax(square[:, :, np.newaxis] == np.arange(size)[np.newaxis, np.newaxis, :], axis=axis) for axis in range(3)])
num, denom = 0, 1
while True:
axis, u, v, ws = latin.decision()
if axis is None:
break
w = chosen[axis, u, v]
num += ws.index(w)*denom
denom *= len(ws)
latin.choose(axis, u, v, w)
return num

def decode_sized(size, num):
latin = Latin(size)
denom = 1
while True:
axis, u, v, ws = latin.decision()
if axis is None:
break
if not ws:
return None, 0
latin.choose(axis, u, v, ws[num % len(ws)])
num //= len(ws)
denom *= len(ws)
return latin.chosen.tolist(), denom

def compress(square):
size = len(square)
assert size > 0
num = encode_sized(size, square)
while size > 1:
size -= 1
square, denom = decode_sized(size, num)
num += denom
return '{:b}'.format(num + 1)[1:]

def decompress(bits):
num = int('1' + bits, 2) - 1
size = 1
while True:
square, denom = decode_sized(size, num)
num -= denom
if num < 0:
return square
size += 1

total = 0
with open('latin_squares.txt') as f:
while True:
square = [list(map(int, l.split(','))) for l in iter(lambda: next(f), '\n')]
if not square:
break

bits = compress(square)
assert set(bits) <= {'0', '1'}
assert square == decompress(bits)
print('Square {}: {} bits'.format(len(square), len(bits)))
total += len(bits)

print('Total: {} bits = {} bytes'.format(total, total/8.0))


Output:

Square 1: 0 bits
Square 2: 1 bits
Square 3: 3 bits
Square 4: 8 bits
Square 5: 12 bits
Square 6: 29 bits
Square 7: 43 bits
Square 8: 66 bits
Square 9: 94 bits
Square 10: 122 bits
Square 11: 153 bits
Square 12: 198 bits
Square 13: 250 bits
Square 14: 305 bits
Square 15: 363 bits
Square 16: 436 bits
Square 17: 506 bits
Square 18: 584 bits
Square 19: 674 bits
Square 20: 763 bits
Square 21: 877 bits
Square 22: 978 bits
Square 23: 1097 bits
Square 24: 1230 bits
Square 25: 1357 bits
Total: 10149 bits = 1268.625 bytes

• I'm trying this code at ideone, but it just gives runtime errors. I modified it using stdin instead of file f. ideone.com/fKGSQd – edc65 Jul 13 '16 at 17:10
• @edc65 It doesn't work because Ideone's NumPy is outdated. – Dennis Jul 13 '16 at 19:01
• @edc65 Ideone has NumPy 1.8.2 which is too old for np.stack(). In this case it can be replaced with np.array([…]), and I have done so in the current version. – Anders Kaseorg Jul 13 '16 at 22:05
• hmmm. are all the squares stored in one byte stream? is the information about their size also stored, or the decoder assumes that they are of size 1,2,3,… etc? – Display Name Aug 27 '16 at 7:11
• @SargeBorsch Each square is compressed to a separate bitstream. The decompressor recovers the square size unambiguously from the bit stream, using the algorithm I described. No assumption is used. – Anders Kaseorg Aug 27 '16 at 19:35

# Python 3, 10772 bits (1346.5 bytes)

def compress(rows):
columns = list(zip(*rows))
size = len(rows)
symbols = range(size)
output = size - 1
weight = 25
for i in symbols:
for j in symbols:
choices = set(rows[i][j:]) & set(columns[j][i:])
output += weight * sorted(choices).index(rows[i][j])
weight *= len(choices)
return bin(output + 1)[3:]

def decompress(bitstring):
number = int('1' + bitstring, 2) - 1
number, size = divmod(number, 25)
size += 1
symbols = range(size)
rows = [[None] * size for _ in symbols]
columns = [list(column) for column in zip(*rows)]
for i in symbols:
for j in symbols:
choices = set(symbols) - set(rows[i]) - set(columns[j])
number, index = divmod(number, len(choices))
rows[i][j] = columns[j][i] = sorted(choices)[index]
return rows


Takes 0.1 seconds to compress and decompress the combined test cases.

Verify the score on Ideone.

• Woah, care to explain? – Nathan Merrill Jul 12 '16 at 17:54
• In a nutshell, the compressor travels through the square in reading order, keeping track of the symbols that already appeared in that row and column, and arithmetically encoding the index of the symbol in the ascending list of possible symbols. I'll add a detailed explanation after cleaning my code up a bit and testing if bijective base 256 saves any bytes. – Dennis Jul 12 '16 at 17:57
• I'm not completety sure what your code is doing, but isn't it possible to leave the last line out and solve it while decompressing? – Yytsi Jul 12 '16 at 18:12
• @TuukkaX When there's only one possible symbol len(possible) is 1 and possible.index(rows[i][j]) is 0, so that symbol is encoded at no cost. – Dennis Jul 12 '16 at 18:36
• Yay, the new test cases saved 6 bits. :) – Dennis Jul 12 '16 at 20:43

# MATLAB, 3'062.5 2'888.125 bytes

This approach just ditches the last row and the last column of the square, and converts each entry into words of a certain bit depth. The bit depth is chosen minimal for the given size square. (Suggestion by @KarlNapf) These words are just appended to each other. Decompression is just the reverse.

The sum for all the test cases is 23'105 bits or 2'888.125 bytes. (Still holds for the updated test cases, as the size of my outputs is only dependent of the size of the input.)

function bin=compress(a)
%get rid of last row and column:
s=a(1:end-1,1:end-1);
s = s(:)';
bin = [];
%choose bit depth:
bitDepth = ceil(log2(numel(a(:,1))));
for x=s;
bin = [bin, dec2bin(x,bitDepth)];
end
end

function a=decompress(bin)
%determine bit depth
N=0;
f=@(n)ceil(log2(n)).*(n-1).^2;
while f(N)~= numel(bin)
N=N+1;
end
bitDepth = ceil(log2(N));
%binary to decimal:
assert(mod(numel(bin),bitDepth)==0,'invalid input length')
a=[];
for k=1:numel(bin)/bitDepth;
number = bin2dec([bin(bitDepth*(k-1) + (1:bitDepth)),' ']);
a = [a,number];
end
n = sqrt(numel(a));
a = reshape(a,n,n);
disp(a)
%reconstruct last row/column:
n=size(a,1)+1;
a(n,n)=0;%resize
%complete rows:
v = 0:n-1;
for k=1:n
a(k,n) = setdiff(v,a(k,1:n-1));
a(n,k) = setdiff(v,a(1:n-1,k));
end
end

• You could compress a little more by using a variable bitrate, like forn=9..16 4 bits are enough. – Karl Napf Jul 12 '16 at 15:06
• @KarlNapf How do you discriminate the different length words then? As far as I know you then need additional prefixes, don't you? – flawr Jul 12 '16 at 15:13
• Not variable inside one compression, more like depending on the size of the square. If n>16 then use 5 bits fixed, if 8<n<=16 use 4 bits fixed and so on. – Karl Napf Jul 12 '16 at 15:44
• Oh right this makes sense, thank you! – flawr Jul 12 '16 at 15:55
• For the same reason you're doing it the other way around, it's probobably the way you're used to. =) – flawr Jul 12 '16 at 17:32

# J, 2444 bytes

Relies on the builtin A. to convert to and from a permutation of integers [0, n) and a permutation index.

### Compress, 36 bytes

({:a.)joinstring<@(a.{~255&#.inv)@A.


The input is a 2d array representing the Latin square. Each row is converted to a permutation index, and that index is converted to a list of base 255 digits and replaced with an ASCII value. Each string is then joined using the ASCII character at 255.

### Decompress, 45 bytes

[:(A.i.@#)[:(_&,(255&#.&x:);._1~1,255&=)u:inv


Splits the input string at each ASCII value of 255, and parse each group as base 255 digits. Then using the number of groups, create a list of integers [0, length) and permute it according to each index and return it as a 2d array.

# Python, 60524521 3556 bytes

compress takes the square as a multiline string, just like the examples and returns a binary string, whereas decompress does the opposite.

import bz2
import math

def compress(L):
if L=="0":
C = []
else:
#split elements
elems=[l.split(',') for l in L.split('\n')]
n=len(elems)
#remove last row and col
cropd=[e[:-1] for e in elems][:-1]
C = [int(c) for d in cropd for c in d]

#turn to string
B=map(chr,C)
B=''.join(B)

#compress if needed
if len(B) > 36:
BZ=bz2.BZ2Compressor(9)
BZ.compress(B)
B=BZ.flush()

return B

def decompress(C):

#decompress if needed
if len(C) > 40:
BZ=bz2.BZ2Decompressor()
C=BZ.decompress(C)

C = map(ord,C)
n = int(math.sqrt(len(C)))
if n==0: return "0"

#reshape to list of lists
elems = [C[i:i+n] for i in xrange(0, len(C), n)]

#determine target length
n = len(elems)+1
L = []
#restore last column
for i in xrange(n-1):
S = {j for j in range(n)}
L.append([])
for e in elems[i]:
L[i].append(e)
S.remove(e)
L[i].append(S.pop())
#restore last row
L.append([])
for col in xrange(n):
S = {j for j in range(n)}
for row in xrange(n-1):
S.remove(L[row][col])
L[-1].append(S.pop())
#merge elements
orig='\n'.join([','.join([str(e) for e in l]) for l in L])
return orig


Remove the last row+column and zip the rest.

• Edit1: well base64 does not seem necessary
• Edit2: now converting the chopped table into a binary string and compress only if necessary

# Python 3, 1955 bytes

Yet another one that uses permutation indices...

from math import factorial

test_data_name = 'latin_squares.txt'

''' Read CSV number grids; grids are separated by empty lines '''
grid = []
with open(fname) as f:
for line in f:
line = line.strip()
if line:
grid.append([int(u) for u in line.split(',') if u])
elif grid:
yield grid
grid = []
if grid:
yield grid

def show(grid):
a = [','.join([str(u) for u in row]) for row in grid]
print('\n'.join(a), end='\n\n')

def perm(seq, base, k):
''' Build kth ordered permutation of seq '''
seq = seq[:]
p = []
for j in range(len(seq) - 1, 0, -1):
q, k = divmod(k, base)
p.append(seq.pop(q))
base //= j
p.append(seq)
return p

def index(p):
''' Calculate index number of sequence p,
which is a permutation of range(len(p))
'''
#Generate factorial base code
fcode = [sum(u < v for u in p[i+1:]) for i, v in enumerate(p[:-1])]

#Convert factorial base code to integer
k, base = 0, 1
for j, v in enumerate(reversed(fcode), 2):
k += v * base
base *= j
return k

def encode_latin(grid):
num = len(grid)
fbase = factorial(num)

#Encode grid rows by their permutation index,
#in reverse order, starting from the 2nd-last row
codenum = 0
for row in grid[-2::-1]:
codenum = codenum * fbase + index(row)
return codenum

def decode_latin(num, codenum):
seq = list(range(num))
sbase = factorial(num - 1)
fbase = sbase * num

#Extract rows
grid = []
for i in range(num - 1):
codenum, k = divmod(codenum, fbase)
grid.append(perm(seq, sbase, k))

#Build the last row from the missing element of each column
allnums = set(seq)
grid.append([allnums.difference(t).pop() for t in zip(*grid)])
return grid

byteorder = 'little'

def compress(grid):
num = len(grid)
codenum = encode_latin(grid)
length = -(-codenum.bit_length() // 8)
numbytes = num.to_bytes(1, byteorder)
codebytes = codenum.to_bytes(length, byteorder)
return numbytes + codebytes

def decompress(codebytes):
numbytes, codebytes= codebytes[:1], codebytes[1:]
num = int.from_bytes(numbytes, byteorder)
if num == 1:
return []
else:
codenum = int.from_bytes(codebytes, byteorder)
return decode_latin(num, codenum)

total = 0
for i, grid in enumerate(grid_reader(test_data_name), 1):
#show(grid)
codebytes = compress(grid)
length = len(codebytes)
total += length
newgrid = decompress(codebytes)
ok = newgrid == grid
print('{:>2}: Length = {:>3}, {}'.format(i, length, ok))
#print('Code:', codebytes)
#show(newgrid)

print('Total bytes: {}'.format(total))


output

 1: Length =   1, True
2: Length =   1, True
3: Length =   2, True
4: Length =   3, True
5: Length =   5, True
6: Length =   7, True
7: Length =  11, True
8: Length =  14, True
9: Length =  20, True
10: Length =  26, True
11: Length =  33, True
12: Length =  41, True
13: Length =  50, True
14: Length =  61, True
15: Length =  72, True
16: Length =  84, True
17: Length =  98, True
18: Length = 113, True
19: Length = 129, True
20: Length = 147, True
21: Length = 165, True
22: Length = 185, True
23: Length = 206, True
24: Length = 229, True
25: Length = 252, True
Total bytes: 1955


## Python3 - 3,572 3,581 bytes

from itertools import *
from math import *

def int2base(x,b,alphabet='0123456789abcdefghijklmnopqrstuvwxyz'):
if isinstance(x,complex):
return (int2base(x.real,b,alphabet) , int2base(x.imag,b,alphabet))
if x<=0:
if x==0:return alphabet
else:return  '-' + int2base(-x,b,alphabet)
rets=''
while x>0:
x,idx = divmod(x,b)
rets = alphabet[idx] + rets
return rets

def lexicographic_index(p):
result = 0
for j in range(len(p)):
k = sum(1 for i in p[j + 1:] if i < p[j])
result += k * factorial(len(p) - j - 1)
return result

def getPermutationByindex(sequence, index):
S = list(sequence)
permutation = []
while S != []:
f = factorial(len(S) - 1)
i = int(floor(index / f))
x = S[i]
index %= f
permutation.append(x)
del S[i]
return tuple(permutation)

alphabet = "abcdefghijklmnopqrstuvwxyz"

def dataCompress(lst):
n = len(lst)

output = alphabet[n-1]+"|"

for line in lst:
output += "%s|" % int2base(lexicographic_index(line), 36)

return output[:len(output) - 1]

indexes = data.split("|")
n = alphabet.index(indexes) + 1
del indexes

lst = []

for index in indexes:
if index != '':
lst.append(getPermutationByindex(range(n), int(index, 36)))

return lst


dataCompress takes a list of integer tuples and returns a string.

dateDeCompress takes a string and returns a list of integer tuples.

In short, for each line, this program takes that lines permutation index and saves it in base 36. Decompressing takes a long time with big inputs but compression is really fast even on big inputs.

## Usage:

dataCompress([(2,0,1),(1,2,0),(0,1,2)])

result: c|4|3|0

dataDeCompress("c|4|3|0")

result: [(2, 0, 1), (1, 2, 0), (0, 1, 2)]

• You'd probably get a lot better runtime if you didn't wrap your permutations calls in list calls - permutations returns a generator, which lazily generates all the permutations, but if you try to make it into a list, it eagerly generates all the permutations, which takes a very long time. – user45941 Jul 12 '16 at 15:27
• Could you explain a bit better how to use your code? – user45941 Jul 12 '16 at 15:32
• @Mego Sure, maybe I'll implement the lazy evaluation also, although it's still fairly uncomputable. – Yytsi Jul 12 '16 at 15:33
• – user45941 Jul 12 '16 at 15:35
• – user45941 Jul 13 '16 at 6:02

# Java, 2310 bytes

We convert each row of the square to a number representing which lexicographic permutation it is using factoradic numbers, also known as a factorial number system, which is useful for numbering permutations.

We write the square to a binary file where the first byte is the size of the square, and then each row has one byte for the number of bytes in the binary representation of a Java BigInteger, followed by the bytes of that BigInteger.

To reverse the process and decompress the square we read the size back and then each BigInteger, and use that number to generate each row of the square.

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Latin {
public static void main(String[] args) {
if (args.length != 3) {
System.out.println("java Latin {-c | -d} infile outfile");
} else if (args.equals("-c")) {
compress(args, args);
} else if (args.equals("-d")) {
decompress(args, args);
} else {
throw new IllegalArgumentException(
"Invalid mode: " + args + ", not -c or -d");
}
}

public static void compress(String filename, String outname) {
try (OutputStream os =
new BufferedOutputStream(new FileOutputStream(outname))) {
if (line == null) return;
int size = line.split(",").length;
if (size > 127) throw new ArithmeticException(
"Overflow: square too large");
Permutor perm = new Permutor(size);
os.write((byte) size); // write size of square

do {
List<Integer> nums = Arrays.stream(line.split(","))
.map(Integer::new)
.collect(Collectors.toList());
byte[] bits = perm.which(nums).toByteArray();
os.write((byte) bits.length); // write length of bigint
os.write(bits); // write bits of bigint
} while ((line = br.readLine()) != null);
}
} catch (IOException e) {
System.out.println("Error compressing " + filename);
e.printStackTrace();
}
}

public static void decompress(String filename, String outname) {
try (BufferedInputStream is =
new BufferedInputStream(new FileInputStream(filename))) {
try (BufferedWriter bw =
Files.newBufferedWriter(Paths.get(outname))) {
int size = is.read(); // size of latin square
Permutor perm = new Permutor(size);
for (int i = 0; i < size; ++i) {
int num = is.read(); // number of bytes in bigint
if (num == -1) {
throw new IOException(
"Unexpected end of file reading " + filename);
}
byte[] buf = new byte[num];
throw new IOException(
"Unexpected end of file reading " + filename);
}
String row = perm.nth(new BigInteger(buf)).stream()
.map(Object::toString)
.collect(Collectors.joining(","));
bw.write(row);
bw.newLine();
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
}


Permutor is adapted from a class I wrote a few years ago to work with permutations:

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.math.BigInteger;
import static java.math.BigInteger.ZERO;
import static java.math.BigInteger.ONE;

public class Permutor {
private final List<Integer> items;

public Permutor(int n) {
items = new ArrayList<>();
for (int i = 0; i < n; ++i) items.add(i);
}

public BigInteger size() {
return factorial(items.size());
}

private BigInteger factorial(int x) {
BigInteger f = ONE;
for (int i = 2; i <= x; ++i) {
f = f.multiply(BigInteger.valueOf(i));
}
return f;
}

public List<Integer> nth(long n) {
return nth(BigInteger.valueOf(n));
}

public List<Integer> nth(BigInteger n) {
if (n.compareTo(size()) > 0) {
throw new IllegalArgumentException("too high");
}
n = n.subtract(ONE);
List<Integer> perm = new ArrayList<>(items);
int offset = 0, size = perm.size() - 1;
while (n.compareTo(ZERO) > 0) {
BigInteger fact = factorial(size);
BigInteger mult = n.divide(fact);
n = n.subtract(mult.multiply(fact));
int pos = mult.intValue();
Integer t = perm.get(offset + pos);
perm.remove((int) (offset + pos));
--size;
++offset;
}
return perm;
}

public BigInteger which(List<Integer> perm) {
BigInteger n = ONE;
List<Integer> copy = new ArrayList<>(items);
int size = copy.size() - 1;
for (Integer t : perm) {
int pos = copy.indexOf(t);
if (pos < 0) throw new IllegalArgumentException("invalid");
copy.remove((int) pos);
--size;
}
return n;
}
}


Usage:

With a Latin square in latin.txt, compress it:

java Latin -c latin.txt latin.compressed


And decompress it:

java Latin -d latin.compressed latin.decompressed