Brainflak Multiplikation Metagolf

17

Diese Frage ist die erste von mehreren Brain-Flak-Geburtstagsherausforderungen, mit denen Brain-Flaks erster Geburtstag gefeiert werden soll! Weitere Informationen zu Brain-Flaks Geburtstag finden Sie hier

Letzten Sommer hatten wir den Brain-Flak Integer Metagolf und die daraus resultierenden Antworten waren seitdem für die Brain-Flak-Community sehr nützlich. Die Hauptsache, die den Integer Metagolf so effizient macht, ist eine Technik namens Multiplication Hardcoding.

In Brain-Flak ist die Laufzeitvervielfachung extrem teuer. Das kürzeste bekannte Multiplikations-Snippet ist:

({}<>)({<({}[()])><>({})<>}{}<><{}>)

Von Megatom entdeckt

Es gibt jedoch eine sehr einfache Möglichkeit, eine Kompilierzeitmultiplikation zu erstellen. Zum Beispiel wird der folgende Code mit 5 multipliziert:

 (({})({})({})({}){})

Probieren Sie es online!

Dies funktioniert, weil aufeinanderfolgende Ausdrücke zusammenaddiert werden. Jeder ({})tut nichts mit dem Stapel ( {}knallt und (..)drückt ihn nach hinten) und wertet alles aus, was sich oben auf dem Stapel befindet. Alle diese Ausdrücke summieren sich bis zu fünf Mal auf dem Stapel.

Für jeden nder folgenden Zeichenfolgenausdrücke wird ein Snippet erstellt, das die Oberseite des Stapels mit multipliziert n:

"("+"({})"*(n-1)+"{})"

Dies funktioniert, indem nAusdrücke erstellt werden, die alle oben im Stapel ausgewertet werden. Der erste n-1ändert eigentlich nichts und der letzte entfernt die Oberseite des Stapels vor dem Push.

Bei zusammengesetzten Zahlen können Sie mehrere kleinere Ausdrücke miteinander verketten, um Bytes zu sparen. Zum Beispiel können Sie mit 25 multiplizieren, indem Sie zweimal mit 5 multiplizieren:

(({})({})({})({}){})(({})({})({})({}){})

Dies ist ziemlich einfach, und für einige Zahlen funktioniert es ziemlich gut, es gibt jedoch bessere Möglichkeiten, dies zu tun. Zum Beispiel verwendet eine Methode, die ich mir ausgedacht habe, die binäre Darstellung der Zahl. ( Hier ist eine Python-Implementierung ) Diese neue Methode ist viel effektiver als der oben gezeigte einfache Zeichenfolgenausdruck, aber es ist nicht das Ende, es gibt alle möglichen interessanten Möglichkeiten zur Hardcode-Multiplikation und wahrscheinlich eine Tonne, die noch niemand entdeckt hat.

Ich denke, es ist Zeit zu sehen, wie gut wir werden können.

Kurzer Überblick über Brain-Flak

Hier finden Sie eine Beschreibung von allem, was Sie über Brain-Flak für diese Herausforderung wissen müssen.

Brain-Flak hat "Niladen" und "Monaden". Niladen sind Klammern, in denen sich nichts befindet. Jeder Nilad tut etwas und gibt einen Wert zurück. Für diese Herausforderung sind {}und die beiden Niladen, mit denen wir uns befassen <>. {}Fügt den oberen Rand des aktiven Stapels ein und gibt seinen Wert zurück. <>Schaltet den aktiven Stapel und den inaktiven Stapel um, so dass der aktive Stapel inaktiv wird und der inaktive Stapel aktiv wird, und gibt Null zurück.

Monaden sind Klammern mit Dingen darin. Sie nehmen ein einzelnes Argument, die Summe von allem in sich, führen manchmal eine Aktion aus und geben dann einen Wert zurück. Die drei davon sind wir besorgt mit sind (...), <...>und [...]. Die wichtigste Monade für diese Herausforderung (...)nimmt den Wert des Inneren und schiebt ihn auf den aktiven Stapel. Es gibt dann das Argument zurück. <...>und [...]sind beide "träge" Monaden, das heißt, sie führen keine Aktion aus, sondern modifizieren den Wert, den sie übergeben werden. <...>Gibt unabhängig vom übergebenen Argument immer Null zurück. Inzwischen [...]kehrt immer mal das Argument zurück -1.


Beispielprogramme mit Erläuterung

Wenn Sie noch nie in Brain-Flak programmiert haben, ist es möglicherweise eine gute Idee, sich einige Beispielprogramme mit den beschriebenen Vorgängen anzusehen

({}{})

Das fügt die oberen zwei Zahlen auf dem Stapel hinzu. Jeder {}wirft einen Wert vom Stapel und (...)drückt seine Summe zurück.

({}[{}])

In ähnlicher Weise subtrahiert dies den zweiten Gegenstand auf dem Stapel vom ersten. Wie zuvor gibt jeder {}Wert einen Wert aus, der jedoch durch den Wert [..]um den zweiten Wert addiert wird. Wieder (...)drückt der die Summe.

({}<{}>)

Dadurch wird der zweite Wert auf dem Stapel entfernt, wobei der oberste Wert erhalten bleibt. Es funktioniert genauso wie die letzten beiden, außer dass der zweite Wert durch die stummgeschaltet wird, <...>sodass beim Drücken nur der erste Wert zurückgeschoben wird.

(({}))

Dadurch wird eine zweite Kopie des Werts oben im Stapel erstellt. Dies geschieht, indem der obere Teil des Stapels {}abgerufen und der Wert abgerufen wird. Der erste Teil (..)schiebt ihn dann auf seinen Wert zurück. Der zweite (...)nimmt den vom ersten zurückgegebenen Wert und legt diesen ebenfalls auf dem Stapel ab. eine zweite Kopie erstellen.

Aufgabe

Wenn Sie eine Ganzzahl angeben, nerstellen Sie ein stapelreines Brain-Flak-Snippet, das die Spitze des aktuellen Stapels mit multipliziert n.

Sie dürfen die folgenden Brain-Flak-Operationen ausführen

(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{}    -> Pop nilad, Pops the TOS and returns its value
<>    -> Switch nilad, Switches the active and inactive stack

Die anderen Operationen sind zum Zweck der Herausforderung gesperrt.

Wertung

Ihre Punktzahl ist die kumulative Länge aller Programme von n=2bis n=10000. Stellen Sie sicher, dass Sie zur Überprüfung einen Link zur Ausgabe Ihres Programms einfügen.

Weizen-Assistent
quelle
1
Warum sind aus Interesse die Operationen 1 und loop verboten?
Neil
@Neil Der Stapelhöhenoperator ist ebenfalls gesperrt.
Erik der Outgolfer
1
@EriktheOutgolfer Ich hatte diesen in der Ganzzahl-Metagolf ohnehin schon verboten.
Neil
7
Informatiker sind komisch. Sie erfinden Programmiersprachen, die von Natur aus nicht zu gebrauchen sind, und fordern sich gegenseitig heraus, Golf-Code zu schreiben, um einfache Probleme in dieser Sprache zu lösen. Nichts ist esoterischer als dies. +1 Guter Herr.
Draco18s
1
@ Qwerp-Derp Ich habe mich mit der Optimierung der Ausgabe des verknüpften Python-Programms (aktuelle Punktzahl 681950) befasst und dabei eine geringfügige Einsparung von 4492 [...]festgestellt. Das ist also ein Anfang.
Neil

Antworten:

2

Ruby, 669856

$answers = Hash.new{|hash,n|
  valid = []
  2.upto(n**0.5){|i|
    valid.push("("+hash[n/i]+")"+"({})"*(i-2)+"{}") if n%i == 0
  }
  valid.push("({})"+hash[n-1])
  (hash[n] = valid.min_by{|s| s.length})
}
$answers[1] = "{}"

def full_answer n
  "("+$answers[n]+")"
end

Dies ist eine schnelle Basisantwort. Erste 1000 min-Programme finden Sie hier . (Ich habe versucht, alle zu veröffentlichen, aber das hat die maximale Pastebin-Größe überlastet.) Ich kann später eine Code-Erklärung hinzufügen.

Beispiele:

360:    ((((((({})(({}){}){})({}){})({}){}){}){}){})
4608:   (((((((((((({})({}){})({}){}){}){}){}){}){}){}){}){}){})
9991:   (({})((({})(((((((({})((({})({}){}){}){}){}){}){}){}){}){}){})({}){}){})
MegaTom
quelle