Fondo
En algunos futuros posibles, el mundo convertirá sus sistemas numéricos de decimal (base 10 o b10
) a alguna otra base (binaria b2
, octal b8
, hexadecimal b16
o incluso unaria b1
, ¡en cuyo caso estamos jodidos!). Por lo tanto, en preparación para este posible evento que cambiará el mundo, decide probar todos sus programas a prueba de bases. Esto se puede hacer mediante el uso de sólo singulares 0
s y 1
s en conjunción con los operadores para reemplazar las constantes número existente.
Sin embargo, solo hay un problema: tiene un montón de programas para cambiar, ¡y convertir manualmente cada número en una expresión tomaría semanas! Por lo tanto, decide escribir un programa (o función) para decidir qué expresión debe reemplazar cada número.
Entrada
La entrada será un entero positivo. Su código debe ser capaz de manejar cualquier número entero hasta 1000.
(Si su código admite decimales y / o entradas negativas, consulte la Puntuación a continuación).
Salida
Su código debe generar una expresión que evalúe la entrada en al menos un idioma. Este puede ser cualquier idioma; no tiene que ser el mismo en el que está escrito su programa o función. Además, esta expresión no necesita ser un programa o función completa.
Para mayor claridad, la salida puede contener cualquiera de estas operaciones:
- incremento / decremento
- agregar / suma
- restar / negar
- multiplicar / duplicar (¡solo si no involucra directamente el número
2
!) - dividir / módulo
- exponentes / logaritmos
- square / sqrt (de nuevo, ¡solo si estos no involucran directamente el número
2
!) - operaciones bit a bit (bOR, bAND, bNOT, bXOR, bit-shifts)
- establecer / obtener variables
- manipulación de pila
Es posible que no se utilice eval()
o cualquier funciones similares en la salida. Tampoco puede utilizar en la salida ninguna función que realice una acción o acciones distintas a las mencionadas anteriormente.
Ah, y una cosa más: dado que queremos que la salida sea válida en tantas bases como sea posible, las únicas constantes numéricas que puede contener son 0
y 1
. Números como 10
(diez) no están permitidos, a menos que el idioma lo interprete como a 1
y a 0
. El uso de cadenas para contener números tampoco está permitido, al igual que el uso de caracteres como CJam's A
- K
(que representan 10
- 20
).
Casos de prueba
(Todas las salidas están en JavaScript, pero pueden funcionar en otros idiomas).
Entrada 1:
2
Salida posible 1:
1+1
Entrada 2:
13
Salida posible 2:
(a=1+1+1)*a+a+1
Entrada 3:
60
Salida posible 3:
(b=(a=1+1+1+1)*a)*a-a
Entrada 4:
777
Salida posible 4:
(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1
Entrada 5:
1000
Salida posible 5:
Math.pow((a=1+1+1)*a+1,a)
Tanteo
El objetivo de este desafío es acortar la salida de su código tanto como sea posible. Su puntaje se calculará de esta manera:
Puntuación base: el recuento de bytes promedio de todas las salidas para enteros 1 a 1000.
Puntuación decimal: si su código admite al menos 3 decimales, este es el recuento de bytes promedio de todas las salidas de la secuencia de números que comienzan
0.001
y terminan en1000
, aumentando en1.001
cada momento.0.001, 1.002, 2.003...998.999, 1000.000
Luego, obtenga un 50% de descuento en este puntaje.Puntuación negativa: si su código admite números negativos y cero, este es el recuento de bytes promedio de las salidas de todos los enteros desde
-1000
hasta0
. Luego, obtenga un 10% de descuento en este puntaje.
(La forma más fácil de calcularlos probablemente sería un bucle con su programa / función dentro).
Su puntaje final es el promedio de cualquiera de las fórmulas anteriores que se aplican.
Si la salida no es determinista (es decir, algo aleatorio; varias ejecuciones con la misma entrada producen múltiples salidas únicas), entonces la puntuación para cada entrada está determinada por la salida más grande durante diez ejecuciones en mi CPU.
Además, como no sabe cuán valiosos serán los datos de la computadora en el futuro, el recuento de bytes de su código generador debe ser inferior a 512 bytes.
El puntaje más bajo en dos semanas (el 30 de septiembre) será declarado ganador. ¡Felicitaciones a tu ganador, @ThomasKwa !
Tabla de clasificación
Para asegurarse de que su respuesta se muestre correctamente, comience con este encabezado:
# Language name/Other language name, X points
¿Dónde X
está el puntaje de tu respuesta? Ejemplo:
# CJam/Pyth, 25.38 points
Si tiene alguna pregunta o sugerencia, hágamelo saber. ¡Buena suerte!
fuente
0
o1
por defecto?Integer.parseInt("1000", 1+1+1+1+1+1+1+1+1+1)
? Estoy bastante seguro de queparseInt
solo usa las operaciones permitidas ;-)Respuestas:
Código de máquina Python / Zilog Z80,
11.65311.488Bonificaciones: números negativos.
Asume que el
hl
par de registros inicialmente contiene 0 y devuelve el resultadohl
.Solo se usan estas tres instrucciones:
Utilizamos una pequeña modificación de la representación binaria balanceada de mínimo peso BBR2 . Dado que BBR2 minimiza el peso (número de dígitos distintos de cero), pero queremos minimizar el peso más el número de cambios de bits, cambiamos una constante en el algoritmo de
3/2
a5/3
.Para calcular la puntuación y verificar, use este código:
Salida de ejemplo:
O en asamblea:
Más programas de ejemplo:
Posibles optimizaciones: OP reglas que los
inc h
ydec h
las instrucciones, que cambian directamente el byte superiorhl
, son ilegales, perosla h
y los indocumentadossl1 h
(desplazamientos de bit a la izquierda 1 sobreh
ese cambio en una0
y1
se permiten, respectivamente).sla h
ysl1 h
son dos bytes cada uno, pero a veces pueden acortar la salida.fuente
+
traducedec
. Sigo leyendo los ejemplos negativos mal.CJam / CJam,
143.26342.71328.89923.90121.90320.468No se aplican bonificaciones.
Pruébelo en línea: ejecución de muestra | calculadora de puntaje | verificación
Ejecuciones de ejemplo
fuente
%
con una expresión más larga. Los enlaces deberían funcionar ahora.ß / BrainFuck, 34.201 puntos
ß fuente (194B):
Si alguien está interesado, agregaré una explicación. La salida BF ya está bastante optimizada, pero supongo que podría usar los 318B restantes de código ß para implementar
operador de colisión de eliminación.Muestras:
Corriendo en windows:
Corriendo en Linux:
Validar en el intérprete BF en línea .
Puntuaciones:
= 37.495
.= 60.959 * 0.5 = ~30.48
.= 38.4765234765235 * 0.9 = ~34.629
= (37.495 + 30.48 + 34.629)/3 = 34.201
.fuente
Ruby / Ruby, 29.77885
31.873 * 0.9 (negativo) 30.872 (positivo).
La estrategia básica es la representación simétrica de base 3 ("ternario equilibrado"), es decir, cuando los dígitos son en
-1,0,1
lugar de0,1,2
Aquí está la salida de 0 a 40 antes de la limpieza
Y despues de la limpieza
fuente
Ceilán / Ceilán,
49.8640.95 puntosLa tercera versión usa Ceylon 1.2 para el generador y 509 bytes de código:
import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}
Se reduce a 35,22 puntos, pero no lo pondré en la línea del título porque Celyon 1.2 solo se publicó el 29 de octubre. No creo que pueda implementar este algoritmo en Ceylon 1.1 en este tamaño). Más detalles allí abajo, aquí describiré la segunda versión. (La primera versión se puede ver en el historial: solo admitía números positivos, pero cabía en 256 bytes).
Segunda versión
Ahora, la segunda versión, que admite enteros negativos (y 0), y generalmente crea una salida un poco más corta al usar además
-
. (Esta versión en realidad usa la longitud permitida, la primera intentó permanecer por debajo de 256 bytes en lugar de 512).El código tiene una longitud de 487, por lo que aún queda espacio para más optimizaciones más adelante. (También hay muchas reservas en forma de espacios en blanco y nombres largos de variables).
La puntuación:
Algunas salidas de muestra:
Como puede ver, los negativos son siempre un byte (el principal
-
) más largos que los positivos correspondientes.La idea base es la misma que el programa anterior: encuentre un cuadrado cerca de nuestro número objetivo y represente su raíz y el resto de forma recursiva. Pero ahora permitimos que nuestro cuadrado sea también más grande que el número objetivo, lo que hace que el resto sea negativo. (Se
+0.5
puede cambiar a una constante diferente para ajustar el algoritmo, pero parece que ya llegué al óptimo aquí; tanto 0.4 como 0.6 dan peores resultados).Para hacer que los valores negativos sean negativos (y de lo contrario tener la misma estructura que los positivos, pasamos el operador
sign
a nuestra función recursivap
, es decir,"+"
o"-"
. Podemos usar eso para la combinación en los casos triviales (es decir, n <9) también en cuanto al resto si es positivo, y use el signo opuesto para el resto si es negativo.La
proof
función maneja el signo inicial (con un caso especial para 0), lap
función hace el trabajo real, con recursividad.Tercera versión, para Ceilán 1.2
La versión de golf (es decir, comentarios y espacios en blanco eliminados) se publica en la parte superior, a exactamente 509 bytes de código.
Esto usa el mismo principio básico que la segunda versión, pero en lugar de solo cuadrados, también trata de usar potencias de números más altas (prueba de exponentes del 2 al 8), y usa el resultado más corto. También almacena en caché los resultados, ya que de lo contrario esto sería inaceptablemente lento para números más grandes con muchas llamadas recursivas.
Tanteo:
La gran construcción con sangría en el medio son tres comprensiones iterables anidadas, las dos internas dentro de una expresión let. Estos se desatan usando la función de expansión dos veces, y la
reduce
función encuentra la más corta de esas cadenas.He presentado una solicitud de función para poder hacer esto en una sola comprensión.
Dentro de la comprensión, estamos construyendo una cadena desde la raíz
r
, el exponentex
y el resto (n-w
ow-n
).La
let
expresión y lamap
función son nuevas en Ceylon 1.2.map
podría haber sido reemplazado porHashMap
(que habría necesitado más caracteres para la importación, aunque probablemente sería aún más rápido, ya que no construiría el mapa nuevo para cada nueva entrada). Laslet
expresiones comolet (w = r ^ x)
podrían haber sido reemplazadas usando unaif
cláusula comoif(exists w = true then r ^ x)
(y entonces tampoco hubiera necesitado las dosexpand
llamadas), pero esto aún sería un poco más largo, no encajando dentro de los 511 bytes permitidos.Aquí las salidas de muestra correspondientes a las seleccionadas anteriormente, todas ellas excepto los números realmente pequeños son más cortos:
Por ejemplo, ahora tenemos 1000 = (3 ^ 2 + 1) ^ 3, en lugar de 1000 = (6 ^ 2-4) ^ 2-5 ^ 2 + 1.
fuente
less than 512
. Sou puedes usar un máximo. de 511 bytes;)Ruby / dc
20,29618.41416.968¡Programación dinámica! Define una lista de funciones que, dada una instrucción de CC, devuelve una nueva expresión y el valor numérico de esa expresión. Luego, comenzando con
1
predefinido, crea una lista de todos los valores accesibles hasta el valor deseado incluido.editar:
Se agregó una función para n-1 y se hizo ejecutar el algoritmo a través de múltiples pases. Parece necesitar 7 pases para estabilizarse. Tuve que acortar algunos nombres de variables para permanecer dentro de 512 bytes.
editar 2:
Se agregaron funciones para n (n-1) , n (n + 1) y n ^ 3 mientras estaba en eso. Acorté el código un poco más, aterrizando exactamente en 512 bytes.
Números generados:
La salida consta completamente de cinco caracteres diferentes:
1
empuja el valor 1 en la pila;d
duplica la parte superior de la pila;+
,-
Y*
hace estallar los dos valores superiores y empuja su suma, diferencia, y producto, respectivamente. Cada expresión generada agrega solo un valor a la pila después de la ejecución....
fuente
-
operador mientras te mantienes dentro del conteo de bytes?Python 2.6,
78.069- 66.265 puntosPresentando mi respuesta por lo que vale (no mucho en este caso ... pero demostrando claramente que para este desafío no es suficiente pensar simplemente en componer la salida como una suma de valores desplazados en bits; cuando se tiene en cuenta que no hay dígitos fuera de 0 o 1 puede aparecer en la salida). Podría volver más tarde con una forma diferente de generar resultados.
El código en sí no es demasiado largo (176 caracteres):
Genera resultados correctos pero detallados:
Fragmento que calcula la puntuación:
fuente