Auto-meta-code-golf

13

Estás harto de todos los desafíos de codegolf. Por lo tanto, decide escribir un programa que automáticamente desarrolle algún código de Python para usted. Hay 3 casos de prueba:

print quickSort([0,7,3,-1,8,10,57,2])
def quickSort(arr):
    less = []
    pivotList = []
    more = []
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        less = quickSort(less)
        more = quickSort(more)
        return less + pivotList + more

for i in xrange(1, 101):
    if i % 15 == 0:
        print "FizzBuzz"
    elif i % 3 == 0:
        print "Fizz"
    elif i % 5 == 0:
        print "Buzz"
    else:
        print i

from sys import argv

def randomGenerator(seed=1):
    max_int32 = (1 << 31) - 1
    seed = seed & max_int32

    while True:
        seed = (seed * 214013 + 2531011) & max_int32
        yield seed >> 16

def deal(seed):
    nc = 52
    cards = range(nc - 1, -1, -1)
    rnd = randomGenerator(seed)
    for i, r in zip(range(nc), rnd):
        j = (nc - 1) - r % (nc - i)
        cards[i], cards[j] = cards[j], cards[i]
    return cards

def show(cards):
    l = ["A23456789TJQK"[c / 4] + "CDHS"[c % 4] for c in cards]
    for i in range(0, len(cards), 8):
        print " ", " ".join(l[i : i+8])

if __name__ == '__main__':
    seed = int(argv[1]) if len(argv) == 2 else 11982
    print "Hand", seed
    deck = deal(seed)
    show(deck)

Reglas:

  1. Su programa no debe apuntar al código que publiqué específicamente, y debería funcionar con cualquier código de Python 2. Me reservo el derecho de cambiar el código fuente que está siendo codegolf. Puede suponer que no hay cadenas de varias líneas (por lo que no tiene que crear un analizador completo) y que no se llama a los locales ().

  2. La salida de su programa debe ejecutarse de manera idéntica al código fuente original. (Es decir, debe producir la misma salida. Los nombres de variables y las construcciones de lenguaje se pueden cambiar, siempre que la salida permanezca igual)

  3. Puede usar STDIO o un archivo para hacer su entrada / salida del código fuente.

Su puntaje será la suma de los bytes de la salida de su programa.

(El código mencionado anteriormente se ha tomado de http://rosettacode.org/ bajo la Licencia de Documentación Libre GNU 1.2 )

Nathan Merrill
fuente
3
Aquí hay un caso de prueba adicional para que la gente lo intente, para ser tortuoso.
Sp3000
44
¿Cuál es su modelo para determinar si la salida " [se ejecuta] de manera idéntica al código fuente original "? Por ejemplo, para el segundo ejemplo, creo que eliminar if __name__ == '__main__':afectaría el comportamiento en algunos contextos pero no en otros. Para otro ejemplo, si la entrada no oculta supone que lee un int de stdin y lanza un tipo de excepción si se le da algo más, ¿podría la entrada golfed lanzar un tipo diferente de excepción si se le da un número entero?
Peter Taylor
2
¿Qué pasa con un programa como este random_long_variable=0;print locals():?
Justin

Respuestas:

4

Python 2.7, 794

He tenido la intención de construir un minificador para Python por un tiempo, así que esta es una buena oportunidad para investigar el problema.

El programa utiliza una combinación de análisis de expresiones regulares y operaciones de análisis de Python. El espacio en blanco se minimiza. Las variables definidas por el usuario se reemplazan por una variable de una sola letra (¡que no está en uso!). Finalmente, elwhile True declaración se pone a dieta.

Los tres casos de prueba se verifican como funcionando correctamente. Me podría imaginar algunos ejemplos patológicos que podrían dar lugar a errores en el código generado, pero el algoritmo debería ser robusto en la mayoría de las circunstancias.

Resultados

228 t1.py
128 t2.py
438 t3.py
794 total

Salida

def c(a):
 b=[]
 d=[]
 f=[]
 if len(a)<=1:
  return a
 else:
  e=a[0]
  for i in a:
   if i<e:
    b.append(i)
   elif i>e:
    f.append(i)
   else:
    d.append(i)
  b=c(b)
  f=c(f)
  return b+d+f
print c([0,7,3,-1,8,10,57,2])


for i in xrange(1,101):
 if i%15==0:
  print"FizzBuzz"
 elif i%3==0:
  print"Fizz"
 elif i%5==0:
  print"Buzz"
 else:
  print i


from sys import argv
def a(k=1):
 b=(1<<31)-1
 k=k&b
 while 1:
  k=(k*214013+2531011)&b
  yield k>>16
def d(k):
 f=52
 h=range(f-1,-1,-1)
 g=a(k)
 for i,r in zip(range(f),g):
  j=(f-1)-r%(f-i)
  h[i],h[j]=h[j],h[i]
 return h
def m(h):
 l=["A23456789TJQK"[c/4]+"CDHS"[c%4]for c in h]
 for i in range(0,len(h),8):
  print" "," ".join(l[i:i+8])
if __name__=='__main__':
 k=int(argv[1])if len(argv)==2 else 11982
 print"Hand",k
 e=d(k)
 m(e)

Código

import sys
import re
from tokenize import generate_tokens
from token import tok_name
from keyword import iskeyword

wr = sys.stdout.write

def pyparse(text):
    'Return [TYPE,TOKEN] pair list'
    # Use KEYWORD,NAME,NUMBER,OP,STRING,NL,NEWLINE,COMMENT,INDENT,DEDENT
    rawtokens = generate_tokens(text.readline)
    tokens = [[tok_name[n], t] for n,t,p1,p2,dx in rawtokens]
    for tpair in tokens:
        if tpair[0] == 'NAME' and iskeyword(tpair[1]):
            tpair[0] = 'KEYWORD'
    return tokens

def finduservars(filename):
    'Return a set of user variables that we can replace with a-zA-Z'
    varset = set()
    for line in open(filename):
        line = line.strip()
        match = re.match(r'def\s+(\w+)\s*\((.*)\)\s*:', line)
        if match:
            func, args = match.groups()
            varset.add(func)
            arglist = re.findall(r'(\w+|=)', args)
            for a in arglist:
                if a == '=':
                    break  # keyword args follow - too hard to parse
                varset.add(a)
            continue
        match = re.match(r'(\w+)\s*=.+', line)
        if match:
            assigned = match.group(1)
            varset.add(assigned)
            continue
    return set(v for v in list(varset) if len(v) > 1)

filename = sys.argv[1]
tokenlist = pyparse(open(filename))

# Build map for var->char conversion:
varset = finduservars(filename)
singles = [text for tok,text in tokenlist if tok=='NAME' and len(text)==1]
allvar = [chr(n) for n in range(97,123)+range(65,91)]
charvar = [c for c in allvar if c not in singles]
varreplaced = list(varset)[:len(charvar)]
varmap = dict((v, charvar.pop(0)) for v in varreplaced)

prev = 'NONE'
indent = ['']
output = []
add = output.append
for tok, text in tokenlist:
    if tok == 'NL':
        continue
    elif tok == 'INDENT':
        indent.append( text.replace('    ', ' ') )
        output[-1] = indent[-1]
    elif tok == 'DEDENT':
        indent.pop(-1)
        output[-1] = indent[-1]
    elif tok == 'NEWLINE':
        add(text)
        add(indent[-1])
    elif tok in 'KEYWORD,NAME,NUMBER':
        if prev in 'KEYWORD,NAME,NUMBER':
            add(' ')
        if tok == 'NAME':
            if output[-2] == 'while' and text == 'True':
                add('1') # common verbose idiom
            else:
                add(varmap.get(text, text))
        else:
            add(text)
    else:
        add(text)
    prev = tok

wr(''.join(output))
Caballero Lógico
fuente
4

sed, 1074 (antes 1390)

Tipo de respuesta muy suave, de fruta baja, para que la pelota ruede:

/^$/d                  # Remove empty lines
/^[ <--TAB-->]*#/d     # Remove whole-line comments
s/    /<--TAB-->/g     # Replace 4 spaces with tabs
/^[^'"]*$/s/ *([|&:,<>=*/%+-]) */\1/g  # Remove spaces before/after operators

Reemplazar <--TAB-->con TABpersonajes reales

Deficiencia obvia:

  • Se supone que las sangrías son exactamente 4 espacios en el código de entrada.

Como podemos asumir que no hay cadenas de varias líneas, solo eliminamos los espacios iniciales / finales de los operadores si no hay 'o "en la línea dada. Esto podría mejorarse, pero <murmura algo sobre sed regex siempre siendo codicioso> .

Prueba de la siguiente manera:

$ cat qs.py fizzbuzz.py cards.py | wc -c
1390
$ sed -rf pygolf.sed qs.py fizzbuzz.py cards.py | wc -c
1074
$ sed -rf pygolf.sed qs.py fizzbuzz.py cards.py | python
[-1, 0, 2, 3, 7, 8, 10, 57]
1
2
Fizz
...
98
Fizz
Buzz
Hand 11982
  AH AS 4H AC 2D 6S TS JS
  3D 3H QS QC 8S 7H AD KS
  KD 6H 5S 4D 9H JH 9S 3C
  JC 5D 5C 8C 9D TD KH 7C
  6C 2C TH QH 6D TC 4S 7S
  JD 7D 8H 9C 2H QD 4C 5H
  KC 8D 2S 3S
$ 
Trauma digital
fuente
No es necesario que busque cadenas de varias líneas, pero sus dos últimas definitivamente deben actualizarse.
Nathan Merrill
@NathanMerrill sí. El espacio inicial / final del operador uno es un poco mejor ahora, pero el sangrado será mucho más difícil de generalizar, y es donde obtengo aproximadamente 2/3 de la ganancia.
Trauma digital
3

Python 3.4, 1134

Este programa debería funcionar bien para la mayoría de los programas. Curiosamente, el caso de prueba Sp3000 es mucho más fácil de optimizar para mi programa que sus programas. La entrada se acepta a través del archivo especificado en el primer argumento. El archivo real se modifica.

import subprocess
from sys import argv

progamtext = open(argv[1]).read()

if 'argv' in progamtext or 'input' in progamtext or 'open' in programtext:#Make sure the program always produces the same results.
    exit(0)

program = subprocess.Popen(['C:\Python27\python', argv[1]], stdout=subprocess.PIPE, stderr=subprocess.PIPE)
program.wait()
erroroutput1 = str(program.stderr.read())
output1 = str(program.stdout.read())
program = subprocess.Popen(['C:\Python27\python', argv[1]], stdout=subprocess.PIPE, stderr=subprocess.PIPE)
program.wait()
erroroutput2 = str(program.stderr.read())
output2 = str(program.stdout.read())
if erroroutput1 != erroroutput2 or output1 != output2:#Make sure the program always produces the same results.
    exit(0)

newprog = ''
if erroroutput1:
    newprog += "import sys\n" + "sys.stderr.write("+ erroroutput1 + ')'
    if output1:
        newprog += "\n"
if output1:
    newprog += 'print ' + output1

if len(newprog) > len(progamtext):
    exit(0)

open(argv[1],mode='w').write(newprog)

Cómo funciona:

Primero, este programa verifica si su programa interactúa con el usuario o si usa aleatoriamente. Si lo hace, el programa no se modifica. A continuación, se ejecuta el programa. El programa luego se reemplaza conprint "output" . Finalmente, si el programa es más corto que su salida, no se modifica.

Programa de Sp3000, optimizado:

import sys
sys.stderr.write(b'')
print b'0.540377721372\r\n3\r\n1\r\n7\r\n99\r\nf\r\n[5, 5]\r\n53\r\n53\r\n53\r\n'

Programa de bonificación súper de Sp3000, optimizado:

La versión optimizada solo tiene un descuento del 0,001% del tiempo.

import sys
sys.stderr.write(b'')
print b'B\r\n'
El numero uno
fuente
1
Estoy seguro de que hay otros efectos externos que argv, inputy random, que su código rompería. ;)
Martin Ender
2
Jaja Tal vez debería haber puesto algo de no determinismo, print id(0)es bueno.
Sp3000
@ Martin fijado (en su mayoría). :)
TheNumberOne
Je, muy creativo.
Nathan Merrill