21
\$\begingroup\$

Background

PICASCII is a neat tool that converts images into ASCII art.

It achieves different degrees of brightness by using the following ten ASCII characters:

@#+';:,.` 

We'll say that these charxels (character elements) have brightnesses from 1 (at-sign) to 10 (space).

Below, you can see the results of converting a little code, the Welsh flag, an overhanded fractal, a large trout and a little golf, displayed with the correct font:

ASCII art

Your can see the images in this fiddle and download them from Google Drive.

Task

While the end results of PICASCII are visually pleasing, all five images combined weigh 153,559 bytes. How much could these images be compressed if we are willing to sacrifice part of their quality?

Your task is to write a program that accepts an ASCII art image such as the above ones and a minimum quality as input and prints a lossy compression of the image – in form of a full program or a function returning a single string – that satisfies the quality requirement.

This means that you do not get to write a separate decompressor; it must be built-in into each of the compressed images.

The original image will consist of charxels with brightnesses between 1 and 10, separated by linefeeds into lines of the same length. The compressed image must have the same dimensions and use the same set of characters.

For an uncompressed image consisting of n charxels, the quality of a compressed version of the image is defined as

quality formula

where ci is the brightness of the ith charxel of the compressed image's output and ui the brightness of the ith charxel of the uncompressed image.

Scoring

Your code will be run with the five images from above as input and minimum quality settings of 0.50, 0.60, 0.70, 0.80 and 0.90 for each of the images.

Your score is the geometric mean of the sizes of all compressed images, i.e., the twenty-fifth root of the product of the lengths of all twenty-five compressed images.

The lowest score wins!

Additional rules

  • Your code has to work for arbitrary images, not just the ones used for scoring.

    It is expected that you optimize your code towards the test cases, but a program that does not even attempt to compress arbitrary images won't get an upvote from me.

  • Your compressor may use built-in byte stream compressors (e.g., gzip), but you have to implement them yourself for the compressed images.

    Bulit-ins normally used in byte stream decompressors (e.g., base conversion, run-length decoding) are allowed.

  • Compressor and compressed images do not have to be in the same language.

    However, you must pick a single language for all compressed images.

  • For each compressed image, standard code golf rules apply.

Verification

I've made a CJam script to easily verify all quality requirements and calculate a submission's score.

You can download the Java interpreter from here or here.

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

Example

Bash → PHP, score 30344.0474

cat

Achieves 100% quality for all inputs.

$ 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
\$\endgroup\$
  • \$\begingroup\$ I'm having some trouble understanding this part: If someone chooses q=0.5, then each char in the input file should be replaced by the char with half the brightness in the output, right? Obviously excluding the whitespace since that would mess up the entire image. \$\endgroup\$ – Nicolás Siplis Jul 16 '15 at 7:12
  • 1
    \$\begingroup\$ Its all too confusing and loopholey. How do you stop a mattmahoney.net/dc/barf.html entry? Can the decompressor read any file other than the compressed image too? Can you provide a python script or something that actually checks the quality an image and calculates a score so there can be no quibbles on that front too? Etc. \$\endgroup\$ – Will Jul 16 '15 at 7:47
  • 1
    \$\begingroup\$ @Will Confusing? Maybe. But I don't think it's loopholey. Each compressed image has to be a program or function, so unfunny jokes like BARF are automatically excluded. I don't know Python, but I'll think of something to verification simple. \$\endgroup\$ – Dennis Jul 16 '15 at 14:43
  • 8
    \$\begingroup\$ "I've made a CJam script to easily verify all quality requirements and calculate a submission's score." Do people really use this thing to do normal scripts? Dear lord... \$\endgroup\$ – Fatalize Jul 16 '15 at 18:35
4
\$\begingroup\$

Java → CJam, score ≈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();
        }
    }
}

Requires the CJam jar in the classpath. If you give it 2 command line arguments (file name and quality), it appends ".cjam" to the file name and writes the compressed image there. Otherwise it calculates its score on the 5 test images, which are assumed to be in the current directory. The program also verifies every compressed image automatically. You may want to double-check the score calculation in case there's any discrepancy.

The techniques used (so far) are: scaling to half (horizontally, vertically or both) if it doesn't reduce the quality too much, a custom-coded RLE, and base conversion to pack more data into each character while remaining in the printable ASCII range.

\$\endgroup\$
  • \$\begingroup\$ Could you give me a brief overview on how to run this? I compiled it (successfully, I think) with javac -cp cjam-0.6.5.jar Compress.java, but java -cp cjam-0.6.5.jar Compress says Error: Could not find or load main class Compress and java Compress doesn't find the CJam class. \$\endgroup\$ – Dennis Jun 22 '16 at 21:57
  • \$\begingroup\$ @Dennis You need to add the directory that contains Compress.class to the classpath (-cp). If it's in the current directory, use -cp .:cjam-0.6.5.jar (in windoze I think you need a semicolon instead of a colon) \$\endgroup\$ – aditsu Jun 23 '16 at 4:44
  • \$\begingroup\$ That did the trick, thank you. \$\endgroup\$ – Dennis Jun 23 '16 at 5:03
2
\$\begingroup\$

Python 3.5 (main and output) (currently noncompeting)

Happy Birthday, Challenge! Here's your present: an answer!

EDIT: Converted output to python code, improved compression rate (slightly) EDIT2: Made it print raw when size is 1. Improved score, but score needs to be calculated again. EDIT3: @Dennis pointed out that I still haev bugs to fix, so I marked the answer as noncompeting

Code:

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

This answer could use a lot of improvements, so I'll probably be working on it more over the weekend.

How this works:

  • Divide image into blocks of size size.
  • Find best matching block
    • Blocks can have gradient now!
  • Calculate quality (according to formula) for entire image.
  • If correct, write zipped image to file.
  • Otherwise, decrement size and try again.

This algorithm works well for low quality (0.5, 0.6) but doesn't work too well on the higher quality images (actually inflates). It is also really slow.

Here I have all the generated files, so you won't have to re-generate them again.

\$\endgroup\$
  • \$\begingroup\$ Finally, an answer! It's technically non-competing though, since I created Bubblegum after posting this challenge... I'll run the scoring script later and maybe port it to a less esoteric language. \$\endgroup\$ – Dennis Jun 17 '16 at 1:49
  • \$\begingroup\$ @Dennis Ah, well it shouldn't be too hard to port the output to a python script. Thanks for the heads-up \$\endgroup\$ – Blue Jun 17 '16 at 1:51
  • \$\begingroup\$ I just re-read my challenge (after a year, I was a little fuzzy on the details), and it says Your compressor may use built-in byte stream compressors (e.g., gzip), but you have to implement them yourself for the compressed images. That means Bubblegum is out anyway. \$\endgroup\$ – Dennis Jun 17 '16 at 2:36
  • \$\begingroup\$ I finally remembered I had promised to score this; sorry for the delay. Your code seems to have a typo (comping should be compimg), which I fixed to run the program. Unless I made a mistake when running your code, the dimensions of some of the generated images are incorrect (e.g., image2.txt has 33,164 bytes, but image2-50.0.txt has 33,329) and other do not generate the same file when running the generated programs (image3-50.0.txt has a quality of 0.5110, but running the generated program results in a quality of 0.4508). \$\endgroup\$ – Dennis Jun 22 '16 at 21:43
  • \$\begingroup\$ Addendum: I downloaded image3-50.0.py from your Dropbox and it matches the file I generated. \$\endgroup\$ – Dennis Jun 22 '16 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.