tło

PICASCII to zgrabne narzędzie, które konwertuje obrazy do sztuki ASCII.

Osiąga różne stopnie jasności, używając następujących dziesięciu znaków ASCII:

@#+';:,.` 

Powiemy, że te znaki (elementy postaci) mają jasność od 1 (znak) do 10 (spacja).

Poniżej można zobaczyć wyniki konwersji małego kodu, flagi walijskiej, przeładowanego fraktala, dużego pstrąga i małego golfa, wyświetlanych z poprawną czcionką:

Możesz zobaczyć obrazy w tym skrzypce i pobrać je z Dysku Google .

Zadanie

Podczas gdy końcowe wyniki PICASCII są przyjemne wizualnie, wszystkie pięć obrazów łącznie waży 153.559 bajtów. Jak bardzo można skompresować te obrazy, jeśli chcemy poświęcić część ich jakości?

Twoim zadaniem jest napisanie programu, który akceptuje obraz artystyczny ASCII, taki jak powyższy i minimalną jakość jako dane wejściowe, i drukuje stratną kompresję obrazu - w postaci pełnego programu lub funkcji zwracającej pojedynczy ciąg znaków - który spełnia wymóg jakości.

Oznacza to, że nie musisz pisać osobnego dekompresora; musi być wbudowany w każdy skompresowany obraz.

Oryginalny obraz będzie składał się z znaków o jasności od 1 do 10, oddzielonych liniami do linii o tej samej długości. Skompresowany obraz musi mieć te same wymiary i używać tego samego zestawu znaków.

W przypadku nieskompresowanego obrazu składającego się z n znaków, jakość skompresowanej wersji obrazu jest zdefiniowana jako

gdzie c _i to jasność i- ^tego znaku wyjściowego skompresowanego obrazu, a u _i jasność i- ^tego znaku wyjściowego skompresowanego obrazu.

Punktacja

Twój kod będzie uruchamiany z pięcioma obrazami z góry jako wejściowymi i minimalnymi ustawieniami jakości 0,50, 0,60, 0,70, 0,80 i 0,90 dla każdego z obrazów.

Twój wynik jest średnią geometryczną rozmiarów wszystkich skompresowanych obrazów, tj. Dwudziestego piątego pierwiastka iloczynu długości wszystkich dwudziestu pięciu skompresowanych obrazów.

Najniższy wynik wygrywa!

Dodatkowe zasady

• Twój kod musi działać w przypadku dowolnych obrazów, a nie tylko tych używanych do oceniania.

  Oczekuje się, że zoptymalizujesz swój kod pod kątem przypadków testowych, ale program, który nawet nie próbuje kompresować dowolnych obrazów, nie otrzyma ode mnie opinii.

• Twój kompresor może używać wbudowanych kompresorów strumienia bajtów (np. Gzip), ale musisz sam je wdrożyć dla skompresowanych obrazów.

  Wbudowane zwykle używane w dekompresorach strumienia bajtów (np. Konwersja bazy, dekodowanie długości przebiegu) są dozwolone.

• Kompresor i skompresowane obrazy nie muszą być w tym samym języku.

  Musisz jednak wybrać jeden język dla wszystkich skompresowanych obrazów.

• Do każdego skompresowanego obrazu obowiązują standardowe reguły gry w golfa.

Weryfikacja

Stworzyłem skrypt CJam, aby łatwo zweryfikować wszystkie wymagania jakościowe i obliczyć wynik zgłoszenia.

Możesz pobrać interpreter Java tutaj lub tutaj .

e# URLs of the uncompressed images.
e# "%s" will get replaced by 1, 2, 3, 4, 5.

"file:///home/dennis/codegolf/53199/original/image%s.txt"

e# URLs of the compressed images (source code).
e# "%s-%s" will get replaced by "1-50", "1-60", ... "5-90".

"file:///home/dennis/codegolf/53199/code/image%s-%s.php"

e# URLs of the compressed images (output).

"file:///home/dennis/codegolf/53199/output/image%s-%s.txt"

e# Code

:O;:C;:U;5,:)
{
    5,5f+Af*
    {
        C[IQ]e%g,X*:X;
        ISQS
        [U[I]e%O[IQ]e%]
        {g_W=N&{W<}&}%
        _Nf/::,:=
        {
            {N-"@#+';:,.` "f#}%z
            _::m2f#:+\,81d*/mq1m8#
            _"%04.4f"e%S
            @100*iQ<"(too low)"*
        }{
            ;"Dimension mismatch."
        }?
        N]o
    }fQ
}fI
N"SCORE: %04.4f"X1d25/#e%N

Przykład

Bash → PHP, wynik 30344.0474

cat

Osiąga 100% jakości dla wszystkich nakładów.

$ java -jar cjam-0.6.5.jar vrfy.cjam
1 50 1.0000 
1 60 1.0000 
1 70 1.0000 
1 80 1.0000 
1 90 1.0000 
2 50 1.0000 
2 60 1.0000 
2 70 1.0000 
2 80 1.0000 
2 90 1.0000 
3 50 1.0000 
3 60 1.0000 
3 70 1.0000 
3 80 1.0000 
3 90 1.0000 
4 50 1.0000 
4 60 1.0000 
4 70 1.0000 
4 80 1.0000 
4 90 1.0000 
5 50 1.0000 
5 60 1.0000 
5 70 1.0000 
5 80 1.0000 
5 90 1.0000 

SCORE: 30344.0474

Java → CJam, wynik 17 4417.89

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import net.aditsu.cjam.CJam;

public class Compress {
    protected static final char[] DIGITS = "0123456789ABCDEFGHIJK".toCharArray();
    protected static final String CHARS = "@#+';:,.` ";
    protected static final char[] CHR = CHARS.toCharArray();

    private static class Img {
        public final int rows;
        public final int cols;
        public final int[][] a;

        public Img(final int rows, final int cols) {
            this.rows = rows;
            this.cols = cols;
            a = new int[rows][cols];
        }

        public Img(final List<String> l) {
            rows = l.size();
            cols = l.get(0).length();
            a = new int[rows][cols];
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    a[i][j] = CHARS.indexOf(l.get(i).charAt(j));
                }
            }
        }

        public static Img read(final Reader r) {
            try {
                final BufferedReader br = new BufferedReader(r);
                final List<String> l = new ArrayList<>();
                while (true) {
                    final String s = br.readLine();
                    if (s == null || s.isEmpty()) {
                        break;
                    }
                    l.add(s);
                }
                br.close();
                return new Img(l);
            }
            catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public static Img read(final File f) {
            try {
                return read(new FileReader(f));
            }
            catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public Img scaleDown(final int fr, final int fc) {
            final int r1 = (rows + fr - 1) / fr;
            final int c1 = (cols + fc - 1) / fc;
            final Img x = new Img(r1, c1);
            final int[][] q = new int[r1][c1];
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    x.a[i / fr][j / fc] += a[i][j];
                    q[i / fr][j / fc]++;
                }
            }
            for (int i = 0; i < r1; ++i) {
                for (int j = 0; j < c1; ++j) {
                    x.a[i][j] /= q[i][j];
                }
            }
            return x;
        }

        public Img scaleUp(final int fr, final int fc) {
            final int r1 = rows * fr;
            final int c1 = cols * fc;
            final Img x = new Img(r1, c1);
            for (int i = 0; i < r1; ++i) {
                for (int j = 0; j < c1; ++j) {
                    x.a[i][j] = a[i / fr][j / fc];
                }
            }
            return x;
        }

        public Img crop(final int r, final int c) {
            if (r == rows && c == cols) {
                return this;
            }
            final Img x = new Img(r, c);
            for (int i = 0; i < r; ++i) {
                for (int j = 0; j < c; ++j) {
                    x.a[i][j] = a[i][j];
                }
            }
            return x;
        }

        public Img rescale(final int fr, final int fc) {
            return scaleDown(fr, fc).scaleUp(fr, fc).crop(rows, cols);
        }

        public double quality(final Img x) {
            if (x.rows != rows || x.cols != cols) {
                throw new IllegalArgumentException();
            }
            double t = 0;
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    final int y = a[i][j] - x.a[i][j];
                    t += y * y;
                }
            }
            t /= 81 * rows * cols;
            t = 1 - Math.sqrt(t);
            return Math.pow(t, 8);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    sb.append(CHR[a[i][j]]);
                }
                sb.append('\n');
            }
            return sb.toString();
        }

        public Array toArray() {
            final Array x = new Array(rows * cols);
            int k = 0;
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    x.a[k++] = a[i][j];
                }
            }
            return x;
        }

        public String compress(final double quality) {
            int bi = 1;
            int bj = 1;
            int bs = rows * cols;
            Img bx = this;

            for (int i = 1; i < 3; ++i) {
                for (int j = 1; j < 3; ++j) {
                    Img x = rescale(i, j);
                    if (quality(x) >= quality) {
                        x = scaleDown(i, j);
                        if (x.rows * x.cols < bs) {
                            bi = i;
                            bj = j;
                            bs = x.rows * x.cols;
                            bx = x;
                        }
                    }
                }
            }

            Array a = bx.toArray();
            int bf = 0;
            for (int i = 1; i <= 20; ++i) {
                final int t = a.rle11(i).n;
                if (t < bs) {
                    bs = t;
                    bf = i;
                }
            }

            int b = 10;
            if (bf > 0) {
                b = 11;
                a = a.rle11(bf);
            }

            String s = null;
            for (int i = 92; i < 97; ++i) {
                for (char c = ' '; c < '$'; ++c) {
                    final String t = a.cjamBase(b, i, c);
                    boolean ok = true;
                    for (int j = 0; j < t.length(); ++j) {
                        if (t.charAt(j) > '~') {
                            ok = false;
                            break;
                        }
                    }
                    if (!ok) {
                        continue;
                    }
                    if (s == null || t.length() < s.length()) {
                        s = t;
                    }
                }
            }

            if (bf > 0) {
                s += "{(_A={;()";
                if (bf > 1) {
                    s += DIGITS[bf] + "*";
                }
                s += "\\(a@*}&\\}h]e_";
            }
            if (bi * bj == 1) {
                return s + '"' + CHARS + "\"f=" + cols + "/N*";
            }
            s += bx.cols + "/";
            if (bi > 1) {
                s += bi + "e*";
                if (rows % 2 == 1) {
                    s += "W<";
                }
            }
            if (bj > 1) {
                s += bj + "fe*";
                if (cols % 2 == 1) {
                    s += "Wf<";
                }
            }
            return s + '"' + CHARS + "\"ff=N*";
        }

        public void verify(final String s, final double quality) {
            final String t = CJam.run(s, "");
            final Img x = read(new StringReader(t));
            final double q = quality(x);
            if (q < quality) {
                throw new RuntimeException(q + " < " + quality);
            }
//          System.out.println(q + " >= " + quality);
        }
    }

    private static class Array {
        public final int[] a;
        public final int n;

        public Array(final int n) {
            this.n = n;
            a = new int[n];
        }

        public Array(final int[] a) {
            this.a = a;
            n = a.length;
        }

        public String join() {
            final StringBuilder sb = new StringBuilder();
            for (int x : a) {
                sb.append(x).append(' ');
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }

//      public String cjamStr() {
//          final StringBuilder sb = new StringBuilder("\"");
//          for (int x : a) {
//              sb.append(DIGITS[x]);
//          }
//          sb.append("\":~");
//          return sb.toString();
//      }

        public String cjamBase(final int m, final int b, final char c) {
            final boolean zero = a[0] == 0;
            String s = join();
            if (zero) {
                s = "1 " + s;
            }
            s = CJam.run("q~]" + m + "b" + b + "b'" + c + "f+`", s);
            s += "'" + c + "fm" + b + "b" + DIGITS[m] + "b";
            if (zero) {
                s += "1>";
            }
            return s;
        }

        public Array rle11(final int f) {
            final int[] b = new int[n];
            int m = 0;
            int x = -1;
            int k = 0;
            for (int i = 0; i <= n; ++i) {
                final int t = i == n ? -2 : a[i];
                if (t == x && m < 11 * f) {
                    m++;
                }
                else {
                    if (m >= f && m > 3) {
                        b[k++] = 10;
                        b[k++] = m / f - 1;
                        b[k++] = x;
                        for (int j = 0; j < m % f; ++j) {
                            b[k++] = x;
                        }
                    }
                    else {
                        for (int j = 0; j < m; ++j) {
                            b[k++] = x;
                        }
                    }
                    m = 1;
                    x = t;
                }
            }
            return new Array(Arrays.copyOf(b, k));
        }
    }

    private static void score() {
        double p = 1;
        for (int i = 1; i < 6; ++i) {
            final File f = new File("image" + i + ".txt");
            final Img img = Img.read(f);
            final int n = (int) f.length();
            for (int j = 5; j < 10; ++j) {
                final double q = j / 10.0;
                final String s = img.compress(q);
                System.out.println(f.getName() + ", " + q + ": " + n + " -> " + s.length());
                img.verify(s, q);
                p *= s.length();
            }
        }
        System.out.println(Math.pow(p, 1 / 25.0));
    }

    public static void main(final String... args) {
        if (args.length != 2) {
            score();
            return;
        }
        final String fname = args[0];
        final double quality = Double.parseDouble(args[1]);
        try {
            final Img img = Img.read(new File(fname));
            final String s = img.compress(quality);
            img.verify(s, quality);
            final FileWriter fw = new FileWriter(fname + ".cjam");
            fw.write(s);
            fw.close();
        }
        catch (IOException e) {
            throw new RuntimeException();
        }
    }
}

Wymaga słoika CJam w ścieżce klasy. Jeśli podasz mu 2 argumenty wiersza poleceń (nazwę i jakość pliku), dopisze „.cjam” do nazwy pliku i zapisze tam skompresowany obraz. W przeciwnym razie oblicza swój wynik na 5 obrazach testowych, które, jak się zakłada, znajdują się w bieżącym katalogu. Program automatycznie weryfikuje również każdy skompresowany obraz. W razie jakichkolwiek rozbieżności możesz ponownie sprawdzić obliczenia wyniku.

Stosowane techniki (jak dotąd) to: skalowanie do połowy (poziomo, pionowo lub oba), jeśli nie obniża to zbytnio jakości, niestandardowo zakodowany RLE i konwersja bazy, aby spakować więcej danych do każdego znaku, pozostając w zakres ASCII do wydruku.

Python 3.5 (główny i wyjściowy) (obecnie niekonkurencyjny)

Wszystkiego najlepszego, wyzwanie! Oto twój prezent: odpowiedź!

EDYCJA: Przekształcono dane wyjściowe na kod Pythona, poprawiono stopień kompresji (nieznacznie) EDYCJA 2: Sprawiło, że drukowało się na surowo, gdy sizema 1. Poprawiony wynik, ale wynik należy ponownie obliczyć. EDIT3: @Dennis wskazał, że wciąż mam błędy do naprawienia, więc oznaczyłem odpowiedź jako niekonkurencyjną

Kod:

import sys
LIST = [' ','`','.',',',':',';',"'",'+','#','@']

def charxel_to_brightness(charxel):
    return LIST.index(charxel)

def brightness_to_charxel(bright):
    return LIST[bright]

def image_to_brightness(imagetext):
    return [list(map(charxel_to_brightness,line)) for line in imagetext.split("\n")]

def brightness_to_image(brightarray):
    return '\n'.join([''.join(map(brightness_to_charxel,line)) for line in brightarray])

def split_into_parts(lst,size):
    return [lst[x:x+size] for x in range(0, len(lst), size)]

def gen_updown(startxel,endxel,size):
    return [[int((size-r)*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]

def gen_leftright(startxel,endxel,size):
    return [[int((size-c)*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]

def gen_tlbr(startxel,endxel,size):
    return [[int((2*size-r-c)/2*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]

def gen_bltr(startxel,endxel,size):
    return [[int((size-r+c)/2*(endxel-startxel)/size+startxel) for c in range(size)] for r in range(size)]

def gen_block(code,startxel,endxel,size):
    if code==0:return gen_updown(startxel,endxel,size)
    if code==1:return gen_leftright(startxel,endxel,size)
    if code==2:return gen_bltr(startxel,endxel,size)
    if code==3:return gen_tlbr(startxel,endxel,size)

def vars_to_data(code,startxel,endxel):
    acc=endxel
    acc+=startxel<<4
    acc+=code<<8
    return acc

def data_to_vars(data):
    code=data>>8
    startxel=(data>>4)&15
    endxel=data&15
    return code,startxel,endxel

def split_into_squares(imgarray,size):
    rows = split_into_parts(imgarray,size)
    allsquares = []
    for rowblock in rows:
        splitrows = []
        for row in rowblock:
            row = split_into_parts(row,size)
            splitrows.append(row)
        rowdict = []
        for row in splitrows:
            for x in range(len(row)):
                if len(rowdict)<=x:
                    rowdict.append([])
                rowdict[x].append(row[x])
        allsquares.append(rowdict)
    return allsquares

def calc_quality(imgarray,comparray):
    acc=0
    for row in range(len(imgarray)):
        for col in range(len(imgarray[row])):
            acc+=pow(imgarray[row][col]-comparray[row][col],2)
    return (1-(acc/81.0/sum([len(row) for row in imgarray]))**.5)**8

def fuse_squares(squarray):
    output=[]
    counter=0
    scounter=0
    sqrow=0
    while sqrow<len(squarray):
        if scounter<len(squarray[sqrow][0]):
            output.append([])
            for square in squarray[sqrow]:
                output[counter].extend(square[scounter])
            scounter+=1
            counter+=1
        else:
            scounter=0
            sqrow+=1
    return output

def main_calc(imgarray,threshold):
    imgarray = image_to_brightness(imgarray)
    size = 9
    quality = 0
    compimg=[]
    datarray=[]
    testdata = [vars_to_data(c,s,e) for c in range(4) for s in range(10) for e in range(10)]
    while quality<threshold:
        squares = split_into_squares(imgarray,size)
        compimg = []
        datarray = []
        testblock = [gen_block(c,s,e,size) for c in range(4) for s in range(10) for e in range(10)]
        for row in squares:
            comprow = []
            datrow=[]
            for square in row:
                quality_values = [calc_quality(square,block) for block in testblock]
                best_quality = quality_values.index(max(quality_values))
                comprow.append(testblock[best_quality])
                datrow.append(testdata[best_quality])
            compimg.append(comprow)
            datarray.append(datrow)
        compimg = fuse_squares(compimg)
        quality = calc_quality(imgarray,compimg)
        print("Size:{} Quality:{}".format(size,quality))
        size-=1
    return brightness_to_image(compimg),datarray,size+1

template = '''def s(d,s,e,z):
 x=range(z)
 return d<1 and[[int((z-r)*(e-s)/z+s)for c in x]for r in x]or d==1 and[[int((z-c)*(e-s)/z+s)for c in x]for r in x]or d==2 and[[int((2*z-r-c)/2*(e-s)/z+s)for c in x]for r in x]or d>2 and[[int((z-r+c)/2*(e-s)/z+s)for c in x] for r in x]
i=lambda a:'\\n'.join([''.join(map(lambda r:" `.,:;'+#@"[r],l))for l in a])
def f(a):
 o=[];c=0;s=0;r=0
 while r<len(a):
  if s<len(a[r][0]):
   o.append([])
   for q in a[r]:
    o[c].extend(q[s])
   s+=1;c+=1
  else:
   s=0;r+=1
 return o
t={};z={}
print(i(f([[s(D>>8,(D>>4)&15,D&15,z)for D in R]for R in t])))'''

template_size_1 = '''print("""{}""")'''   

def main(filename,threshold):
    print(filename+" "+str(threshold))
    file = open(filename,'r')
    compimg,datarray,size = main_calc(file.read(),threshold)
    file.close()
    textoutput = open(filename.split(".")[0]+"-"+str(threshold*100)+".txt",'w')
    textoutput.write(compimg)
    textoutput.close()
    compoutput = open(filename.split(".")[0]+"-"+str(threshold*100)+".py",'w')
    datarray = str(datarray).replace(" ","")
    code = ""
    if size==1:
        code = template_size_1.format(compimg)
    else:
        code= template.format(datarray,str(size))
    compoutput.write(code)
    compoutput.close()
    print("done")

if __name__ == "__main__":
    main(sys.argv[1],float(sys.argv[2]))

Ta odpowiedź mogłaby przydać wiele ulepszeń, więc prawdopodobnie będę pracować nad nią więcej w weekend.

Jak to działa:

• Podziel obraz na bloki wielkości size.
• Znajdź najlepiej pasujący blok
  • Bloki mogą teraz mieć gradient!
• Oblicz jakość (według wzoru) dla całego obrazu.
• Jeśli jest poprawny, zapisz spakowany obraz do pliku.
• W przeciwnym razie zmniejsz sizei spróbuj ponownie.

Ten algorytm działa dobrze dla niskiej jakości (0,5, 0,6), ale nie działa zbyt dobrze na obrazach o wyższej jakości (w rzeczywistości się zawęża). Jest również bardzo powolny.

Tutaj mam wszystkie wygenerowane pliki, więc nie będziesz musiał ponownie ich generować.