Łaciński kwadrat jest kwadratem, który nie powtórzył symboli w rzędach lub kolumnach: .

13420
21304
32041
04213
40132

I jak wie wielu graczy Sudoku, nie potrzebujesz wszystkich liczb, aby wydedukować pozostałe liczby.

Twoim zadaniem jest skompresowanie łacińskiego kwadratu do jak najmniejszej liczby bajtów. Musisz podać jeden lub dwa programy, które kompresują / dekompresują.

Różne informacje:

• Zawsze będą używane liczby 0..N-1, gdzie Njest długość krawędzi kwadratu, iN<=25
• Podczas dekompresji kwadrat łaciński musi być identyczny z danymi wejściowymi.
• Twój program (programy) powinien móc (de) kompresować dowolny kwadrat łaciński (w ramach maksymalnego rozmiaru kwadratu), a nie tylko te, które podałem. Wskaźniki kompresji również powinny być podobne.
• Musisz faktycznie uruchomić kompresję i dekompresor, aby uzyskać wynik (bez środowisk uruchomieniowych na końcu wszechświata)

Przypadki testowe można znaleźć na github . Twój wynik to całkowity rozmiar skompresowanych przypadków testowych.

EDYCJA: Od 20:07 7 lipca zaktualizowałem przypadki testowe (w celu rozwiązania problemu z generacją). Uruchom ponownie program w nowych przypadkach testowych. Dzięki Anders Kaseorg .

Python, 1281.375 1266825 bajtów

Kodujemy na łacinę jedną „decyzję” naraz, przy czym każda decyzja ma jedną z tych trzech form:

• która liczba idzie w wierszu i , kolumnie j ;
• w wierszu i , w której kolumnie wpisuje się liczba k ;
• w kolumnie j , w którym wierszu wchodzi liczba k .

Na każdym etapie dokonujemy wszystkich logicznych wniosków na podstawie wcześniejszych decyzji, a następnie wybieramy decyzję przy użyciu jak najmniejszej liczby możliwych wyborów, które w związku z tym reprezentują najmniejszą liczbę bitów.

Wybory są zapewniane przez prosty dekoder arytmetyczny (div / mod przez liczbę wyborów). Ale to pozostawia pewną nadmiarowość w kodowaniu: jeśli k dekoduje do kwadratu, w którym iloczyn wszystkich liczb wyborów wynosił m , to k + m , k + 2⋅ m , k + 3⋅ m ,… dekoduje do tego samego kwadratu z resztkami na końcu.

Korzystamy z tej nadmiarowości, aby uniknąć jawnego kodowania wielkości kwadratu. Dekompresor rozpoczyna od próby odkodowania kwadratu o rozmiarze 1. Ilekroć dekoder kończy stan resztki, wyrzuca ten wynik, odejmuje m od pierwotnej liczby, zwiększa rozmiar o 1 i próbuje ponownie.

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))

Wydajność:

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

MATLAB, 3'062,5 2'888,125 bajtów

To podejście po prostu porzuca ostatni rząd i ostatnią kolumnę kwadratu i przekształca każdy wpis w słowa o określonej głębokości bitowej. Głębokość bitów jest wybierana minimalnie dla danego rozmiaru kwadratu. (Sugestia @KarlNapf) Te słowa są po prostu dołączane do siebie. Dekompresja jest odwrotna.

Suma dla wszystkich przypadków testowych wynosi 23'105 bitów lub 2'888,125 bajtów. (Nadal obowiązuje dla zaktualizowanych przypadków testowych, ponieważ rozmiar moich wyników zależy tylko od wielkości danych wejściowych.)

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

Python 3, 10772 bity (1346,5 bajtów)

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

Kompresja i dekompresja połączonych przypadków testowych zajmuje 0,1 sekundy.

Sprawdź wynik w Ideone .

J , 2444 bajty

Polega na wbudowanym A.konwertowaniu na i z permutacji liczb całkowitych [0, n) i indeksu permutacji.

Kompresuj, 36 bajtów

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

Dane wejściowe to tablica 2d reprezentująca kwadrat łaciński. Każdy wiersz jest konwertowany na indeks permutacji, a ten indeks jest konwertowany na listę podstawowych 255 cyfr i zastępowany wartością ASCII. Każdy ciąg jest następnie łączony przy użyciu znaku ASCII w 255.

Dekompresuj, 45 bajtów

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

Dzieli łańcuch wejściowy na każdą wartość ASCII równą 255 i analizuje każdą grupę jako podstawowe 255 cyfr. Następnie, korzystając z liczby grup, utwórz listę liczb całkowitych [0, długość) i permutuj ją zgodnie z każdym indeksem i zwróć jako tablicę 2d.

Python, 6052 4521 3556 bajtów

compressprzyjmuje kwadrat jako ciąg wielowierszowy, podobnie jak w przykładach i zwraca ciąg binarny, podczas gdy decompressrobi odwrotnie.

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

Usuń ostatni wiersz + kolumnę i spakuj resztę.

• Edycja1: dobrze base64nie wydaje się konieczne
• Edycja2: teraz konwertuje posiekaną tabelę na ciąg binarny i kompresuje tylko w razie potrzeby

Python 3, 1955 bajtów

Jeszcze inny, który wykorzystuje wskaźniki permutacji ...

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))

wydajność

 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 3581 bajtów

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

dataCompress pobiera listę krotek całkowitych i zwraca ciąg znaków.

dateDeCompress pobiera ciąg i zwraca listę krotek całkowitych.

Krótko mówiąc, dla każdej linii program pobiera indeks permutacji linii i zapisuje go w bazie 36. Dekompresja zajmuje dużo czasu przy dużych wejściach, ale kompresja jest naprawdę szybka nawet przy dużych wejściach.

Stosowanie:

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

wynik: c|4|3|0

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

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

Java, 2310 bajtów

Konwertujemy każdy wiersz kwadratu na liczbę reprezentującą, która permutacja leksykograficzna używa liczb czynnikowych, znanych również jako system liczb czynnikowych , który jest przydatny do permutacji numeracji.

Zapisujemy kwadrat do pliku binarnego, w którym pierwszy bajt ma rozmiar kwadratu, a następnie każdy wiersz ma jeden bajt na liczbę bajtów w binarnej reprezentacji BigInteger Java, a następnie bajty tej BigInteger.

Aby odwrócić proces i zdekompresować kwadrat, odczytujemy rozmiar z powrotem, a następnie każdą BigInteger i używamy tej liczby do generowania każdego wiersza kwadratu.

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[0].equals("-c")) {
            compress(args[1], args[2]);
        } else if (args[0].equals("-d")) {
            decompress(args[1], args[2]);
        } else {
            throw new IllegalArgumentException(
                "Invalid mode: " + args[0] + ", not -c or -d");
        }
    }

    public static void compress(String filename, String outname) {
        try (BufferedReader br = Files.newBufferedReader(Paths.get(filename))) {
            try (OutputStream os =
                    new BufferedOutputStream(new FileOutputStream(outname))) {
                String line = br.readLine();
                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];
                    int read = is.read(buf); // read bits of bigint into buf
                    if (read != 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) {
            System.out.println("Error reading " + filename);
            e.printStackTrace();
        }
    }
}

Permutor jest przystosowany z klasy, którą napisałem kilka lat temu, do pracy z permutacjami:

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));
            perm.add(offset, t);
            --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");
            n = n.add(factorial(size).multiply(BigInteger.valueOf(pos)));
            copy.remove((int) pos);
            --size;
        }
        return n;
    }
}

Stosowanie:

Z kwadratem łacińskim latin.txt, ściśnij:

java Latin -c latin.txt latin.compressed

I rozpakuj to:

java Latin -d latin.compressed latin.decompressed