I have three non-MP/cheating solutions.

The second one is still quite compact and produces output that isn't
too
long. The third one uses prime factorization. It can handle negative
integers and generates fairly short output.


For the second solution, the results for some tests are:

9999
=> 216: ?(*?(*?(-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??
*??-??*??-??*??-??*??-??
*??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-??-
(?--?()-(?--?()
99999
=> 254: ??*??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??
*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??
*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??*??-??
*??-??*??-??*??-??*??-??*??-??*??-??*??-??*?--??-??-??-??-??-?-
(0..10000).to_a.inject(0) {|a, i| a + symbolify(i).size}
=> 1180737

real    0m7.480s
user    0m7.300s
sys     0m0.100s


For the third solution, the numbers are:

9999
=> 65: (?--?*)*(?--?*)*((?*-?()*(?*-(?--?())-??)*((?*-?()*(?*-?
()*?)-??)
99999
=> 60: (?--?*)*(?--?*)*?)*((?*-?()*(?*-?()*(?--?*)*(??-?()-(?--?())
(0..10000).to_a.inject(0) {|a, i| a + symbolify(i).size}
=> 539965

real    0m8.201s
user    0m7.991s
sys     0m0.110s


Regards,
Thomas.


And here is the code:


------------------ Solution 1

require 'mathn'
include Math
def symbolify(int)
    (['?(']*(n=int<2?1:(log(int)/log(?()).ceil)).join('*')<<'-(?)-?
()'*(?(**n-int)
end



------------------ Solution 2

require 'mathn'
include Math
def symbolify(int)
    syms = ['??', '?-', '?*', '?)', '?(']
    ns   = syms.map {|s| v = eval(s); [n = int < 2 ? 1 : (log(int) /
log(v)).ceil, s, v ** n - int]}
    n, s, rest = ns.sort_by {|n, s, sum| sum}[0]
    str  = ([s] * n).join('*')
    (syms + syms[0..-2].map {|s| "(#{s}-?()"}).each do |s|
        break if rest == 0
        t, rest = rest.divmod(eval(s))
        syms.each do |s1|
            t1, t = t.divmod(eval(s1))
            str << "-#{s}*#{s1}" * t1
        end
        str << "-#{s}" * t
    end
    str
end



------------------ Solution 3

require 'mathn'
module Symbolify
    @quick = false # Not for incremental benchmarking
    SYMS = ['?(', '?)', '?*', '?-', '??'].map {|e| [eval(e), e]}
    BLACKLIST = []
    @top = ??
    @multiples = SYMS.map {|a,b| a}
    @multiples_limit = 1000000
    VALS = Hash.new do |h, k0|
        k = k0.abs
        if !h.has_key?(k)
            BLACKLIST << k
            h[k] = k.prime_division.map do |p, n|
                pre = []
                n1 = n
                while n > 0 and n1 > 0
                    pn1 = p ** n1
                    if h.has_key?(pn1)
                        pre << h[pn1]
                        n1 = n -= n1
                    else
                        n1 -= 1
                    end
                end
                if n == 0
                    pre
                else
                    ps = nil
                    SYMS.each do |i, sym|
                        pi = p + i
                        unless BLACKLIST.include?(pi)
                            BLACKLIST << pi
                            s = "(#{h[pi]}-#{sym})"
                            BLACKLIST.pop
                            ps = s unless ps and s.size > ps.size
                            break if @quick
                            if s.size == 7
                                SYMS << [p, s]
                                break
                            end
                        end
                    end
                    pre.concat([ps] * n)
                end
            end.join('*')
            BLACKLIST.pop
        end
        if k0 < 0
            h[k0] = "#{h[k]}*(?(-?))"
        else
            h[k0]
        end
    end
    VALS[0] = "(#{SYMS[0][1]}-#{SYMS[0][1]})"
    VALS[1] = "(?)-?()"
    SYMS.each {|v, s| VALS[v] = s}

    def self.multiples(max)
        return if @multiples.empty? or @top > max * 2 or @quick or max
> @multiples_limit
        begin
            multiples = []
            SYMS.each do |j, jsym|
                @multiples.each do |i|
                    sym = VALS[i]
                    ij = i * j
                    multiples << ij
                    ijsym = "#{sym}*#{jsym}"
                    VALS[ij] = ijsym unless VALS.has_key?(ij) and
VALS[ij].size > ijsym.size
                    @top = ij if ij > @top
                    break if @top > max * 2
                end
            end
            @multiples = multiples
        end until @multiples.empty? or @top > max * 2
    end

    def self.quick(bool)
        @quick = bool
    end
end


def symbolify(int)
    Symbolify.multiples(int)
    Symbolify::VALS[int]
end