Diese Herausforderung basiert auf der Idee des Wechselrichters von Plouffle .
Schreiben Sie ein Programm in einer beliebigen Sprache, die Folgendes tut:
Nimmt als Eingabe eine nicht negative rationale Zahl,
Xdie in Dezimalzahl geschrieben ist, zum Beispiel 34.147425.Gibt einen mathematischen Ausdruck zurück, der nur nicht negative Ganzzahlen, Leerzeichen, Klammern und die folgenden Binäroperatoren verwendet:
- Zusatz
+ - Subtraktion
- - Multiplikation
* - Teilung
/ - Potenzierung
^
Der Ausdruck sollte
Xalle Ziffern von bewerten oder zumindest mit diesen übereinstimmenX. Um das Beispiel fortzusetzen, könnte eine korrekte Ausgabe sein13 + 20^(5/4) / 2, da 13 + 20 ^ (5/4) / 2 = 34.1474252688 ...- Zusatz
Die Ausgabe kann optional in polnischer Notation (Präfix) oder in umgekehrter polnischer Notation (Postfix) geschrieben werden, dh
+ 13 / ^ 20 / 5 4 2ist in Ordnung.
Das Programm unterliegt den folgenden Einschränkungen:
Standard Lücken sind verboten! Insbesondere kann das Programm keine externe Nachschlagetabelle lesen.
Der Quellcode des Programms muss kürzer als 1024 Zeichen sein.
Das Programm mit dem niedrigsten durchschnittlichen Komprimierungsverhältnis gewinnt.
Um Ihr durchschnittliches Komprimierungsverhältnis zu bestimmen, können Sie das folgende Python-Skript verwenden oder ein eigenes gleichwertiges Programm schreiben. Hier ist die Liste von 1000 Zufallszahlen.
import random
def f(x):
# edit this function so that it will return
# the output of your program given x as input
return "1 + 1"
random.seed(666)
S = 1000 # number of samples
t = 0.0
for n in xrange(0, S):
# pick a random decimal number
x = random.uniform(0, 1000)
# compute the compression ratio
# length of output / length of input
r = len(f(x).translate(None, " +-*/^()")) / float(len(str(x).translate(None, ".")))
t += r
print "Your average compression ratio is:", t / SViel Glück!
ANMERKUNGEN:
Leerzeichen in der Ausgabe sind nicht obligatorisch. Saiten wie
1+1,1 +2oder1 + 2, sind alle in Ordnung. In der Tat berücksichtigt das Skript zum Berechnen der Punktzahl keine Leerzeichen und Klammern in der Länge der Ausgabe. Beachten Sie jedoch, dass die Verwendung von Leerzeichen erforderlich ist, wenn Sie die polnische oder die umgekehrte polnische Notation wählen.In Bezug auf die übliche Infixnotation lauten die Prioritätsregeln wie folgt: zuerst alle Exponentiation (
^), dann alle Divisionen (/), dann alle Multiplikationen (*), dann alle Additionen (+) und alle Subtraktionen (-). Aber ich weiß nicht, wie wichtig dies sein könnte, da Sie Klammern verwenden können.Eine Möglichkeit, die Funktion
fim obigen Skript zu bearbeiten, kann die folgende sein. Ich denke jedoch, dass dies von Ihrem Betriebssystem abhängt. unter GNU / Linux funktioniert es. Nennen Sie Ihr Programm "inverter" (oder "inverter.exe") und legen Sie es im selben Verzeichnis wie das Python-Skript ab. Ihr Programm sollteXals erstes Argument der Befehlszeile abgerufen und den Ausdruck in STDOUT zurückgegeben werden. Bearbeiten Sie dannfwie folgt:import os def f(x): return os.popen("./inverter " + str(x)).read()
EDIT: Infolge des Kommentars von Thomas Kwa tragen die Operatoren jetzt nicht mehr zur Länge des Ausdrucks bei. Die Herausforderung sollte "herausfordernder" sein.
X = 5.23ein Wert von5.2301in Ordnung ist, aber5.2299nicht?Antworten:
Haskell, 1.08404005439
Dies verwendet die
approxRationalFunktion, die eine Gleitkommazahl mit der Genauigkeit eines bestimmten Epsilons in einen Bruch umwandelt. Es gibt einfach diesen Bruch zurück. Da Haskell Rationals mit einem%Dazwischen druckt , müssen wir es durch das Teilungszeichen ersetzen/.Der Genauigkeitsparameter wird aus der eingegebenen Nummer berechnet. Wir müssen berücksichtigen, dass alle Ziffern übereinstimmen müssen, also
4.39ist das in Ordnung,4.3aber4.29nicht. Ich füge a5an die Zahl an und die Genauigkeit ist a4999an der gleichen Dezimalstelle wie die angehängte5, zZB
34.147425->43777/1282.Bearbeiten: Die Regeln für die Genauigkeit haben sich geändert. Der Testfall enthält Zahlen mit bis zu 11 Dezimalstellen, die alle übereinstimmen müssen.
Bearbeiten II: Es scheint, dass das bereitgestellte Python-Skript keine nachgestellten Zeilenumbrüche entfernt, daher habe ich von
putStrLnzu geändertputStr.Edit III: wieder neue Bewertungsregeln
quelle
1e-6funktioniert auch, aber das ist kein Codegolf ...Mathematica,
1.10121.10976107226107Bisher hat dies die niedrigste Punktzahl! Gibt das Rationale mit dem kleinsten Nenner an, wenn die Ziffern angegeben sind. (Entschuldigung für die Unlesbarkeit, ich habe vergessen, dass dies für eine Minute kein Golfwettbewerb war.) Einige Tests:
quelle
Python, 1.25927791772
Ich bin überrascht, dass niemand sonst den offensichtlichen Ansatz ausprobiert hat, der etwa 26% Overhead verursacht:
Dies konvertiert nur
XX.XXXXinXXXXXX/10^4und so weiter. Für die meisten Testnummern bedeutet dies, 12 Ziffern (und einen nicht gezählten Dezimalpunkt) in dieselben 12 Ziffern plus drei weitere (plus zwei nicht gezählte Symbole) umzuwandeln.quelle
JavaScript 1.7056771894771656
Sehr einfache, sehr schlechte Punktzahl
quelle
Python, 1.9901028749
Fortgesetzte Brüche erweisen sich leider als kein ernstzunehmender Konkurrent.
Beispiele:
quelle
Python, 1.10900874126
Die tatsächliche Bewertung der fortgesetzten Brüche in meiner vorherigen Antwort ergibt das Äquivalent der mathematischen Antwort von @ LegionMammal978, die ich für das naive Optimum halte. Um dies besser zu machen, müssen Sie kreativ mit der Darstellung der Ganzzahlen umgehen, möglicherweise auch mit der Suche nach suboptimalen Brüchen, um die Darstellung von Ganzzahlen zu vereinfachen.
Beispiele:
quelle