20
\$\begingroup\$

I'm letting this one out of the sandbox. Hopefully it is well-written and make sense, feel free to improve.

So in order to make 1+ more popular (and ease the creation of golfed 1+ text-printing programs) here comes the metagolf challenge:

The 1+ Language

1+ is a fun deque-based esolang where 1 is the only literal, and other numbers are constructed with operators

It is also "monotonic", that is, it only has the + and * operators, and not - or /

The deque is often referred to as a "stack", and one end of the deques is often referred to as the "top"

Here are the commands:

  • 1 pushes 1
  • + and * pop 2 numbers, and push their sum and product respectively
  • " duplicates the top number
  • / and \ rotate the stack upwards and downwards respectively. That is, / moves the top number to the bottom and \ does the exact reverse
  • ^ swaps the top two numbers
  • < is the only comparison operator (although it probably won't do much in Kolmogorov-complexity challenges)
  • . and , input an integer and a Unicode character respectively, and push it onto the stack. You are not allowed to take input here
  • : and ; output an integer and a Unicode character respectively. In the original interpreter, the : command outputs with a trailing newline, but here we allow both with a trailing newline and without a trailing newline
  • # is a goto-command that pops the top value n, and sends program flow to immediately after the nth # in the current line of execution (where numbering starts from 0)
  • Functions are defined with (name|code) and are called with (name). The name can be empty and the point where they are defined causes their execution too. They are separate lines of execution, so the numbering of #'s in them starts from 0

Original interpreter

Slightly modified interpreter to remove integer output trailing newline

Challenge

Your challenge is to write a program that inputs some text and outputs a 1+ program that outputs the text. The program can be in any language (lesser-known ones preferably), but it must output valid programs for any text.

Do not golf the test cases manually, otherwise I'll change them.

Winning criteria

Your score for a particular test case is your output length divided by the input length. The total score is the sum of the scores of all test cases. The lower, the better.

The test cases are:

  1. "Hello, World!"
  2. We're no strangers to code golf, you know the rules, and so do I
  3. A keyboard so real you can almost TASTE it
  4. Pascal's Tree-angle
\$\endgroup\$
14
  • 3
    \$\begingroup\$ I'm not sure how possible it would be to game the scoring system, but just in case, I'd recommend explicitly disallowing doing so, and saying that you could change the scoring test cases if any answer did try to optimise for them \$\endgroup\$ Aug 13, 2020 at 16:10
  • \$\begingroup\$ @cairdcoinheringaahing You are right, although I thought about it and carefully selected the challenges such that it will take more effort to golf them manually than to write a metagolfer. \$\endgroup\$ Aug 14, 2020 at 1:13
  • 1
    \$\begingroup\$ @cairdcoinheringaahing Optimizing for the given test cases is already a standard loophole, so does not need to be restated here. \$\endgroup\$ Aug 14, 2020 at 2:02
  • 1
    \$\begingroup\$ Well, for example you might generate all the letters onto the stack and then finish tne program with a 1##;1# that prints until the stack runs out \$\endgroup\$
    – Jo King
    Aug 14, 2020 at 11:55
  • 1
    \$\begingroup\$ I'm here.\${}{}{}{}{}\$ \$\endgroup\$ Feb 3, 2022 at 22:14

6 Answers 6

18
\$\begingroup\$

JavaScript (Node.js),  16.26 ... 12.30  12.19

8.31 + 1.13 + 0.91 + 1.84

Saved 1.69 by optimizing the initial code, as suggested by @JoKing
Saved 1.31 by using a precomputed table of code snippets, as suggested by @Mukundan314
Saved 0.11 by counting the patterns more accurately, as suggested by @JoKing

Source

const CHAR_SET =
  " !\"#$%&'*+,-./0123456789:;<=>?@" +
  "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`" +
  "abcdefghijklmnopqrstuvwxyz{}";

const CHAR_MAP = {
  10 : '11+1+"*1+',
  32 : '11+"*"*"+',
  33 : '11+"*"*"+1+',
  34 : '11+"*"*1+"+',
  35 : '11+"*1+"1+1+*',
  36 : '11+1+"+"*',
  37 : '11+1+"+"*1+',
  38 : '11+"1+"+"*+',
  39 : '11+1+""+"*+',
  40 : '11+"*"1+*"+',
  41 : '11+"*1+"1+"*+',
  42 : '11+1+"+"1+*',
  43 : '11+1+"+"1+*1+',
  44 : '11+"*"1+"+1+*',
  45 : '11+1+""1+1+**',
  46 : '11+1+""1+1+**1+',
  47 : '11+"*1+"1+"1+*+',
  48 : '11+1+"1+"**',
  49 : '11+1+"+1+"*',
  50 : '11+"*1+"*"+',
  51 : '11+1+"1+"*1+*',
  52 : '11+1+""+1+"*+',
  53 : '11+1+"1+1+"*"++',
  54 : '11+1+""**"+',
  55 : '11+1+"+"1+"*+',
  56 : '11+1+"+1+"1+*',
  57 : '11+1+""*"+1+*',
  58 : '11+"*"1+"*+"+',
  59 : '11+1+""+1+"1+*+',
  60 : '11+1+"1+"1+**',
  61 : '11+1+"1+"1+**1+',
  62 : '11+1+"+"1+"1+*+',
  63 : '11+1+"""+1+**',
  64 : '11+"*"+"*',
  65 : '11+"*"+"*1+',
  66 : '11+""*"+"*+',
  67 : '11+1+"1+"+"*+',
  68 : '11+"*""*1+*',
  69 : '11+"*""*1+*1+',
  70 : '11+""*""*1+*+',
  71 : '11+1+"+1+"1+"*+',
  72 : '11+1+"+"*"+',
  73 : '11+1+"+"*"+1+',
  74 : '11+1+"+"*1+"+',
  75 : '11+1+"1+1+"**',
  76 : '11+"*""+"1+*+',
  77 : '11+"1+"1+1+"**+',
  78 : '11+1+"+""+1+*',
  79 : '11+1+"+""+1+*1+',
  80 : '11+"*""1+**',
  81 : '11+1+"*"*',
  82 : '11+1+"*"*1+',
  83 : '11+"1+"*"*+',
  84 : '11+1+""*"*+',
  85 : '11+1+""*"*+1+',
  86 : '11+"1+""*"*++',
  87 : '11+1+"""*"*++',
  88 : '11+"*"+"1+1+1+*',
  89 : '11+"*"+"1+"*+',
  90 : '11+1+"*"1+*',
  91 : '11+1+"*"1+*1+',
  92 : '11+"1+"*"1+*+',
  93 : '11+1+""*"1+*+',
  94 : '11+1+""*"1+*+1+',
  95 : '11+"1+""*"1+*++',
  96 : '11+1+"1+"**"+',
  97 : '11+1+"1+"**"+1+',
  98 : '11+1+"+1+"*"+',
  99 : '11+1+"*"1+1+*',
  100: '11+1+"*1+"*',
  101: '11+1+"*1+"*1+',
  102: '11+"1+"*1+"*+',
  103: '11+1+""*1+"*+',
  104: '11+"*"1+"*1+*',
  105: '11+"*1+""+"*+',
  106: '11+1+"""*1+"*++',
  107: '11+""*1+""+"*++',
  108: '11+1+""+"**',
  109: '11+1+"*"1+"*+',
  110: '11+1+"*1+"1+*',
  111: '11+1+""+"*1+*',
  112: '11+1+"+1+"1+*"+',
  113: '11+1+""*1+"1+*+',
  114: '11+1+""+"*1+1+*',
  115: '11+"*1+""+"1+*+',
  116: '11+"*""1+"*+*',
  117: '11+1+"""+"*+*',
  118: '11+1+"*""1+"*++',
  119: '11+1+"*"1+"1+*+',
  120: '11+"*"1+"1+**',
  121: '11+"1+"*+"*',
  122: '11+"1+"*+"*1+',
  123: '11+""1+"*+"*+',
  124: '11+1+""*1+1+"*+',
  125: '11+"*1+""**',
  126: '11+1+""+"1+**'
}

const MAX_WINDOW = 100;

function encode(str) {
  let out = '', cmd = [], stk = [], pos = [];

  Buffer.from(str).forEach((c, i) => {
    let j = stk.indexOf(c);

    if(~j) {
      cmd[pos[j]] = cmd[pos[j]].replace(/;/, '";');
      cmd.push(';');
      stk = stk.slice(0, j);
      pos = pos.slice(0, j);
    }
    else {
      cmd.push(CHAR_MAP[c] + ';');
    }
    stk.push(c);
    pos.push(i);
  });

  out += cmd.join('');

  for(let n = 0;; n++) {
    let id = (function genId(n) {
      return n ? CHAR_SET[n % CHAR_SET.length] + genId(n / CHAR_SET.length | 0) : ''
    })(n);

    let max = 0, best = null, stat = {};

    for(let i = 0; i < out.length; i++) {
      let sub = '', p = 0, c;

      for(let w = 0; w < MAX_WINDOW && (c = out[i + w]); w++) {
        sub += c;
        p += (c == '(') - (c == ')');

        if(p < 0 || c == '|') break;

        if(!p) {
          (stat[sub] = stat[sub] || []).push(i);
        }
      }
    }

    let A = Object.keys(stat).map(sub => {
      let w = sub.length,
          b = ~w,
          cnt = stat[sub].reduce((t, a) => a < b + w ? t : (b = a, t + 1), 0),
          saved = cnt * w - ((cnt - 1) * (id.length + 2) + w + id.length + 3);

      return [ saved, sub, w ];
    })
    .sort((a, b) => b[0] - a[0]);

    if(!A.length) break;

    let [ saved, sub ] = A[0];

    if(saved < 1) break;

    if(saved > max) {
      max = saved;
      best = sub;
    }

    if(best === null) break;

    out =
      out.split(best).map((s, i) =>
        i ? i == 1 ? `(${id}|` + best + ')' + s : `(${id})` + s : s
      ).join('');
  }

  return out;
}

Try it online!

Outputs

How?

Building the code snippets

The table of code snippets CHAR_MAP was built with the following program. This is a brute-force search that keeps the shortest snippet for each character, or the one that contains the most 1's in case of a tie. The idea behind this last rule is to use similar building strategies whenever possible to improve the final compression.

let snippet = {};

(function search(stk, cmd) {
  let n = stk[0];

  if(stk.length == 1 && n < 127) {
    snippet[n] =
      !snippet[n] || (
        snippet[n].length > cmd.length || (
          snippet[n].length == cmd.length &&
          snippet[n].split('1').length < cmd.split('1').length
        )
      ) ?
        cmd
      :
        snippet[n];
  }
  if(cmd.length < 15) {
    if(stk.length >= 2) {
      let a = stk[stk.length - 2], b = stk[stk.length - 1];

      search([...stk.slice(0, -2), a * b], cmd + '*');
      search([...stk.slice(0, -2), a + b], cmd + '+');
    }
    search([...stk, 1], cmd + '1');
    search([...stk, stk[stk.length - 1]], cmd + '"');
  }
})([1, 1], '11');

console.log(snippet);

Try it online!

Optimizing the initial code

The initial code is first optimized by re-using characters that were previously generated whenever possible. For instance, Hello, World! is optimized as:

[H];[e];[l]";";[o]";[,];[ ];[W];;[r];;[d];[!];

where each character within brackets is one of the code snippets generated above.

Compressing the code with functions

We then iteratively look for the sub-string in the code that leads to the highest savings when replaced with a function call.

We make sure that the selected sub-strings have balanced parentheses and do not contain a |.

Below are all the compression steps for "Hello, World!".

Initial code:

11+1+"+"*"+;11+1+"*1+"*1+;11+1+""+"**";";11+1+""+"*1+*";11+"*"1+"+1+*;11+"*"*"+;11+1+"""
*"*++;;11+1+""+"*1+1+*;;11+1+"*1+"*;11+"*"*"+1+;

We replace ;11+1+" with a function with an empty name:

11+1+"+"*"+(|;11+1+")*1+"*1+()"+"**";"()"+"*1+*";11+"*"1+"+1+*;11+"*"*"+()""*"*++;()"+"*
1+1+*;()*1+"*;11+"*"*"+1+;

We replace ;11+"*" with a function named !:

11+1+"+"*"+(|;11+1+")*1+"*1+()"+"**";"()"+"*1+*"(!|;11+"*")1+"+1+*(!)*"+()""*"*++;()"+"*
1+1+*;()*1+"*(!)*"+1+;

We replace ()"+"* with a function named ":

11+1+"+"*"+(|;11+1+")*1+"*1+("|()"+"*)*";"(")1+*"(!|;11+"*")1+"+1+*(!)*"+()""*"*++;(")1+
1+*;()*1+"*(!)*"+1+;
\$\endgroup\$
6
  • \$\begingroup\$ So fast... HOW DID IT WORK????? \$\endgroup\$ Aug 14, 2020 at 8:31
  • \$\begingroup\$ The generated keyboard code is really efficient. Almost like a hand-written one. \$\endgroup\$ Aug 14, 2020 at 12:13
  • \$\begingroup\$ Oh wow, that was way more effective than I was expecting! Another strategy I thought of was to push the whole string to the stack in reverse, and print it all out in a loop at the end with 1##;1#, which will save on all the ;s, but this is incompatible with the duplicate code \$\endgroup\$
    – Jo King
    Aug 14, 2020 at 12:28
  • \$\begingroup\$ @JoKing Speaking of duplicate code I'm working on a stronger version \$\endgroup\$ Aug 15, 2020 at 14:41
  • \$\begingroup\$ @Mukundan314 Thank you for the suggestion! I was able to get -1.31 by building my own table. \$\endgroup\$
    – Arnauld
    Aug 16, 2020 at 15:41
8
\$\begingroup\$

Python 2, 13.62 + 3.18 + 3.17 + 2.90 = 22.87

def gen_prog(inp):
    prog = ''
    inp = map(ord, inp)
    vals = sorted(set(inp))[::-1]
    funcnames = ([''] + sorted(set(map(chr,range(32, 127))) - set('()|~')))[:len(vals)]
    val2funcname = {k:v for (k,v) in zip(sorted(vals, key=lambda c:-inp.count(c)), funcnames)}
    func_defined = {f: False for f in funcnames + ['~']}
    for n in inp:
        f = val2funcname[n]
        frag = '(' + f
        if not func_defined[f]:
            frag += '|1'
            for b in bin(n)[3:]:
                frag += ('(~)' if func_defined['~'] else '(~|"+1+)') if b == '1' else '"+'
                if b == '1': func_defined['~'] = True
            frag += ';'
            func_defined[f] = True
        frag += ')'
        if inp.count(n) == 1: frag = frag[2+len(f):-1]
        prog += frag
    return prog

Hello, World!

We're no strangers...

A keyboard...

Pascal's...

Improved the average score for large test cases by embedding the print command into the functions.


Python 2, 13.62 + 4.00 + 3.87 + 3.65 = 25.14

def gen_prog(inp):
    prog = '1(~|"+1+)'
    inp = map(ord, inp)
    vals = sorted(set(inp))[::-1]
    funcnames = ([''] + sorted(set(map(chr,range(32, 127))) - set('()|~')))[:len(vals)]
    val2funcname = {k:v for (k,v) in zip(sorted(vals, key=lambda c:-inp.count(c)), funcnames)}
    for i,v in enumerate(vals): prog += '(' + val2funcname[v] + '|' + '1'*(i==len(vals)-1)
    for i,v in enumerate(vals[::-1]):
        diff = v - (vals[::-1] + [1])[i-1]
        prog += '1' + bin(diff)[3:].replace('0', '"+').replace('1', '(~)') + '+)'
    for n in inp: prog += '(' + val2funcname[n] + ');'
    return prog

Hello, World!

We're no strangers...

A keyboard...

Pascal's...

Basically wraps every char that appears in the output into a named function. Almost every ASCII printable character is OK for function name, so we don't need any two-char names, and one of them can be zero-char, which is assigned to the most frequent character.

\$\endgroup\$
4
  • \$\begingroup\$ how on earth did you do this \$\endgroup\$ Aug 14, 2020 at 8:14
  • \$\begingroup\$ @HighlyRadioactive Mine is still relatively naive. Arnauld's is a real beast. \$\endgroup\$
    – Bubbler
    Aug 14, 2020 at 8:30
  • 1
    \$\begingroup\$ @HighlyRadioactive And mine is still far from optimal because it applies only one kind of heuristic. Hello, World! alone can obviously be compressed much better -- and the way the scoring system is designed, it has a significant impact on the final score. \$\endgroup\$
    – Arnauld
    Aug 14, 2020 at 9:31
  • \$\begingroup\$ I designed it that way is because, I want it to matter a lot. \$\endgroup\$ Aug 14, 2020 at 10:27
3
\$\begingroup\$

C++, Score = Whatever

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <cctype>

using namespace std;
vector<char> a[256], code;
stack<unsigned long long> st;
int max_depth;
void constant_gen(int depth) {
    if (depth == max_depth) {
        if (st.top() < 256 && a[st.top()].empty()) {
            a[st.top()] = code;
        }
        return;
    }
    st.push(1); code.push_back('1');
    constant_gen(depth+1);
    st.pop(); code.pop_back();
    if (st.size() >= 1) {
        st.push(st.top()); code.push_back('"');
        constant_gen(depth+1);
        st.pop(); code.pop_back();
    }
    if (st.size() >= 2) {
        int h = st.top(); st.pop();
        int r = st.top(); st.pop();
        st.push(h + r); code.push_back('+');
        constant_gen(depth+1);
        st.pop(); code.pop_back();
        st.push(r); st.push(h);
        
        h = st.top(); st.pop();
        r = st.top(); st.pop();
        st.push(h * r); code.push_back('*');
        constant_gen(depth+1);
        st.pop(); code.pop_back();
        st.push(r); st.push(h);
    }
}
int main() {
    char ch;
    max_depth = 1;
    for (int i=0; i<5; i++) {
        a[0].push_back("11+1<"[i]);
    }
    while (max_depth < 16) {
        constant_gen(0);
        max_depth += 2;
    }
    while ((ch = getchar()) != EOF) {
        if (isdigit(ch)) {
            ch = ch - '0';
        }
        for (int i=0; i<a[ch].size(); i++) {
            cout << a[ch][i];
        }
        if (ch < 10) {
            cout << ":";
        } else {
            cout << ";";
        }
    }
    return 0;
}

Most of the code generates the constant table.

\$\endgroup\$
0
2
\$\begingroup\$

Python 2, 14.15 + 13.40 + 13.61 13.55 + 11.85 10.01 = 53.01 51.11

def gen_prog(inp):
    prog = '1(|"+1+)'
    
    parts = []
    prev_int = False

    for c in inp:
        if prev_int and c.isdigit():
            parts[-1] += c
        elif c.isdigit() and c != '0':
            prev_int = True
            parts.append(c)
        else:
            prev_int = False
            parts.append(c)

    for c in parts:
        if c == '0':
            prog += "11+1<:"
        elif c[0].isdigit():
            prog += '1' + bin(int(c))[3:].replace('0', '"+').replace('1', '()') + ':'
        else:
            prog += '1' + bin(ord(c))[3:].replace('0', '"+').replace('1', '()') + ';'

    return prog

Hello, World!
We're no strangers to code golf, you know the rules, and so do I
A keyboard so real you can almost TASTE it
Pascal's Tree-angle

\$\endgroup\$
1
  • \$\begingroup\$ Impressive! Let's see if I can beat this... \$\endgroup\$ Aug 14, 2020 at 7:09
2
\$\begingroup\$

MAWP, 173.69 + ? + ? + ? points

%[25W|]%%0~%[{![1A1:]%1A[1A76W1M;]%69W5M;}]

This submission only uses the 1 and + and ; instructions. Not very efficient, but works reliably.

Hello, World! all by itself took 10 minutes to run and give output. The result was 2258 bytes, and the rest of the strings are way bigger.

I think it's better for my computer not to run any more of the test cases.

Try it!

\$\endgroup\$
8
  • \$\begingroup\$ So you use MAWP to golf 1+... I still can't enter chatrooms. \$\endgroup\$ Aug 14, 2020 at 11:01
  • 3
    \$\begingroup\$ more like bowling 1+. Maybe you should try asking a mod via email. \$\endgroup\$
    – Razetime
    Aug 14, 2020 at 11:26
  • \$\begingroup\$ Mod won't help because this happens on all SE site chatroom. \$\endgroup\$ Aug 14, 2020 at 11:32
  • \$\begingroup\$ @HighlyRadioactive For the record, all SE mods can help with issues like that if they happen in future. \$\endgroup\$
    – wizzwizz4
    Aug 14, 2020 at 12:55
  • \$\begingroup\$ @wizzwizz4 More likely a problem on my site because it sometimes magically disappear like now (although I suspect it might be temporary) \$\endgroup\$ Aug 14, 2020 at 12:57
1
\$\begingroup\$

Python 3, 10.08 + ? + ? + 5.36 points

Code is a bit slow, still running tests.

import itertools
from difflib import SequenceMatcher

string = '''Hello, World!'''

def create_constants(string):
    chars = ['1','"','+','*']
    g = list(set(string))
    combinations = []
    consts = []
    nums = []
    for i in range(2,13):
        combinations.extend(list(map(''.join, itertools.product(chars, repeat=i))))

    print('Generated combinations')
    codes = [ord(i) for i in g]
    for combination in combinations:
        stack = [2]
        for char in combination:
            try:
                if char == '1':
                    stack.append(1)
                elif char == '+':
                    stack.append(stack.pop() + stack.pop())
                elif char == '*':
                    stack.append(stack.pop() * stack.pop())
                elif char == '"':
                    stack.append(stack[-1])
            except:
                pass
            if stack != [] and stack[-1] in codes:
                nums.append(stack[-1])
                codes.remove(stack[-1])
                consts.append('11+'+combination)
                if codes == []:
                    return consts, nums

in_order = []
consts, nums = create_constants(string)
for i in string:
    in_order.append(consts[nums.index(ord(i))])
code = ";".join(in_order) + ';'
substring_counts={}

f=lambda s,n:max(l:=[s[j:j+n]for j in range(len(s))],key=l.count)
k = {}
for i in list(range(2,len(code)))[::-1]:
    d = f(code,i)
    if code.count(d) > 1:
        saved = len(d) * code.count(d) - 4 - ((code.count(d) + 1) * 2)
        if saved > 0:
            k[d] = saved
try:
    most_occuring = max(k, key=k.get)
    code = code.replace(most_occuring, '()')
    code = code.replace('()','(|' +  most_occuring + ')',1)
except:
    pass
print(code)

This is my first answer to a question of such kind. I'm also quite inexperienced, but with the combined forces of my knowledge and stackoverflow I managed to make something half-decent :D

\$\endgroup\$
1
  • \$\begingroup\$ That's almost as unfair as MAWP! \$\endgroup\$ Aug 21, 2020 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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