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+;
1##;1#
that prints until the stack runs out \$\endgroup\$