Einführung: Kombinatorische Logik
Die kombinatorische Logik (CL) basiert auf sogenannten Kombinatoren , die im Grunde genommen Funktionen sind. Es gibt zwei grundlegende "eingebaute" Kombinatoren Sund K, die später erklärt werden.
Linke Assoziativität
CL ist linksassoziativ , was bedeutet, dass Klammern (die etwas enthalten), die sich ganz links von einem anderen Klammerpaar befinden, entfernt werden können, wobei das betreffende Material freigegeben wird. Zum Beispiel so etwas:
((a b) c)
Kann auf reduziert werden
(a b c)
Befindet (a b)sich der ganz links von der größeren Halterung ((a b) c), so kann er entfernt werden.
Ein viel größeres Beispiel für Linksassoziationen (eckige Klammern sind Erklärungen):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Klammern können auch reduziert werden, wenn mehr als ein Paar um dieselben Objekte gewickelt ist. Beispiele:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Builtins
CL verfügt über zwei "eingebaute" Kombinatoren, Smit Kdenen Objekte (einzelne Kombinatoren oder eine Gruppe von Kombinatoren / Gruppen, die in eckige Klammern eingeschlossen sind) wie folgt gewechselt werden können:
K x y = x
S x y z = x z (y z)
Wo x, yundz kann Stand-In für alles sein.
Ein Beispiel für Sund Ksind wie folgt:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Ein anderes Beispiel:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Das Obige sind Beispiele für normale CL-Anweisungen, bei denen die Anweisung nicht weiter ausgewertet werden kann und ein Endergebnis in einer endlichen Zeitspanne erzielt wird. Es gibt nicht normale Anweisungen (CL-Anweisungen, die nicht enden und für immer ausgewertet werden), aber sie liegen nicht im Rahmen der Herausforderung und müssen nicht behandelt werden.
Wenn Sie mehr über CL erfahren möchten, lesen Sie diese Wikipedia-Seite .
Aufgabe:
Ihre Aufgabe ist es, zusätzliche Kombinatoren zu erstellen, die die Anzahl der Argumente und die Auswertung als Eingabe berücksichtigen.
{amount_of_args} = {evaluated}
Wo {amount_of_args}ist eine positive ganze Zahl gleich der Anzahl der Argumente und {evaluated}besteht aus:
- Argumente bis zur Menge der
1Argumente, mit dem ersten Argument,2wobei das das zweite usw. ist.- Es wird garantiert, dass Argumentnummern über der Anzahl der Argumente (also nur
4wenn ) nicht in angezeigt werden .{amount_of_args}3{evaluated}
- Es wird garantiert, dass Argumentnummern über der Anzahl der Argumente (also nur
- Klammern
()
Beispiele für Eingaben sind:
3 = 2 3 1
4 = 1 (2 (3 4))
Bei der ersten Eingabe wird nach einem Kombinator (z. B. R) mit drei Argumenten ( R 1 2 3) gefragt , der dann ausgewertet wird zu:
R 1 2 3 -> 2 3 1
Die zweite Eingabe fragt danach (mit einem Kombinator-Namen A):
A 1 2 3 4 -> 1 (2 (3 4))
In Anbetracht der Eingabe in diesem Format, müssen Sie eine Reihe von zurückgeben S, Kund (), die , wenn sie mit einem combinator Namen ersetzt und mit Argumenten ausführen, gibt das gleiche ausgewertete Aussage wie die{evaluated} Block , wenn der Befehlsblock wird wieder für diesen combinator Namen ersetzt.
Bei der Ausgabe-Kombinator-Anweisung werden möglicherweise die Leerzeichen und die äußeren Klammern entfernt, sodass so etwas wie umgewandelt werden (S K K (S S))kannSKK(SS) .
Wenn Sie Ihr Programms der Ausgänge zu testen, hat @aditsu einen kombinatorischen Logik - Parser gemacht (einschließlich S, K, Iund auch andere , die gerne Bund C) hier .
Ergebnis:
Da es sich um einen Metagolf handelt , besteht das Ziel dieser Herausforderung darin, die geringstmögliche Anzahl von Bytes in der angegebenen Ausgabe zu erzielen diesen 50 Testfällen . Bitte geben Sie Ihre Ergebnisse für die 50 Testfälle in die Antwort ein oder erstellen Sie ein Pastebin (oder ähnliches) und veröffentlichen Sie einen Link zu diesem Pastebin.
Bei einem Gleichstand gewinnt die früheste Lösung.
Regeln:
- Ihre Antwort muss eine RICHTIGE Ausgabe zurückgeben. Bei einer Eingabe muss die korrekte Ausgabe gemäß der Definition in der Task zurückgegeben werden.
- Ihre Antwort muss für jeden Testfall innerhalb einer Stunde auf einem modernen Laptop ausgegeben werden.
- Eine Hardcodierung von Lösungen ist nicht zulässig. Sie können jedoch bis zu 10 Kombinatoren fest codieren.
- Ihr Programm muss jedes Mal dieselbe Lösung für dieselbe Eingabe zurückgeben.
- Ihr Programm muss für jede Eingabe ein gültiges Ergebnis liefern, nicht nur für Testfälle.
quelle
1, können Sie1von allem subtrahieren und dann die Lösung für diese Antwort einpackenK(). Beispiel: Lösung für2 -> 1istK, also Lösung für3 -> 2istKK, Lösung für4 -> 3istK(KK)usw.Antworten:
Haskell , Punktzahl 5017
Dies kombiniert den dümmsten möglichen Algorithmus zur Abstraktionseliminierung ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) mit einem Gucklochoptimierer, der nach jeder Anwendung verwendet wird. Die wichtigste Optimierungsregel ist S (K x ) (K y ) ↦ K ( xy ), wodurch verhindert wird, dass der Algorithmus immer exponentiell explodiert .
Der Regelsatz ist als Liste von Zeichenfolgenpaaren konfiguriert, sodass Sie leicht mit neuen Regeln herumspielen können. Als besonderen Vorteil der Wiederverwendung des Eingabe-Parsers für diesen Zweck werden S, K und ich auch in den Eingabe-Kombinatoren akzeptiert.
Regeln werden nicht unbedingt angewendet; Stattdessen werden sowohl die alte als auch die neue Version beibehalten und suboptimale Versionen werden nur dann gelöscht, wenn ihre Länge die der besten Version um mehr als eine Konstante (derzeit 3 Byte) überschreitet.
Die Partitur wird leicht verbessert, indem I als grundlegender Kombinator behandelt wird, bis die Ausgangsstufe es in SKK umschreibt. Auf diese Weise kann KI = K (SKK) bei der Ausgabe um 4 Byte auf SK verkürzt werden, ohne den Rest der Optimierungen zu verwechseln.
Probieren Sie es online!
Ausgabe
quelle
S (K x) (K y) = K (x y))?ruleStrings. Wenn wir das nicht getan hätten, wäre die Ausgabe exponentiell länger: Für dieses winzige Beispiel hätten wir S (S (KS) (S (KS) (S (KK) (KS))) (S (S (KS) (S (KK) (KK)) (S (KK) (SKK)))) (S (S (KS) (S (S (KS) (S (KK) (KS))) ( S (S (KS) (S (KK) (KK)) (SK))) (S (KK) (SK))) anstelle von S (KS) K.Summe der Lösungslängen:
12945 85085872Haskell-Code, der Eingabezeilen von stdin nimmt und sich nicht darum kümmert, ob das Trennzeichen
=oder->:Es implementiert die verbesserte Klammerabstraktion aus Abschnitt 3.2 von John Tromp: Binäre Lambda-Rechnung und kombinatorische Logik, auf die aus dem Wikipedia-Artikel über kombinatorische Logik verwiesen wird. Die nützlichsten Sonderfälle verwenden den
SKombinator nur, um die Anzahl der Subtermini zu erhöhen, um ein tiefes Verschachteln von Variablen zu vermeiden. Der Fall, der die Gleichheit einiger Subtermen prüft, wird für keinen der Testfälle benötigt. Während es keinen speziellen Fall für die Behandlung desWKombinators gibt (siehe Peters Antwort), arbeiten die Regeln zusammen, um den kürzerenSS(SK)Ausdruck zu finden . (Ich habe zuerst einen Fehler gemacht, indem ich versucht habe, die inneren Aufrufe zu optimierenabstract, dann diesWOptimierung nicht erfolgt und das Gesamtergebnis war 16 Byte länger.)Und hier sind die Ergebnisse aus den Testfällen:
quelle
8486 mit S, K, I, W
Erläuterung
Der Standard - Algorithmus (wie beispielsweise in Kapitel 18 von To a Mockingbird Mock ) vier Fälle verwendet, entsprechend den Kombinatoren
S,K,I = SKKund eine einfache Links Association. Ich denke, das ist es, was Christians Antwort umsetzt. Dies ist ausreichend, aber nicht unbedingt optimal. Da wir bis zu 10 Kombinatoren fest codieren dürfen, bleiben 7 Optionen.Andere bekannte kombinatorische Kombinatoren sind
die zusammen mit
K, eine vollständige Basis machen . In SK sind diesund die
SKIRegeln leiten dieselben Ausdrücke fürBund abC, aber fürWsieS S (K (S K K)). Ich habe mich daher fürWeinen Sonderfall entschieden.Programm (CJam)
Online-Testsuite
Generierte Ausgaben:
quelle