ascii2bf.py

import sys
import math
from collections import defaultdict

# ideally, we need to minimize the state changes
# so we need to track the transitions

s = sys.stdin.read()
rle = []
freq = defaultdict(int)
maxrun = defaultdict(int)
transition = defaultdict(int)
lastc = None
run = 1
for c in s:
    freq[c] += 1
    if c == lastc:
        run += 1
        maxrun[c] = max(maxrun[c], run)
    else:
        if lastc is not None:
            a = chr(ord(min(lastc, c)))
            b = chr(ord(max(lastc, c)))
            if run > 10:
                transition[(-1, a)] += 1
                transition[(-1, b)] += 1
            else:
                transition[(a, b)] += 1
            rle.append((lastc, run))
        run = 1
    lastc = c
rle.append((lastc, run))
print rle

chars = freq.keys()
N = len(chars)
freq = sorted([(f, c) for c, f in freq.iteritems()], reverse=True)
maxrun = sorted([(f, c) for c, f in maxrun.iteritems()], reverse=True)
print "chars", chars
print "freq", freq
print "maxrun", maxrun

edgelist = sorted([(f, c) for c, f in transition.iteritems()], reverse=True)
print "edgelist", edgelist


best = 1e30
def tfreq(c1, c2):
    a = chr(ord(min(c1, c2)))
    b = chr(ord(max(c1, c2)))
    return transition[(a, b)]


def optimalseq(soln, n, score):
    global best
    bestsoln = None
    if n == N:
        if score < best:
            best = score
            print score, soln
            return soln
        return None
    for c in chars:
        if c in soln:
            continue
        soln.append(c)
        prevscore = score
        for i in range(n):
            score += abs(i-n) * tfreq(soln[i], c)
        score += 2 * (n+1) * transition[(-1, c)]
        if score < best:
            s = optimalseq(soln, n+1, score)
            if s is not None:
                bestsoln = s[:]
        soln.pop()
        score = prevscore
    return bestsoln


# first, output optimal sequence
soln = optimalseq([], 0, 0)
print soln


def factor(n):
    f1 = int(math.sqrt(n))
    while f1 > 0:
        f2 = n/f1
        if f1*f2 == n:
            return max(f1, f2), min(f1, f2)
        f1 += 1
    return n, 1


def factor2(n):
    bestl = None
    f1 = int(math.sqrt(n))
    bestf1, bestf2, bestf3 = None, None, None
    while f1 <= n:
        f2 = n/f1
        f3 = n - f1*f2
        l = f1+f2+f3
        if bestl is None or l < bestl:
            bestl = l
            bestf1, bestf2, bestf3 = f1, f2, f3
        f1 += 1
    return bestf1, bestf2, bestf3


def incrbatch(target, bfmem, n):
    cmds = []
    limit = len(bfmem)
    while limit > 0 and bfmem[limit-1] == target[limit-1]:
        limit -= 1
    if limit == 0:
        return
    for i in range(limit):
        cmds.append('>')
        if bfmem[i] < target[i]:
            cmds.append('+'*n)
    cmds.append('<' * limit)
    return ''.join(cmds)


def incrloop(target, bfmem, f1, f2):
    cmds = []
    cmds.append('+'*f1)
    cmds.append('[')
    cmds.append(incrbatch(target, bfmem, f2))
    cmds.append('-]')
    return ''.join(cmds)


def initbfmem():
    # now, we need to initialize these memory cells (hm, but if the frequency
    # is low enough for some characters, is it worth it?)
    bfmem = [0] * N
    targetmem = map(ord, soln)
    acc = 0
    while True:
        left = [x for x in targetmem if x > acc]
        if len(left) == 0:
            break
        m = min(left) - acc
        if m == 0:
            break
        f1, f2 = factor(m)
        # print m, f1, f2, bfmem
        if f2 == 1:
            print incrbatch(targetmem, bfmem, f1)
        else:
            print incrloop(targetmem, bfmem, f1, f2)
        for i in range(N):
            if bfmem[i] < targetmem[i]:
                bfmem[i] += m
        acc += m
    print bfmem


# that works, but kind of sucks.  to optimize, we need to generate the shortest
# sequence of:
# [k1, [k2], [k3]] where each memory location i is incremented by
# k1*k2[i] + k3[i]  (where k2[i] and k3[i] can be zero)
# once k1 is determined, k2 and k3 are unique, so we need to find the optimal sequence of [k1,...]
# the length of the encoding is sum(k1[i]), sum(k2[i][j]) + sum(k3[i][j]) + m*len(k1)
# we could also have k2 or k3 be negative
# actually we shoudl definitely consider k3<0
# and actually k3 only applies at the end of the sequence for each one anyway
# as there is nothing to be gained from putting it earlier

# so, hmm
# we want the largest k1 at each stage
def factorall(arr):
    mostppl = 0
    bestk1 = None
    bestk2 = None
    n = min(arr)
    while n >= 1:
        k2 = [x/n for x in arr]
        ppl = float(sum((x*n for x in k2)))/(n+sum(k2))
        # progress per length
        # print n, ppl, k2
        if ppl > mostppl:
            mostppl, bestk1, bestk2 = ppl, n, k2
        n -= 1
    a = [bestk2[i]*bestk1 for i in range(len(arr))]
    return a, bestk1, bestk2


arr, bestk1, bestk2 = factorall(map(ord, soln))
print bestk1, bestk2, arr

init = ['+'*bestk1, '[']
for k in bestk2:
    init.append('>')
    init.append('+'*k)
init.append('<'*len(bestk2))
init.append('-]')
print ''.join(init)
cursor = -1
output = []
for c, runlen in rle:
    idx = soln.index(c)
    cdiff = idx - cursor
    # to do RLE: move cursor to -1, '+'*f1, '[', '>'*index, '.'*f2, '<'*index, '-]'
    if runlen > 2:
        f1, f2, f3 = factor2(runlen)
        rlelen = cursor+1 + f1 + 3*idx + f2 + 3
        if f3 != 0:
            rlelen += f3
        if rlelen < abs(cdiff)+runlen and ord(c) == arr[idx]:  # can only do this after the memory locations are set
            output.append('<'*(cursor+1))
            output.append('+'*f1)
            output.append('[')
            output.append('>'*(idx+1))
            output.append('.'*f2)
            output.append('<'*(idx+1))
            output.append('-]')
            if f3 != 0:
                output.append('>'*(idx+1))
                output.append('.'*f3)
                cursor = idx
            else:
                cursor = -1
            continue
    if cdiff < 0:
        output.append('<' * (-cdiff))
    elif cdiff > 0:
        output.append('>' * cdiff)
    cursor += cdiff
    residue = ord(c) - arr[cursor]
    if residue > 0:
        output.append('+' * residue)
    elif residue < 0:
        output.append('-' * (-residue))
    arr[cursor] += residue
    output.append('.'*runlen)
print ''.join(output)