C++, score: 9708
Uses an A*-like search algorithm (i.e. what used to be A* but was tweaked a lot so that it doesn't run out of RAM and searches fast enough, at the cost of finding non-optimal solutions), where the possible actions from a state are:
- Print a character (if it's the next character needed)
- Execute a precomputed sequence of commands to push the next character needed onto the stack
- Execute a precomputed sequence of commands to change the top of the stack number to the next character needed
- Duplicate the top of the stack, as long as that won't increase its size beyond 5
- Swap the top 2 items on the stack
- Rotate the top 3 items on the stack
Uses an algorithm extremely similar to the one used in MegaTom's Ruby answer to compute the sequences of commands mentioned (however it's slightly better, as it uses more possible transitions).
Doesn't handle digits as special, easier-to-print characters; the score would be even lower if it would.
The complete source code:
#include <x86intrin.h>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>
//std::string shortestpath(int from, int to);
//std::string shortestpath(int to);
std::string shortestpath(int to, bool grown = false);
std::string shortestpath(int from, int to, bool grown = false);
std::map<std::pair<int,int>, std::pair<std::string, bool>> cache2;
std::map<int, std::pair<std::string, bool>> cache1;
std::string shortestpath(int to, bool grown)
{
if(cache1.count(to) && (grown || cache1[to].second == false)) return cache1[to].first;
std::vector<std::string> paths;
paths.push_back(std::string(to + 6, ' ')); paths[0].back() = '+';
for(int i = 1; i < to - 1; i++)
paths.push_back(shortestpath(i, grown) + shortestpath(i, to, grown));
cache1[to] = {*std::min_element(paths.begin(), paths.end(), [](auto a, auto b){return a.size() < b.size();}), false};
return cache1[to].first;
}
std::string shortestpath(int from, int to, bool grown)
{
if(to > 512 || from > 512) return "qwertyuiopqwertyuiopqwertyuiopqwertyuioqwertyuiopqweryuiopqwertyuiopqwertyuiopqwertyuioqwertyuiopqwertyuiopqwertyuiopqwertyuiopqwertyuiop";
//printf("from=%d, to=%d\n", from, to);
if(cache2.count({from, to}) && (grown || cache2[{from, to}].second == false)) return cache2[{from, to}].first;
std::vector<std::string> paths;
if(from == to) paths.push_back("");
if(from > to) paths.push_back(shortestpath(from - to, grown) + " *");
if(from > to && from > 0) paths.push_back(" + *" + shortestpath(0, to, grown));
if(from > to && from > 1) paths.push_back(" + *" + shortestpath(1, to, grown));
//if(from > to) paths.push_back(" +" + shortestpath(to, grown));
if(from > to)
for(int i = to + 1; i < from; i++)
{
if(from % i == to) paths.push_back(shortestpath(i, grown) + " *");
if(from / i == to) paths.push_back(shortestpath(i, grown) + " *");
}
if(from < to && from > 1 && (from*from <= to || !grown))
{
bool ng = from*from > to;
paths.push_back(" + *" + shortestpath(from*from, to, grown | ng));
}
if(from < to && from > 0 && (from+from <= to || !grown))
{
bool ng = from+from > to;
paths.push_back(" +*" + shortestpath(from+from, to, grown | ng));
}
if(from < to && from > 1 && to >= 2 * from) paths.push_back(" +"+shortestpath(from,to/from, grown)+" *" + shortestpath(to/from*from, to, grown));
if(from < to && from > 1 && to >= 2 * from && !grown)
{
bool ng = (to/from+1) * from > to;
paths.push_back(" +" + shortestpath(from, to/from + 1, grown + ng) + " *" + shortestpath((to/from+1)*from, to, ng));
}
if(from < to && from > 0 && to >= 2*from) paths.push_back(" +"+shortestpath(from,to-from, grown)+"*");
if(from < to) paths.push_back(shortestpath(to-from, grown)+"*");
cache2[{from, to}] = {*std::min_element(paths.begin(), paths.end(), [](auto a, auto b){return a.size() < b.size();}), grown};
return cache2[{from, to}].first;
}
std::string target;
struct astate
{
std::vector<int> stack;
int i = 0;
int heur() const
{
return 3 * (target.size() - i);
}
bool operator < (const astate& rhs) const
{
if(i != rhs.i) return i > rhs.i;
return stack < rhs.stack;
}
};
struct sstate
{
astate as;
int f;
bool operator < (const sstate& rhs) const
{
if(f != rhs.f) return f < rhs.f;
if(as.heur() != rhs.as.heur()) return as.heur() < rhs.as.heur();
return as < rhs.as;
}
};
int metagolf(std::string target)
{
std::map<int, int> icounts;
int hw = 2;
::target = target;
sstate start = {{{}, 0}, 0};
std::map<astate, std::pair<astate, std::string>> prev;
std::map<astate, int> dists; dists[start.as] = 0;
std::set<sstate> openset; openset.insert(start);
bool done = false;
//int itsleft = 100;
astate beststate = start.as;
while(!openset.empty())
{
auto it = openset.begin();
auto[cs, cf] = *it; openset.erase(it);
icounts[cs.i]++;
if(icounts[cs.i + 3] > 250) continue; //{ printf("continuing: i=%d\n", cs.i); continue; }
int cd = dists[cs];
if(cs.i == target.size()) { done = true; beststate = cs; break; };
//print
if(!cs.stack.empty() && cs.stack.back() == target[cs.i])
{
auto next = cs;
int dist = cd + 2;
next.i++; next.stack.pop_back();
if(dists.count(next) == 0 || dist < dists[next])
{
dists[next] = dist;
openset.insert({next, dist + hw*next.heur()});
prev[next] = {cs, " ."};
}
}
//shortestpath from
if(!cs.stack.empty())
{
auto next = cs;
std::string path = shortestpath(cs.stack.back(), target[cs.i]);
int dist = cd + path.size();
next.stack.back() = target[cs.i];
if(dists.count(next) == 0 || dist < dists[next])
{
dists[next] = dist;
openset.insert({next, dist + hw*next.heur()});
prev[next] = {cs, path};
}
}
//shortestpath to
{
auto next = cs;
std::string path = shortestpath(target[cs.i]);
int dist = cd + path.size();
next.stack.push_back(target[cs.i]);
if(dists.count(next) == 0 || dist < dists[next])
{
dists[next] = dist;
openset.insert({next, dist + hw*next.heur()});
prev[next] = {cs, path};
}
}
//dup if size below 5
if(!cs.stack.empty() && cs.stack.size() < 5)
{
auto next = cs;
int dist = cd + 2;
next.stack.push_back(next.stack.back());
if(dists.count(next) == 0 || dist < dists[next])
{
dists[next] = dist;
openset.insert({next, dist + hw*next.heur()});
prev[next] = {cs, " +"};
}
}
//swap
if(cs.stack.size() >= 2)
{
auto next = cs;
int dist = cd + 3;
std::swap(next.stack.back(), next.stack[next.stack.size() - 2]);
if(dists.count(next) == 0 || dist < dists[next])
{
dists[next] = dist;
openset.insert({next, dist + hw*next.heur()});
prev[next] = {cs, " +"};
}
}
//rot
if(cs.stack.size() >= 3)
{
auto next = cs;
int dist = cd + 4;
std::swap(next.stack.back(), next.stack[next.stack.size() - 2]);
std::swap(next.stack[next.stack.size() - 3], next.stack[next.stack.size() - 2]);
if(dists.count(next) == 0 || dist < dists[next])
{
dists[next] = dist;
openset.insert({next, dist + hw*next.heur()});
prev[next] = {cs, " +"};
}
}
}
astate cur = beststate;
std::vector<std::string> code;
while(cur < start.as || start.as < cur)
{
auto[pr, path] = prev[cur];
code.push_back(path);
cur = pr;
}
std::reverse(code.begin(), code.end());
std::string ans;
for(auto s : code) ans += s;
printf("%s\n", ans.data());
return ans.size();
}
int main()//int64_t argc, char*argv[])
{
int ans = 0;
for(int from = 0; from < 256; from++)
for(int to = 0; to < 256; to++)
{
auto p = shortestpath(from, to);
int len = p.size();
ans += len;
//if(len < 35) continue;
//printf("%d->%d: %d\n", from, to, p.size());
//printf("%s\n", p.data());
}
printf("total length of all transitions within [0, 256): %d\n", ans);
std::vector<std::string> targets { "Hello, World!", "pneumonoultramicroscopicsilicovolcanoconiosis", ".oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.", "Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.", "36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165", "bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63", "7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I", R"T(n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8"eFP`Mn:zt-#mfCV2AL2^fL"A)T" };
int res = 0;
for(std::string target : targets)
{
int len = metagolf(target);
res += len;
printf("%d\n", len);
}
printf("total length of all programs: %d\n", res);
}
Output:
total length of all transitions within [0, 256): 1425541
+ +* + * +* . + + +* + ** + . + +* + . + . + +* + . + +* +* + . + + * +* . +* + * . + . +* . . + * . + + +** .
208
+ + + ** +* + . + * + . + + + * * . + +* + . + + + * . + +* + . + . + . + . + + * . + +* . + + +* + . + + + +* * + . + + * + . + * . +* + . + . + . + +* + . + + + . + + . +* . + +* + . + + . + . + . + +* + . + . + . + + +* + . + +* . + . + . + . + + * . + + + * + . + + . + . + . + + . + * + . + + . +* + . + . .
517
+ + +* + +* + +* +**** + . + + + + +* + * ** + . + + + * +* * + . + + . + . + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + + . + . . .
386
+ +* + * +* . + + +* + ** + . + + + * + . + +* + . +* + . +* + . +* . + +* +* + . + + * +* . + + +* . + + . + + . + +* + . +* + . + +* + . +* . + . + + * +* + . + + +* . + + . + + . + + +** . + + + +** . + . + + + + +** * . + +* . +* + . + + . + + + * . + . +* + . + + * . + + . + + . + + + * . + + + * . + + + ** . + + . + + . + + * . + + . + + * . + +* + . + . + . + + + + * + . + +* + . +* . + . + + +* . + + + +** . + . + + + +* +* * . + . + * . + . + + . + + + ** + . + +* . + + . + + * + . + + . + + + +** + . + +* . + + * . +* . + . . + . + + * + . + * . + . + + + + + * + ** + . + +* +** + . + * + . + . + + +** + . +* + . +* + . + * + . + + . + . + * . + + * . + + + ** + . + + + . + + * + . + + +* + . + + +** . + . + + +** . + . + +* + +** . + + + * + . + + * . +* . + . +* + . +* . + + +* +** + . + + . + + . + +* + . + + * . +* + . + +* + . +* + . +* . + + . + . + + + * + . + +* . + * . . +* .
1588
+ + +* +* +* +** + . + + +* + . +* + . + + + * + . + +* . + * + . + +* . + . + * + . + + * . . + . + + +* + . + . + +* . + + * . + . + + +* + . + . + +* . + + * . + . + + + . + . + . + . + +* + . + + + * . + +* . + . + . + . + +* . + . + +* . + . + . + + + * + . + . +* + . + . + + . +* . + + + * + . + + . + + * . . + + * . + +* . + + * . . + + . + . . + + + +* + . + + . + * . + +* . + + * + . + + * . + . + . + * + . + +* . + + . + + * . . + . . + + + * + . + . + +* . + . + + + +* . . + . . + . + + * + . + + +* . . + . + +* + . + +* . + + . + . + . + + * . + +* . +* . + + + + * + . + + . +* . + . + . + + * + . + +* . + + . + + * . + . + . + +* . + . . + + +* + . +* + . +* + . + + +* . + . . + . + + +* + . + + + * + . . + +* . + . +* . + + . + + . + +* + . +* . + + * + . +* . + . + . + + * . + . + * .
1261
+ + * +* + . + +* +* * + . +* + . + + + + * + +*** + . + +* . + + * + . + +* . . + + * . + . +* + . + + + ** + . +* . + +* +* + . + + * . + + + * . + +* . + . + . + + * + . + + + +* +** + . + + + . + * + . + +* + + + *** . +* . +* +* + . + + + +** . +* + . + +* . + . + +* + . +* . + + * . + +* + . + +* . . + +* + . + + +* * + . + . . + +* + . . + + +* + * + . + + +* +** . + + + * +* * + . +* + . + + +* . + * . +* . + + * + . + . + +* + . + + +* + . + . . + +* + . + . + + * * . + + ** . + + +** . + + * + . + +* + . + . . + + +* + ** + . + + + * +** + . + + * + . + +* . + * . +* + . + + * * . + +* . + +* + . + + * . + . + . +* + . + + * + . + + * + . + + * + . + + +* + ** . + +* . + + +* +** . + + . + . . + + +* + . + . + . + + * + . + +* . + * + . + + + + * + ** + . +* + . + +* . + * . +* +* . + +* +* . + + + + + +*** + . + + +* + * . + . + + * . + . +* + . + . +* +* . + +* . + + +** . + + * + . + + + + * +** . + + + * . +* + * . . + +* . + + * . + + + * . + +* + . + . + . + +** + . +* + . + + * . + + +* +* + . + . +* . + +* . + * + . + * .
1763
+ + + * +** + . + + + +** + . + + +* +** . + + +* + +** + . + +* +* . + + +** . + + * + . + +* . + + * . + + * + . + +* . + * . + + +* + . + +* . + +* . + + ** . + + + * . + + . + + . + +* . + + * . + + + + *** . + . + + * . + + +* + . + . + +** . . + + + + * + . + . +* + . +* + . + +* . + +* . + + + + +** * + . + + + * +** . + + + * * + . . + +* . + * . + + + * + . + +* + . + + . + +* + * . +* + . + + * . + + ** + . + + +* + . +* . + + + * * + . + + * . + . + + * . + + . + + +* . + + +* . + +* + ** + . + + + * + . + +* . + + * + . +* . +* . + * . + +* . + + + * +* + . + * + . + + * . + +* + . + . + +* +* . + + + * + ** + . + + . + . + + * . + + +* + * . + + * . + +* +* + . + +* + * +* + . + +* . + +* + . +* +* . + + * . + + +* . + + + * . + + +* . + * + . + . + + + + + ** * + . + +* + . + +** + . + . + + +** + . + +* . + + +** . + +* +* . + + +* . + + +* + . + + + ** . + + * . . + + +* +* . + + * . + + +* + . +* + . + . + +* + . + +* + . +* . + + . + +* . + +* . + +* . + + +* + * . + * + . + + . + + +* + . + + + +* . + . + * + . + +* +* . + + * . +* . + +* +* . + +* + . +* . + + + ** + . + . + +** .
1938
+ +* + + ** + . + + + + * +* ** + . + + + + +*** + . + + +* + . + . +* + . +* + . + + + + +* + ** * + . + +* . + . +* . + +* + . + +* * . + + +* * + . + + +** + . + +* + * . + +* +* . +* . + + + * +** + . + + + +* * . +* + . + + * + . + + +* . + +* . + + * +* . + +* + * . + + +* +* . + +* + * . +* + . + +* + . + + +** . + + ** . + +* + * + . +* . + + * . + +* . + + * + . + + + . + +* +* . + . + + +* + . + + + * . +* +* . +* + . + + . + + +* + +* * + . + . + * + . + + + +* + ** . + +* . + + * . +* +* + . + + + ** + . + + * + +** . . + + + +** + . + + +* + * + . +* . + +* . + + +* * + . +* . . + +* + . + + . + + +* . + + * +* . + + * . + + . + +* . + + . + . + +* + * + . + + . + + + * + . + . + +* . + +* + +* * . + * + . + + + * . + + . + . + + + +* +* * . +* + . + + +* + . + + * . +* + . + +* . + + +* * . + +* . + + + + +** * + . + + +* + ** . + . + +* + * . + + +* + ** + . + + + +** . +* . + +* . + +* + . + + +* . + + +** + . + +* +* . + . + + * . + +* + . + + +* + ** . + +* +* + . + +** + . + + + ** . + * . + . + + * + . + +* . +* . + + +* + . + + +* + . + +* +** . + + +** + . + +* + * + . + + +* + * . +* + . + + + * . + + ** + . + . + + +* * . . . + . +* + * .
2047
total length of all programs: 9708
