Caddyshack or: How to compress already-golfed code

9

3

In golf, a knowledgable caddie helps an already good golfer to be even better. In this challenge, you build a "caddie" to help you code golf. In particular, your caddie will compress golfed code in such a way that another program can uncompress and then run the code. A good caddie will compress golfed code to be much smaller than the original golfed code. In fact, in caddie-assisted Python (say), you might be able to golf on par with a Jelly golfer!

Formally, a caddie for a language L is a pair (E,D) of programs. The program E takes as input any code c in L and outputs a string s. The program D takes s as input along with any input x of c and returns the output of c(x). We do not require E and D to be written in L. You could say that E is a transpiler that converts c into a version s that runs in the language D. We are interested in transpilers E for which E(c) tends to be smaller than c, even when c is already golfed.

Write a caddie (E,D) for any language L of your choosing. When you first post a caddie here, its score is infinity. Use the following method to update your score:

  • Let C denote the challenge in with at least 10 points that was posted first after your submission.
  • Let c denote the shortest posted solution to C that is written in L.
  • Your score is infinity unless C and c both exist, at which point your score is size(E(c))/size(c).

Recompute your score whenever either C or c changes. Lowest score wins.

Dustin G. Mixon

Posted 2020-01-02T20:26:53.660

Reputation: 1 833

1This is a very nice question imho. – Anush – 2020-01-04T13:45:14.213

I am a bit confused about "The program D takes s as input along with any input x of c and returns the output of c(x)." Does this just mean that D is the inverse of E? Or does D have to work for any caddy? – sugarfi – 2020-01-09T01:08:51.733

@sugarfi - D is designed with E, for E. One possibility is that D uncompresses s to obtain c and then evaluates c on input x. Yes, this conversion from s to c can be thought of as the inverse of E. – Dustin G. Mixon – 2020-01-09T01:13:08.810

Is Japt a valid caddie for JavaScript?

– None – 2020-01-11T14:46:03.773

@a'_' - If there's a program E that converts from JavaScript to Japt, then it's valid, yes. – Dustin G. Mixon – 2020-01-11T23:11:22.263

I have a question about the string s - can it be effectively binary - a set of bytes with values of 0-255 - or should it be restricted to 'bytes that can be printed'. Is it envisioned that s can be printed as 'code' in a Code-Golf post? Do you have a list of characters we should not use? Oh and great challenge. – tom – 2020-01-13T01:03:42.853

@tom - I'm not so picky about s. A set of bytes with values of 0-255 will suffice for this challenge. – Dustin G. Mixon – 2020-01-13T01:19:41.653

Answers

2

Python 3 Caddy, interprets BrainF***

Score: \$\frac{38}{224}\approx0.17\$ (with newlines removed)

Program E

from textwrap import wrap

x = input('Code: ')
i = ['<', '>', '+', '-', '[', ']', '.', ',']
o = ''
for c in x:
    if c in i:
        o += str(i.index(c) + 1)
if o:
    d = wrap(o, 6)
    d = [int(x) for x in d]
    o = ''
    for c in d:
        o += chr(int(c) + 128)
print('Compressed: ', o)

The way this works is by converting every instruction in the input to a digit, then concatenating those digits to a number. Then it splits that number into 6-digit groups and converts each to a Unicode character. (A number higher than 6 could be used, by that would cause errors for large programs). Then it outputs it.

Program D

x = input('Compressed: ')
p = input('Input: ')
p = list(p)
d = ''
for c in x:
    c = ord(c) - 128
    d += str(c)
d = d.replace('-', '')
i = ['<', '>', '+', '-', '[', ']', '.', ',']
o = ''
for n in d:
    n = int(n) - 1
    o += i[n]
tape = [0] * 30000
head = 0
m = {}
m2 = {}
stack = []
for i in range(len(o)):
    char = o[i]
    if char == '[':
        stack.append(i)
    elif char == ']':
        begin = stack.pop()
        m[begin] = i + 1
        m2[i] = begin
i = 0
while i < len(o):
    char = o[i]
    if char == '<':
        head -= 1
        i += 1
    elif char == '>':
        head += 1
        i += 1
    elif char == '+':
        tape[head] += 1
        i += 1
    elif char == '-':
        tape[head] -= 1
        i += 1
    elif char == '[':
        if tape[head] == 0:
            i = m[i]
        else:
            i += 1
    elif char == ']':
        if tape[head] != 0:
            i = m2[i]
        else:
            i += 1
    elif char == '.':
        print(chr(tape[head]), end='')
        i += 1
    elif char == ',':
        try:
            tape[head] = ord(p.pop(0))
        except:
            tape[head] = 0
        i += 1

This is pretty simple, it just reverses the compression algorithm and evaluates the result.

sugarfi

Posted 2020-01-02T20:26:53.660

Reputation: 1 239

FYI - Here is a link to what is currently challenge C for your post, but I don't see a solution coded in BrainF*** yet: https://codegolf.stackexchange.com/questions/197879/convert-a-32-bit-binary-ipv4-address-to-its-quad-dotted-notation

– Dustin G. Mixon – 2020-01-11T00:36:18.130

@DustinG.Mixon - yeah, I checked the new challenges, but none had a solution in BrainF*** – sugarfi – 2020-01-11T00:50:43.537

Also, you are allowed to post a BrainF*** solution to that challenge and then compress it here. – Dustin G. Mixon – 2020-01-11T23:08:53.263

@DustinG.Mixon - ok, I will do that soon – sugarfi – 2020-01-11T23:54:46.023

@DustinG.Mixon - Finally found a BrainF answer! Updating my score now. – sugarfi – 2020-01-16T21:39:17.673

I don't see a BrainF answer for that challenge. Am I missing something? – Dustin G. Mixon – 2020-01-17T04:05:21.250

@DustinG.Mixon - Which challenge? I got this one from "Add two numbers". I would have posted one on a new challenge, but I am not any good at BrainF. – sugarfi – 2020-01-17T21:08:01.637