Generate brainfuck text

genbf.rb

class Array
    def sum
        inject(0, :+)
    end
    
    def mean
        sum.to_f / size
    end
    
    def delta
        each_cons(2).map { |x, y| y - x }
    end
    
    def order(inds)
        inds.map { |i| self[i] }
    end
    
    def index_all(n = nil, &proc)
        unless n.nil?
            proc = Proc.new { |e| e == n }
        end
        inds = []
        each_with_index { |e, i|
            inds.push i if proc[e]
        }
        inds
    end
end

def dist(x, y)
    (x - y).abs
end

def force_arr_sort(str)
    if str.is_a? String
        return str.chars.map(&:ord).sort
    else
        return str.sort
    end
end

def find_cores(n, str)
    arr = force_arr_sort(str)
    deltas = arr.delta
    split_inds = []
    (n - 1).times {
        max = deltas.max
        inds = deltas.index_all(max)
        # attach one with furthest index from current inds
        dest_ind = 0
        max_ind = Float::INFINITY
        inds.map.with_index { |e, j|
            cdist = 0
            split_inds.each { |i|
                cdist += dist(i, e)
            }
            if cdist < max_ind
                max_ind = cdist
                dest_ind = j
            end
        }
        deltas[inds[dest_ind]] = -1
        split_inds.push inds[dest_ind]
    }
    sections = []
    build = []
    arr.each_with_index { |e, i|
        build.push e
        if split_inds.include? i
            sections.push build.clone
            build = []
        end
    }
    sections.push build
    cores = sections.map { |sxn|
        avg = sxn.mean
        # find closest element to average
        core = sxn.min_by { |e| (e - avg).abs }
    }
    [cores, sections]
end

def bf_move_amount(n)
    (n < 0 ? "<" : ">") * n.abs
end

def bf_add_amount(n)
    (n < 0 ? "-" : "+") * n.abs
end

#doesn't work for zeroes in string
def gen_bf(str, core_amount = nil)
    @gen_bf_memo ||= {}
    key = core_amount
    pair = [str, key]
    return @gen_bf_memo[pair] if @gen_bf_memo.has_key? pair
    # todo: find nice way to find core (brute force might be faster)
    if core_amount == nil
        # find optimal core amount (kind of faulty)
        threshold = 2 # minimal delta difference
        
        deltas = force_arr_sort(str).delta
        # p deltas
        core_amount = 0
        while deltas.max > threshold
            m = deltas.max
            deltas[deltas.index(m)] = -1
            core_amount += 1
        end
        
        # p core_amount
    end
    
    cores, sections = find_cores(core_amount, str)
    
    # explanation, assuming core_amount == 3:
    #   cores = c0 c1 c2
    #   find numbers n0, n1, n2, j0, j1, j2, k such that:
    #   k*n0 + j0 = c0
    #   etc.
    #   and sum(coeff) is minimized
    
    # find k, brute force over (2..12)
    ks = {}
    k = (2..20).min_by { |k_test|
        ns = []
        js = []
        cores.each { |core|
            d, m = core.divmod(k_test)
            # puts "#{k_test}*#{d}+#{m} = #{k_test*d+m}"
            ns.push d
            js.push m
        }
        ks[k_test] = [ns, js]
        # minimization factor
        (ns + js + [k_test]).sum
    }
    ns, js = ks[k]
    # [k, ns, js]
    # p cores
    
    
    # find optimal ordering
    size_map = {}
    (0...ns.size).to_a.permutation.min_by { |ordering|
        scp = sections.order ordering
        crp = cores.order ordering
        cur_section = core_amount - 1
        result = ""
        str.chars.each { |char|
            o = char.ord
            # identify section
            sec_ind = scp.index { |e| e.include? o }
            # move to section
            result += bf_move_amount(sec_ind - cur_section)
            cur_section = sec_ind
            result += bf_add_amount(o - crp[sec_ind])
            crp[sec_ind] = o
            result += "."
        }
        # p result
        size_map[result.size] = [result, ordering]
        result.size
    }
    
    _, (after, ordering) = size_map.min
    
    crp = cores.order ordering
    nsp = ns.order ordering
    jsp = js.order ordering
    # p crp, nsp, jsp
    result = ""
    result += "+" * k
    result += "["
    nsp.each { |n|
        result += ">" + "+" * n
    }
    result += "<" * nsp.size
    result += "-]"
    jsp.each { |j|
        result += ">" + "+" * j
    }
    # 0 c0 c1 ... _cN_
    # generate each character of the input
    result += after
    # erase self
    # can be made to work with zeroes for a higher expense
    result += "[>]<[[-]<]"
    # size_map.min[1]
    # result
    @gen_bf_memo[pair] = result
    
    return result
end

def gen_bf_auto(str)
    # possible cores
    core_upperbound = 7
    optimal_core = (1..core_upperbound).to_a.min_by { |core|
        gen_bf(str, core)
    }
    # memoized, should be find for repetition
    gen_bf(str, optimal_core)
end