Auto-meta-code-golf

13

Você está cansado de todos os desafios do codegolf. Portanto, você decide escrever um programa que irá automaticamente jogar algum código Python para você. Existem 3 casos de teste:

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)

Regras:

  1. Seu programa não deve ter como alvo o código que eu postei especificamente e deve funcionar com qualquer código Python 2. Reservo-me o direito de alterar o código-fonte que está sendo codificado. Você pode assumir que não há seqüências de várias linhas (portanto, não é necessário criar um analisador completo) e que locals () não é chamado.

  2. A saída do seu programa deve ser executada de maneira idêntica ao código fonte original. (Ou seja, ele deve produzir a mesma saída. Nomes de variáveis ​​e construções de idioma podem ser alterados, desde que a saída permaneça a mesma)

  3. Você pode usar o STDIO ou um arquivo para fazer sua entrada / saída do código fonte.

Sua pontuação será a soma dos bytes da saída do seu programa.

(O código listado acima foi retirado de http://rosettacode.org/ sob a GNU Free Documentation License 1.2 )

Nathan Merrill
fonte
3
Aqui está um caso de teste de bônus para as pessoas tentarem, serem desonestas.
Sp3000
4
Qual é o seu modelo para determinar se a saída " é executada de maneira idêntica ao código-fonte original "? Por exemplo, para o segundo exemplo, acredito que a remoção if __name__ == '__main__':afetaria o comportamento em alguns contextos, mas não em outros. Por outro exemplo, se a entrada não-gasta pressupõe que lê um int a partir de stdin e lança um tipo de exceção se for dada outra coisa, a entrada golfed poderia lançar um tipo diferente de exceção se receber um número inteiro?
Peter Taylor
2
Que tal um programa como este random_long_variable=0;print locals():?
Justin

Respostas:

4

Python 2.7, 794

Eu pretendo criar um minifier para Python por um tempo, portanto esta é uma boa oportunidade para investigar o problema.

O programa usa uma combinação de análise de expressão regular e operações do analisador Python. O espaço em branco é minimizado. As variáveis ​​definidas pelo usuário são substituídas por uma única variável de letra (que não está em uso!). Finalmente, a while Truedeclaração é colocada em uma dieta.

Todos os três casos de teste são verificados como funcionando corretamente. Eu poderia imaginar alguns exemplos patológicos que poderiam resultar em erros no código gerado, mas o algoritmo deve ser robusto na maioria das circunstâncias.

Resultados

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

Resultado

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))
Cavaleiro Lógico
fonte
4

sed, 1074 (abaixo de 1390)

Resposta muito suave, tipo fruta baixa, para fazer a bola rolar:

/^$/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

Substitua <--TAB-->por TABcaracteres reais

Deficiência óbvia:

  • Recuos assumidos como exatamente 4 espaços no código de entrada.

Como não podemos assumir cadeias de linhas múltiplas, apenas removeremos espaços iniciais / finais dos operadores se não houver 'ou "na linha especificada. Isso poderia ser melhorado, mas <murmura algo sobre o sed regex ser sempre ganancioso> .

Teste da seguinte forma:

$ 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
fonte
Você não precisa procurar cadeias de linhas múltiplas, mas as duas últimas definitivamente precisam ser atualizadas.
Nathan Merrill
@NathanMerrill yup. O operador que lidera / arrasta um espaço agora é um pouco melhor, mas o recuo será muito mais difícil de generalizar - e é onde eu recebo cerca de 2/3 do ganho.
Digital Trauma
3

Python 3.4, 1134

Este programa deve funcionar bem para a maioria dos programas. Estranhamente, o caso de teste do Sp3000 é muito mais fácil de otimizar para o meu programa do que para os seus programas. A entrada é aceita através do arquivo especificado no primeiro argumento. O arquivo real é modificado.

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)

Como funciona:

Primeiro, este programa verifica se seu programa interage com o usuário ou usa aleatoriamente. Se isso acontecer, o programa não será modificado. Em seguida, o programa é executado. O programa é então substituído por print "output". Finalmente, se o programa for mais curto que sua saída, ele não será modificado.

O programa Sp3000, otimizado:

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'

O programa de super bônus do Sp3000, otimizado:

A versão otimizada está desativada apenas em 0,001% do tempo.

import sys
sys.stderr.write(b'')
print b'B\r\n'
O número um
fonte
1
Tenho certeza de que existem outros efeitos externos que argv, inpute random, que seu código quebraria. ;)
Martin Ender
2
Hah. Talvez eu devesse ter colocado um não-determinismo - print id(0)é bom.
Sp3000
@Martin Corrigido (principalmente). :)
TheNumberOne
Heh, muito criativo.
Nathan Merrill