Auto-meta-kod-golf

13

Masz dość wszystkich wyzwań związanych z codegolfem. Dlatego decydujesz się napisać program, który automatycznie zagra dla ciebie kod Pythona. Istnieją 3 przypadki testowe:

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)

Zasady:

  1. Twój program nie może celować w kod, który specjalnie opublikowałem i powinien działać z dowolnym kodem Python 2. Zastrzegam sobie prawo do zmiany kodowanego kodu źródłowego. Możesz założyć, że nie ma łańcuchów wielowierszowych (więc nie masz zbudowanego pełnego parsera) i że locals () nie jest wywoływany.

  2. Dane wyjściowe programu powinny działać w identyczny sposób jak oryginalny kod źródłowy. (Mianowicie, musi generować takie same dane wyjściowe. Nazwy zmiennych i konstrukcje językowe można zmieniać, o ile dane wyjściowe pozostają takie same)

  3. Możesz użyć STDIO lub pliku, aby wprowadzić / wyprowadzić kod źródłowy.

Twój wynik będzie sumą bajtów wyniku programu.

(Powyższy kod pochodzi z http://rosettacode.org/ na licencji GNU Free Documentation License 1.2 )

Nathan Merrill
źródło
3
Oto dodatkowy przypadek testowy dla ludzi, którzy mogą spróbować, aby być przebiegłym.
Sp3000,
4
Jaki jest twój model określania, czy wyjście „ [działa] w identyczny sposób jak oryginalny kod źródłowy ”? Na przykład w drugim przykładzie uważam, że usunięcie if __name__ == '__main__':miałoby wpływ na zachowanie w niektórych kontekstach, ale nie w innych. Dla innego przykładu, jeśli wejście bez golfa zakłada, że ​​odczytuje wartość int ze standardowego wejścia i zgłasza jeden typ wyjątku, jeśli otrzyma coś innego, czy wejście do gry w golfa może rzucić inny typ wyjątku, jeśli otrzyma wartość inną niż całkowita?
Peter Taylor
2
Co takiego programu: random_long_variable=0;print locals()?
Justin

Odpowiedzi:

4

Python 2.7, 794

Chciałem zbudować minifikator dla Pythona, więc jest to dobra okazja do zbadania problemu.

Program wykorzystuje połączenie analizy wyrażeń regularnych i operacji analizatora składni w języku Python. Biała przestrzeń jest zminimalizowana. Zmienne zdefiniowane przez użytkownika są zastępowane zmienną jednoliterową (która nie jest używana!). Wreszcie while Trueoświadczenie zostało wprowadzone na temat diety.

Wszystkie trzy przypadki testowe sprawdzają, czy działają poprawnie. Mogę sobie wyobrazić kilka patologicznych przykładów, które mogą powodować błędy w generowanym kodzie, ale algorytm powinien być solidny w większości przypadków.

Wyniki

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

Wynik

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)

Kod

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))
Logic Knight
źródło
4

sed, 1074 (wcześniej 1390)

Bardzo łagodny, nisko wiszący owoc, aby rzucić piłkę:

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

Zamień na <--TAB-->prawdziwe TABpostacie

Oczywista wada:

  • Zakłada się, że wcięcia mają dokładnie 4 spacje w kodzie wejściowym.

Ponieważ nie możemy zakładać żadnych ciągów wieloliniowych, usuwamy spacje wiodące / końcowe tylko od operatorów, jeśli nie ma ich 'lub "w danym wierszu. Można to poprawić, ale <mruczy coś o tym, że sed regex zawsze jest chciwy> .

Testuj w następujący sposób:

$ 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
$ 
Cyfrowa trauma
źródło
Nie musisz sprawdzać ciągów wieloliniowych, ale dwa ostatnie zdecydowanie wymagają aktualizacji.
Nathan Merrill,
@NathanMerrill tak. Operator prowadzący / kończący spację jeden jest teraz nieco lepszy, ale wcięcie będzie trudniejsze do uogólnienia - i tam uzyskuję około 2/3 wzmocnienia.
Cyfrowy uraz
3

Python 3.4, 1134

Ten program powinien działać poprawnie dla większości programów. O dziwo, przypadek testowy Sp3000 jest znacznie łatwiej zoptymalizować dla mojego programu niż twoje programy. Dane wejściowe są akceptowane przez plik określony w pierwszym argumencie. Rzeczywisty plik został zmodyfikowany.

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)

Jak to działa:

Najpierw ten program sprawdza, czy Twój program w ogóle wchodzi w interakcje z użytkownikiem lub używa losowo. Jeśli tak, program nie jest modyfikowany. Następnie program jest uruchamiany. Program jest następnie zastępowany przez print "output". Wreszcie, jeśli program jest krótszy niż jego wynik, jest niemodyfikowany.

Program Sp3000, zoptymalizowany:

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'

Super premiowy program Sp3000, zoptymalizowany:

Zoptymalizowana wersja jest wyłączona tylko 0,001% czasu.

import sys
sys.stderr.write(b'')
print b'B\r\n'
Numer jeden
źródło
1
Jestem pewien, że istnieją inne niż efekty zewnętrzne argv, inputoraz random, co byłoby złamać kod. ;)
Martin Ender
2
Hah Może powinienem był wprowadzić jakiś niedeterminizm - print id(0)jest dobry.
Sp3000,
@Martin Naprawiono (głównie). :)
TheNumberOne
Hej, bardzo kreatywny.
Nathan Merrill