text:
Starry Metagolf
Starry is a funny esoteric programming language in which code consists only of +*.,`' where the actual command represented by each of those characters is determined by the number of spaces in front of it. That makes it tricky even to golf fixed-output challenges, because different commands can account for vastly different numbers of bytes. In particular, number literals have a unary representation which makes it necessary to build up larger numbers by operating on smaller ones.
Therefore, this challenge is about writing a program which can golf such Starry programs.
How does Starry work?
(A few details are left unspecified on esolangs, so I'm going with the behaviour of the Ruby interpreter.)
Starry is a stack-based language, with a single stack of arbitrary-precision integer values (which is initially empty).
The only meaningful characters are:
+*.,`'

and spaces. All other characters are ignored. Each sequence of spaces followed by one of those non-space characters represents a single instruction. The type of instruction depends on the non-space character and the number of spaces.
The instructions are:
Spaces  Symbol  Meaning
0         +     Invalid opcode.
1         +     Duplicate top of stack.
2         +     Swap top 2 stack elements.
3         +     Rotate top 3 stack elements. That is, send the top stack element
                two positions down. [... 1 2 3] becomes [... 3 1 2].
4         +     Pop and discard top of stack.
n ≥ 5     +     Push n − 5 to stack.
0 mod 5   *     Pop y, pop x, push x + y.
1 mod 5   *     Pop y, pop x, push x − y.
2 mod 5   *     Pop y, pop x, push x * y.
3 mod 5   *     Pop y, pop x, push x / y, rounded towards -∞.
4 mod 5   *     Pop y, pop x, push x % y. The sign of the result matches the sign of y.
0 mod 2   .     Pop a value and print it as a decimal number.
1 mod 2   .     Pop a value and print it as an ASCII character. This throws an error
                if the value is not in the range [0, 255].
n         `     Mark label n.
n         '     Pop a value; if non-zero, jump to label n.

Note that the interpreter scans the source code for the labels before execution begins, so it's possible to jump forwards as well as backwards.
Of course, Starry also has input commands (using , analogously to .), but those are irrelevant for this challenge.
The Challenge
Given a string, generate a Starry program which takes no input and prints that string exactly to STDOUT.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
You may assume that the string is not longer than 128 characters and that it will consist only of printable ASCII characters (code points 0x20 to 0x7E).
Your solution should process any such input in less than 5 minutes on a reasonable desktop machine (there's some leeway to this; if it takes a few minutes more on my laptop I don't mind, but if it takes 15, I'll disqualify it).
Your solution will be tested on a number of different strings listed below. Your score is the total byte count of the corresponding Starry programs. In the case of a tie, the shortest metagolfer wins. That is, don't bother golfing your own code unless there is a tie (which I think will only happen in the case that an optimal solution is possible).
You must not optimise your code towards the specific test cases listed below. Specifically, you shouldn't hardcode hand-crafted solutions for them. Optimising towards classes of strings whose structure is similar to that of the given strings is fine. If I suspect anyone of hardcoding solutions, I reserve the right to replace some or all of the test cases (with strings of comparable structures).
Test Cases
Each line is a separate test case:
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
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

Credits for the second test case go to Dennis. Credits for the fourth test case go to Sp3000.
Reference Solution
Here is a really basic reference solution in CJam:
q{S5*\iS*'+S'.}%

You can run it against the entire test suite here. The scores are:
1233
5240
4223
11110
7735
10497
11524
11392
Total: 62954

It's the simplest possible approach: push each character's code point as a literal, and then print it. It makes no use of small differences between consecutive characters, integer printing, repetitive parts of the string etc. I'll leave those things to you.
I believe there is a lot of room for improvement. For reference, the shortest handcrafted "Hello, World!" is only 169 bytes long.

Ruby, 13461 10997
$s = {};
def shortest a,b=nil
    return $s[[a,b]] if $s[[a,b]]
    l = []
    if b
        if a == b
            return $s[[a,b]] = ""
        elsif a > b
            l.push shortest(a-b)+" *"
            l.push " +   *"+shortest(1,b) if a > 1
            l.push " + *"+shortest(0,b) if a > 0
            l.push "    +"+shortest(b)
        elsif a < b
            l.push " +  *"+shortest(a*a,b) if a*a>a && a*a<=b
            l.push " +*"+shortest(a+a,b) if a+a<=b && a+a>a
            l.push shortest(b-a)+"*"
            l.push " +"+shortest(a,b/a)+"  *" if a>2 && b%a == 0
            l.push " +"+shortest(a,b-a)+"*" if a>1 && b>a*2
        end
    else
        l.push ' '*(a+5)+'+' #if a < 6
        (1..a/2).each {|n|
            l.push shortest(n)+shortest(n,a)
        }
    end
    return $s[[a,b]] = l.min_by{|x|x.length}
end

def starry(str)
    arr = str.bytes.map{|b|
        if b>47 && b<58
            b-48# change digets to numbers
        else
            b
        end
    }

    startNum = (1..128).min_by{|x|arr.inject{|s,y|s + [shortest(x,y).length+2,shortest(y).length].min}+shortest(x).length}
    #one number to be put on the stack at the start.

    code = shortest(startNum)
    code += [
        shortest(arr[0]),
        " +"+shortest(startNum, arr[0])
    ].min_by{|x|x.length}

    arr.each_cons(2) do |a|
        pr = a[0]<10?'.':' .'
        code += [
            pr+shortest(a[1]),
            " +"+pr+shortest(a[0], a[1]),
            pr+" +"+shortest(startNum, a[1])
        ].min_by{|x|x.length}
    end
    code += arr[-1]<10?'.':' .'
end

a = ["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",
"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"]
c = a.map{
    |s|
    starry(s).length
}
p c.inject(0){|a,b|a+b}

The method starry answers the given question.
Results:
230
639
682
1974
1024
1897
2115
2436
Total: 10997

How it works
shortest is the main algorithm.
It takes one number and finds the shortest way to place it on the stack, or it takes two numbers, and returns code to put the second on the stack assuming the first one is already on. $s is a Hash to hold the results of these operations for further use.
starry takes a string and splits it into an array of character codes (or numbers for digests). It starts the code with one number on the bottom of the stack. Next it calculates the shortest way it can generate each successive number, possibly copying the last one or using the number put on the stack at the beginning.

Python 3, 17071 11845
from functools import lru_cache
import heapq
import time

cases = r"""
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
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
""".strip().splitlines()

@lru_cache(maxsize=128)
def shortest_m_to_n(m, n):
    if m is None:
        L = []
    else:
        L = [m]

    to_search = [[0, "", L]]
    seen = set()

    while True:
        length, code, stack = heapq.heappop(to_search)

        if len(stack) == 1 and stack[-1] == n:
            return code

        seen.add(tuple(stack))
        options = []

        for i in range(1, 11):
            new_stack = stack[:] + [i]
            new_code = code + ' '*(i+5) + '+'
            options.append([len(new_code), new_code, new_stack])

        if stack:
            new_stack = stack[:] + [stack[-1]]
            new_code = code + " +"
            options.append([len(new_code), new_code, new_stack])

        if len(stack) >= 2:
            x, y = stack[-2:]

            for i, op in enumerate(['+', '-', '*', '//', '%']):
                try:
                    new_elem = eval("{}{}{}".format(x, op, y))
                    new_stack = stack[:-2] + [new_elem]
                    new_code = code + ' '*i + '*'
                    options.append([len(new_code), new_code, new_stack])

                except ZeroDivisionError:
                    pass

        for op in options:
            if tuple(op[2]) in seen or len(op[2]) > 4 or op[2][-1] > 200:
                continue

            heapq.heappush(to_search, op)

def lcs(s1, s2):
    dp_row = [""]*(len(s2)+1)

    for i, c1 in enumerate(s1):
        new_dp_row = [""]

        for j, c2 in enumerate(s2):
            if c1 == c2 and not c1.isdigit():
                new_dp_row.append(dp_row[j] + c1)
            else:
                new_dp_row.append(max(dp_row[j+1], new_dp_row[-1], key=len))

        dp_row = new_dp_row

    return dp_row[-1]

def metagolf(s):
    keep = ""
    split_index = 0

    for i in range(1, len(s)):
        l = lcs(s[:i], s[i:][::-1])
        if len(l) > len(keep):
            keep = l
            split_index = i

    code = []
    stack = []
    keep_ptr = 0
    i = 0

    while i < len(s):
        c = s[i]
        n = ord(c)

        if c in "0123456789":
            code += [" "*(int(c)+5) + "+."]
            i += 1
            continue

        if stack:
            if stack[-1] == n:
                code += [" +", " ."]
            elif len(stack) >= 2 and stack[-2] == n:
                for j in range(len(code)):
                    if code[~j] == " +":
                        code[~j] = ""
                        break

                code += [" +", " ."]
                stack.pop()
            else:
                code += [shortest_m_to_n(stack[-1], n), " +", " ."]
                stack[-1] = n

        else:
            code += [shortest_m_to_n(None, n), " +", " ."]
            stack.append(n)

        while i < split_index and keep[keep_ptr:][:1] == c:
            code += [" +"]
            keep_ptr += 1
            stack.append(n)

        i += 1

    code = "".join(code)

    if code[-4:] == " + .":
        code = code[:-4] + " ."

    return code

total = 0

for case in cases:
    start_time = time.time()

    s = metagolf(case)
    print(len(s), time.time() - start_time)
    total += len(s)
    print(s)
    print('='*50)

print(total)

The relevant function is the aptly named metagolf.
The results are:
210
676
684
2007
1463
2071
2204
2530
Total: 11845

You can find the full output here.
Brief explanation
I'm going to keep the explanation brief since there's many things still to be improved.
The basic algorithm just looks at pairs of chars, and finds the optimal way to transition from one char to another via BFS. Digits are currently pushed and printed immediately, although this will be changed later.
There's also a little longest-common-subsequence going on, to leave a few elements on the stack for reuse later. It's not as good as repetition, but provides decent savings.

Hooray, someone to battle :-) Of course, now I see that mine has a long way to go...

JavaScript, 25158 23778
Now ES5-compatible!
String.prototype.repeat = String.prototype.repeat || function (n) { return Array(n+1).join(this); }

function starrify(x) {
  function c(x){return x.charCodeAt()}
  var char = x[0], result = ' '.repeat(c(char)+5)+'+ + .';
  x=x.slice(1);
  for(var i in x) {
    if (char < x[i]) {
      result += ' '.repeat(c(x[i])-c(char)+5)+'+* + .';
    } else if (char > x[i]) {
      if(c(char)-c(x[i]) < c(x[i])) {
        result += ' '.repeat(c(char)-c(x[i])+5)+'+ * + .';
      } else {
        result += ' '.repeat(c(x[i])+5)+'+ + .';
      }
    } else {
      result += ' + .';
    }
    char = x[i];
  }
  return result;
}

Results:
432
949
2465
3996
1805
3551
5205
5375
Total: 23778

A good start in my opinion, but obviously not finished. Instead of creating each char separately, it adds or subtracts from the previous char code. I'll add an full explanation when I'm done meta-golfing.

Yep, it works in Firefox now, although Chrome still complains about charCodeAt.

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

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Integer Complexity
Your task is to write a program that, on input n, outputs the minimal expression of each number 1 through n in order. The shortest program in bytes wins.
A minimal expression combines 1's with addition and multiplication to result in the given number, using as few 1's as possible. For example, 23 is expressed as 23=((1+1+1)(1+1)+1)(1+1+1)+1+1 with eleven ones, which is minimal.
Requirements:

The program must take as input a positive natural number n.
Output must be in this format: 20 = ((1+1+1)(1+1+1)+1)(1+1)
Your output may not have needless parentheses, like 8 = ((1+1)(1+1))(1+1).
The multiplication sign * is optional.
Spaces are optional.
You don't have to output all the possible equations for given value: For example, you have the choice to output 4=1+1+1+1 or 4=(1+1)(1+1). You don't have to output both.
The shortest program (in bytes) in each language wins.

1=1
2=1+1
3=1+1+1
4=1+1+1+1
5=1+1+1+1+1
6=(1+1+1)(1+1)
7=(1+1+1)(1+1)+1
8=(1+1+1+1)(1+1)
9=(1+1+1)(1+1+1)
10=(1+1+1)(1+1+1)+1
11=(1+1+1)(1+1+1)+1+1
12=(1+1+1)(1+1)(1+1)
13=(1+1+1)(1+1)(1+1)+1
14=((1+1+1)(1+1)+1)(1+1)
15=(1+1+1+1+1)(1+1+1)
16=(1+1+1+1)(1+1)(1+1)
17=(1+1+1+1)(1+1)(1+1)+1
18=(1+1+1)(1+1+1)(1+1)
19=(1+1+1)(1+1+1)(1+1)+1
20=((1+1+1)(1+1+1)+1)(1+1)

Here are some more test cases: (remember, that other expressions with the same number of 1's are also allowed)
157=((1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1

444=((1+1+1)(1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)

1223=((1+1+1)(1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)(1+1+1+1+1)+1+1+1

15535=((((1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)((1+1+1)(1+1)+1)+1)(1+1+1)+1)(1+1+1)(1+1+1)+1

45197=((((1+1+1)(1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1+1)+1+1

Good Luck!
- The Turtle

Your bullet #6 is not finished (it's missing the example output for n=20) and 2) you say at the beginning that the integer complexity, which is distinct from the equation, has to be output, but you don't include that in any of the examples except the very first one.

I'm still not clear. Do you just output the equation?

Yes. The integer complexity should not be outputted. I will also clarify that. Sorry for the mistakes. :(

Whoops, I said bullet #6 when I should've said bullet #5, in your requirements list. As for the other issue, thanks for fixing it. :)

Related: http://oeis.org/A005245 http://oeis.org/A061373 and finally http://oeis.org/A091333

Pyth, 60 bytes
LjWqeb\1b`()L?tbho/N\1++'tb"+1"m+y'/bdy'df!%bTr2b1VSQ++N\='N

Demonstration
The online compiler can reach 1223 before the time out, thanks to Pyth's automatic function memoization.
1223=((1+1+1)(1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)(1+1+1+1+1)+1+1+1

In abbrieviated notaion,
1223=(3^5+1)*5+3

This uses a recursive function ', which calculates all possbile products and sums which could give the desired output, finds the shortest string with each final operation, then compares them by 1 count and returns the first one.
It uses a helper function, y, which parenthesizes an expression only if it needs to be parenthesized.
Offline, I am running the program with the input 15535, and it is nearly complete. Results are printed incrementally, so it is easy to see the progress.
Final lines of the output:
15535=((((1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)((1+1+1)(1+1)+1)+1)(1+1+1)+1)(1+1+1)(1+1+1)+1

real    7m8.430s
user    7m7.158s
sys 0m0.945s

In abbreviated notation,
15535=(((3^4+1)*(3*2+1)+1)*3+1)*3^2+1

CJam, 105 102 98 96 bytes
q~{)'=1$2,{:I{I1$-'+}%3/1>Imf'*+aImp!*+{)\{j}%\+}:F%{e_"+*"-:+}$0=}j2,{F)_'*={;{'(\')}%1}&*}jN}/

Try it online in the CJam interpreter.
Test run
The online interpreter is too slow for the larger test cases. Even with the Java interpreter, the larger test cases will take a long time and require a significant amount of memory.
$ time cjam integer-complexity.cjam <<< 157
1=1
2=1+1
3=1+1+1
4=1+1+1+1
5=1+1+1+1+1
6=(1+1)(1+1+1)
7=1+(1+1)(1+1+1)
8=(1+1)(1+1)(1+1)
9=(1+1+1)(1+1+1)
10=1+(1+1+1)(1+1+1)
11=1+1+(1+1+1)(1+1+1)
12=(1+1)(1+1)(1+1+1)
13=1+(1+1)(1+1)(1+1+1)
14=(1+1)(1+(1+1)(1+1+1))
15=(1+1+1)(1+1+1+1+1)
16=(1+1)(1+1)(1+1)(1+1)
17=1+(1+1)(1+1)(1+1)(1+1)
18=(1+1)(1+1+1)(1+1+1)
19=1+(1+1)(1+1+1)(1+1+1)
20=(1+1)(1+1)(1+1+1+1+1)
21=(1+1+1)(1+(1+1)(1+1+1))
22=1+(1+1+1)(1+(1+1)(1+1+1))
23=1+1+(1+1+1)(1+(1+1)(1+1+1))
24=(1+1)(1+1)(1+1)(1+1+1)
25=1+(1+1)(1+1)(1+1)(1+1+1)
26=(1+1)(1+(1+1)(1+1)(1+1+1))
27=(1+1+1)(1+1+1)(1+1+1)
28=1+(1+1+1)(1+1+1)(1+1+1)
29=1+1+(1+1+1)(1+1+1)(1+1+1)
30=(1+1)(1+1+1)(1+1+1+1+1)
31=1+(1+1)(1+1+1)(1+1+1+1+1)
32=(1+1)(1+1)(1+1)(1+1)(1+1)
33=1+(1+1)(1+1)(1+1)(1+1)(1+1)
34=(1+1)(1+(1+1)(1+1)(1+1)(1+1))
35=(1+1+1+1+1)(1+(1+1)(1+1+1))
36=(1+1)(1+1)(1+1+1)(1+1+1)
37=1+(1+1)(1+1)(1+1+1)(1+1+1)
38=(1+1)(1+(1+1)(1+1+1)(1+1+1))
39=(1+1+1)(1+(1+1)(1+1)(1+1+1))
40=(1+1)(1+1)(1+1)(1+1+1+1+1)
41=1+(1+1)(1+1)(1+1)(1+1+1+1+1)
42=(1+1)(1+1+1)(1+(1+1)(1+1+1))
43=1+(1+1)(1+1+1)(1+(1+1)(1+1+1))
44=(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
45=(1+1+1)(1+1+1)(1+1+1+1+1)
46=1+(1+1+1)(1+1+1)(1+1+1+1+1)
47=1+1+(1+1+1)(1+1+1)(1+1+1+1+1)
48=(1+1)(1+1)(1+1)(1+1)(1+1+1)
49=1+(1+1)(1+1)(1+1)(1+1)(1+1+1)
50=(1+1)(1+1+1+1+1)(1+1+1+1+1)
51=(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
52=(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
53=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
54=(1+1)(1+1+1)(1+1+1)(1+1+1)
55=1+(1+1)(1+1+1)(1+1+1)(1+1+1)
56=(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
57=(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
58=1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
59=1+1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
60=(1+1)(1+1)(1+1+1)(1+1+1+1+1)
61=1+(1+1)(1+1)(1+1+1)(1+1+1+1+1)
62=(1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
63=(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
64=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
65=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
66=(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
67=1+(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
68=(1+1)(1+1)(1+(1+1)(1+1)(1+1)(1+1))
69=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1)(1+1))
70=(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
71=1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
72=(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
73=1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
74=(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
75=(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
76=(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
77=1+(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
78=(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
79=1+(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
80=(1+1)(1+1)(1+1)(1+1)(1+1+1+1+1)
81=(1+1+1)(1+1+1)(1+1+1)(1+1+1)
82=1+(1+1+1)(1+1+1)(1+1+1)(1+1+1)
83=1+1+(1+1+1)(1+1+1)(1+1+1)(1+1+1)
84=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1))
85=1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1))
86=(1+1)(1+(1+1)(1+1+1)(1+(1+1)(1+1+1)))
87=(1+1+1)(1+1+(1+1+1)(1+1+1)(1+1+1))
88=(1+1)(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
89=1+(1+1)(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
90=(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
91=1+(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
92=1+1+(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
93=(1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
94=1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
95=(1+1+1+1+1)(1+(1+1)(1+1+1)(1+1+1))
96=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1+1)
97=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1+1)
98=(1+1)(1+(1+1)(1+1+1))(1+(1+1)(1+1+1))
99=(1+1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
100=(1+1)(1+1)(1+1+1+1+1)(1+1+1+1+1)
101=1+(1+1)(1+1)(1+1+1+1+1)(1+1+1+1+1)
102=(1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
103=1+(1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
104=(1+1)(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
105=(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
106=1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
107=1+1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
108=(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
109=1+(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
110=1+1+(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
111=(1+1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
112=(1+1)(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
113=1+(1+1)(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
114=(1+1)(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
115=1+(1+1)(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
116=(1+1)(1+1)(1+1+(1+1+1)(1+1+1)(1+1+1))
117=(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
118=1+(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
119=(1+(1+1)(1+1+1))(1+(1+1)(1+1)(1+1)(1+1))
120=(1+1)(1+1)(1+1)(1+1+1)(1+1+1+1+1)
121=1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1+1+1)
122=(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1+1+1))
123=(1+1+1)(1+(1+1)(1+1)(1+1)(1+1+1+1+1))
124=(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
125=(1+1+1+1+1)(1+1+1+1+1)(1+1+1+1+1)
126=(1+1)(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
127=1+(1+1)(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
128=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
129=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
130=(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1))
131=1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1))
132=(1+1)(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
133=(1+(1+1)(1+1+1))(1+(1+1)(1+1+1)(1+1+1))
134=1+(1+(1+1)(1+1+1))(1+(1+1)(1+1+1)(1+1+1))
135=(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
136=1+(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
137=1+1+(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
138=(1+1)(1+1+1)(1+1+(1+1+1)(1+(1+1)(1+1+1)))
139=1+(1+1)(1+1+1)(1+1+(1+1+1)(1+(1+1)(1+1+1)))
140=(1+1)(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
141=1+(1+1)(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
142=(1+1)(1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1)))
143=(1+1+(1+1+1)(1+1+1))(1+(1+1)(1+1)(1+1+1))
144=(1+1)(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
145=1+(1+1)(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
146=(1+1)(1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1))
147=(1+1+1)(1+(1+1)(1+1+1))(1+(1+1)(1+1+1))
148=(1+1)(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
149=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
150=(1+1)(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
151=1+(1+1)(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
152=(1+1)(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
153=(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
154=1+(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
155=(1+1+1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
156=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
157=1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))

real    0m3.896s
user    0m4.892s
sys     0m0.066s

Given enough time, it would produce these solutions for the next test cases:
444=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
1223=1+1+(1+1+1)(1+1+(1+1+1)(1+1+1))(1+(1+1)(1+1)(1+1+1)(1+1+1))

How does it work?

@flawr I'm still hoping to golf this a bit more. I'll add an explanation when I am done/give up.

Julia, 229 bytes
n->(F=i->K[i]>0?E[i]:"("E[i]")";C=[1;3:n+1];K=0C;E=fill("1",n);for s=1:n for i=1:s÷2 (D=C[i]+C[s-i])<C[s]?(C[s]=D;E[s]=E[i]"+"E[s-i];K[s]=0):s%i>0||(D=C[i]+C[j=s÷i])<C[s]&&(C[s]=D;E[s]=F(i)F(j);K[s]=1)end;println("$s="E[s])end)

This is actually pretty fast. Assigning the function to f and running @time f(15535) gives the output (last two lines only)
15535=1+(1+1+1)(1+1+1)(1+(1+1+1)(1+(1+(1+1)(1+1+1))(1+(1+1+1)(1+1+1)(1+1+1)(1+1+1))))
32.211583 seconds (263.30 M allocations: 4.839 GB, 4.81% gc time)

and for @time f(45197), it gives
45197=1+1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1)(1+1+1))))
289.749564 seconds (2.42 G allocations: 43.660 GB, 4.91% gc time)

So, what's the code doing? Simple - C holds the current one-Count for the number, K is an indicator array keeping track of whether the expression is, fundamentally, a sum or a product, for the purposes of dealing with bracketing, and E holds the Expression itself. Working its way up from s=1 through to n, the code searches for the minimal representation of number s in terms of lower values, by looking for either a sum or a product. If it's a product, then it checks the two components and puts brackets around them if they're sums. That check is done in function F, to save bytes (because it has to be done twice, for the two factors).

Haskell, 208 bytes
import Data.List;f n=mapM putStrLn[show x++"="++m x|x<-[1..n]];m 1="1";m n=head$sortOn(filter(>'0'))[let b=m$div n x;q=last b>'0'in concat["(",m x,")",['('|q],b,[')'|q]]|x<-[2..n-1],mod n x<1]++[m(n-1)++"+1"]

Try it online!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Set Theoretic Arithmetic (+ and *)
Set Theoretic Arithmetic
Premise
There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (most similar to the second link).
This challenge, unlike those previous, will use a set theoretic definition of the natural numbers (N):

and

for example,

and so on.
The Challenge
Our goal is to use set operations (see below), to add and multiply natural numbers. For this purpose, all entries will be in the same 'set language' whose interpreter is below. This will provide consistency as well as easier scoring.
This interpreter allows you to manipulate natural numbers as sets. Your task will be to write two program bodies (see below), one of which adds natural numbers, the other of which multiplies them.
Preliminary Notes on Sets
Sets follow the usual mathematical structure. Here are some important points:

Sets are not ordered.
No set contains itself
Elements are either in a set or not, this is boolean. Therefore set elements cannot have multiplicities (i.e. an element cannot be in a set multiple times.)

Interpreter and specifics
A 'program' for this challenge is written in 'set language' and consists of two parts: a header and a body.
Header
The header is very simple. It tells the interpreter what program you are solving. The header is the opening line of the program. It begins with either the + or * character, followed by two integers, space delimited.
For example:
+ 3 5

or
* 19 2

are valid headers. The first indicates that you are trying to solve 3+5, meaning that your answer should be 8. The second is similar except with multiplication.
Body
The body is where your actual instructions to the interpreter are. This is what truly constitutes your "addition" or "multiplication" program. Your answer will have consist of two program bodies, one for each task. You will then change the headers to actually carry out the test cases.
Syntax and Instructions
Instructions consist of a command followed by zero or more parameters. For the purposes of the following demonstrations, any alphabet character is the name of a variable. Recall that all variables are sets. label is the name of a label (labels are words followed by semicolons (i.e. main_loop:), int is an integer. The following are the valid instructions:

Flow Control:

jump label jump unconditionally to the label. A label is a 'word' followed by a semicolon: e.g. main_loop: is a label.
je A label jump to label if A is empty
jne A label jump to label if A is non-empty
jic A B label jump to label if A contains B
jidc A B label jump to label if A does not contain B

Variable Assignment

assign A B or assign A int  or
 where set(int) is the set representation of int

Set Ops

union A B C
intersect A B C
difference A B C
add A B
remove A B

Debugging

print A prints the true value of A, where {} is the empty set
printi variable prints integer representation of A, if it exists, otherwise outputs error.

Comments

; The semicolon indicates that the rest of the line is a comment and will be ignored by the interpreter

Further Info
At program start, there are three pre-existing variables. They are set1, set2 and ANSWER. set1 takes the value of the first header parameter. set2 takes the value of the second. ANSWER is initially the empty set. Upon program completion, the interpreter checks if ANSWER is the integer representation of the answer to the arithmetic problem defined in the header. If it is, it indicates this with a message to stdout.
The interpreter also displays the number of operations used. Every instruction is one operation. Initiating a label also costs one operation (Labels can only be initiated once).
You may have a maximum of 20 variables (including the 3 predefined variables) and 20 labels.
Interpreter code

IMPORTANT NOTES ON THIS INTERPRETER

Things are very slow when using large numbers (>30) in this interpreter. I will outline the reasons for this.

The structures of sets is such that in increasing by one natural number, you effectively double the size of the set structure. The nth natural number has 2^n empty sets within it (by this I mean that if you look n as a tree, there are n empty sets. Note only empty sets can be leaves.) This means that dealing with 30 is significantly more costly than dealing with 20 or 10 (you're looking at 2^10 vs 2^20 vs 2^30).
Equality checks are recursive. Since sets are allegedly unordered, this seemed the natural way to tackle this.
There are two memory leaks that I couldn't figure out how to fix. I'm bad at C/C++, sorry. Since we're dealing with small numbers only, and allocated memory is freed at program end, this shouldn't really be that much of an issue. (Before anyone says anything, yes I know about std::vector; I was doing this as a learning exercise. If you do know how to fix it, please let me know and I will make the edits, otherwise, since it works, I will leave it as is.)

Also, notice the include path to set.h in the interpreter.cpp file. Without further ado, the source code (C++):
set.h
using namespace std;

//MEMORY LEAK IN THE ADD_SELF METHOD
class set {

    private:
        long m_size;
        set* m_elements;
        bool m_initialized;
        long m_value;

    public:
        set() {

            m_size =0;
            m_initialized = false;
            m_value=0;
        }

        ~set() {
            if(m_initialized) {
                //delete[] m_elements;
            }
        }

        void init() {
            if(!m_initialized) {
                m_elements = new set[0];

                m_initialized = true;
            }
        }

        void uninit() {
            if(m_initialized) {
                //delete[] m_elements;
            }
        }

        long size() {
            return m_size;
        }

        set* elements() {
            return m_elements;
        }

        bool is_empty() {
            if(m_size ==0) {return true;}
            else {return false;}
        }

        bool is_eq(set otherset) {
            if( (*this).size() != otherset.size() ) {
                return false;
            }
            else if ( (*this).size()==0 && otherset.size()==0 ) {
                return true;
            }
            else {
                for(int i=0;i<m_size;i++) {
                    bool matched = false;
                    for(int j=0;j<otherset.size();j++) {

                        matched = (*(m_elements+i)).is_eq( *(otherset.elements()+j) );
                        if( matched) {
                            break;
                        }
                    }
                    if(!matched) {
                        return false;
                    }
                }
                return true;
            }
        }

        bool contains(set set1) {
            for(int i=0;i<m_size;i++) {
                if( (*(m_elements+i)).is_eq(set1) ) {
                    return true;
                }
            }
            return false;
        }

        void add(set element) {
            (*this).init();

            bool alreadythere = false;
            for(int i=0;i<m_size;i++) {
                if( (*(m_elements+i)).is_eq(element) ) {
                    alreadythere=true;
                }
            }
            if(!alreadythere) {
                set *temp = new set[m_size+1];
                for(int i=0; i<m_size; i++) {
                    *(temp+i)= *(m_elements+i);
                }
                *(temp+m_size)=element;

                m_size++;
                delete[] m_elements;
                m_elements = new set[m_size];

                for(int i=0;i<m_size;i++) {
                    *(m_elements+i) = *(temp+i);
                }
                delete[] temp;
            }
        }

        void add_self() {

            set temp_set;
            for(int i=0;i<m_size;i++) {
                temp_set.add( *(m_elements+i) );
            }
            (*this).add(temp_set);
            temp_set.uninit();
        }

        void remove(set set1) {
            (*this).init();
            for(int i=0;i<m_size;i++) {
                if(  (*(m_elements+i)).is_eq(set1) ) {

                    set* temp = new set[m_size-1];
                    for(int j=0;j<m_size;j++) {

                        if(j<i) {
                            *(temp+j)=*(m_elements+j);
                        }
                        else if(j>i) {
                            *(temp+j-1)=*(m_elements+j);
                        }
                    }
                    delete[] m_elements;
                    m_size--;
                    m_elements = new set[m_size];
                    for(int j=0;j<m_size;j++) {
                        *(m_elements+j)= *(temp+j);
                    }
                    delete[] temp;
                    break;
                }
            }
        }

        void join(set set1) {
            for(int i=0;i<set1.size();i++) {
                (*this).add( *(set1.elements()+i) );
            }
        }

        void diff(set set1) {
            for(int i=0;i<set1.size();i++) {
                (*this).remove( *(set1.elements()+i) );
            }
        }

        void intersect(set set1) {
             for(int i=0;i<m_size;i++) {

                bool keep = false;
                 for(int j=0;j<set1.size();j++) {
                     if(  (*(m_elements+i)).is_eq( *(set1.elements()+j) ) ) {
                         keep = true;
                         break;
                     }
                 }
                 if(!keep) {
                    (*this).remove( *(m_elements+i) );
                 }
             }
         }

        void natural(long number) {
            //////////////////////////
            //MEMORY LEAK?
            //delete[] m_elements;
            /////////////////////////
            m_size = 0;
            m_elements = new set[m_size];

            for(long i=1;i<=number;i++) {
                (*this).add_self();
            }
            m_value = number;
        }

        void disp() {
            if( m_size==0) {cout<<"{}";}
            else {
                cout<<"{";
                for(int i=0; i<m_size; i++) {
                    (*(m_elements+i)).disp();
                    if(i<m_size-1) {cout<<", ";}
                    //else{cout<<" ";}
                }
                cout<<"}";
            }
        }

        long value() {
            return m_value;
        }

};
const set EMPTY_SET;

interpreter.cpp
#include<fstream>
#include<iostream>
#include<string>
#include<assert.h>
#include<cmath>
#include "headers/set.h"
using namespace std;
string labels[20];
int jump_points[20];
int label_index=0;
const int max_var = 20;
set* set_ptrs[max_var];
string set_names[max_var];
long OPERATIONS = 0;

void assign_var(string name, set other_set) {
    static int index = 0;
    bool exists = false;
    int i = 0;
    while(i<index) {
        if(name==set_names[i]) {
            exists = true;
            break;
        }
        i++;
    }
    if(exists && index<max_var) {
        *(set_ptrs[i]) = other_set;
    }
    else if(!exists && index<max_var) {
        set_ptrs[index] = new set;
        *(set_ptrs[index]) = other_set;
        set_names[index] = name;
        index++;
    }
}

int getJumpPoint(string str) {
    for(int i=0;i<label_index;i++) {
        //cout<<labels[i]<<"\n";
        if(labels[i]==str) {
            //cout<<jump_points[i];
            return jump_points[i];
        }
    }
    cerr<<"Invalid Label Name: '"<<str<<"'\n";
    //assert(0);
    return -1;
}

long strToLong(string str) {
    long j=str.size()-1;
    long value = 0;
    for(long i=0;i<str.size();i++) {
        long x = str[i]-48;
        assert(x>=0 && x<=9);  // Crash if there was a non digit character
        value+=x*floor( pow(10,j) );
        j--;
    }
    return value;
}

long getValue(string str) {
    for(int i=0;i<max_var;i++) {
        if(set_names[i]==str) {
            set set1;
            set1.natural( (*(set_ptrs[i])).size() );
            if( set1.is_eq( *(set_ptrs[i]) )   ) {
                return (*(set_ptrs[i])).size();
            }
            else {
                cerr<<"That is not a valid integer construction";
                return 0;
            }
        }
    }
    return strToLong(str);
}

int main(int argc, char** argv){
    if(argc<2){std::cerr<<"No input file given"; return 1;}
    ifstream inf(argv[1]);
    if(!inf){std::cerr<<"File open failed";return 1;}
    assign_var("ANSWER", EMPTY_SET);
    int answer;
    string str;
    inf>>str;
    if(str=="*") {
        inf>>str;
        long a = strToLong(str);
        inf>>str;
        long b = strToLong(str);
        answer = a*b;
        set set1; set set2;
        set1.natural(a); set2.natural(b);
        assign_var("set1", set1);
        assign_var("set2",set2);
        //cout<<answer;
    }
    else if(str=="+") {
        inf>>str;
        long a = strToLong(str);
        inf>>str;
        long b = strToLong(str);
        answer = a+b;
        set set1; set set2;
        set1.natural(a); set2.natural(b);
        assign_var("set1", set1);
        assign_var("set2",set2);
        //cout<<answer;
    }
    else{
         cerr<<"file must start with '+' or '*'";
        return 1;
    }

    // parse for labels
    while(inf) {
        if(inf) {
            inf>>str;
            if(str[str.size()-1]==':') {
                str.erase(str.size()-1);
                labels[label_index] = str;
                jump_points[label_index] = inf.tellg();
                //cout<<str<<": "<<jump_points[label_index]<<"\n";
                label_index++;
                OPERATIONS++;
            }
        }
    }

    inf.clear();
    inf.seekg(0,ios::beg);
    // parse for everything else

    while(inf) {
        if(inf) {
            inf>>str;

            if(str==";") {
                getline(inf, str,'\n');
            }

            // jump label
            if(str=="jump") {
                inf>>str;
                inf.seekg( getJumpPoint(str),ios::beg);
                OPERATIONS++;
            }

            // je set label
            if(str=="je") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str) {
                        if( (*(set_ptrs[i])).is_eq(EMPTY_SET) ) {
                            inf>>str;
                            inf.seekg( getJumpPoint(str),ios::beg);
                            OPERATIONS++;
                        }
                        break;
                    }
                }
            }

            // jne set label
            if(str=="jne") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str) {
                        if(! (*(set_ptrs[i])).is_eq(EMPTY_SET) ) {
                            inf>>str;
                            inf.seekg( getJumpPoint(str),ios::beg);
                            OPERATIONS++;
                        }
                        break;
                    }
                }
            }

            // jic set1 set2 label
            // jump if set1 contains set2
            if(str=="jic") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set set2;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str ) {
                        set1 = *(set_ptrs[i]);
                    }
                    if(set_names[i]==str2) {
                        set2 = *(set_ptrs[i]);
                    }
                }
                if( set1.contains(set2) ) {
                    inf>>str;
                    inf.seekg( getJumpPoint(str),ios::beg);
                    OPERATIONS++;
                }
                else {inf>>str;}
            }

            // jidc set1 set2 label
            // jump if set1 doesn't contain set2
            if(str=="jidc") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set set2;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str ) {
                        set1 = *(set_ptrs[i]);
                    }
                    if(set_names[i]==str2) {
                        set2 = *(set_ptrs[i]);
                    }
                }
                if( !set1.contains(set2) ) {
                    inf>>str;
                    inf.seekg( getJumpPoint(str),ios::beg);
                    OPERATIONS++;
                }
                else {inf>>str;}
            }

            // assign variable set/int
            if(str=="assign") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set1.natural( getValue(str2) );
                assign_var(str,set1);
                OPERATIONS++;

            }

            // union set1 set2 set3
            // set1 = set2 u set3
            if(str=="union") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]);
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.join(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;

            }

            // intersect set1 set2 set3
            // set1 = set2^set3
            if(str == "intersect") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]);
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.intersect(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;
            }

            // difference set1 set2 set3
            // set1 = set2\set3
            if(str == "difference") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]);
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.diff(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;
            }

            // add set1 set2
            // put set2 in set 1
            if(str=="add") {
                inf>>str;
                int i = 0; int j =0;
                while(i<max_var) {
                    if(set_names[i]==str) {
                        break;
                    }
                    i++;
                }
                inf>>str;
                while(j<max_var) {
                    if(set_names[j]==str) {
                    break;
                    }
                    j++;
                }
                set set2 = *(set_ptrs[j]);
                if( ! (*(set_ptrs[i])).is_eq(set2) ){
                    (*(set_ptrs[i])).add(set2);
                }
                else {
                    (*(set_ptrs[i])).add_self();
                }
                OPERATIONS++;
            }

            // remove set1 set2
            // remove set2 from set1
            if(str=="remove") {
                inf>>str;
                int i = 0; int j =0;
                while(i<max_var) {
                    if(set_names[i]==str) {
                        break;
                    }
                    i++;
                }
                inf>>str;
                while(j<max_var) {
                    if(set_names[j]==str) {
                    break;
                    }
                    j++;
                }
                set set2 = *(set_ptrs[j]);
                (*(set_ptrs[i])).remove(set2);
                OPERATIONS++;
            }

            // print set
            // prints true representation of set
            if(str=="print") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if(set_names[i]==str) {
                        (*(set_ptrs[i])).disp();
                    }
                }
                cout<<"\n";
            }

            // printi set
            // prints integer representation of set, if exists.
            if(str=="printi") {
                inf>>str;
                cout<<getValue(str);
                cout<<"\n";
            }
        }
    }

    cout<<"You used "<<OPERATIONS<<" operations\n";
    set testset;
    testset.natural(answer);
    switch( testset.is_eq( *(set_ptrs[0]) ) ) {
        case 1:
            cout<<"Your answer is correct, the set 'ANSWER' is equivalent "<<answer<<".\n";
            break;
        case 0:
            cout<<"Your answer is incorrect\n";
    }
   // cout<<"\n";
    return 0;
}

Winning condition
You are two write two program BODIES, one of which multiplies the numbers in the headers, the other of which adds the numbers in the headers.
This is a fastest-code challenge. What is fastest will be determined by the number of operations used to solve two test cases for each program. The test cases are the following headers lines:
For addition:
+ 15 12

and
+ 12 15

and for multiplication
* 4 5

and
* 5 4

A score for each case is the number of operations used (the interpreter will indicate this number upon program completion). The total score is the sum of the scores for each test case.
See my example entry for an example of a valid entry.
A winning submission satisfies the following:

contains two program bodies, one which multiplies and one which adds
has the lowest total score (sum of scores in test cases)
Given sufficient time and memory, works for any integer that could be handled by the interpreter (~2^31)
Displays no errors when run
Does not use debugging commands
Does not exploit flaws in the interpreter. This means that your actual program should be valid as pseudo-code as well as an interpretable program in 'set language'.
Does not exploit standard loopholes (this means no hardcoding test cases.)

Please see my example for reference implementation and example usage of the language.

@Calvin'sHobbies Thought that was just my browser. Is there an easy place to make the pictures?

@LiamNoronha: I took care of it. $$...$$ works on Meta, but not on Main. I used CodeCogs to generate the images.

Thank you @El'endiaStarman for fixing the markup notation

Have you tried tackling those memory leaks with valgrind?

No I haven't, I was under the impression that valgrind just helps you find them? I was just getting crashes when I called delete.

@LiamNoronha Valgrind monitors all sorts of invalid memory access and is quite often able to tell you where you've leaked something or called delete twice etc.

@MartinBüttner Thank you, I'll keep that in mind for future reference, unless you think that the code really needs to be fixed. (I think the memory leak is pretty trivial in terms of performance slowing when compared to the set sizes, so I would be inclined to let this one go)

not sufficient room for optimization

I'm voting to close this question as off-topic because there is not enough room for optimization

Example Answer, 1323 Operations
Note that this is an example, not a real entry.
Addition Body
Note that this body will not run without a header.
Comments are not necessary in an actual answer, but are there to help teach the basics of the language.
assign ANSWER set2                  ; ANSWER = set2
main:                               ; create label 'main'
    add ANSWER ANSWER               ; Answer union {Answer}, i.e. ANSWER++
    assign looper1 0
    assign looper2 0
    jump dec
    continue:
        intersect set1 set1 looper2 ; set1 = set1 intersect looper2, i.e. set1 = min(set1,looper2)
        jne set1 main
        jump end
dec:
    add looper1 looper1             ; looper1++
    jidc set1 looper1 continue      ; jump if looper >= set1
    add looper2 looper2             ; looper2++
    jump dec
end:

For test case
+ 15 12

uses 440 operations and for test case
+ 12 15

uses 299 operations.
Multiplication Body
assign mult_loop 0
main:
    jic set1 mult_loop addition
    jump end

addition:
    assign temp2 set2
    main_add:
        add ANSWER ANSWER
        assign looper1 0
        assign looper2 0
        jump dec
        cont_add:
            intersect temp2 temp2 looper2
            jne temp2 main_add
            jump end_add
    dec:
        add looper1 looper1
        jidc temp2 looper1 cont_add
        add looper2 looper2
        jump dec
    end_add:
        add mult_loop mult_loop
        jump main

end:

For test case
* 4 5

uses 305 operations and for test case
* 5 4

uses 279 operations.
Therefore my total score is 440+299+305+279 = 1323

Unfortunately, the only improvement I can think of is to sort the the inputs into min and max using union and intersection, so that the two additions and the two multiplications get the same (lower) score. That doesn't seem like a sufficient improvement to rip off the rest of this reference solution. ;)

@MartinBüttner Hah I just assumed my first attempts would be pretty awful. Well if that's the case, we might as well close the question then

Eh, just because I can't think of anything better doesn't mean much better approaches exist. We'll see... ;)

@MartinBüttner I was afraid something like this might happen, but since I put very little effort into the solutions, I assumed they would be easy to beat. I'll give it a week or so.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Layout Text in Columns
Write a program or function that given some text, a number of columns, and the column width, formats the text into columns. This is plain text typography.
Rules
Input

The text will be a string of printable ASCII and may contain newlines and spaces (but not tabs).
The number of columns will be a positive integer.
The column width is an integer greater or equal to 2 that specifies how many characters per column.

For this challenge, a word will consist of any non-whitespace characters. The input consists of one string and two integers, which may be taken in any order.
Output
Output is the text formatted into balanced columns with as many words on each line as will fit.

If a word is too long to fit in a column, put the word on the next line if there is another word on the current line and the line could be padded to the column width with three spaces or less.
Otherwise, hyphenate the word so that it fills the rest of the line. Hyphenate wherever the line ends; don't worry about hyphenating between syllables.
Columns should be separated by a margin of four space characters.
The columns should be balanced so that they all have an equal number of lines if possible.
The leftmost columns should have an extra line if necessary.
Any line breaks and multiple spaces should be preserved. Trailing spaces are optional after the last column.

Examples
Text:
The number of columns will be a positive integer.  Columns should be separated by a margin of four space characters.

The columns should be balanced.  The column width is greater than two.

Columns: 3, width: 10
The number    separated     ns should
of columns    by a marg-    be balanc-
will be a     in of four    ed.  The
positive      space cha-    column wi-
integer.      racters.      dth is gr-
Columns                     eater than
should be     The colum-    two.

Text:
This line is hyphenated.
This line, on the other hand, is not.

Columns: 1, width: 20
This line is hyphen-
ated.
This line, on the
other hand, is not.

Text: Tiny columns. columns: 4, width: 2
T-    c-    u-    s.
i-    o-    m-
ny    l-    n-

Text: Two  spaces.<space> columns: 5, width: 2
T-          p-    c-    s.
wo    s-    a-    e-

Text: <newline>A phrase columns: 2, width: 5
         rase
A ph-

Text: A short sentence. columns: 10, width: 5
A sh-    ort      sent-    ence.

Text: It's "no word" 1234567890 -+-+-+-+ (*&!) columns: 3, width: 6
It's      12345-    +-+
"no       67890     (*&!)
word"     -+-+--

This is code-golf; standard rules apply.

Possible dupe

@Mego The challenges are related, however, this one requires hyphenating certain words and balancing columns, so I think it is different enough.

Is s:'tiny', c:4, w:2 = t- i- n- y or t- i- ny??

@TFeld My examples were wrong, it should be t- i- ny. Is everything right now, or do I need to fix it again?

Not sure, should tiny s be t- i- n- y_  s or t- i- ny s

@TFeld It should be t- i- ny s I'm trying to do it by hand, so I really apologize for changing the examples so much.

Python 3, 336 339 335 bytes
@Jerry Jeremiah's recent activity on this question inspired me to try it myself, and see if Python 3 couldn't manage to beat the old Python 2 answer, and, after some painful golfing, I managed to get this slightly shorter:
def F(c,w,s):
 r,R,i,e=[""],[],0," "
 for j in s.split(e):
  while 1:
   if(a:=len(r[i]))+len(j)<=w:r[i]+=j.replace("\n",e*(w-a))+e;break
   elif a+min(3,w)>w:r[i]+=e*(w-a+1)
   else:r[i]+=j[:w-a-1]+"- ";j=j[w-a-1:]
   i+=1;r+=[""]
 h=-(-len(r)//c);r+=[e]*c;exec(c*"R.append(r[:h]);del r[:h];");return"\n".join(map("   ".join,zip(*R)))

Try it online!
Takes three arguments, as columns, width, text. It does require that all newlines in the input have a leading and trailing space, despite my best efforts to fix that.
Edit +3 bytes: Thanks @jezza_99 for pointing out it was erroring out, turns out my golf of assigning w-a to b didn't work, because the assignment wasn't in code that ran every loop.
Edit -4 bytes: -3 from @Sylvester Kruin spotting that I could save bytes by defining a variable for " ", and another -1 by cleaning up the line that pads r so the zip() doesn't truncate the text if some of the columns in the final row aren't filled up.
Ungolfed code and explanation
def F(c,w,s):
    r,R,i=[""],[],0
    for j in s.split(" "): ## Loop through each word in the input
        while 1: ## While we havent finished adding this word
            if (a:=len(r[i]))+len(j)<=w: ## If theres room for the full word
                r[i]+=j.replace("\n"," "*(w-a))+" " ## Add it + a trailing space, and if the string is a newline, replace it with enough spaces to finish the line
                break ## Break to next word
            elif a+min(3,w)>w: # If this line can be padded with spaces
                r[i]+=" "*(w-a+1) ## Pad with spaces
            else: ## Need to hypenate
                r[i]+=j[:w-a-1]+"- " ## Add as much word as can fit plus the hypen
                j=j[w-a-1:] ## Trim the part of this word we added
            i+=1 ## Jump to next line
            r+=[""] ## Initialize that line to the empty string
    h=-(-len(r)//c) ## Determine column height
    r+=[""]*c ## Pad the last row with empty strings so the zip() truncate it if some of the columns are incomplete
    for j in range(c): ## Convert the flat list into a list containing each column
        R.append(r[:h])
        del r[:h]
    return "\n".join( ## Join each line with a newline
                    map("   ".join, ## Use map() to .join the columns of each line with 3 spaces
                                    zip(*R))) ## Zip the lists to get a list of each line

You are getting an error for the test case Tiny columns. columns: 4, width: 2

Oh sh*t @jezza_99, It was working at some point, time to figure out what I changed that broke it

Hate it when that happens aye. Good luck with the bug hunt

@jezza_99 luckily found it quick, unfortunately the bug was a golf I made that turned out to not work

To reduce it by one byte, you can create a variable x like this: x=" ", and use x instead of " " in the rest of the code. Unfortunately, the link is too long to post in a comment :-.

Oh good one @SylvesterKruin!

Can save another byte by replacing "    " with (e*4)

@jezza_99 you'd think, unfortunately I cant, as that's actually 3 spaces, as every line gets a trailing space at the end when I put the words together, so (e*3) would actually be the same byte count

Ah thought it was 4, my bad

Python 2, 346 338 bytes
i,C,W=input()
r=[]
for l in [x or' 'for x in i.split('\n')]:
 while l:
  if' '==l[0]:l=l[1:]
  w=l[:W];x=W;s=w.rfind(' ')+1
  if max(W-3,0)<s:w=w[:s];x-=W-s
  elif x<len(l)and' 'not in l[x:x+1]:w=w[:-1]+'-';x-=1
  r+=[w];l=l[x:]
r=[s.ljust(W)for s in r+['']*(C-1)]
print'\n'.join('    '.join(s)for s in zip(*zip(*[iter(r)]*((len(r))/C))))

Input as 'string',C,W

Thanks, fixed by changing to rstrip().

Great! that saves me the strip() at the end.

C++ 386
Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter
#import<bits/stdc++.h>
#define b t.push_back
#define r l.substr
using namespace std;main(int n,char**a){int i=0,p,c=atoi(a[1]),w=atoi(a[2]);vector<string>t;for(string l;getline(cin,l);)for(;p=l.find_last_of(" \n",w),l=~p&&p>w-4?b(r(0,p)),r(p+1):w/l.size()?b(l),"":(b(r(0,w-1)+"-"),r(w-1)),l[0];);for(p=~-t.size()/c+1;i<p;i+=puts(""))for(n=0;n<c;b(""))cout<<left<<setw(w+4)<<t[i+n++*p];}

Try it online!

383 bytes


text:
Tips for golfing in Burlesque
This serves as a catalog for tips related to golfing in Burlesque.
Burlesque is a lazy, esoteric programming language. It's mostly used on anarchy golf while popularity on Codegolf is not as high. However, this catalog is intended to be used by people golfing on anarchy golf as well.
Please only mention tricks and not obvious shortcuts. An obvious shortcut is for example using r\ instead of r@\[ because the built-in r\ is defined to be r@\[ and is stated as such in the documentation and is thus just an obvious shortcut.

Using ".. .."wd instead of {".."".."}
If you need a Block of Strings such as {"abc" "def"} it is shorter to use the words built-in: "abc def"wd.
Using ra to parse fail-safe
ps will fail if the input is not properly formated or might produce unwanted results. In such cases, using ra is better.
blsq ) "5,"ra
5
blsq ) "5,"ps
{5 ,}
blsq ) "5a"ps
{ERROR: (line 1, column 3):
unexpected end of input}
blsq ) "5a"ra
5

Using , to drop stdin
, is defined as a pop instruction if and only if there is exactly one element on the stack. It's used to pop STDIN from the stack when it's not needed but there (such as for example is the case on anarchy golf).
Abusing the way mo is defined
mo is defined as 1R@\/?* and is used to generate a Block containing multiples of N:
blsq ) 3mo9.+
{3 6 9 12 15 18 21 24 27}

Yet due to side effects of ?* you can do some nasty things with it if you don't provide a number:
blsq ) "1"mo9.+
{"11" "21" "31" "41" "51" "61" "71" "81" "91"}

blsq ) {1 2 3 4}mo9.+
{1 4 9 16}


text:
Most creative/diabolical/entertaining way to find Python version?
There are important differences between Python 2 and 3, so it's often useful to know which version of the interpreter is running your code. The straightforward method is something like this:
def get_python_version():
    import sys
    return sys.version_info.major

But you can exploit other differences to come up with other solutions to this. My favorite so far is this:
def get_python_version():
    version = 3;[2 for version in range(3)]
    return version

What's the most creative/diabolical/entertaining snippet you can come up with that returns the Python version?

http://codegolf.stackexchange.com/a/55963/42963

Related: link1, link2