EDIT: Wie einige von Ihnen vermuteten, gab es einen Fehler im offiziellen Dolmetscher: Die Reihenfolge der Komposition .
wurde umgekehrt. Ich hatte zwei Versionen des Dolmetschers und habe hier die falsche verwendet. Die Beispiele wurden auch für diese falsche Version geschrieben. Ich habe den Interpreter im Repository und die folgenden Beispiele behoben. Die Beschreibung von >
war auch etwas mehrdeutig, also habe ich das behoben. Ich entschuldige mich auch dafür, dass ich so lange gebraucht habe, dass ich in echte Dinge verwickelt war.
EDIT2: Mein Interpreter hatte einen Fehler, dessen Implementierung .
sich in den Beispielen widerspiegelte (sie stützten sich auf undefiniertes Verhalten). Das Problem ist jetzt behoben.
Einführung
Shift ist eine esoterische funktionale Programmiersprache, die ich vor ein paar Jahren erstellt, aber heute veröffentlicht habe. Es ist stapelbasiert, hat aber auch automatisches Currying wie Haskell.
Spezifikation
In Shift gibt es zwei Datentypen:
- Funktionen, die eine beliebige positive Arität (Anzahl der Eingänge) haben und die eine Liste der Ausgänge zurückgeben. Beispielsweise hat eine Funktion, die ihre einzige Eingabe dupliziert, Arität 1, und eine Funktion, die ihre beiden Eingaben vertauscht, hat Arität 2.
- Leerzeichen, die alle identisch sind und keinen anderen Zweck haben, als keine Funktionen zu sein.
Ein Shift-Programm besteht aus null oder mehr Befehlen , von denen jeder ein einzelnes ASCII-Zeichen ist. Insgesamt gibt es 8 Befehle:
!
( apply ) fügt eine Funktionf
und einen Wertx
aus dem Stapel ein und giltf
fürx
. Wennf
Arity 1 vorhanden ist, wird die Listef(x)
an der Vorderseite des Stapels hinzugefügt. Wenn es arity hatn > 1
, wird eine neue(n-1)
-ary-Funktiong
auf den Stack verschoben . Es nimmt Eingaben und kehrt zurück .x1,x2,...,xn-1
f(x,x1,x2,...,xn-1)
?
( leer ) schiebt ein Leerzeichen auf den Stapel.+
( Klon ) schiebt eine unäre Funktion auf den Stapel, die ihre Eingabe dupliziert: Jeder Wertx
wird zugeordnet[x,x]
.>
( shift ) schiebt eine unäre Funktion, die einen
-ary-Funktion übernimmt, auf den Stapelf
und gibt eine(n+1)
-ary-Funktion zurückg
, die ihr erstes Argument ignoriertx
,f
die verbleibenden aufruft undx
vor dem Ergebnis angreift . Zum Beispielshift(clone)
ist eine Binärfunktion, die Eingabena,b
und Rückgaben entgegennimmt[a,b,b]
./
( fork ) schiebt eine ternäre Funktion, die drei Eingaben benötigta,b,c
, auf den Stapel und gibt zurück,[b]
wenn siea
leer ist, und[c]
ansonsten.$
( Anruf ) drückt auf den Stapel eine binäre Funktion , die eine Funktion öffnetf
und einen Wertx
, und wendetf
aufx
genau wie der!
Fall ist..
( chain ) schiebt eine Binärfunktion auf den Stapel, die zwei Funktionenf
undg
und ihre Zusammensetzung zurückgibt: Eine Funktionh
, die dieselbe Arität wief
hat und deren Eingaben normal sind, giltf
für sie und dann vollständig fürg
das Ergebnis (Aufrufe) es so oft, wie es seine Arität vorschreibt), mit unbenutzten Gegenständen aus der Ausgabe desf
Verbleibs im Ergebnis vonh
. Zum Beispiel sei angenommen , daßf
eine binäre Funktion ist, die ihr zweites Argument Klonen undg
ist Anruf . Wenn der Stapel enthält[f,g,a,b,c]
und wir tun.!!
, dann enthält er[chain(f,g),a,b,c]
; Wenn wir es als!!
nächstes tun ,f
wird es zuerst angewendeta,b
, um zu produzieren[a,b,b]
wird danng
auf die ersten beiden Elemente davon angewendet, da seine Arität 2 ist und erzeugt[a(b),b]
, und der Stapel wird schließlich sein[a(b),b,c]
.@
( sagen wir ) drückt eine unäre Funktion, die einfach ihre Eingabe zurückgibt und druckt,0
wenn es ein Leerzeichen war und1
wenn es eine Funktion war.
Beachten Sie, dass alle Befehle außer dem !
einfachen Verschieben eines Werts auf den Stapel keine Möglichkeit zur Eingabe bieten und die einzige Möglichkeit zur Ausgabe die Verwendung ist @
. Ein Programm wird interpretiert, indem die Befehle einzeln ausgewertet, 0
s oder 1
s gedruckt werden, wenn "say" aufgerufen wird, und beendet werden. Jedes hier nicht beschriebene Verhalten (Anwenden eines Leerzeichens, Anwenden eines Stapels der Länge 0 oder 1, Aufrufen von "Kette" auf ein Leerzeichen usw.) ist undefiniert: Der Interpreter kann abstürzen, stillschweigend fehlschlagen, nach Eingaben fragen oder was auch immer.
Die Aufgabe
Ihre Aufgabe ist es, einen Dolmetscher für Shift zu schreiben. Es sollte von STDIN, der Befehlszeile oder dem Funktionsargument ein zu interpretierendes Shift-Programm nehmen und in STDOUT drucken oder die resultierende (möglicherweise unendliche) Ausgabe von 0
s und 1
s zurückgeben. Wenn Sie eine Funktion schreiben, müssen Sie in irgendeiner Weise auf die Ausgaben mit unendlicher Länge zugreifen können (Generator in Python, Lazy List in Haskell usw.). Alternativ können Sie eine andere Eingabe, eine Zahl n
, verwenden und mindestens n
Zeichen der Ausgabe zurückgeben, wenn diese länger als ist n
.
Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.
Testfälle
Dieses Schichtprogramm druckt 01
:
?@!@@!
Von links beginnend: Drücken Sie ein Leerzeichen, drücken Sie say und wenden Sie das say auf das Leerzeichen an. Dies gibt aus 0
. Drücken Sie dann zweimal auf " Sagen" und wenden Sie das zweite Wort auf das erste an. Dies gibt aus 1
.
Dieses Programm wiederholt sich für immer und erzeugt keine Ausgabe:
$+.!!+!!
Drücken Sie call und clone und wenden Sie dann chain auf sie an (wir benötigen zwei !
s, da chain eine binäre Funktion ist). Jetzt enthält der Stapel eine Funktion, die ein Argument akzeptiert, es dupliziert und die erste Kopie der zweiten aufruft. Mit +!!
duplizieren wir diese Funktion und rufen sie selbst auf.
Dieses Programm druckt 0010
:
?@$.++>!.!!.!!.!!!!+?/!!!@!@>!!!
Schieben Sie ein Leerzeichen und sagen Sie . Erstellen Sie dann eine Binärfunktion, die das zweite Argument b
kopiert, dann das erste kopiert a
und mit sich selbst komponiert. Anschließend wendet Sie die Komposition auf die Kopie von an b
und gibt sie zurück [a(a(b)),b]
. Wenden Sie es auf say und blank an und wenden Sie dann say auf die beiden auf dem Stapel verbleibenden Elemente an.
Dieses Programm druckt 0
. Für jedes !!!
angehängte Element wird ein zusätzliches gedruckt 0
.
?@+$>!>!+>!///!!>!>!.!!.!!.!!+!!!!
Schieben Sie ein Leerzeichen und sagen Sie . Erstellen Sie dann eine ternäre Funktion, die f,g,x
als Eingabe und Rückgabe verwendet wird [f,f,g,g(x)]
. Clone , dass Funktion, und es auf sich, sagen wir , und der Rohling. Diese Anwendung ändert den Stapel nicht, sodass wir die Funktion beliebig oft erneut anwenden können.
Dieses Programm druckt die unendliche Folge 001011011101111...
, wobei die Anzahl der 1
s immer um eins zunimmt:
@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!
Das Repository enthält eine mit Anmerkungen versehene Version.
quelle
f(x1, x2, ..., xn)
undg(y1, y2, ..., ym)
. Durch das Aufrufen werden.
beide Popups angezeigt und eine Funktion gedrückth(z1, z2, ..., zn)
. Jetzt können Sie all diese Argumente auffressen, indem Sie sie schrittweise verarbeiten!
. Nachn
solchen Anwendungen hatte die verbleibende Funktion nur ein Argument und berechnet zu diesem Zeitpunktf(z1, z2, ..., zn)
(dhf
angewendet auf alle Argumente, die Sie eingegeben haben), wodurch einige neue Werte übertragen werden, und verwendet dann sofortm
Werte aus dem Stapel und ruftg
sie auf..
funktioniert genau wie von Martin beschrieben, außer dass das Ergebnis undefiniert ist , wennf
eine Liste mit weniger alsm
Werten zurückgegeben wird (die Komposition hat Aritätn
, sodass sie nicht mehr Argumente vom Stapel essen kann). Im Wesentlichen wird die Ausgabe vonf
als temporärer Stapel verwendet, auf den mal mitg
geschoben und angewendetm
wird!
, und das Ergebnis davon wird dem Hauptstapel hinzugefügt.Antworten:
Python 2,
752667534506445436427404398393 BytesDas ist keineswegs kurz ... aber ich habe mein Bestes gegeben. Irgendwelche Golfvorschläge wären sehr dankbar ...
EDIT6: Dies ist jetzt ein Skript anstelle einer Funktion. Speichern Sie es in einer Datei (shift.py, forex) und führen Sie es dann mit aus
$ python shift.py '<my_input>'
. Stellen Sie sicher, dass die Eingabe in einfache Anführungszeichen gesetzt wird, da sonst die Eingabezeichen verrückt werden.EDIT7: Aaaaaaund ... es ist nicht mehr lesbar. Aber ich habe 23 weitere Bytes entfernt, also ist das gut, denke ich? Ich werde auch eine ungolfed Version posten.
EDIT8: Noch ein Golf, dank @Zgarb.
EDIT: danke an @DLosc für die Golfhilfe! Hat es geschafft, es um 85 Bytes zu reduzieren.
EDIT2: Schneiden Sie eine Tonne unnötiger Wrapper aus und lassen Sie sie um weitere 133 Bytes fallen!
EDIT3: ... und 28 weitere dank @ Sp3000 und @orlp im Chat!
EDIT4: Mit Hilfe von @orlp & @ Sp3000 wurden alle Dekoratoren entfernt und jetzt sind es 61 Bytes kürzer.
EDIT5: hilf mir, ich kann nicht aufhören, dies zu spielen ... 9 weitere Bytes sind weg. Wenn Sie die endgültige print-Anweisung entfernen, werden weitere 7 gespeichert. Wenn Sie jedoch m () in einer Schleife ausführen, befindet sich die gesamte Ausgabe in derselben Zeile. Ist das in Ordnung?
Hier ist eine ungolfed Version:
Die Grundidee ist, dass die Python-Liste sehr gut als Stapel funktioniert. Durch das Speichern speichere
u=k.append
ich nicht nur Zeichen,sondern kann sie auch(nicht mehr!).@u
als Dekorator für Push-Funktionen verwendenDa die beiden Funktionen, die auf Funktionen von n-arity wirken, eine beliebige Anzahl von Argumenten akzeptieren müssen, musste ich sie verwenden
*args
, was bedeutete, dass mein ursprünglicher Plan zur Verfolgung von f.func_code.co_argcount durch eine Arität ersetzt werden mussteDekorateurAttribut.In Bezug auf die Verarbeitung von unendlichen Programmen wird der Interpreter ausgeführt, bis die maximale rekursive Tiefe erreicht ist. Der RuntimeError-Handler unten lässt ihn an diesem Punkt leise beenden und druckt dann die aktuelle Ausgabezeichenfolge aus.
Testfälle:
quelle
['1','0'][...]
nur ersetzen'10'[...]
. 3) Warumx is 0
und nichtx==0
(oderx<1
)? 4) Geben Sie nicht anRuntimeError
, sondernexcept
reichen Sie einfach aus . 5) Da Sie Python 2 verwenden, gelten Tabulatoren und Leerzeichen als unterschiedliche Einrückungsstufen. Sie sollten jedoch ~ 25 Byte sparen.x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))
schneiden - die logischen Operatoren schließen immer noch kurz, verwenden jedoch weniger Zeichen als das ternäre. Speichern Sie dann ein weiteres Byte, indem Siex.a-1
als Bedingung (0 / false, wennx
1, ungleich Null / true, andernfalls) die Ausdrücke 'then' und 'else' austauschen :x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y)
. (Ich muss noch mehr Golf spielen, jetzt wo du an mir vorbeigegangen bist ...; ^))x.a==1
es wahr ist, aberx(y)
etwas Falsches zurückgibt, versucht es auch zu bewertenu(...)
. Aber es sieht so aus, als müssten Sie nicht die mickrigen 3 Bytes speichern, die Sie erhalten hätten! Ich gebe zu, Sir: Sie haben mich übertroffen.RuntimeError
während meins den Benutzer nur auffordert, stderr umzuleiten ... also sind wir wahrscheinlich sogar auf Streitereien. ; ^)*_
in den Lambdas?Ghostscript
Noch nicht Golf gespielt, da ich die Parsing-Funktion noch ausarbeiten muss.
Diese Implementierung verwendet
_
und:
anstelle von>
und/
und erfordert, dass alle Programmzeichen durch Leerzeichen getrennt werden. Dies liegt daran, dass>
und/
sind keine gültigen Namen in Postscript, und die Operatoren sind nicht selbstabgrenzend, aber dies wird behoben, wenn ich den Parser schreibe.Der erste Teil des Codes sollte ziemlich transparent sein, da er lediglich die Definitionen der Operatorfunktionen wiederholt. Die Magie geschieht in der Definition von
!
.Die Art und Weise
!
funktioniert , ist einfach: Erstens, es fügt Argumentx
zuf
durch das Vorsetzenx
auf den Inhaltf
, es zurück auf den Stapel schieben, und eine Kopie des Ergebnisses zu benennenfun
.Anschließend wird der gesamte Stapel als Array zusammengefasst.
.runandhide
ist eine Ghostscript-Erweiterung zum Ausführen von Sandbox-Code, die den Inhalt des vorhergehenden Arrays vor der Prozedur verbirgt, mit der es aufgerufen wird. Derdict
Befehl verschiebt ein neues Wörterbuch auf den Diktierstapel und schränkt den Umfang der darin definierten Namen ein, bisend
es wieder entfernt wird. Es ersetzt auch=only
(den Ausgabeoperator, in dem ich verwende@
) durch einen Dummy- Operator , wodurch die Ausgabe während des Testlaufs unterdrückt wird.stopped
ist das PostScript-Äquivalent dertry
in anderen Sprachen gefundenen Anweisung und gibt true zurück, wenn die Prozedur einen Fehler ausgelöst hat, und false, wenn sie vollständig ausgeführt wurde.Sobald der Testlauf von
fun
abgeschlossen ist, stellt das Programm den ursprünglichen Stapel aus dem verborgenen Array wieder her. Wenn esfun
ohne Fehler abgeschlossen wurde, führt es ihn tatsächlich aus und behält die Ausgabe bei.quelle
Python3,
685670634633 BytesIch bin mir ziemlich sicher, dass dies das längste ist, was ich jemals Golf gespielt habe. Früher war es etwas lesbar, aber das Befolgen des Ratschlags von @ sirpercival hat diesen Nachteil beseitigt !
k
ist der Stapel, der Funktionen enthält, die als Zeichenfolgen dargestellt werden"h(0,0)"
(was c h ain ist ). Wenn eine Funktion als Argument an eine andere Funktion übergeben wird, werden sierepr
und alle Zahlen inkrementiert :"h('h(1,1)',0)"
. Sobald alle0
s in einer Funktion ersetzt wurden, wird das Ganze an übergebeneval
, wodurch die entsprechende Python-Funktion aufgerufen wird. Die meisten davon sind Lambda-Funktionen, die aus der großen Zeichenfolge in Zeile 6 vonexec
in Zeile 7 generiert werden .Das größte Problem bestand darin, mehrere Ebenen verschachtelter Funktionen zu erhöhen, in Anführungszeichen zu setzen und ordnungsgemäß zu entkommen. Ich könnte ein bisschen mehr bei Regex-Operationen sparen, wenn ich davon ausgehen könnte, dass die Funktionsverschachtelung nicht tiefer als 9 Ebenen verläuft, aber wie in den Kommentaren erwähnt, ist dies wahrscheinlich keine sichere Annahme.
Ungolfed frühere Version des Codes:
Der einzige mögliche Fehler dieser Implementierung besteht darin, dass sie eine Rekursion verwendet, sodass Programme, die unendlich sein sollten, die maximale Rekursionstiefe ziemlich schnell erreichen. (Sie möchten wahrscheinlich stderr umleiten, wenn Sie ein unendliches Programm ausführen - andernfalls überschwemmt der Stack-Trace die tatsächliche Ausgabe.) Ansonsten scheint alles zu funktionieren.
quelle
lambda a
und komprimierbar sein solltenk.pop()
.k.pop()
Situation sowieso ein wenig weniger repetitiv gemacht.)Ceylon,
116710571031Ich verstehe es nicht so kurz wie die monotypisierten Python-Versionen ...
import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}
Hier ist eine formatierte (und kommentierte) Version desselben Codes (mit Leerzeichen / Zeilenumbrüchen / Kommentaren werden 4867 Bytes):
Die Funktionen Klonen
e
, Verschiebent
, Verzweigenk
, Aufrufenl
, Sageny
und Verkettenn
verwenden den letzten Buchstaben der Namen für die abgekürzte Version, da dies weniger Kollisionen ergab. (Trivia: Gabel wurde ursprünglich auf diese Weise definiert:[Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];
- wenn ich umbenanntblank
zub
, diese brach, weil es nun die Parameter verglichena
undb
stattdessena
mit dem Rohling hat mich einige Zeit zu debuggen..)Die
z
Funktion wird gemeinsam genutzt, da meine IDE diese Funktionen ausführt. Das Befehlszeilentool kann auch nicht gemeinsam genutzte Funktionen ausführen.quelle