title: Write a code golfer

text:
# Question
Title: Write a code golfer
Your job, should you choose to not refuse it, is to write a program that will "golf" a piece of given code in your language of choice.

Basic functionality:

* Remove extraneous whitespace
* Remove comments

'Advanced' functionality:

* Combine declarations (`int x; int y; int z;` to `int x, y, z;`)
* Use shorter variations of basic control structures (`while(1)` is replaced with `for(;;)`)
* Move code around (`i = 0; while(i < 10) { /* ... */ ++i; }` to `for(i = 0; i < 10; ++i) { /* ... */ }`)
* Etc

# Answer
> 18 votes
# Python with Python

Does a bunch of stuff including renaming of variables, getting rid of unnecessary whitespace and comments, and putting as much as it can on one line. Doesn't always completely work with fancier python syntax and I'll will be continuing to update with any fixes.

Code:

```
import string
import keyword
import pkgutil

builtins = __builtins__.__dict__.keys()

vars = {}
#imported = builtins+string.__dict__.keys()+['append','extend','count','index','insert','pop','remove','reverse','sort']
multiline = ''
ml_last = ''
strings = []
defined = []
undefined = []

def get_name(name):
    if name.startswith('__'):
        vars[name] = name
        return name
    if name in vars:
        return vars[name]

    for c in string.letters+'_':
        if c not in vars.values():
            vars[name] = c
            return c

    for c0 in string.letters+'_':
        for c1 in string.letters+string.digits+'_':
            if c0+c1 not in vars.values():
                if c0+c1 in keyword.kwlist:
                    continue
                vars[name] = c0+c1
                return c0+c1

def replace_names(expr,defining=False,prefix = '',assign=True):
    if ';' in expr:
        ns = ''
        for e in expr.split(';'):
            ns += replace_names(e,assign=assign)+';'
        return ns[:-1]

    global multiline
    expr = expr.strip()
    if expr in ['']+keyword.kwlist:
        return expr
    if expr == '""':
        return '"'+strings.pop(0)+'"'
    if expr == "''":
        return "'"+strings.pop(0)+"'"

    if '=' in expr and assign:
        e = expr[:]
        vals = ['']
        while '=' in e:
            i = e.index('=')
            if e != '' and e[0] == '=':
                vals[-1] += '='
                e = e[1:]
                continue
            if e[i-1] not in '!<>*/+-%' and e[i+1] != '=' and (vals[-1]+e[:i]).count('(') == (vals[-1]+e[:i]).count(')'):
                vals[-1] += e[:i]
                e = e[i+1:]
                vals.append('')
            else:
                vals[-1] += e[:i+1]
                e = e[i+1:]

        if len(vals) > 1:
            vals[-1] += e
            ns = ''
            left,val = vals[:-1],vals[-1]
            for l in left:
                rs = replace_names(l,True,assign=assign)
                ns += rs+'='
            ns += replace_names(val,assign=assign)
            return ns

    if expr[0] in ['(','[','{']:
        try:
            delimit = expr[0]
            i = 0; level = 1
            while level > 0:
                i += 1
                char = expr[i]
                if char in '([{':
                    level += 1
                if char in ')]}':
                    level -= 1
            inner = expr[1:i]
            rest = expr[i+1:]
            return expr[0]+replace_names(inner,defining,assign=False)+expr[i]+replace_names(rest,defining,assign=assign)

        except IndexError:
            multiline = expr
            return ''

    if expr.startswith('for') and not expr.endswith('in'):
        varname = ''
        curword = ''
        for i,char in enumerate(expr):
            if char in string.letters+string.digits+'_':
                curword += char
            else:
                if curword == 'in':
                    break
                curword = ''
            varname += char
        rest = expr[i:]

        dpart = replace_names(varname[3:-2],True,assign=assign)
        rpart = replace_names(rest,assign=assign)
        return 'for' + ' '*(dpart[0] in string.letters+string.digits+'_') + dpart + ' '*(dpart[-1] in string.letters+string.digits+'_') + 'in' + ' '*(rpart[0] in string.letters+string.digits+'_') + rpart

    if expr.startswith('lambda'):
        args = expr.split('lambda',1)[1].split(':')[0]
        replace_names(args,True,assign=assign)

    poses = ['' if e == -1 else e for e in (expr.find(char) for char in ['(','[','{'])]
    pos = min(poses)
    if pos != '':
        delimit = '([{'[poses.index(pos)]
        first,rest = expr.split(delimit,1)
        return replace_names(first,defining,assign=assign)+replace_names(delimit+rest,defining,assign=assign)

    multiline = ''
    if ' ' in expr:
        ns = ''
        for sub in expr.split(' '):
            rs = replace_names(sub,defining,assign=assign)
            if rs == '':
                continue
            if ns != '' and (ns[-1] in string.letters+string.digits+'_' and rs[0] in string.letters+string.digits+'_'):
                ns += ' '+rs
            else:
                ns += rs
        return ns

    for cmp in ['**=','//=','==','!=','<>','<=','>=','+=','-=','*=','/=','%=','//','**','<<','>>','<','>','+','-','*','/','%','&','|','^','~',':',',','.']:
        if cmp in expr:
            ns = ''
            for sub in expr.split(cmp):
                rs = replace_names(sub,defining,prefix,assign=assign)+cmp
                ns += rs
                if cmp == '.':
                    prefix += rs
            return ns[:-len(cmp)]

    if expr[0] in string.digits:
        return expr
    if not defining and expr not in defined:
        #print '---',prefix+expr
        if prefix+expr not in undefined and (prefix == '' or prefix[0] != '.') :
            undefined.append(prefix+expr)
        return expr
    if defining:
        if prefix+expr in undefined:
            undefined.remove(prefix+expr)
        if expr not in defined:
            defined.append(expr)
    return get_name(expr)

def fix_names(line):
    for cmp in ['**=','//=','==','!=','<>','<=','>=','+=','-=','*=','/=','%=','//','**','<<','>>','<','>','+','-','*','/','%','&','|','^','~',':',',','.','=','(',')','[',']','{','}']:
        if cmp in line:
            ns = ''
            for sub in line.split(cmp):
                ns += fix_names(sub)+cmp
            return ns[:-len(cmp)]
    if line in defined and line not in vars.values():
        return vars[line]
    return line

def first_pass(file):
    lines_firstpass = []
    for line in file:
        if line.strip() == '':
            continue
        indent = 0
        for char in line:
            if not char in string.whitespace:
                break
            indent += 1

        if multiline != '':
            line_string = ml_last
        else:
            line_string = ''
            #line_string = '\t'*indent
        line = multiline + line.strip()

        newline = ''
        while line:
            char = line[0]
            if char in ['"',"'"]:
                limit=char; i=0
                inside = ''
                escape = False
                while True:
                    i+=1; char = line[i]
                    if escape:
                        escape = False
                        inside += char
                        continue
                    if char == '\\':
                        escape = True
                    elif char == limit:
                        break
                    inside += char
                strings.append(inside)
                newline += limit*2
                line = line[i+1:]
            else:
                if char == '#':
                    break
                newline += char
                line = line[1:]
        line = newline

        if line == '':
            continue
        if ' ' not in line:
            first = ''
        else:
            first,line = line.split(' ',1)

        if first in ['class','def']:
            name = line.split('(')[0].split(':')[0].strip()
            line_string += first+' '
            defined.append(name)
            line_string += get_name(name)
            if '(' in line:
                line_string += '('
                inner = line.split('(',1)[1]
                inner = ')'.join(inner.split(')')[:-1])
                part = ''
                for char in inner:
                    if char == ',' and part.count('(') == part.count(')'):
                        line_string += replace_names(part,True)+','
                        part = ''
                    else:
                        part += char
                line_string += replace_names(part,True)+')'
            line_string += ':'

        to_import = ''
        importing = []
        if first == 'from':
            module,rest = line.split('import')
            module = module.strip()
            #imported.append(module)
            first,line = 'import',rest
            to_import += 'from '+module+' '

        if first == 'import':
            to_import += 'import '
            for module in line.split(','):
                module = module.strip()
                #imported.append(module)
                to_import += module+','
            to_import = to_import[:-1]
            line_string += to_import

        if line_string.strip() == '':
            r = replace_names(first+' '+line)
            if multiline != '':
                ml_last = line_string + r
                continue
            line_string += r
            ml_last = ''
        lines_firstpass.append((indent,line_string))
        #print '\t'*indent+line_string

    for i,(indent,line) in enumerate(lines_firstpass):
        lines_firstpass[i] = (indent,fix_names(line))
    return lines_firstpass

def second_pass(firstpass):
    lines = []
    current_line = ''
    current_line_indent = 0
    last_indent = 0
    for i,(indent,line) in enumerate(firstpass):
        for kw in keyword.kwlist:
            if line[:len(kw)] == kw:
                first = kw
                line = line[len(kw):]
                break
        else:
            first = ''
        limit=';'
        for kw in ['import','global']:
            if first == kw and current_line.startswith(kw):
                first = ''
                line = line.strip()
                limit=','

        if first not in ['if','elif','else','while','for','def','class','try','except','finally'] and indent == last_indent:
            current_line += limit*(current_line != '') + first + line
        else:
            lines.append((current_line_indent,current_line))
            current_line = first + line
            current_line_indent = indent
        last_indent = indent
    lines.append((current_line_indent,current_line))

    new_lines = []
    i = 0
    while i < len(lines):
        indent,line = lines[i]
        if i != len(lines)-1 and lines[i+1][0] == indent + 1 and (i == len(lines)-2 or lines[i+2][0] <= indent):
            new_lines.append((indent,line+lines[i+1][1]))
            i += 1
        else:
            new_lines.append((indent,line))
        i += 1
    return new_lines

def third_pass(lines):
    new_definitions = ''
    for u in sorted(undefined,key=lambda s:-s.count('.')):
        #print u
        parts = u.split('.')
        if parts[0] in vars.values():
            continue
        c = 0
        for indent,line in lines:
            if line.startswith('import'):
                continue
            c += line.count(u)
        if c > 1:
            new_definitions += ';'*(new_definitions!='')+get_name(u)+'='+u
            for ind,(indent,line) in enumerate(lines):
                if line.startswith('import'):
                    continue
                nline = ''
                cur_word = ''
                i = 0
                while i < len(line):
                    char = line[i]
                    if char not in string.letters+string.digits+'_.':
                        if cur_word == u:
                            nline += get_name(u)
                        else:
                            nline += cur_word
                        cur_word = ''
                        nline += char
                        i += 1
                        continue
                    if char in '"\'':
                        nline += char
                        limit = char
                        escape = False
                        while True:
                            i += 1
                            char = line[i]
                            nline += char
                            if escape:
                                escape = False
                                continue
                            if char == '\\':
                                escape = True
                            if char == limit:
                                break
                        i += 1
                        continue
                    cur_word += char
                    i += 1
                lines[ind] = (indent,nline+cur_word)

    return [lines[0]]+[(0,new_definitions)]+lines[1:]

def golf(filename):
    file = open(filename)
    write_file = open('golfed.py','w')
    for indent,line in third_pass(second_pass(first_pass(file))):
        write_file.write('\t'*(indent/2)+' '*(indent%2)+line+'\n')
    file.close()
    write_file.close()

#print first_pass(["for u in sorted(undefined,key=lambda s:-s.count('.')):"])
golf('golfer.py')

```

Tested on an old fractal drawing program I had (**4672** to **1889**):

Original:

```
import pygame
import math
import os
import colorsys
from decimal import *

#two = Decimal(2)
#half = Decimal(0.5)

def fractal_check_point(function,x,y):
    #n = (Decimal(0),Decimal(0))
    n = (0,0)
    i = 0
    last_dist = 0
    while n[0]**2 + n[1]**2 <= 16 and i < max_iter:
        nr,ni = function(n)
        n = (nr+x,ni+y)
        i+=1
    if i == max_iter:
        return False

    #extra = math.log(math.log( (n[0]**two + n[1]**two)**half )/math.log(300),2)
    extra = math.log(math.log( (n[0]**2 + n[1]**2)**0.5 )/math.log(300),2)

    #prev = math.sqrt(last_dist)
    #final = math.sqrt(n.real**2+n.imag**2)

    return i - extra

def f((r,i)):
    return (r**2 - i**2, 2*r*i)

screen_size = (500,500)
try: screen = pygame.display.set_mode(screen_size)
except pygame.error:
    print 'Too large to draw to window...'
    screen = pygame.Surface(screen_size)

#pixels = pygame.PixelArray(screen)

#xmin = Decimal(- 2.2)
#xmax = Decimal(.8)
#
#ymin = Decimal(- 1.5)
#ymax = Decimal(1.5)

max_iter = 50

xmin = -2.2
xmax = 0.8
ymin = -1.5
ymax = 1.5

def draw_fractal():
    print repr(xmin),repr(xmax)
    print repr(ymin),repr(ymax)
    print

    xlist = []
    ylist = []

    for x in range(screen_size[0]):
        #xlist.append(Decimal(x)*(xmax-xmin)/Decimal(screen_size[0])+xmin)
        xlist.append(x*(xmax-xmin)/screen_size[0]+xmin)

    for y in range(screen_size[1]):
        #ylist.append(Decimal(y)*(ymax-ymin)/Decimal(screen_size[1])+ymin)
        ylist.append(y*(ymax-ymin)/screen_size[1]+ymin)

    xi = 0
    for x in xlist:
        yi = 0
        for y in ylist:
            val = fractal_check_point(f,x,y)
            if val == False:
                screen.set_at((xi,yi),(0,0,0))
                #pixels[xi][yi] = (0,0,0)
            else:
                r,g,b = colorsys.hsv_to_rgb(val/10.0 % 1, 1, 1)
                screen.set_at((xi,yi),(r*255,g*255,b*255))
                ##screen.set_at((xi,yi),(0,(val/300.0)**.25*255,(val/300.0)**.25*255))
                #pixels[xi][yi] = (0,(val/300.0)**.25*255,(val/300.0)**.25*255)

            yi += 1
        xi += 1
        pygame.event.get()
        pygame.display.update((xi-1,0,1,screen_size[1]))
    save_surface('F:\FractalZoom\\')

def save_surface(dirname):
    i = 0
    name = '%05d.bmp' % i
    while name in os.listdir(dirname):
        i += 1
        name = '%05d.bmp' % i
    pygame.image.save(screen,dirname+name)
    print 'saved'

x_min_step = 0
x_max_step = 0
y_min_step = 0
y_max_step = 0

savefail = 0

def zoom(xmin_target,xmax_target,ymin_target,ymax_target,steps):
    global xmin
    global xmax
    global ymin
    global ymax

    xc = (xmax_target + xmin_target)/2
    yc = (ymax_target + ymin_target)/2

    d_xmin = ((xc-xmin_target)/(xc-xmin))**(1.0/steps)
    d_xmax = ((xc-xmax_target)/(xc-xmax))**(1.0/steps)
    d_ymin = ((yc-ymin_target)/(yc-ymin))**(1.0/steps)
    d_ymax = ((yc-ymax_target)/(yc-ymax))**(1.0/steps)

    for s in range(steps):
        xmin = xc-(xc-xmin)*d_xmin
        xmax = xc-(xc-xmax)*d_xmax
        ymin = yc-(yc-ymin)*d_ymin
        ymax = yc-(yc-ymax)*d_ymax

        draw_fractal()
        save_dir = 'D:\FractalZoom\\'
        global savefail
        if not savefail:
            try:
                save_surface(save_dir)
            except:
                print 'Warning: Cannot save in given directory '+save_dir+', will not save images.'
                savefail = 1

#zoom(.5,.6,.5,.6,10)
#zoom(-1.07996839017,-1.07996839014,-0.27125861927,-0.27125861923,100)

#n = 1
#while 1:
#    pygame.display.update()
#    pygame.event.get()
#
#    def f(x):
#        if x == 0:
#            return 0
#        else:
#            return x**n
#    draw_fractal()
#    n += .0001

draw_fractal()
zooming = 0
#firstx = Decimal(0)
#firsty = Decimal(0)
firstx = firsty = 0

clicking = 0
while 1:
    pygame.display.update()
    pygame.event.get()
    mx, my = pygame.mouse.get_pos()
    rx, ry = pygame.mouse.get_rel()

#   mx = Decimal(mx)
#   my = Decimal(my)
#   sx = Decimal(screen_size[0])
#   sy = Decimal(screen_size[1])
    sx = screen_size[0]
    sy = screen_size[1]

    if pygame.mouse.get_pressed()[0]:
        if clicking == 0:
            clicking = 1
        if zooming and clicking == 1:
            secondx = mx*(xmax-xmin)/sx+xmin
            secondy = my*(ymax-ymin)/sy+ymin

            firstx = firstx*(xmax-xmin)/sx+xmin
            firsty = firsty*(ymax-ymin)/sy+ymin

            if secondx < firstx:
                xmin = secondx
                xmax = firstx
            else:
                xmin = firstx
                xmax = secondx

            if secondy < firsty:
                ymin = secondy
                ymax = firsty

            else:
                ymin = firsty
                ymax = secondy

            screen.fill((0,0,0))
            screen.lock()
            draw_fractal()
            screen.unlock()
            zooming = 0

        elif clicking == 1:
            firstx = mx
            firsty = my

            zooming = 1
            screen.set_at((firstx,firsty),(255,255,255))

        if clicking:
            clicking = 2

    else:
        clicking = 0

```

Golfed:

```
import pygame,math,os,colorsys;from decimal import *
ai=pygame.event.get;aj=pygame.display.update;ak=math.log;al=pygame.mouse;am=False;an=pygame;ao=repr;ap=range;aq=os
def a(b,c,d):
 e=(0,0);f=0;g=0
 while e[0]**2+e[1]**2<=16 and f<o:h,i=b(e);e=(h+c,i+d);f+=1
 if f==o:return False
 j=ak(ak((e[0]**2+e[1]**2)**0.5)/ak(300),2);return f-j
def k((l,f)):return(l**2-f**2,2*l*f)
m=(500,500)
try:n=pygame.display.set_mode(m)
except pygame.error:print'Too large to draw to window...';n=pygame.Surface(m)
o=50;p=-2.2;q=0.8;r=-1.5;s=1.5
def t():
 print ao(p),ao(q);print ao(r),ao(s);print;u=[];v=[]
 for c in ap(m[0]):u.append(c*(q-p)/m[0]+p)
 for d in ap(m[1]):v.append(d*(s-r)/m[1]+r)
 w=0
 for c in u:
    x=0
    for d in v:
     y=a(k,c,d)
     if y==am:n.set_at((w,x),(0,0,0))
     else:l,z,A=colorsys.hsv_to_rgb(y/10.0%1,1,1);n.set_at((w,x),(l*255,z*255,A*255))
     x+=1
    w+=1;ai();aj((w-1,0,1,m[1]))
 B('F:\FractalZoom\\')
def B(C):
 f=0;D='%05d.bmp'%f
 while D in os.listdir(C):f+=1;D='%05d.bmp'%f
 pygame.image.save(n,C+D);print'saved'
E=0;F=0;G=0;H=0;I=0
def J(K,L,M,N,O):
 global p,q,r,s;P=(L+K)/2;Q=(N+M)/2;R=((P-K)/(P-p))**(1.0/O);S=((P-L)/(P-q))**(1.0/O);T=((Q-M)/(Q-r))**(1.0/O);U=((Q-N)/(Q-s))**(1.0/O)
 for V in ap(O):
    p=P-(P-p)*R;q=P-(P-q)*S;r=Q-(Q-r)*T;s=Q-(Q-s)*U;t();W='D:\FractalZoom\\';global I
    if not I:
     try:B(W)
     except:print'Warning: Cannot save in given directory '+W+', will not save images.';I=1
t();X=0;Y=Z=0;_=0
while 1:
 aj();ai();aa,ab=pygame.mouse.get_pos();ac,ad=pygame.mouse.get_rel();ae=m[0];af=m[1]
 if pygame.mouse.get_pressed()[0]:
    if _==0:_=1
    if X and _==1:
     ag=aa*(q-p)/ae+p;ah=ab*(s-r)/af+r;Y=Y*(q-p)/ae+p;Z=Z*(s-r)/af+r
     if ag<Y:p=ag;q=Y
     else:p=Y;q=ag
     if ah<Z:r=ah;s=Z
     else:r=Z;s=ah
     n.fill((0,0,0));n.lock();t();n.unlock();X=0
    elif _==1:Y=aa;Z=ab;X=1;n.set_at((Y,Z),(255,255,255))
    if _:_=2
 else:_=0

```

Run on itself (creating a very long quine) (**9951** to **5323**):

```
import string,keyword,pkgutil;a=__builtins__.__dict__.keys();b={};c='';d='';e=[];f=[];g=[]
aw=string.letters;ax=string.digits;ay=keyword.kwlist;az=False;aA=True;aB=len;aC=enumerate;aD=open
def h(i):
 if i.startswith('__'):b[i]=i;return i
 if i in b:return b[i]
 for j in aw+'_':
    if j not in b.values():b[i]=j;return j
 for k in aw+'_':
    for l in aw+ax+'_':
     if k+l not in b.values():
        if k+l in ay:continue
        b[i]=k+l;return k+l
def m(n,o=az,p='',q=aA):
 if';'in n:
    r=''
    for s in n.split(';'):r+=m(s,q=q)+';'
    return r[:-1]
 global c;n=n.strip()
 if n in['']+ay:return n
 if n=='""':return'"'+e.pop(0)+'"'
 if n=="''":return"'"+e.pop(0)+"'"
 if'='in n and q:
    s=n[:];t=['']
    while'='in s:
     u=s.index('=')
     if s!=''and s[0]=='=':t[-1]+='=';s=s[1:];continue
     if s[u-1]not in'!<>*/+-%'and s[u+1]!='='and(t[-1]+s[:u]).count('(')==(t[-1]+s[:u]).count(')'):t[-1]+=s[:u];s=s[u+1:];t.append('')
     else:t[-1]+=s[:u+1];s=s[u+1:]
    if aB(t)>1:
     t[-1]+=s;r='';v,w=t[:-1],t[-1]
     for x in v:y=m(x,aA,q=q);r+=y+'='
     r+=m(w,q=q);return r
 if n[0]in['(','[','{']:
    try:
     z=n[0];u=0;A=1
     while A>0:
        u+=1;B=n[u]
        if B in'([{':A+=1
        if B in')]}':A-=1
     C=n[1:u];D=n[u+1:];return n[0]+m(C,o,q=az)+n[u]+m(D,o,q=q)
    except IndexError:c=n;return''
 if n.startswith('for')and not n.endswith('in'):
    E='';F=''
    for u,B in aC(n):
     if B in aw+ax+'_':F+=B
     else:
        if F=='in':break
        F=''
     E+=B
    D=n[u:];G=m(E[3:-2],aA,q=q);H=m(D,q=q);return'for'+' '*(G[0]in aw+ax+'_')+G+' '*(G[-1]in aw+ax+'_')+'in'+' '*(H[0]in aw+ax+'_')+H
 if n.startswith('lambda'):I=n.split('lambda',1)[1].split(':')[0];m(I,aA,q=q)
 J=[''if s==-1 else s for s in(n.find(B)for B in['(','[','{'])];K=min(J)
 if K!='':z='([{'[J.index(K)];L,D=n.split(z,1);return m(L,o,q=q)+m(z+D,o,q=q)
 c=''
 if' 'in n:
    r=''
    for M in n.split(' '):
     y=m(M,o,q=q)
     if y=='':continue
     if r!=''and(r[-1]in aw+ax+'_'and y[0]in aw+ax+'_'):r+=' '+y
     else:r+=y
    return r
 for N in['**=','//=','==','!=','<>','<=','>=','+=','-=','*=','/=','%=','//','**','<<','>>','<','>','+','-','*','/','%','&','|','^','~',':',',','.']:
    if N in n:
     r=''
     for M in n.split(N):
        y=m(M,o,p,q=q)+N;r+=y
        if N=='.':p+=y
     return r[:-aB(N)]
 if n[0]in ax:return n
 if not o and n not in f:
    if p+n not in g and(p==''or p[0]!='.'):g.append(p+n)
    return n
 if o:
    if p+n in g:g.remove(p+n)
    if n not in f:f.append(n)
 return h(n)
def O(P):
 for N in['**=','//=','==','!=','<>','<=','>=','+=','-=','*=','/=','%=','//','**','<<','>>','<','>','+','-','*','/','%','&','|','^','~',':',',','.','=','(',')','[',']','{','}']:
    if N in P:
     r=''
     for M in P.split(N):r+=O(M)+N
     return r[:-aB(N)]
 if P in f and P not in b.values():return b[P]
 return P
def Q(R):
 S=[]
 for P in R:
    if P.strip()=='':continue
    T=0
    for B in P:
     if not B in string.whitespace:break
     T+=1
    if c!='':U=d
    else:U=''
    P=c+P.strip();V=''
    while P:
     B=P[0]
     if B in['"',"'"]:
        W=B;u=0;X='';Y=False
        while aA:
         u+=1;B=P[u]
         if Y:Y=az;X+=B;continue
         if B=='\\':Y=True
         elif B==W:break
         X+=B
        e.append(X);V+=W*2;P=P[u+1:]
     else:
        if B=='#':break
        V+=B;P=P[1:]
    P=V
    if P=='':continue
    if' 'not in P:L=''
    else:L,P=P.split(' ',1)
    if L in['class','def']:
     i=P.split('(')[0].split(':')[0].strip();U+=L+' ';f.append(i);U+=h(i)
     if'('in P:
        U+='(';C=P.split('(',1)[1];C=')'.join(C.split(')')[:-1]);Z=''
        for B in C:
         if B==','and Z.count('(')==Z.count(')'):U+=m(Z,aA)+',';Z=''
         else:Z+=B
        U+=m(Z,aA)+')'
     U+=':'
    _='';aa=[]
    if L=='from':ab,D=P.split('import');ab=ab.strip();L,P='import',D;_+='from '+ab+' '
    if L=='import':
     _+='import '
     for ab in P.split(','):ab=ab.strip();_+=ab+','
     _=_[:-1];U+=_
    if U.strip()=='':
     ac=m(L+' '+P)
     if c!='':d=U+ac;continue
     U+=ac;d=''
    S.append((T,U))
 for u,(T,P)in aC(S):S[u]=(T,O(P))
 return S
def ad(ae):
 af=[];ag='';ah=0;ai=0
 for u,(T,P)in aC(ae):
    for aj in ay:
     if P[:aB(aj)]==aj:L=aj;P=P[aB(aj):];break
    else:L=''
    W=';'
    for aj in['import','global']:
     if L==aj and ag.startswith(aj):L='';P=P.strip();W=','
    if L not in['if','elif','else','while','for','def','class','try','except','finally']and T==ai:ag+=W*(ag!='')+L+P
    else:af.append((ah,ag));ag=L+P;ah=T
    ai=T
 af.append((ah,ag));ak=[];u=0
 while u<aB(af):
    T,P=af[u]
    if u!=aB(af)-1 and af[u+1][0]==T+1 and(u==aB(af)-2 or af[u+2][0]<=T):ak.append((T,P+af[u+1][1]));u+=1
    else:ak.append((T,P))
    u+=1
 return ak
def al(af):
 am=''
 for an in sorted(g,key=lambda s:-s.count('.')):
    ao=an.split('.')
    if ao[0]in b.values():continue
    j=0
    for T,P in af:
     if P.startswith('import'):continue
     j+=P.count(an)
    if j>1:
     am+=';'*(am!='')+h(an)+'='+an
     for ap,(T,P)in aC(af):
        if P.startswith('import'):continue
        aq='';ar='';u=0
        while u<aB(P):
         B=P[u]
         if B not in aw+ax+'_.':
            if ar==an:aq+=h(an)
            else:aq+=ar
            ar='';aq+=B;u+=1;continue
         if B in'"\'':
            aq+=B;W=B;Y=False
            while aA:
             u+=1;B=P[u];aq+=B
             if Y:Y=az;continue
             if B=='\\':Y=True
             if B==W:break
            u+=1;continue
         ar+=B;u+=1
        af[ap]=(T,aq+ar)
 return[af[0]]+[(0,am)]+af[1:]
def at(au):
 R=aD(au);av=aD('golfed.py','w')
 for T,P in al(ad(Q(R))):av.write('\t'*(T/2)+' '*(T%2)+P+'\n')
 R.close();av.close()
at('golfer.py')

```

# Answer
> 14 votes
## BrainFuck - 489 Characters

Removes all non executable characters. Respects comments from # to end of line.

```
,[>--[<++>+++++++]<+[>+>+<<-]>[<+>-]+>[<->[-]]<[[,----------]]<>>--[>+
<++++++]<<--------[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>+<<<-[>+>+<<-]>
[<+>-]+>[<->[-]]<[->>.<<]>>+<<<-[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>+
<<<-[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>++++++++++++++<<<------------
--[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>++<<<--[>+>+<<-]>[<+>-]+>[<->[-
]]<[->>.<<]>++++[>+++++++<-]>+<<++++[<------->-]<-[>+>+<<-]>[<+>-]+>[<
->[-]]<[->>.<<]>>++<<<--[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>[-]<<<,]

```

Naturally run through itself from this source:

```
,[

#subtract #
>--[<++>+++++++]<+

#strip comments
[>+>+<<-]>[<+>-]+>[<->[-]]<[[,----------]]<

#put '+' in 4th cell
>>--[>+<++++++]<<
#+
--------
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>+<<<
#,
-
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>+<<<
#-
-
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>+<<<
#.
-
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>++++++++++++++<<<
#<
--------------
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>++<<<
#>
--
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>++++[>+++++++<-]>+<<
#[
++++[<------->-]<-
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>++<<<
#]
--
[>+>+<<-]>[<+>-]+>[<->[-]]<[->>.<<]>>[-]<<<
,]

```

# Answer
> 4 votes
# Brainfuck golfer in Bash (v3)

This is a work in progress, I will keep updating it if I can.

Reads from a file (the filename should be the first command-line argument).

For now all it does is

* Remove any characters that are not `<>+-.,[]`
* Remove two-character strings that do nothing useful, e.g. `<>`, `><`, `+-`, `-+`
* When it is done, it repeats the entire procedure, so `>>>><<<<<` gets reduced to `<`

## Code

```
#!/bin/bash

#if the file exists, take input from it
if [ -f $1 ]; then
input=`cat $1`
else
#complain to STDERR and exit
echo "File not found. Exiting with status 1.">&2
exit 1
fi

original=$input #save the original input
code=$input #save original input to another variable which we will be golfing
code=`echo $code|grep -o "[][<>.,+-]"|tr -d " \n"` #remove non-executable chars
output=$code; #this will be output
hits=-1; #Count the number of golfing operations carried out every time the code loops. When this is 0, the code will be completely golfed.

until [ $hits = 0 ]; do
hits=0
#we will be processing the optimised version from last time
code=$output
output=""

#Keep taking characters off from $code until it is empty
until [ m$code = m ]; do
#examine the first two chars
c1=${code:0:1}
code=`echo $code|cut -c2-`
c2=${code:0:1}
#if this is 1, the two characters now being read will be removed
ignore=0

if [ $c1$c2 = "<>" ] ; then
#set the second character to be taken off as well and not saved to output
ignore=1
elif [ $c1$c2 = "><" ] ; then
ignore=1
elif [ $c1$c2 = "+-" ] ; then
ignore=1
elif [ $c1$c2 = "-+" ] ; then
ignore=1
else
#save the char we took off to output, we aren't removing it
output=$output$c1;
fi

if [ $ignore = 1 ]; then
#ignore the second character and save no chars to output
code=`echo $code|cut -c2-`
#another hit
hits=`expr $hits + 1`
fi

#end inner until loop
done
#end main loop
done

#done, print output
echo $output;
exit 0;

```

## How it works

After removing all non-executable characters, it does the following. The hits counter is set to `-1` at the start - it counts how many golfing operations were carried out each time the outer loop runs.

1. If the code being golfed is empty, go to step 5.
2. Read the first two chars from the code, and remove the first char.
3. If they are `<>`, `><`, `+-` or `-+`, add 1 to the `hits` counter and go back to step 1.
4. If not, save the first character to output and go to step 1.
5. If the hits counter is 0, print output and exit.
6. If not, reset the hits counter to 0, set the code being golfed to be the output variable, reset output to the empty string, and go to step 1.

# Answer
> 3 votes
# HQ9+ golfer in Bash (v3)

I know HQ9+ is useless, but I might as well submit a five-liner for it. It reads from ~~standard input~~ a file. The path to the file should be the first command-line argument.

## Features

* Removes all comment characters (anything except `HhQq9+`)
* Removes `+` (it increments a number but there is no way to print that number)
* Converts `hq` to uppercase (not golfing)

## Code

```
#!/bin/bash
if [ -f $1 ]; then
input=`cat $1`
else exit 1; fi
echo $input|tr "[[:lower:]]" "[[:upper:]]"|grep -o "[HQ9]"|tr -d ' \n'
exit 0

```

# Answer
> 3 votes
# Java with Java

Takes the file name as a command line argument, and edits the file in place.

* Removes comments
* Shortens identifiers (including classes, methods, variables, method parameters, and lambda expression parameters)
* Trims spaces
* Shortens imports
* Removes unnecessary braces around one-line statements
* Converts `while(true)` to `for(;;)`
* Removes unneeded modifiers, such as `private` and `final`

When the program is run on itself, its size is reduced from 7792 to 4366.

```
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Golfer {

    public static void main(String[] args) throws IOException {
        Path path = new File(args[0]).toPath();
        String program = Files.readAllLines(path).stream().collect(Collectors.joining("\n"));
        Golfer golfer = new Golfer(program);
        System.out.println(golfer.toString().length() + " characters");
        System.out.println(golfer.toString().getBytes().length + " bytes");
        golfer.golf();
        String str = golfer.toString();
        Files.write(path, Arrays.asList(str));
        System.out.println(golfer);
        System.out.println(golfer.toString().length() + " characters");
        System.out.println(golfer.toString().getBytes().length + " bytes");
    }

    private String program;

    public Golfer(String program) {
        this.program = program;
    }

    public void golf() {
        doUnicodeSubstitutions();
        protectStrings();
        removeComments();
        removeDuplicateSpaces();
        removeExcessSpaces();
        removeUnnecessaryModifiers();
        simplifyImports();
        shortenIdentifiers();
        improveControlStructures();
        unprotectStrings();
    }

    void removeDuplicateSpaces() {
        program = program.replaceAll("\\s+", " ");
    }

    void removeExcessSpaces() {
        program = program.trim();
        program = program.replaceAll("([.,;:?!@%^&*()\\[\\]{}=|/<>~]) ", "$1");
        program = program.replaceAll(" ([.,;:?!@%^&*()\\[\\]{}=|/<>~])", "$1");
        program = program.replaceAll("([^+]) \\+", "$1+").replaceAll("\\+\\+ \\+", "+++").replaceAll("\\+ ([^+])", "+$1");
        program = program.replaceAll("([^-]) -", "$1-").replaceAll("-- -", "---").replaceAll("- ([^-])", "-$1");
    }

    void removeUnnecessaryModifiers() {
        program = program.replaceAll("private |final |@Override ", "");
    }

    void simplifyImports() {
        int startImports = program.indexOf("import ");
        List<String> imports = new ArrayList();
        Matcher importMatcher = Pattern.compile("import [A-Za-z0-9$_.*]*;").matcher(program);
        while (importMatcher.find()) {
            imports.add(importMatcher.group());
        }
        for (int i = 0; i < imports.size(); i++) {
            if (!imports.get(i).endsWith("*;")) {
                imports.set(i, imports.get(i).replaceFirst("\\.[A-Za-z0-9$_]*;", "\\.*;"));
            }
            imports = imports.stream().distinct().collect(Collectors.toList());
            program = program.replaceAll("import [A-Za-z0-9$_.*]*;", "");
            program = program.substring(0, startImports) + String.join("", imports) + program.substring(startImports);
        }
    }

    private List<Character> unusedCharacters;

    void shortenIdentifiers() {
        unusedCharacters = IntStream.concat(IntStream.rangeClosed('a', 'z'), IntStream.rangeClosed('A', 'Z'))
                .mapToObj(i -> (char) i)
                .filter(c -> !Pattern.compile("[^A-Za-z0-9$_']" + c + "[^A-Za-z0-9$_]").matcher(program).find())
                .collect(Collectors.toList());
        shortenIdentifiers("(class|interface|enum) ([A-Za-z0-9$_]{2,})( extends [A-Za-z0-9$_]+)?( implements [A-Za-z0-9$_,]+)?\\{",
                           2, "[^A-Za-z0-9$_]", "[^A-Za-z0-9$_]");
        shortenIdentifiers("([A-Za-z0-9$_]+(\\[+\\]+| )|<[A-Za-z0-9$_,]+>+\\[+\\]+)(?<!implements |else |package |import |return )([A-Za-z0-9$_]{2,})(?<!null)[=,;)]",
                           3, "[^A-Za-z0-9$_]", "[^A-Za-z0-9$_(]");
        shortenIdentifiers("([A-Za-z0-9$_]+ |<[A-Za-z0-9$_,]+>+)(?<!new |else )([A-Za-z0-9$_]{2,})(?<!main|toString|compareTo|equals|hashCode|paint|repaint)\\(",
                           2, "[^A-Za-z0-9$_]", "\\(", "::", "[^A-Za-z0-9$_]");
        shortenIdentifiers("[^A-Za-z0-9$_]([A-Za-z0-9$_]{2,})(,[A-Za-z0-9$_]+)*\\)?->",
                           1, "[^A-Za-z0-9$_]", "[^A-Za-z0-9$_(]");
    }

    void shortenIdentifiers(String pattern, int groupNumber, String... afficesForReplacement) {
        Pattern compiledPattern = Pattern.compile(pattern);
        Matcher matcher;
        while ((matcher = compiledPattern.matcher(program)).find()) {
            String identifer = matcher.group(groupNumber);
            char newIdentifier;
            if (unusedCharacters.remove((Character) identifer.charAt(0))) {
                newIdentifier = identifer.charAt(0);
            } else if (Character.isUpperCase(identifer.charAt(0))
                       && unusedCharacters.remove((Character) Character.toLowerCase(identifer.charAt(0)))) {
                newIdentifier = Character.toLowerCase(identifer.charAt(0));
            } else if (Character.isLowerCase(identifer.charAt(0))
                       && unusedCharacters.remove((Character) Character.toUpperCase(identifer.charAt(0)))) {
                newIdentifier = Character.toUpperCase(identifer.charAt(0));
            } else if (unusedCharacters.size() > 0) {
                newIdentifier = unusedCharacters.remove(0);
            } else {
                System.err.println("out of identifiers");
                break;
            }
            for (int i = 0; i < afficesForReplacement.length; i += 2) {
                program = program.replaceAll('(' + afficesForReplacement[i] + ')' + identifer + "(?=" + afficesForReplacement[i + 1] + ')', "$1" + newIdentifier);
            }
        }
    }

    void improveControlStructures() {
        program = program.replaceAll("while\\(([^()]+)\\)\\{", "for(;$1;){");
        program = program.replaceAll("for\\(([^()]*);true;([^()]*)\\)", "for($1;;$2)");
        while (!program.equals(removeBrackets(program))) {
            program = removeBrackets(program);
        }
    }

    String removeBrackets(String string) {
        return string.replaceAll("((if|while|do)\\([^{;]*\\))\\{([^;}]*;)\\}", "$1$3")
                .replaceAll("else\\{([^;}]*;)\\}", "else $1")
                .replaceAll("(for\\([^{;]*;[^{;]*;[^{;]*\\))\\{([^;}]*;)\\}", "$1$2");
    }

    void protectStrings() {
        adjustStrings(1000);
    }

    void unprotectStrings() {
        adjustStrings(-1000);
    }

    void adjustStrings(int n) {
        char[] chars = new char[program.length()];
        for (int i = 0; i < program.length(); i++) {
            chars[i] = program.charAt(i);
            if (chars[i] == '"' && chars[i - 1] != '\'') {
                for (i++; chars.length > i + 1 && program.charAt(i) != '"'; i++) {
                    chars[i] = (char) (program.charAt(i) + n);
                }
                chars[i] = program.charAt(i);
            }
        }
        program = new String(chars);
    }

    void removeComments() {
        program = program.replaceAll("(?s)/\\*.*\\*/", "");
        program = program.replaceAll("//.*\n", "");
    }

    void doUnicodeSubstitutions() {
        List<Character> chars = new ArrayList();
        for (int i = 0; i < program.length(); i++) {
            if (program.charAt(i) != '\\' || program.charAt(i + 1) != 'u') {
                chars.add(program.charAt(i));
            } else {
                chars.add((char) Integer.parseInt(program.substring(i + 2, i + 6), 16));
                i += 5;
            }
        }
        char[] charArray = new char[chars.size()];
        for (int i = 0; i < charArray.length; i++) {
            charArray[i] = chars.get(i);
        }
        program = new String(charArray);
    }

    @Override
    public String toString() {
        return program;
    }
}

```

# Answer
> 2 votes
## Perl, Parts 1 - 2

(removes comments and ignores `#` characters inside double quotes)

(removes all whitespace after brackets and `=` signs)

I did not try to golf this code. Maybe, when it is done, it could golf itself.

```
$/="\n\n";
chomp($prog = <>);
for(1..length($prog)){
 $rev.=chop $prog;
}
#print$rev;
for(1..length($rev)){
 $temp = chop$rev;
 if ($temp eq '"'){
  if($quote == 0){$quote = 1}
  else{$quote = 0}
 }
 if($temp eq '#' && $quote == 0){$comment = 1}
 if($temp eq "\n"){
  $comment = 0;
 }
 if($comment != 1){
  $prog.=$temp;
 }
}
for(1..length($prog)){
 $rev.=chop $prog;
}
for(1..length($rev)){
 $temp = chop$rev;
 if ($temp eq ";" || $temp eq "}" || $temp eq ")" || $temp eq "=" || $temp eq "{"){
  $ws = 2;
 }
 if(($temp eq "\n" || $temp eq " ") && $ws != 0){$ws = 1}elsif($ws==1){$ws=0}
 if($ws != 1){
  $prog.=$temp;
 }
}
print$prog;

```

Example input

```
for(1..10) {
 print "Hello, World!";#prints hello world
 print ($n = <>); #prints "#"
}

```

Output

```
for(1..10){print "Hello, World!";print ($n =<>);}

```

Next, it will eliminate spaces between symbols and alphanumeric characters.

# Answer
> 1 votes
# Java golfer in Perl

WIP at the moment, although it gets pretty nice code right now.

Features:

* Removes all comments
* Removes unnecessary whitespace
* Removes package declarations (it's single-file anyway!)

## Code

```
#!/usr/bin/env perl
use strict;
use warnings;

my $string_re = qr/"(?:\\[btnfr"'\\]|\\(?:[0-3][0-7][0-7]|[0-7]{1,2})|\\u+[0-9a-fA-F]{4}|[^\r\n\\"])*"/;
my @lines = <>;
my @strings = ();

# First, replace strings with placeholders. Strings suck REALLY hard when replacing.
map {
  while (m/$string_re/) {
    s//"\032".@strings."\032"/e;
    push @strings, $&;
  }
} @lines;

# Remove comments
my $in_comment = 0;
my $partial_line;

sub remove_comments {
  my $line = $_[0];
  start:
  if ($in_comment) {
    if ((my $mulc_end_index = index $line, '*/') != -1) {
      $line = $partial_line . substr $line, $mulc_end_index + 2;
      $in_comment = 0;
      goto no_comment;
    }
    return 0;
  }

  no_comment:
  my $eolc_idx = index $line, '//';
  my $mulc_idx = index $line, '/*';

  if ($mulc_idx == -1 || ($eolc_idx != -1 && $eolc_idx < $mulc_idx)) {
    $line =~ s;//.*$;;;
  } elsif ($mulc_idx != -1) {
    $in_comment = 1;
    $partial_line = substr $line, 0, $mulc_idx;
    goto start;
  }
  $_ = $line;
  return 1
}

@lines = grep {&remove_comments($_)} @lines;

# Remove empty lines, remove line ends
@lines = grep(!/^\s*$/, @lines);
map {chomp;s/^\s*//;s/\s*$//} @lines;

# Remove unnecessary whitespace
map {s/\s*([][(){}><|&~,;=!+-])\s*/$1/g} @lines;

# Remove unnecessary package declaration
$lines[0] =~ s/^package [^;]+;//;

# Finally, put strings back.
map {s/\032(\d+?)\032/$strings[$1]/g} @lines;

print @lines;

```

---
Tags: popularity-contest, metagolf
---


title: Print the Longest Sentence

text:
# Question
Title: Print the Longest Sentence
*I've searched around, and cannot find a challenge too similar to this one--however, it would not surprise me if this is not the first of its kind. My apologies if I've overlooked something.*

# The Challenge

This challenge is intended to amuse those of every skill level and users of every language. Your task, in itself, is very simple. Write a program (or function) that prints the longest sentence in 140 bytes.

# The Input

Your code should not receive input from anywhere. You may not take any arguments, any values from STDIN, or any word lists. Additionally, built-ins or libraries that generate word lists or manipulate word lists are also banned. Output should be generated by the program itself.

# The Output

Your output should abide by the following rules:

* For simplicity, the output must be in **English**, and must not contain any characters other than `a-z A-Z .,:;()!?-`. (Tabs and newlines should not be present in your sentence, and exactly one space should exist between words)
* Your output may include trailing or leading whitespace, but these do not count toward your final score.
* Your output must be a singular, valid, punctuated, grammatically correct sentence.
* As long as the sentence is syntactically valid, meaning is unimportant. Please refrain from vulgarity.
* Your output should only include words recognized by dictionary.com.
* Your output must not repeat any singular word more than 3 times. Conjunctions and articles are an exception to this rule and may be repeated any number of times.
* Your output must be **finite**.
* Any output method is acceptable--whether it be to STDOUT, a file, a returned string, whatever.

# The Rules

* Your score is the length, in bytes, of the sentence your program generates.
* Program source code should not exceed 140 bytes. *Insert witty comment about how my only method of communication is Twitter here.*
* Your program should terminate within a minute on any modern machine.
* Sufficiently clever code or valid output larger than the code itself may be eligible for a bounty!
* Standard loopholes apply.

*Questions, comments, concerns? Let me know!*

# Answer
# CJam, 140 bytes → 2301 characters

Try it online.

### Code

```
"I'm ""jdÇÉÛ7ª%ùÞtÛù    ±çV(exç3å$Z±³RÌÊ
D»l°ØEøv¸x¡·ðQà\+ÜµjR¡2>ãq§Sã¾iPLÛ"252b27b'`f+'`/2/{~"ing, "+f+~}/"and "\7<]]3*" while "*'.

```

### Output

```
I'm bagging, fagging, gagging, lagging, nagging, ragging, sagging, tagging, wagging, bailing, failing, hailing, jailing, mailing, nailing, railing, sailing, tailing, wailing, capping, lapping, mapping, napping, rapping, sapping, tapping, yapping, zapping, bearing, fearing, gearing, hearing, nearing, rearing, searing, tearing, wearing, bending, fending, lending, mending, pending, rending, sending, tending, vending, wending, betting, getting, jetting, letting, netting, petting, setting, vetting, wetting, dipping, hipping, kipping, nipping, pipping, ripping, sipping, tipping, yipping, zipping, bobbing, dobbing, fobbing, gobbing, jobbing, lobbing, mobbing, robbing, sobbing, bulling, culling, dulling, fulling, gulling, hulling, lulling, mulling, and pulling while I'm bagging, fagging, gagging, lagging, nagging, ragging, sagging, tagging, wagging, bailing, failing, hailing, jailing, mailing, nailing, railing, sailing, tailing, wailing, capping, lapping, mapping, napping, rapping, sapping, tapping, yapping, zapping, bearing, fearing, gearing, hearing, nearing, rearing, searing, tearing, wearing, bending, fending, lending, mending, pending, rending, sending, tending, vending, wending, betting, getting, jetting, letting, netting, petting, setting, vetting, wetting, dipping, hipping, kipping, nipping, pipping, ripping, sipping, tipping, yipping, zipping, bobbing, dobbing, fobbing, gobbing, jobbing, lobbing, mobbing, robbing, sobbing, bulling, culling, dulling, fulling, gulling, hulling, lulling, mulling, and pulling while I'm bagging, fagging, gagging, lagging, nagging, ragging, sagging, tagging, wagging, bailing, failing, hailing, jailing, mailing, nailing, railing, sailing, tailing, wailing, capping, lapping, mapping, napping, rapping, sapping, tapping, yapping, zapping, bearing, fearing, gearing, hearing, nearing, rearing, searing, tearing, wearing, bending, fending, lending, mending, pending, rending, sending, tending, vending, wending, betting, getting, jetting, letting, netting, petting, setting, vetting, wetting, dipping, hipping, kipping, nipping, pipping, ripping, sipping, tipping, yipping, zipping, bobbing, dobbing, fobbing, gobbing, jobbing, lobbing, mobbing, robbing, sobbing, bulling, culling, dulling, fulling, gulling, hulling, lulling, mulling, and pulling.

```

### Explanation

As I'm sure you can tell, my main tactic was to generate a large number of very similar words. My plan was to find groups of words that all had the same spelling after the first letter with a large number of possible first letters, as these could be heavily compressed. To find the best candidates, I grabbed the whole dictionary, grouped words by their spelling after the first letter, and sorted these groups in descending order by the sum of the lengths of all words in the group.

Upon doing this, I discovered that many of the top entries were the present tense of verbs, in the form "\___ing." This was great, because it meant that not only could I abstract the "ing" out of every group, but also every word could simply be thrown in a big list in the sentence because they were all of a form of speech that allowed it. The big mess of characters in the middle of the code encodes as much of this data as I could fit, using multiple compression methods.

As for the sentence structure generated, it's fairly simple. It's certainly a bit redundant, repeating the main phrase 3 times for maximal length, but I believe it's grammatically correct. With the innards of the verb lists cut out, the sentence looks like this:

```
I'm bagging, ... , and pulling while I'm bagging, ... and pulling while I'm bagging, ... and pulling.

```
> 5 votes

# Answer
# Python - Code: 140, Output: 476

NOTE: Currently needs to be modified. Any help on replacing a couple words within the byte limit?

I made use of the built-in documentation for the integer type, and so far I am confident that this is one of the most unique, if not the most creative, approach(es).

Most of the code was overhead used to remove newlines and combine the documentation into a single sentence. Annoyingly, I also had to replace a couple of occurrences of the word "string".

```
import re;print'Cattle, c'+re.sub('a string','a key',re.sub('  ',', but ',re.sub(r'\. ',', and',re.sub(r'\n',' ',int.__doc__.lower()))[28:]))

```

Output:

```
Cattle, convert a key or number to an integer, if possible, and a floating point argument will be truncated towards zero (this does not include a key representation of a floating point number!), but when converting a key, use the optional base, and it is an error to supply a base when converting a non-string, and if base is zero, the proper base is guessed based on the string content, and if the argument is outside the integer range a long object will be returned instead.

```

Run it here: http://repl.it/fsM
> 3 votes

# Answer
# JAVA - Code: 122, length: 153 words, 464 bytes

Java, yep, java. Ok, so I had to make it a function instead of a program. The boilerplate was just too much.

Golfed code:

```
void p(){int i=0;char c=1;while(i++<3){for(c=65;c<90;System.out.print(c+++" and "));}System.out.print(c+" are letters.");}

```

Readable version:

```
void p(){
    int i=0;
    char c=1;
    while(i++<3){
        for(c=65;c<90;System.out.print(c+++" and "));
    }
    System.out.print(c+" are letters.");
}

```

Output: A and B and C and D and E and F and G and H and I and J and K and L and M and N and O and P and Q and R and S and T and U and V and W and X and Y and A and B and C and D and E and F and G and H and I and J and K and L and M and N and O and P and Q and R and S and T and U and V and W and X and Y and A and B and C and D and E and F and G and H and I and J and K and L and M and N and O and P and Q and R and S and T and U and V and W and X and Y and Z are letters.

Each letter is defined under dictionary.com as a valid word in response to its ordinal position in the alphabet. Each word is used at most three times.
> 1 votes

# Answer
# Haskell, code: around 104 bytes, output: as many as your computer can produce within the 1min limit

```
f = let n=4 in putStr $ "Corollary: "++ (replicate n '(') ++ "a-b" ++ (replicate n ')') ++ " equals c."

```

Output example:

```
Corollary: ((((a-b)))) equals c.

```

Of course you can change `n` to any number you want (including expressions like `100^100` to stay within the 140 byte limit) to increase the number of parentheses.
> -1 votes

# Answer
**Excel** (because ... :) ): Code: 135 Output: 211

\[edit\] corrected beginning of sentence, the previous one really wasn't correct, this version is slightly better. Still a bit of a grammar "hack", but still valid by the rules in any case :) \[/edit\]

```
=CONCATENATE("Where ",REPT("someone thinks that ",3),rept("everyone understands when ",3),rept("they believe what ",3),"nobody cares.")

```

**Output:**

```
Where someone thinks that someone thinks that someone thinks that everyone understands when everyone understands when everyone understands when they believe what they believe what they believe what nobody cares.

```
> -2 votes

---
Tags: code-challenge, restricted-source
---


title: Generate math problems

text:
# Question
Title: Generate math problems
**Generate math problems (addition, subtraction, or multiplication) using numbers 0-10. Provide feedback on whether the user was right or wrong and show a score.**

Specifics:

* Must generate addition, subtraction, or multiplication problems
* Numbers used must be 0-10
* Each problem must be equally likely
* If user is correct, must print "correct!" (with the exclamation point)
* If user is wrong, must print "wrong!" (with the exclamation point)
* After providing correct or wrong feedback, must show score with these specifications:

+ Starts with "Score:"
    + Shows number correct and then "correct"
    + Pipe (`|`) separation
    + Shows number wrong and then "wrong"
    + 2 newlines for separation
* Must repeat forever

For counting characters, the Text Mechanic counter will be used.

Sample session:

```
1-7=-6
correct!
Score: 1 correct | 0 wrong

9+3=12
correct!
Score: 2 correct | 0 wrong

4*5=20
correct!
Score: 3 correct | 0 wrong

7-8=3
wrong!
Score: 3 correct | 1 wrong

1*1=3
wrong!
Score: 3 correct | 2 wrong

7+6=

```

# Answer
> 6 votes
**Post-mortem update:**

## Perl 130 bytes

Combining techniques from dan1111's excellent solution with my own, I was able to squeeze one more byte:

```
@b=qw(Score: 0 correct | 0 wrong);$b[$#x=eval^<>?4:1]++while print"$b[@x]!
@b

"x/./,$_=(0|rand 11).chr(41^2+rand 3).~~rand 11,'='

```

There's a few things that might not be immediately obvious. If `@x` is an array, then `$#x` (the largest index of `@x`) will be one smaller than the length of `@x`. In this way, I can use `$#x` to point to the appropriate counting variable, and the length of `@x` to the corresponding message in a single assignment, without having to `+1`. The score string is repeating by `/./`, which will return `1` if an only if `$_` is non-empty.

---

## Perl 131 bytes

Here's my Perl attempt, which is more or less a direct translation of my PHP solution below.

```
@r=correct,${_^($n=eval^<>?z:r)}++while@z=wrong,print"@$n!
Score: $- @r | $% @z

"x@r,$_=(0|rand 11).chr(41^2+rand 3).~~rand 11,'='

```

`$-` and `$%` are used for counting variables as they default to `0`, alleviating the need for a `printf`, and at the same time allowing me to combine the `print` statements into one. The score string is not printed the first iteration because `@r` has not yet been defined, and therefore `x@r` (repeat by the length of the array `@r`) repeats the string zero times, resulting in an empty string.

Once again using `chr(41^2+rand 3)` to generate `+*-`, as well as a bitwise xor `_^` to switch between `r``-` and `z``%`. I would have liked to use a type glob for `*n=eval^<>?z:r`, saving a byte `@$n``@n`, but unfortunately typed as a string this comes back as either `*main::r` or `*main::z`, which isn't very useful.

\</bandwagon\>

---

## PHP 157 (155) bytes

Just to get a smattering of languages:

```
<?for($X=$Y=+$x=correct;$y=wrong;)echo$q=rand(0,10).chr(rand(2,4)^41).rand(0,10),'=',eval("\${_&\$n=$q^fgets(STDIN)?y:x}++;"),$$n,"!
Score: $X $x | $Y $y

";

```

The initial `$X=$Y=+` is necessary, because undefined variables print as an empty string, instead of `0`. Unfortunate, but still shorter than using a `printf`. One thing to notice is the 'magic formula' `chr(rand(2,4)^41)`. *2^41 = 43* (+), *3^41 = 42* (\*) and *4^41 = 45* (-). `chr(rand(3,5)^46)` would also work, but in a different order.

This can be made 2 bytes shorter by using a few binary characters:

```
<?for($‡=$†=+$x=correct;$y=wrong;)echo$q=rand(0,10).chr(rand(2,4)^41).rand(0,10),~Â,eval("\${~\$n=$q^fgets(STDIN)?y:x}++;"),$$n,"!
Score: $‡ $x | $† $y

";

```

where ,  and `Â` are characters *134*, *135* and *194* respectively.

# Answer
> 4 votes
**Perl, 144 characters**

```
@b=qw/+ - * Score: correct 0 | wrong 0/;sub _{print@_;~~rand 11}{_$_=_.$b[rand 3]._,'=';_$b[$x=eval==<>?4:7];$b[$x+1]++;_"!\n@b[3..8]\n\n";redo}

```

Updated (thanks ardnew)

# Answer
> 4 votes
## APL ~~146~~ 145

In index origin zero:

```
o←'+-×'
s←0 0
t←'wrong' 'correct'
l:⍞←(e←(⍕?11),o[?3],(⍕?11)),'='
r←(⍎e)=⍎⍞
s[r]←s[r]+1
(∊t[r]),'!'
'Score: ',s[1],t[1],'|',s[0],t[0]
' '
' '
→l

10×8=80
correct!
 Score:  1 correct | 0 wrong

2×6=16
wrong!
 Score:  1 correct | 1 wrong

2+5=

```

# Answer
> 3 votes
## Python 2, 180 176

```
from random import*
r=randrange
a='correct'
b='wrong'
c=w=0
while 1:e=`r(11)`+'+-*'[r(3)]+`r(11)`;x=input(e+'=')==eval(e);c+=x;w+=1-x;print(b,a)[x]+'!\nScore:',c,a,'|',w,b+'\n'

```

That counter says it's only 171 chars, but I've counted new lines since that's what we normally do in code golf.

Thanks to flornquake for some improvements.

Ungolfed:

```
from random import *
num_correct = num_wrong = 0
while 1:
    expression = str(randrange(11)) + '+-*'[randrange(3)] + str(randrange(11))
    is_correct = input(expression + '=') == eval(expression)
    num_correct += is_correct
    num_wrong += 1 - is_correct
    print ('wrong', 'correct')[is_correct] + '!\nScore:', num_correct, 'correct', '|', num_wrong, 'wrong\n'

```

# Answer
> 3 votes
## Perl 154 chars

```
$x=correct;$y=wrong;R:$_=join qw|+ - *|[rand 3],map~~rand 11,0,0;print"$_=";$c+=$b=<>==eval;printf"%s!$/Score: %d $x | %d $y$/$/",$b?$x:$y,$c,$.-$c;goto R

```

with some newlines:

```
$x=correct;
$y=wrong;
R:
  $_=join qw|+ - *|[rand 3],map~~rand 11,0,0;
  print"$_=";
  $c+=$b=<>==eval;
  printf"%s!$/Score: %d $x | %d $y$/$/",$b?$x:$y,$c,$.-$c;
  goto R

```

# Answer
> 2 votes
## Javascript 169 chars

Here's a solution that doesn't use the console (does that break the rules?) but works via alert boxes (yeah I know...):

```
for(c=w=0;r=Math.random;){prompt(x=~~(r()*9+1)+"+-*"[~~(r()*3)]+~~(r()*9+1))==eval(x)?(m="correct",c++):(m="wrong",w++);alert(m+"!\nScore: "+c+" correct | "+w+" wrong")}

```

The attempts at golfing are quite weak, but this was just for fun right? :)

**EDIT**: Ungolfed version follows. I expanded variable names and split up the assignment of `x` into `a`, `op` and `b`. The logic is the same. Bear in mind that `~~(X)` == `Math.floor(X)` for positive `X`. This is just easier to type.

```
correct=wrong=0;
rand=Math.random;
while(1){
  a=~~(rand()*9+1);
  op="+-*"[~~(rand()*3)];
  b=~~(rand()*9+1);
  x=a+op+b;
  if(prompt(x)==eval(x)){msg="correct";correct++}
  else{msg="wrong";wrong++}
  alert(msg+"!\nScore: "+c+" correct | "+w+" wrong");
}

```

# Answer
> 2 votes
# K, 155

```
k:l:0;
while[1;
    1@(s:,/(($2?11),(1?"+-*"))0 2 1),"=";
    -1@*$[(.:s)="I"$0:0;("correct!";l+:1);("wrong!";k+:1)];
    -1"Score: ",($l)," correct | ",($k)," wrong\n\n"
    ]

```

# Answer
> 2 votes
## **C# - 283 Characters**

This is my solution in C# in 283 characters:

```
var r=new Random();int a=0,b=0,x=0,y=0;var w="";Action C=()=>Console.WriteLine(w);for(;;){x=r.Next(11);y=r.Next(11);int[]R={x+y,x-y,x*y};w=""+x+"+-*"[x%3]+y+"=";C();var f=Console.ReadLine()==""+R[x%3];x=f?a++:b++;w=(f?"correct":"wrong")+"!\nScore:"+a+" correct | "+b+" wrong\n";C();}

```

With more indentation, it looks like:

```
var r=new Random();
int a=0,b=0,x=0,y=0;
var w="";
Action C=()=>Console.WriteLine(w);
for(;;){
    x=r.Next(11);y=r.Next(11);
    int[] R={x+y,x-y,x*y};
    w=""+x+"+-*"[x%3]+y+"=";C();
    var f=Console.ReadLine()==""+R[x%3];
    x=f?a++:b++;
    w=(f?"correct":"wrong")+"!\nScore:"+a+" correct | "+b+" wrong\n";C();
}

```

# Answer
> 2 votes
# CJam, 90 bytes

Seems like I'm a little late to this question... as is my language, so per site rules, this answer can't officially be selected as the winner. But I had completed my answer for a recent question that was marked as a duplicate of this question and didn't want to let it go to waste, so I modified it a bit for this question.

```
{Bmr3mr"+-*"=Bmr]_o'=o~\~li=:R["correct":C"wrong":W?'!N"Score:"SUR+:USCS'|SVR!+:VSWNN]o1}g

```

Due to the interactive nature of the program, the online interpreter cannot be used. You must use the Java interpreter.

I normally post a lengthy explanation, but the code works in about as straightforward of a manner as you can get. That's not to say that I banged this answer out in all of a couple of minutes, though, as there was a fair amount of time spent searching for and making small optimizations.

# Answer
> 1 votes
## Haskell 286

```
import System.Random
main=0?0
s=show
a°b=s a++b
r=randomRIO
d=r(0,10)
p=putStr
c?w=do a<-d;b<-d;i<-r(0,2);let{(#)=[(+),(-),(*)]!!i;o="+-*"!!i};p(s a++o:b°"=");r<-getLine;let{u=fromEnum$read r/=a#b;d=c+1-u;v=w+u};p(["correct!\n","wrong!\n"]!!u);p("Score: "++d°" correct | "++v°" wrong\n\n");d?v

```

# Answer
> 0 votes
## VBA - 250

```
Sub t()
a=0
b=0
While 1
x=Int(Rnd()*11)
y=Int(Rnd()*11)
o=Int(Rnd()*3)
If InputBox(x & Array("+","-","*")(o) & y & "=")=Array(x+y,x-y,x*y)(o) Then r="Correct!":a=a+1 Else r="Wrong!":b=b+1
MsgBox r & vbCr & "Score:" & a & " correct|" & b & " wrong"
Wend
End Sub

```

Runs until the memory limit for the variables is reached, otherwise it runs 'forever'.

---
Tags: code-golf, math, arithmetic
---


# Question
Title: Brainf*** subprograms with unique outputs
You should write a 100-byte long brainfuck (BF) program.

One character will removed from it in every possible way the resulting 100 new (99-byte long) programs. E.g. for the program `++.>.` the 5 subprograms are `+.>.`, `+.>.`, `++>.`, `++..` and `++.>` .

Your score will be the number of unique outputs the 100 programs generate. Higher score is better.

## Details

* **Your programs will be terminated after outputting the first character.**
* Invalid or non-terminating programs and programs generating empty outputs are not counted towards the score.
* The BF cells are 8 bit wrapping ones. (255+1=0, 0-1=255)
* Your program is given no input. If you use `,` in the code it set's the current cell to `0`.
* There are no cells on the left side of the starting position. E.g. `<.` is invalid but `.<` is valid as the execution is terminated at `.`. The tape is unbounded in the other direction.
* Programs with unbalanced brackets (`[` and `]`) are invalid.
* Your original program can be shorter than 100 bytes as it's easy to extend it to 100 bytes without changing the score.
* Your original program doesn't have to be valid BF code.

You can use this python3 program (ideone link) to determine the score of your answer. (For long-running programs you may need to modify the `maxstep` variable.)

## Example

*(For simplicity this program is shorter than 100 bytes.)*

```
Solution: ++,+[-]+><.-,-.

Score: 3

Explanation:

Subprogram     => Output

+,+[-]+><.-,-. => 1
+,+[-]+><.-,-. => 1
+++[-]+><.-,-. => 1
++,[-]+><.-,-. => 1
++,+-]+><.-,-. => None
++,+[]+><.-,-. => None
++,+[-+><.-,-. => None
++,+[-]><.-,-. => 0
++,+[-]+<.-,-. => None
++,+[-]+>.-,-. => 0
++,+[-]+><-,-. => 255
++,+[-]+><.,-. => 1
++,+[-]+><.--. => 1
++,+[-]+><.-,. => 1
++,+[-]+><.-,- => 1

Unique outputs are [0, 1, 255]
Score is 3 for ++,+[-]+><.-,-. (length = 15)

```

In case of a tie the winner is the one with the shorter code. (Your program can be shorter than 100 bytes as stated in the Details section.) If the codes are equal length the winner is the earlier poster.

*Bonus puzzle: without the bolded restriction can you find a program with score 100?*

# Answer
# Score: 35 41 69 78 ~~79~~ 83

(Remove the newline.)

```
-->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>-
>+>->+>->+>->+>->+>->+>->+>->+>++[>[-<+++>]<<++]>.

```

Try it online!

I'm not sure exactly why it works...

# Score: 79

```
X->>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>
+>+>+>+>+>+>+>+>+>+>+>+[>[-<+>>+<]+>[-<+>]<<<+]>>.

```

Try it online!

It was *supposed to* sum 2\*mem\[i\]\*i and add the number of cells (+const) where the addresses are counted from the right to the left. The multiplier 2 and number of cells can make removing + and \> having different parity.

It indeed worked like that in the 69 points version. But the latest version broke that and got something else by coincidence. It calculates sum(mem\[i\]\*i+i+1) and removing + and \> does almost the same, except for the sum(i) which has a difference of the number of cells, which is also the number of different output for either removing + and \>.

For the bonus:

> +.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.
> 13 votes

# Answer
# Score: ~~37~~ 43

```
+>-,->,+-><->-[>---+-+<[--->>+><,+>>>++<><<<+<[>--]]><><+-+>+<<+<><+++<[[<[---->-<-]>++>],>,]<,]<+-.

```

EDIT: Now my program allows some square brackets. Not going to win any prizes with it, but that's what I get for making some weighted RNGs do the busy work for me.

This was generated by a program I wrote in C.

For every `N`th character removed, here are the outputs:

```
N = 0 => 158
N = 1 => 158
N = 2 => 158
N = 3 => 187
N = 4 => 129
N = 5 => 100
N = 6 => 158
N = 7 => 13
N = 8 => 1
N = 9 => 211
N = 10 => 129
N = 11 => 1
N = 12 => 57
N = 13 => 255
N = 14 => Mismatched Braces
N = 15 => 59
N = 16 => 11
N = 17 => 11
N = 18 => 11
N = 19 => 117
N = 20 => 11
N = 21 => 117
N = 22 => 166
N = 23 => Mismatched Braces
N = 24 => 206
N = 25 => 206
N = 26 => 206
N = 27 => 147
N = 28 => 147
N = 29 => 158
N = 30 => 148
N = 31 => 188
N = 32 => 51
N = 33 => 17
N = 34 => 84
N = 35 => 84
N = 36 => 84
N = 37 => 158
N = 38 => 158
N = 39 => 94
N = 40 => 46
N = 41 => 94
N = 42 => 94
N = 43 => 94
N = 44 => 17
N = 45 => 196
N = 46 => Mismatched Braces
N = 47 => 149
N = 48 => No Termination
N = 49 => No Termination
N = 50 => Mismatched Braces
N = 51 => Mismatched Braces
N = 52 => 45
N = 53 => 77
N = 54 => 45
N = 55 => 77
N = 56 => 50
N = 57 => 209
N = 58 => 50
N = 59 => 251
N = 60 => 249
N = 61 => 99
N = 62 => 99
N = 63 => 117
N = 64 => 89
N = 65 => 207
N = 66 => 89
N = 67 => 115
N = 68 => 115
N = 69 => 115
N = 70 => 95
N = 71 => Mismatched Braces
N = 72 => Mismatched Braces
N = 73 => 104
N = 74 => Mismatched Braces
N = 75 => No Termination
N = 76 => No Termination
N = 77 => No Termination
N = 78 => No Termination
N = 79 => Left Overflow
N = 80 => 3
N = 81 => 2
N = 82 => No Termination
N = 83 => Mismatched Braces
N = 84 => No Termination
N = 85 => 133
N = 86 => 133
N = 87 => 0
N = 88 => Mismatched Braces
N = 89 => 158
N = 90 => 0
N = 91 => 4
N = 92 => Mismatched Braces
N = 93 => 0
N = 94 => 158
N = 95 => Mismatched Braces
N = 96 => 0
N = 97 => 157
N = 98 => 159
N = 99 => None

```

There are a total of 37 unique outputs, which are (in numerical order):

```
0, 1, 2, 3, 4, 11, 13, 17, 45, 46, 50, 51, 57, 59, 77, 84, 89, 94, 95, 99,
100, 104, 115, 117, 129, 133, 147, 148, 149, 157, 158, 159, 166, 187, 188,
196, 206, 207, 209, 211, 249, 251, 255

```

I am ~~90%~~ 100% certain this solution is not optimal~~, but proving that may be exceedingly difficult~~. There are a few things that are clear. Having no `.` symbols until the last character *seems* to be the way to go~~, and square brackets (`[]`) seem to be rather useless~~. I did a little bit of thinking here, which I'd like to outline:

Let `L` be the length of the code in bytes (in the challenge, `100`), and `n` be the number of unique outputs of the sub programs.

For `L=3`, there are several optimal solutions of the form `+-.`, where `n=2` (in this case, the outputs are 1 and 255 for `+.` and `-.`, respectively.) This puts the best ratio for `L = 3` at `n/L = 66.67%`. Note that this ratio cannot be beaten for at least `L<10`.

For `L=10`, the solutions are simple enough to bruteforce it. Here are all the best solutions, at `n = 6`:

```
++>-->+<+. => 6
++>-->+<+. => 6
+++>->+<+. => 6
--->->+<+. => 6
++>---><+. => 6
+++>--><+. => 6
-->++>-<-. => 6
+++>+>-<-. => 6
--->+>-<-. => 6
-->+++><-. => 6
--->++><-. => 6

```

Which yields a score ratio of `n/L = 60%`.

As `L->infinity`, it is clear that the ratio must approach 0, since there only 255 possible outputs for a potentially infinite `L`.

The ratio does NOT, however, decrease uniformly. It is not possible to construct a solution for `n=6, L=9`, so the best possible ratio for `L=9` is `5/9 = 55.56% < 60%`.

This begs the question, how *quickly*, and in what matter, does the ratio descend? For `L = 100`, and at `10^9 checks/second`, it would take several orders of magnitude longer than the lifetime of the universe to bruteforce an optimal solution. Is there an elegant way to go about this? ~~I very much doubt that it is down to `37%` for `L = 100`.~~

The ratio actually increases, up to `L=100`. View other answers to confirm.

I'd love to hear your evaluations of the above. I ~~could be~~ was atrociously wrong, after all.
> 9 votes

---
Tags: code-challenge, brainfuck
---


title: Build a top-front-side puzzle solver

text:
# Question
Title: Build a top-front-side puzzle solver
A top-front-side puzzle is a puzzle where you are required to construct a 3-D shape of (usually cubic) blocks given three orthogonal views: a top view, a front view, and a side view.

For example, given a top, front, and side view as follows:

```
Top:        Front:      Side:
. . . .     . . . .     . . . .
. x x .     . x x .     . x x .
. x x .     . x x .     . x x .
. . . .     . . . .     . . . .

In this problem, the side view is taken from the right.

```

A 2x2x2 cube (with volume 8) would satisfy this solution, but it's doable in volume 4, if we have the following layer structure:

```
. . . .     . . . .
. x . .     . . x .
. . x .     . x . .
. . . .     . . . .

```

There are also some unsolvable arrangements. Take, for example:

```
Top:        Front:      Side:
. . . .     . . . .     . . . .
. . . .     . . x .     . . . .
. x . .     . . . .     . x . .
. . . .     . . . .     . . . .

```

If the top view says the block is second from the left, there's no way that can match the front view that says the block must be third from the left. So this arrangement is impossible.

---

Your task is to build a program that, given an arbitrary 4x4 top-front-side puzzle, attempts to solve it in the fewest number of cubes, or declares it unsolvable.

Your program will take as input a series of 48 bits, representing the top, front, and side views. They may be in any format you want (a 6-byte string, a string of 0's and 1's, a 12-digit hex number, etc.), but the order of the bits must map as such:

```
Top: 0x00   Front: 0x10 Side: 0x20
0 1 2 3     0 1 2 3     0 1 2 3
4 5 6 7     4 5 6 7     4 5 6 7
8 9 a b     8 9 a b     8 9 a b
c d e f     c d e f     c d e f

```

In other words, the bits go in a left-to-right, top-to-bottom order, in the top, then front, then side view.

Your program will then output either a series of 64 bits indicating the cubes in the 4x4x4 grid that are filled in, or indicate that the grid is unsolvable.

---

Your program will be scored by running a battery of 1,000,000 test cases.

The test data will be generated by taking the MD5 hashes of the integers "000000" through "999999" as strings, extracting the first 48 bits (12 hexits) of each of these hashes, and using them as input for the top-front-side puzzle. As an example, here are some of the test inputs and the puzzles they generate:

```
Puzzle seed: 000000   hash: 670b14728ad9
Top:        Front:      Side:
. x x .     . . . x     x . . .
x x x x     . x . x     x . x .
. . . .     . x x x     x x . x
x . x x     . . x .     x . . x

Puzzle seed: 000001   hash: 04fc711301f3
Top:        Front:      Side:
. . . .     . x x x     . . . .
. x . .     . . . x     . . . x
x x x x     . . . x     x x x x
x x . .     . . x x     . . x x

Puzzle seed: 000157   hash: fe88e8f9b499
Top:        Front:      Side:
x x x x     x x x .     x . x x
x x x .     x . . .     . x . .
x . . .     x x x x     x . . x
x . . .     x . . x     x . . x

```

The first two are unsolvable, while the last one has a solution with the following layers, front to back:

```
x . . .   . . . .   x x x .   x x x .
. . . .   x . . .   . . . .   . . . .
x . . .   . . . .   . . . .   x x x x
x . . .   . . . .   . . . .   x . . x

There are a total of 16 blocks here, but it can probably be done in less.

```

Your program's score will be determined by the following criteria, in descending order of priority:

* The highest number of solved cases.
* The lowest number of blocks required to solve those cases.
* The shortest code in bytes.

You must submit and calculate the score by yourself, which requires your program to be able to run through all 1,000,000 test cases.

# Answer
# Python: 5360 test-cases solved using 69519 blocks, 594 bytes

This should be the optimal values.

## Approach:

First I'll test if the test-case is actual solvable. I do this by initializing a list of length 64 by ones and set all positions to zero, if there the corresponding pixel of the three views is zero. Then I simple view at the puzzle from all 3 directions, and look if the views are the same as the input views. If there're equal, the puzzle is solvable (we already found the worst solution), otherwise it's unsolvable.

Then I do a branch-and-bound approach for finding the optimal solution.

**Branching:** I have a recursive function. The recursion depth tells how many values are fixed already. In each call of the function I call itself twice, if the value at the current index is 1 (this value can be 0 or 1 in the optimal solution), or once, if the value is 0 (it has to be zero in the optimal solution).

**Bounding:** I use two different strategies here.

1. I calculate the views from the 3 sides in each function call and look If they still match the input values. If they don't match, I don't call the function recursively.
2. I keep the best solution in memory. It there already more fixed ones in the current branch than in the best solution, I can already close that branch. Additionally I can estimate a lower bound for the number of activated blocks, which are not fixed. And the condition becomes `#number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) < #number of activated blocks in the best solution.`

Here's the Python code. It defines a function `f` which expects 3 lists containing 1s and 0s and returns either 0 (not solvable) or a list of 1s and 0s representing the optimal solution.

```
S=sum;r=range
def f(t,f,s):
 for i in r(4):s[4*i:4*i+4]=s[4*i:4*i+4][::-1]
 c=[min(t[i%16],f[(i//16)*4+i%4],s[i//4])for i in r(64)]
 m=lambda:([int(S(c[i::16])>0)for i in r(16)],[int(S(c[i+j:i+j+16:4])>0)for i in r(0,64,16)for j in r(4)],[int(S(c[i+j:i+j+4])>0)for i in r(0,64,16)for j in r(0,16,4)])==(t,f,s)
 Z=[65,0];p=[]
 def g(k):
  if k>63and S(c)<Z[0]:Z[:]=[S(c),c[:]]
  if k>63or S(c[:k])+p[k]>=Z[0]:return
  if c[k]:c[k]=0;m()and g(k+1);c[k]=1
  m()and g(k+1)
 for i in r(64):h,R=(i//16)*4+4,(i//4)%4;p+=[max(S(f[h:]),S(s[h:]))+max((R<1)*S(f[h+i%4-3:h]),S(s[h+R-3:h]))]
 g(0);return Z[1]

```

The code length is 596 bytes/chars. And here's the test framework:

```
from hashlib import md5
from time import time

N = 1000000
start=time();count=blocks=0
for n in range(N):
 bits = list(map(int,"{:048b}".format(int(md5("{:06}".format(n).encode("utf-8")).hexdigest()[:12], 16))))
 result = f(bits[:16], bits[16:32], bits[32:])
 if result:
  count += 1
  blocks += sum(result)
  print("Seed: {:06}, blocks: {}, cube: {}".format(n, sum(result), result))
print()
print("{} out of {} puzzles are solvable using {} blocks.".format(count, N, blocks))
print("Total time: {:.2f} seconds".format(time()-start))

```

You can find an ungolfed version of the program here. It's also a little bit faster.

## Results:

5360 out of 1000000 puzzles are solvable. In total we need 69519 blocks. The number of blocks varies from 6 blocks to 18 blocks. The hardest puzzle took about 1 second to solve. It's the puzzle with the seed `"347177"`, which looks like

```
Top:      Front:    Side:
x x . .   x x x x   x . x .
x x x x   x x x x   x x x x
x x x x   x x x x   x x x x
x x . x   x x x x   x . x x

```

and has an optimal solution with 18 cubes. The following is a few from top for each of the layers:

```
Top 1:    Top 2:    Top 3:    Top 4:
. . . .   . x . .   . x . .   x . . .
. . x x   . . x .   x . . .   . x x .
. . . .   . . . x   x x x .   . . . .
x x . .   x . . .   . . . x   . . . x

```

The total running time for all test-cases was about 90 seconds. I used PyPy to execute the my program. CPython (the default Python interpreter) is a bit slower, but also solves all puzzles in only 7 minutes.

You can find the complete output here: The output is self-explanatory. E.g. the output for the puzzle above is:

```
Seed: 347177, blocks: 18, cube: [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]

```
> 5 votes

# Answer
# 5360 cases solved with 69519 blocks; 923 bytes

This is also optimal. Call with an array of ones and zeroes. Throws a `NullPointerException` for invalid input. Some efficiency is sacrificed to golf it. It still completes within a reasonable time for all 1000000 test inputs.

```
import java.util.*;int[]a(int[]a){a b=new a(a);b=b.b(64);return b.d();}class a{List<int[]>a=new ArrayList();List b=new ArrayList();int c;a(int[]d){int e=0,f,g,h,i[]=new int[48];for(;e<64;e++){f=e/16;g=(e%16)/4;h=e%4;if(d[f+12-4*h]+d[16+f+g*4]+d[32+h+g*4]>2){i[f+12-4*h]=i[16+f+g*4]=i[32+h+g*4]=1;a.add(new int[]{f,g,h});c++;}}if(!Arrays.equals(d,i))throw null;b=f();}a(){}a b(int d){if(c-b.size()>d|b.size()<1)return this;a e=c();e.a.remove(b.get(0));e.b.retainAll(e.f());e.c--;e=e.b(d);d=Math.min(e.c,d);a f=c();f=f.b(d);return e.c>f.c?f:e;}a c(){a c=new a();c.a=new ArrayList(a);c.b=new ArrayList(b);c.b.remove(0);c.c=this.c;return c;}int[]d(){int[]d=new int[64];for(int[]e:a)d[e[2]*16+e[1]*4+e[0]]=1;return d;}List f(){List d=new ArrayList();int e,f,g;for(int[]h:a){e=0;f=0;g=0;for(int[]p:a)if(p!=h){e|=h[0]==p[0]&h[1]==p[1]?1:0;f|=h[0]==p[0]&h[2]==p[2]?1:0;g|=h[1]==p[1]&h[2]==p[2]?1:0;}if(e+f+g>2)d.add(h);}return d;}}

```

## Strategy:

I actually used to play this puzzle quite a bit when I was 10. This uses my approach.

**Step 1:**

Form the cube with the most blocks that fits the given views.

**Step 2:**

Create a list of removable pieces. (Any piece with that has another piece on the row its in, the column its in, and the beam its in.)

**Step 3:**

Test every possible way to keep or remove each removable piece. (Via recursive brute-force with pruning.)

**Step 4:**

Keep the best valid cube.

**Ungolfed:**

```
int[] main(int[] bits) {
    Cube cube = new Cube(bits);
    cube = cube.optimize(64);
    return cube.bits();
}

class Cube {

    List<int[]> points = new ArrayList();
    List removablePoints = new ArrayList();
    int size;

    Cube(int[] bits) {
        int i = 0,x,y,z,placed[] = new int[48];
        for (; i < 64; i++) {
            x = i / 16;
            y = (i % 16) / 4;
            z = i % 4;
            if (bits[x + 12 - 4 * z] + bits[16 + x + y * 4] + bits[32 + z + y * 4] > 2) {
                placed[x + 12 - 4 * z] = placed[16 + x + y * 4] = placed[32 + z + y * 4] = 1;
                points.add(new int[]{x, y, z});
                size++;
            }
        }

        if (!Arrays.equals(bits, placed))
            throw null;

        removablePoints = computeRemovablePoints();
    }

    Cube() {
    }

    Cube optimize(int smallestFound) {
        if (size - removablePoints.size() > smallestFound | removablePoints.size() < 1)
            return this;

        Cube cube1 = duplicate();
        cube1.points.remove(removablePoints.get(0));

        cube1.removablePoints.retainAll(cube1.computeRemovablePoints());
        cube1.size--;

        cube1 = cube1.optimize(smallestFound);
        smallestFound = Math.min(cube1.size, smallestFound);

        Cube cube2 = duplicate();

        cube2 = cube2.optimize(smallestFound);

        return cube1.size > cube2.size ? cube2 : cube1;

    }

    Cube duplicate() {
        Cube c = new Cube();
        c.points = new ArrayList(points);
        c.removablePoints = new ArrayList(removablePoints);
        c.removablePoints.remove(0);
        c.size = size;
        return c;
    }

    int[] bits() {
        int[] bits = new int[64];
        for (int[] point : points)
            bits[point[2] * 16 + point[1] * 4 + point[0]] = 1;
        return bits;
    }

    List computeRemovablePoints(){
        List removablePoints = new ArrayList();
        int removableFront, removableTop, removableSide;
        for (int[] point : points) {
            removableFront = 0;
            removableTop = 0;
            removableSide = 0;
            for (int[] p : points)
                if (p != point) {
                    removableFront |= point[0] == p[0] & point[1] == p[1] ? 1 : 0;
                    removableTop |= point[0] == p[0] & point[2] == p[2] ? 1 : 0;
                    removableSide |= point[1] == p[1] & point[2] == p[2] ? 1 : 0;
                }
            if (removableFront + removableTop + removableSide > 2)
                removablePoints.add(point);
        }
        return removablePoints;
    }

    public String toString() {

        String result = "";
        int bits[] = bits(),x,y,z;

        for (z = 0; z < 4; z++) {
            for (y = 0; y < 4; y++) {
                for (x = 0; x < 4; x++) {
                    result += bits[x + 4 * y + 16 * z] > 0 ? 'x' : '.';
                }
                result += System.lineSeparator();
            }
            result += System.lineSeparator();
        }

        return result;

    }
}

```

**Full program:**

```
import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Example cube:
 *
 * origin
 * |   ........
 * |  .      ..
 * | . top  . .
 * v.      .  .
 * ........   .  <- side
 * .      .  .
 * . front. .
 * .      ..
 * ........
 *
 *     / z
 *    /
 *  /
 * .-----> x
 * |
 * |
 * |
 * V y
 */

public class PPCG48247 {

    public static void main(String[] args) throws Exception{
        MessageDigest digest = MessageDigest.getInstance("MD5");
        int totalSolved = 0;
        int totalCubes = 0;

        for (int i = 0; i < 1000000; i++){
            byte[] input = String.format("%06d", i).getBytes();

            byte[] hash = digest.digest(input);
            int[] bits = new int[48];

            for (int j = 0, k = 0; j < 6; j++, k += 8){
                byte b = hash[j];
                bits[k] = (b >> 7) & 1;
                bits[k + 1] = (b >> 6) & 1;
                bits[k + 2] = (b >> 5) & 1;
                bits[k + 3] = (b >> 4) & 1;
                bits[k + 4] = (b >> 3) & 1;
                bits[k + 5] = (b >> 2) & 1;
                bits[k + 6] = (b >> 1) & 1;
                bits[k + 7] = b & 1;
            }

            try {
                int[] solution = new PPCG48247().a(bits);
                totalSolved++;
                for (int b : solution){
                    totalCubes += b;
                }
            } catch (NullPointerException ignored){}

        }
        System.out.println(totalSolved);
        System.out.println(totalCubes);
    }

    int[] main(int[] bits) {
        Cube cube = new Cube(bits);
        cube = cube.optimize(64);
        return cube.bits();
    }

    class Cube {

        List<int[]> points = new ArrayList();
        List removablePoints = new ArrayList();
        int size;

        Cube(int[] bits) {
            int i = 0,x,y,z,placed[] = new int[48];
            for (; i < 64; i++) {
                x = i / 16;
                y = (i % 16) / 4;
                z = i % 4;
                if (bits[x + 12 - 4 * z] + bits[16 + x + y * 4] + bits[32 + z + y * 4] > 2) {
                    placed[x + 12 - 4 * z] = placed[16 + x + y * 4] = placed[32 + z + y * 4] = 1;
                    points.add(new int[]{x, y, z});
                    size++;
                }
            }

            if (!Arrays.equals(bits, placed))
                throw null;

            removablePoints = computeRemovablePoints();
        }

        Cube() {
        }

        Cube optimize(int smallestFound) {
            if (size - removablePoints.size() > smallestFound | removablePoints.size() < 1)
                return this;

            Cube cube1 = duplicate();
            cube1.points.remove(removablePoints.get(0));

            cube1.removablePoints.retainAll(cube1.computeRemovablePoints());
            cube1.size--;

            cube1 = cube1.optimize(smallestFound);
            smallestFound = Math.min(cube1.size, smallestFound);

            Cube cube2 = duplicate();

            cube2 = cube2.optimize(smallestFound);

            return cube1.size > cube2.size ? cube2 : cube1;

        }

        Cube duplicate() {
            Cube c = new Cube();
            c.points = new ArrayList(points);
            c.removablePoints = new ArrayList(removablePoints);
            c.removablePoints.remove(0);
            c.size = size;
            return c;
        }

        int[] bits() {
            int[] bits = new int[64];
            for (int[] point : points)
                bits[point[2] * 16 + point[1] * 4 + point[0]] = 1;
            return bits;
        }

        List computeRemovablePoints(){
            List removablePoints = new ArrayList();
            int removableFront, removableTop, removableSide;
            for (int[] point : points) {
                removableFront = 0;
                removableTop = 0;
                removableSide = 0;
                for (int[] p : points)
                    if (p != point) {
                        removableFront |= point[0] == p[0] & point[1] == p[1] ? 1 : 0;
                        removableTop |= point[0] == p[0] & point[2] == p[2] ? 1 : 0;
                        removableSide |= point[1] == p[1] & point[2] == p[2] ? 1 : 0;
                    }
                if (removableFront + removableTop + removableSide > 2)
                    removablePoints.add(point);
            }
            return removablePoints;
        }

        public String toString() {

            String result = "";
            int bits[] = bits(),x,y,z;

            for (z = 0; z < 4; z++) {
                for (y = 0; y < 4; y++) {
                    for (x = 0; x < 4; x++) {
                        result += bits[x + 4 * y + 16 * z] > 0 ? 'x' : '.';
                    }
                    result += System.lineSeparator();
                }
                result += System.lineSeparator();
            }

            return result;

        }
    }

}

```
> 3 votes

---
Tags: code-challenge, puzzle-solver, optimization, test-battery
---


title: Shortest Substring Index

text:
# Question
Title: Shortest Substring Index
I'm a lazy but efficient person, as many of you probably are as well. So, whenever I'm doing something I want to do it with minimal effort. Which is why I'm asking you to solve this problem for me.

What I have here is a document of sorts. On every line of this document is a single word or short phrase. The document is not sorted, but that's ok I know where everything is. I could use some help finding things faster, and for that I need a second list. This is where you come in. For every line of text in this document, I need some identifier. Something I can `CTRL`+`F`, but it can't be longer than absolutely necessary for getting that one result.

Example input:

```
(blank)
an apple
spiderman 3
7pm pick up laundry
tequila
fake mustache
dishes on wednesday
banana
biscuits
(blank)

```

Example output:

```
ap,3,7,q,f,w,ba,bi

```

I'm going to repeat myself here, to make sure we're on the same page:

* The input is an unformatted text file containing a list of items, separated by line breaks. I have it here in .txt format, it's called "STUFF.TXT"
* The first and last line of the document are empty. Every other line contains an entry of length \>0.
* The file contains only alfanumeric characters (all lower case), spaces, and line breaks.
* Desired output is a list of identifiers, in the same order as my original list.
* I don't want more than one search word for every list item. If there are multiple answers, pick one, I don't care which. In the above example I picked 'ap' for `an apple`, but you could have picked 'n ', ' a', 'pp', 'pl' or 'le'. Not 'an', because that's in `banana`.
* I can assure you, the file is never empty, and it never contains duplicates.
* **If necessary**, you can match on the line terminator. But that's a last resort only to be used when there's no other way to distinguish between list items (e.g. 'apple' and 'apples').

Standard loopholes are not allowed. Also, this is code golf so shortest code wins.

One more example:

```
(blank)
ban
any
king
bean
yen
rake
raki
bar
(blank)

```

And its output:

```
ban,ny,g,be,ye,ke,aki,ar

```

# Answer
# Pyth, 39 bytes

```
Lsm.:bdtUbKfT.zj\,mhf!}Yjb-Kk+yky++bkbK

```

Bruteforces all subsets of every string in increasing length and checks if that string occurs inside any other. If that doesn't work, it will do the same except for all subsets of `\nstring\n`.
> 3 votes

---
Tags: code-golf, string
---


title: ■ or ■+■ or ■+■+■ or ■+■+■+■

text:
# Question
Title: ■ or ■+■ or ■+■+■ or ■+■+■+■
## Sum of squares

Goal: Write a given natural number as sum of squares. Thanks to Lagrange, Fermat and Legendre we know that you can write any positive integer as sum of (one), two, three, or maximal four squares of integers.

Your task is to write a program/function which takes a natural number via stdin/argument and outputs/returns a list of one to four numbers, where the sum of the squares of those numbers equals the input number. But you have to find the shortest possible example, that means if you can write a number as three squares, you may not output the four squares version.

Examples:

```
1 : 1
2 : 1,1
3 : 1,1,1
4 : 2
5 : 1,2
6 : 1,1,2
127 : 1,3,6,9
163 : 1,9,9
1234 : 3,35
1248 : 8,20,28

```

# Answer
# JavaScript: 141

```
function x(i){var a=0,b,c,d;for(;a<i;a++)for(b=0;b<i;b++)for(c=0;c<i;c++)for(d=0;d<i;d++)if(a*a+b*b+c*c+d*d==i){console.log(a,b,c,d);return}}

```
> 0 votes

---
Tags: code-golf
---