BrainF***-optimize a series of numbers

Question

An often-used trick in BF-golfing is something I call "multiply then add." Let's say that you want to initialize the memory to contain a series of numbers, like 87 75 68 96. The simplest way to do this is to simply write out a long series of 326 + signs. A better method, however is below.

++++++++++[>+++++++++>+++++++>+++++++>++++++++++<<<<-]>--->+++++>-->----

(I write this by hand, I hope it works correctly)

The basic idea is that you create a series of numbers (9,7,7,10), multiply them by a constant (10), and then add another series of numbers (-3,5,-2,-4). My invented form of notation writes this as (10;9,7,7,10;-3,5,-2,-4) which directly corresponds to the BF code.

There is a lot of importance placed in how the numbers are divided. If I were to pick a larger constant, then the first series of numbers would be much smaller, yet there will tend to be larger remainders after the multiplication. If I were to pick a smaller constant, then the first series would be larger, but the second series smaller.

Your goal is to write the shortest program to find the best possible way to write a series of numbers in BF using the multiply-then-add strategy.

Your program will recieve a series of non-negative integers. It should find the best way to generate these numbers.

For example, lets say that it receives the series (3,16,8,4), as an easy example. The best way to represent this is by the set of numbers (4;1,4,2,1;-1,0,0,0), which is what your program is expected to output (the exact formatting isn't as important). This corresponds to the following program:

++++[>+>++++>++>+<<<<-]>->>>

Answer 1

Python, 205 characters

def o(l):
    d=lambda l,a:[(d+1,m-a)if m>a/2 else(d,m) for d,m in(divmod(x,a)for x in l)]
    a,x=min((a+sum(abs(x)+abs(y)for x,y in d(l,a)),a,d(l,a))for a in range(1,max(l)+1))[1:]
    return [a]+zip(*x)

Examples:

>>> o([3,16,8,4])
[4, (1, 4, 2, 1), (-1, 0, 0, 0)]
>>> o([87,75,68,96])
[11, (8, 7, 6, 9), (-1, -2, 2, -3)]
>>> o([4,4,4])
[4, (1, 1, 1), (0, 0, 0)]
>>> o([1,2,3,4,5,6,7,8])
[4, (0, 0, 1, 1, 1, 1, 2, 2), (1, 2, -1, 0, 1, 2, -1, 0)]

As a bonus for a very long solution, the BF formater:

def bf(l):
    N,f,s=o(l)
    return ('%s[%s%s-]%s'%(N*'+',
                           ''.join('>' + x*'+' for x in f),
                           ''.join('<' for _ in f),
                           ''.join('>' + abs(x)*('+' if x>0 else '-')for x in s)))

>>> bf([3,16,8,4])
'++++[>+>++++>++>+<<<<-]>->>>'

Answer 2

GolfScript, 74 65 characters

:f$-1=),{[..{1${\2$*-.abs 2$+[@@]}++\),%$0=}+f%{(@+\}%@\+]}%$0=1=

A quite long golfscript solution which simply tries lots of combinations of numbers and takes the shortest representation.

Input is the list of numbers on the stack and output a list of the final numbers (grouped differently compared with the question - constant, tuples of [factor, addon])

Examples:

{
  :f$-1=),{[..{1${\2$*-.abs 2$+[@@]}++\),%$0=}+f%{(@+\}%@\+]}%$0=1=
}:C;

[3 16 8 4] C p             # -> [4 [1 -1] [4 0] [2 0] [1 0]]
[87 75 68 96] C p          # -> [11 [8 -1] [7 -2] [6 2] [9 -3]]
[1 2 3 4 5 6 7 8] C p      # -> [4 [0 1] [0 2] [1 -1] [1 0] [1 1] [1 2] [2 -1] [2 0]]
[5 5 5] C p                # -> [5 [1 0] [1 0] [1 0]]

Answer 3

Javascript 244 characters

function b(c){function e(f,c){n=m.abs;return n(f)+n(c)}a=0;m=Math;for(i=1;i<m.max.apply(null,c);i++)x=[],y=c.map(function(c){r=c/i|0;d=c%i;d=d>i/2?(r++,d-i):d;x.push(d);return r}),l=i+y.reduce(e)+x.reduce(e),a=!a||l<a[0]?[l,i,y,x]:a;return a};

Examples (first digit in output is total program length):

> b([3,16,8,4])
[13, 4, [1, 4, 2, 1], [-1, 0 0 0]]

> b([87,75,68,96])
[49, 11, [8, 7, 6, 9], [-1, 2, 2, -3]]

I think with "=>" syntax coming soon, I could likely condense further. I wish I was better at BF, I think a solution in BF would be interesting as well.

Solution before condensed:

function b(s){
    a = 0;
    m = Math;
    for(i=1; i<m.max.apply(null, s); i++) {
        x = [];
        y = s.map(function(n) {
            r = n/i|0;
            d = n%i;

            d = d > i/2 ? (r++, d-i) : d;
            x.push(d);
            return r;
        });

        l=i+y.reduce(c)+x.reduce(c);
        a = !a || l < a[0] ? [l,i,y,x] : a;
    }
    function c(g, h) {
        n = m.abs;
        return n(g)+n(h);
    }

    return a;
}

Then ran through google closure compiler to condense to a single line.