The 1+ Metagolf Challenge

Question

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

Answer 1

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

• "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

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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!

Answer 6

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