Sebuah Latin persegi adalah persegi yang ada telah berulang simbol dalam baris atau kolom: .

13420
21304
32041
04213
40132

Dan seperti yang diketahui banyak pemain Sudoku, Anda tidak perlu semua angka untuk menyimpulkan angka yang tersisa.

Tantangan Anda adalah untuk mengompresi kotak Latin ke dalam byte sesedikit mungkin. Anda perlu menyediakan satu atau dua program yang mengkompres / mendekompresi.

Berbagai info:

• Angka-angka yang digunakan akan selalu berada 0..N-1, di mana Npanjang tepi kotak, danN<=25
• Pada dekompresi, kotak latin harus identik dengan input.
• Program Anda harus dapat (de) mengompres setiap kotak latin (dalam ukuran kotak maksimum), bukan hanya yang saya sediakan. Rasio kompresi juga harus serupa.
• Anda benar-benar harus menjalankan kompresi dan dekompresor untuk mendapatkan skor Anda (Tidak ada runtime akhir zaman)

Kasing uji dapat ditemukan di github . Skor Anda adalah ukuran total dari kasus uji terkompresi.

EDIT: Pada 20:07 pada tanggal 7 Juli, saya memperbarui kasus uji (untuk memperbaiki masalah generasi). Silakan jalankan kembali program Anda pada kasus uji baru. Terima kasih Anders Kaseorg .

Python, 1281.375 1268.625 byte

Kami menyandikan satu "keputusan" dalam kotak Latin pada satu waktu, di mana setiap keputusan dari salah satu dari tiga bentuk ini:

• nomor mana yang masuk dalam baris i , kolom j ;
• di baris i , kolom mana yang digunakan k ;
• di kolom j , baris yang mana angka k dimasukkan.

Pada setiap langkah, kami membuat semua kesimpulan logis yang kami dapat berdasarkan pada keputusan sebelumnya, lalu mengambil keputusan dengan jumlah pilihan sekecil mungkin, yang karenanya mengambil jumlah bit terkecil untuk diwakili.

Pilihan disediakan oleh dekoder aritmatika sederhana (div / mod dengan jumlah pilihan). Tapi itu meninggalkan beberapa redundansi dalam pengkodean: jika k decode ke kotak di mana produk dari semua jumlah pilihan adalah m , maka k + m , k + 2⋅ m , k + 3⋅ m , ... decode ke kotak yang sama dengan beberapa kondisi sisa di akhir.

Kami memanfaatkan redundansi ini untuk menghindari penyandian ukuran persegi secara eksplisit. Dekompresor dimulai dengan mencoba men-decode kuadrat ukuran 1. Setiap kali decoder selesai dengan status sisa, ia membuang hasil itu, mengurangi m dari angka asli, menambah ukurannya dengan 1, dan mencoba lagi.

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

Keluaran:

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 byte

Pendekatan ini hanya menghilangkan baris terakhir dan kolom terakhir dari bujur sangkar, dan mengubah setiap entri menjadi kata-kata dengan kedalaman bit tertentu. Kedalaman bit dipilih minimal untuk ukuran persegi yang diberikan. (Saran oleh @KarlNapf) Kata-kata ini hanya ditambahkan satu sama lain. Dekompresi hanyalah kebalikannya.

Jumlah untuk semua kasus uji adalah 23'105 bit atau 2'888,125 byte. (Masih berlaku untuk kasus uji yang diperbarui, karena ukuran output saya hanya tergantung pada ukuran 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

Python 3, 10772 bit (1346,5 byte)

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

Memakan waktu 0,1 detik untuk mengompresi dan mendekompres kasus uji kombinasi.

Verifikasi skor di Ideone .

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, 6052 4521 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)

 #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

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 byte

Namun satu lagi yang menggunakan indeks permutasi ...

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

keluaran

 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 byte

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 mengambil daftar tupel integer dan mengembalikan string.

dateDeCompress mengambil string dan mengembalikan daftar tupel integer.

Singkatnya, untuk setiap baris, program ini mengambil indeks permutasi garis itu dan menyimpannya di basis 36. Dekompresi membutuhkan waktu lama dengan input besar tetapi kompresi sangat cepat bahkan pada input besar.

Pemakaian:

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

hasil: c|4|3|0

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

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

Java, 2310 byte

Kami mengonversi setiap baris kuadrat menjadi angka yang menunjukkan permutasi leksikografis yang menggunakan angka faktoradik, yang juga dikenal sebagai sistem bilangan faktorial , yang berguna untuk permutasi penomoran.

Kami menulis kuadrat ke file biner di mana byte pertama adalah ukuran kuadrat, dan kemudian setiap baris memiliki satu byte untuk jumlah byte dalam representasi biner dari Java BigInteger, diikuti oleh byte dari BigInteger itu.

Untuk membalikkan proses dan mendekompresi kuadrat kita membaca ukuran kembali dan kemudian setiap BigInteger, dan menggunakan nomor itu untuk menghasilkan setiap baris kuadrat.

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 diadaptasi dari kelas yang saya tulis beberapa tahun lalu untuk bekerja dengan permutasi:

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;
    }
}

Pemakaian:

Dengan kotak Latin latin.txt, kompres:

java Latin -c latin.txt latin.compressed

Dan dekompreslah:

java Latin -d latin.compressed latin.decompressed