Python, 1281.375 1268.625 바이트

우리는 각 결정이 다음 세 가지 형식 중 하나 인 라틴 정사각형을 한 번에 하나의 “결정”으로 인코딩합니다.

• 행 i , 열 j 에있는 숫자 ;
• 행 i에서 , 숫자 k 가 들어가는 열 ;
• 칼럼에서 J 숫자 열, K가 들어간다.

각 단계에서 이전 결정을 기반으로 할 수있는 모든 논리적 추론을 한 다음 가능한 적은 수의 선택을 통해 결정을 선택하므로 표시 할 비트 수가 가장 적습니다.

선택은 간단한 산술 디코더 (선택 수에 따라 div / mod)에 의해 제공됩니다. 그러나 잎 인코딩 일부 중복 : 만약 K의 선택의 모든 제품 번호이었던 사각으로 디코딩 m은 다음 케이 + m을 , K + 2⋅ m , K + 3⋅ m , … 디코드 동일한 정방형 끝에 남은 상태가 있습니다.

이 중복성을 활용하여 정사각형의 크기를 명시 적으로 인코딩하지 않도록합니다. 압축 해제 기는 크기 1의 제곱을 해독하려고 시도합니다. 디코더가 남은 상태로 끝날 때마다 결과를 버리고 원래 숫자에서 m 을 빼고 크기를 1 씩 증가시킨 후 다시 시도합니다.

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[2].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))

산출:

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

답변

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

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

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

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

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)

 #return to int and determine length
 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[0])+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

from math import factorial

test_data_name = 'latin_squares.txt'

def grid_reader(fname):
    ''' 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[0])
    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 [[0]]
    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))

 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

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[0]
        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[0])

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

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

    return output[:len(output) - 1]

def dataDeCompress(data):
    indexes = data.split("|")
    n = alphabet.index(indexes[0]) + 1
    del indexes[0]

    lst = []

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

    return lst