Los enteros son tediosos de representar en Brain-Flak . Hay 8 operadores:
() Evaluates to 1, but does not push anything on any stack
[] Evaluates to an indeterminate value for the purposes of this question
{} Removes the top of the stack and evaluates to it
<> Switches to or back from the alternate stack and evaluates to zero
(foo) Pushes the value of the expression foo to the stack and evaluates to it
[foo] Evaluates to the negation of foo
{foo} Evaluates the expression foo until the top of the stack is zero
<foo> Evaluates to zero but executes foo anyway
foo
puede consistir en múltiples operadores, en cuyo caso son evaluados y sumados. Por ejemplo, (()())
empuja 2
a la pila (y también evalúa 2
).
Obviamente, el (()...())
mecanismo no es útil en Code Golf ya que grandes números tomarían n*2+2
bytes para representar. Por lo tanto, su desafío es escribir un programa o función que genere en la menor cantidad de bytes posible un programa Brain-Flak que empuje un entero positivo dado n
a la pila activa. Este programa no debe hacer suposiciones sobre el contenido existente de las pilas, por lo que no debe dejar las pilas intercambiadas ni agregar o eliminar valores adicionales de las pilas.
Aunque su programa o función debe ser capaz de devolver un programa Brain-Flak en funcionamiento para todas las entradas de 1 a 1,000,000, el ganador será el programa o función que genere el conjunto más pequeño de programas Brain-Flak apropiados para todos los 1061 números primos entre 1,000 y 10,000 . Debe tener en cuenta el tamaño total de sus salidas para esas 1061 entradas como parte de su envío. Su programa o función puede aceptar el número entero y devolver el programa Brain-Flak (cadena) en cualquiera de los formatos de E / S aceptables habituales. Los lazos se romperán usando el tamaño de su programa o función.
fuente
2n
es4^n catalan(n)
.(()()()...())
. Además, si solo usa números primos, eso podría perderse algunas optimizaciones posibles para los compuestos.[]
no está definido para este desafío? Me resulta extraño implementar 7 de los 8 operadores. De cualquier manera, desafío genial, ¡me siento honrado de que alguien escriba un desafío inspirado en mi propio idioma![]
su respuesta.Respuestas:
Python 2,
593945924458534584165839458250Ok, esta es mi solución.
La función relevante es
push(n)
. Para llamarlo simplemente llame al push en el número entero que desea representar.Explicación
La optimización principal realizada por el programa es la codificación de multiplicación. La idea de la codificación de multiplicación es bastante simple. Presiona el número y luego emerge y lo presiona para crear un nuevo valor. Por ejemplo, para multiplicar por dos, puede usar el siguiente código
((n){})
donde n código produce un número específico. Esto funciona porque ambos(n)
y{}
tienen un valor de n.Esta idea simple puede hacerse más compleja para números más grandes. Tomemos como ejemplo 5, hace un tiempo se descubrió que la mejor manera de multiplicar por cinco era
(((n)){}){}{}
. Este código hace dos copias de los n multiplica uno por 4 y agrega los dos. Usando la misma estrategia hago cada multiplicación basada en la representación binaria de un número. No entraré en los detalles de cómo funciona esto en este momento, pero lo hago cortando la primera representación binaria y reemplazando 0 con){}
y 1 con){}{}
. Luego se asegura de que n se presione el número apropiado de veces y equilibra todos los paréntesis. (Si quieres saber cómo se hace esto, puedes mirar mi código). Si quieres saber por qué esto funciona, solo pregúntame en un comentario. No creo que nadie lea realmente todas las actualizaciones de mi publicación, así que dejé la explicación.Cuando el algoritmo intenta encontrar un código de multiplicación, intenta todos los factores primos de los números. Ignora los factores compuestos porque en un punto los factores compuestos siempre podrían expresarse de manera más concisa como sus propios factores primos; no se sabe si esto sigue siendo cierto.
El otro mecanismo de ahorro de bytes es un buscador de soluciones polinómicas. Hay ciertas formas de polinomios que son fáciles de representar con bucles decrecientes. Estos polinomios incluyen, entre otros, números poligonales. Esta optimización encuentra polinomios que se ajustan al formulario y crea el código que los crea.
Salida
papelera
fuente
n
es mayor o menor quen+1
if n % 3 == 2:
el final de esa función en un nivel.Brain-Flak, 64664
Pruébalo en línea!
Aquí está mi código anotado
Explicación
Esto solo implementa dos reglas a partir de ahora:
Si n es divisible por dos devuelve
(n/2){}
Si n no es divisible por dos devuelve
n-1()
También codifica todos los números menores que 6.
fuente
Perl,
592225915658460 caracteresn()
(11322660 caracteres)(n){}()
(64664 caracteres)((n)){}{}
(63610 caracteres)((n)()){}{}
(63484 caracteres) - este es un cálculo novedoso(n){({}[()])}{}
(60748 caracteres)n[m]
(62800 caracteres)(n){m({}[l])}{}
(58460 caracteres) - este es un cálculo novedosoLa fórmula para ese último cálculo es
n(n/l+1)/2+mn/l
. He intentado algunos otros cálculos, pero ya no son útiles para el resultado dado. El programa realmente genera todos los valores hasta 9999 pero luego enumera los números primos dados y su longitud total.fuente
&try($i * $i, "$numbers[$i]{({})({}[()])}{}");
, que baja a 58032 cuando también agrego&try((3 * $i * $i - $i) / 2, "$numbers[$i]{({})({}[()])({})}{}");
(números cuadrados / pentagonales) - es de aquíPython,
5913658676 caracteresFunción de golf número de Brainflak:
Iteración de números primos:
Salida:
Pastebin
Explicación:
Prepoblamos una lista R de representación de Brain-flak evaluando a enteros individuales en un rango mayor que el necesario [1, m -1] para definir nuestra función f . Las representaciones se forman tomando la representación no utilizada más baja (indexada por l ) y formando muchas representaciones nuevas a partir de ella, manteniendo solo la más corta. La representación no utilizada más baja supone que a todos los números 1 a 1 se les ha asignado una representación, y que estas representaciones ya se han utilizado para producir nuevos números. Si un valor menor que l obtiene una representación más corta, debemos retroceder y reproducir los números que comienzan desde ese punto. La función f produce un programa que guarda el número en la pila agregando paréntesis.
No conocía Brainflak cuando comencé esto, y aprecio mucho la respuesta de Eamon Olive por señalar la fórmula para los números de triángulo. En general, he generalizado el resumen y he sido implacable sobre el control de sumas y diferencias. Agregar muchos múltiplos de sumas ha tenido un gran efecto.
Para aquellos a quienes les importa, aquí está el código de borrador que usé para ver qué fórmulas valieron la pena.
Fórmulas de representación:
(X){}
((X)){}{}
((((X)))){}{}{}{}
((((((X)))))){}{}{}{}{}{}
XY
X[Y]
(X){({}[Y])}{}
(X)({({}[Y])}{}){}
(X)(({({}[Y])}{})){}{}
(X)(({({}[Y])}{}){}){}
etc.
fuente
Lua 5.3, 57522
De hecho, comencé a trabajar en esto cuando se publicó la pregunta, pero lo olvidé hasta el aniversario de Brain-Flak.
Idea similar a las otras respuestas donde se utilizan funciones útiles conocidas para construir números más grandes a partir de buenas representaciones de números más simples.
Una diferencia es que en lugar de resolver subproblemas en términos de números más pequeños, estoy resolviendo subproblemas en términos de números con representaciones más cortas. Creo que esto hace que sea más elegante aprovechar los números negativos y manejar el caso en que los números más pequeños se representan en términos de números más grandes.
Además, tratar de encontrar todos los números que se puedan representar en un determinado tamaño en lugar de intentar representar un número particular lo más pronto posible, en realidad simplifica ciertos cálculos. En lugar de trabajar una fórmula a la inversa para ver si se puede aplicar a un número, la fórmula se puede avanzar y aplicar a cada número.
Otra diferencia es que las soluciones conocidas se almacenan en dos partes: un "prefijo" (opcional) y un "sufijo" (más parecido a un infijo). Se espera que la valoración del prefijo se ignore al calcular el número dado: el prefijo solo contiene código que configura el sufijo para que se ejecute (generalmente empujando una o más cosas a la pila). Entonces, dado un prefijo y un sufijo, el número correspondiente se puede insertar en la pila con
prefix(suffix)
.Esta división básicamente resuelve el mismo problema que la
unpack
función en la respuesta del Asistente de trigo. En lugar de ajustar el código<...>
solo para deshacer esto más tarde, dicho código simplemente se agrega al prefijo.En algunos casos, el prefijo realmente se evalúa (principalmente para la operación de pseudo-exponenciación), por lo que su valoración también se almacena. Sin embargo, esto realmente no causa un gran problema, ya que el generador no está tratando de construir números específicos. Parece implicar teóricamente que podría haber dos piezas de código de la misma longitud y generar el mismo número que no sería redundante en el caché debido a que tienen diferentes valoraciones de prefijos. Sin embargo, no me molesté en explicar esto, ya que no parece importar mucho (al menos en este dominio).
Me imagino que sería fácil reducir el recuento de bytes simplemente agregando más casos, pero por el momento he tenido suficiente.
He corrido hasta 1000000, pero solo he hecho la comprobación de cordura hasta 100000.
Pastebin de salida en primos dados.
fuente
k_limit
yk_max_len
hacer? No estoy seguro de entender el encabezado.k_max_len
. Podría verificar fácilmente que ha encontrado todos los números que solicitó después de procesar cada longitud, pero fue útil para mí poder vincular la longitud máxima durante las pruebas para que el programa se ejecute más rápido. (El procesamiento de longitudes más grandes puede ser muy lento).k_limit
Básicamente es el parámetro de entrada (generará programas para números hasta este), suponiendo que seak_max_len
lo suficientemente grande como para encontrarlos.rubí, 60246 bytes
Yo uso un hash. Encuentro el mejor golf para un número determinado y utilizo los más pequeños para encontrar los más grandes.
¡Los hashes recursivos son muy divertidos!
fuente
Python, 64014 caracteres
No sabía nada sobre Brainflak antes de este desafío y solo jugueteé un poco con él en tryitonline, por lo que podría haber atajos obvios que me perdí. Esta es una solución bastante aburrida, solo divide la entrada en
x=x/2+x%2
ox=x/3+x%3
, lo que sea más corto.Llámalo así:
b(42)
salida en pastebin
fuente
Lua, 64664 bytes
El programa imprime la longitud total de los programas y el programa para la 203a prima (hay una línea que puede cambiar para cambiar cuál se imprime o descomentar una línea para imprimir todos los programas)
En este momento, la única optimización es x = 2 * n + 1
Espero tener tiempo para agregar algunas optimizaciones más para reducir el puntaje.
fuente