Este desafío se basa en la idea del inversor Plouffle .
Escriba un programa en cualquier idioma que haga lo siguiente:
Toma como entrada un número racional no negativo
Xescrito en decimal, por ejemplo 34.147425.Devuelve una expresión matemática utilizando solo enteros no negativos, espacios en blanco, paréntesis y los siguientes operadores binarios:
- Adición
+ - Sustracción
- - Multiplicación
* - División
/ - Exponenciación
^
La expresión debe evaluar
X, o al menos estar de acuerdo con todos los dígitos deX. Para continuar con el ejemplo, una salida correcta podría ser13 + 20^(5/4) / 2, ya que 13 + 20 ^ (5/4) / 2 = 34.1474252688 ...- Adición
La salida puede escribirse opcionalmente en notación polaca (prefijo) o notación polaca inversa (postfix),
+ 13 / ^ 20 / 5 4 2es decir, está bien.
El programa está sujeto a las siguientes restricciones:
¡Las lagunas estándar están prohibidas! En particular, el programa no puede leer ninguna tabla de búsqueda externa.
El código fuente del programa debe ser más corto que 1024 caracteres.
El programa con el índice de compresión promedio más bajo ganará.
Para determinar su relación de compresión promedio, puede usar el siguiente script de Python o escribir su propio programa equivalente. Aquí está la lista de 1000 números aleatorios.
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 / S¡Buena suerte!
NOTAS
Los espacios en blanco en la salida no son obligatorios. Las cadenas como
1+1,1 +2o1 + 2, están bien. De hecho, el script para calcular la puntuación no cuenta espacios en blanco y paréntesis en la longitud de la salida. Sin embargo, tenga en cuenta que el uso de espacios en blanco es necesario si elige la notación polaca o polaca inversa.Con respecto a la notación infija habitual, las reglas de precedencia son las siguientes: primero todas las exponenciaciones (
^), luego todas las divisiones (/), luego todas las multiplicaciones (*), luego todas las sumas (+) y todas las restas (-). Pero no sé cuánto podría importar esto, ya que puedes usar paréntesis.Una forma de editar la función
fen el script anterior puede ser la siguiente, sin embargo, creo que depende de su sistema operativo; en GNU / Linux funciona. Nombre su programa "inversor" (o "inverter.exe") y colóquelo en el mismo directorio que el script Python. Su programa debería serXel primer argumento de la línea de comando y devolver la expresión en STDOUT. Luego edite de lafsiguiente manera:import os def f(x): return os.popen("./inverter " + str(x)).read()
EDITAR: Como consecuencia del comentario de Thomas Kwa, ahora los operadores no contribuyen a la longitud de la expresión. El desafío debería ser más "desafiante".
fuente
X = 5.23un valor de5.2301está bien, pero5.2299no?Respuestas:
Haskell, 1.08404005439
Utiliza la
approxRationalfunción que convierte un número de coma flotante en una fracción con una precisión de un épsilon dado. Simplemente devuelve esta fracción. Como Haskell imprime los racionales con un%intermedio, tenemos que reemplazarlo con el signo de división/.El parámetro de precisión se calcula a partir del número de entrada. Tenemos que tener en cuenta que todos los dígitos deben coincidir, por lo que
4.39está bien4.3pero4.29no lo está. Agrego5a al número y la precisión es a4999en el mismo lugar decimal que el agregado5, por ejemploPor ejemplo,
34.147425->43777/1282.Editar: las reglas de precisión han cambiado. El caso de prueba incluye números con hasta 11 decimales y todos deben coincidir.
Editar II: parece que la secuencia de comandos de Python no elimina las nuevas líneas finales, por lo que he cambiado de
putStrLnaputStr.Edición III: nuevamente, nuevas reglas de puntuación
fuente
1e-6también funciona, pero esto no es codegolf ...Mathematica,
1.10121.10976107226107¡Hasta ahora, este tiene el puntaje más bajo! Da el racional con el mínimo denominador dados los dígitos. (Perdón por la imposibilidad de leer, olvidé que este no era un concurso de golf por un minuto). Algunas pruebas:
fuente
Python, 1.25927791772
Me sorprende que nadie más haya probado el enfoque obvio, que conlleva una sobrecarga del 26%:
Esto simplemente se convierte
XX.XXXXenXXXXXX/10^4y así sucesivamente. Para la mayoría de los números de prueba, esto significa convertir 12 dígitos (y un punto decimal no contado) a los mismos 12 dígitos más tres más (más dos símbolos no contados).fuente
JavaScript 1.7056771894771656
Muy simple, muy mal puntaje
fuente
Python, 1.9901028749
Lamentablemente, las fracciones continuas no resultan ser un contendiente serio.
ejemplos:
fuente
Python, 1.10900874126
En realidad, evaluar las fracciones continuas en mi respuesta anterior arroja el equivalente de la respuesta matemática de @ LegionMammal978, que creo que es el óptimo ingenuo. Hacerlo mejor requerirá ser creativo con la representación de los enteros, posiblemente incluyendo la búsqueda de fracciones subóptimas para obtener enteros más fáciles de representar.
ejemplos:
fuente