Quine Mini-Flak más rápido

26

Mini-Flak es un subconjunto del Cerebro-Flak lenguaje, donde los <>, <...>y []no se permiten operaciones. Estrictamente hablando, no debe coincidir con la siguiente expresión regular:

.*(<|>|\[])

Mini-Flak es el subconjunto completo más pequeño de Turing conocido de Brain-Flak.

Hace un tiempo pude hacer un Quine en Mini-Flak , pero fue demasiado lento para correr en la vida del universo.

Entonces mi desafío para ti es hacer un Quine más rápido.

Tanteo

Para calificar su código coloque una @cybandera al final de su código y ejecútelo en el intérprete de Ruby ( Pruébelo en línea usa el intérprete de ruby) usando la -dbandera. Su puntaje debe imprimirse en STDERR de la siguiente manera:

@cy <score>

Este es el número de ciclos que toma su programa antes de finalizar y es el mismo entre ejecuciones. Dado que cada ciclo tarda aproximadamente la misma cantidad de tiempo en ejecutarse, su puntaje debe estar directamente relacionado con el tiempo que lleva ejecutar su programa.

Si su Quine es demasiado largo para que pueda ejecutarlo razonablemente en su computadora, puede calcular el número de ciclos a mano.

Calcular el número de ciclos no es muy difícil. El número de ciclos equivale a 2 veces el número de mónadas ejecutadas más el número de nilas ejecutadas. Esto es lo mismo que reemplazar cada nilad con un solo personaje y contar el número de caracteres ejecutados en total.

Ejemplo de puntuación

  • (()()()) puntúa 5 porque tiene 1 mónada y 3 nilas.

  • (()()()){({}[()])} puntúa 29 porque la primera parte es la misma que antes y puntúa 5 mientras que el bucle contiene 6 mónadas y 2 nilads puntuando 8. El bucle se ejecuta 3 veces, por lo que contamos su puntaje 3 veces. 1*5 + 3*8 = 29

Requisitos

Tu programa debe ...

  • Tener al menos 2 bytes

  • Imprima su código fuente cuando se ejecute en Brain-Flak usando la -Abandera

  • No coincide con la expresión regular .*(<|>|\[])

Consejos

  • El intérprete de Crane-Flak es categóricamente más rápido que el intérprete de ruby, pero carece de algunas de las características. Recomendaría probar su código usando Crane-Flak primero y luego puntuarlo en el intérprete de ruby ​​cuando sepa que funciona. También recomendaría no ejecutar su programa en TIO. TIO no solo es más lento que el intérprete de escritorio, sino que también expirará en aproximadamente un minuto. Sería extremadamente impresionante si alguien lograra un puntaje lo suficientemente bajo como para ejecutar su programa antes de que TIO expire.

  • [(...)]{}y (...)[{}]funcionan igual <...>pero no rompen el requisito de fuente restringida

  • Puede consultar Brain-Flak y Mini-Flak Quines si desea tener una idea de cómo abordar este desafío.

restricted-source quine fastest-code brain-flak Asistente de trigo
fuente
1
"current best" -> "current only"
HyperNeutrino

Respuestas:

33

Mini-Flak, 6851113 ciclos

El programa (literalmente)

Sé que la mayoría de las personas probablemente no esperan que una quine Mini-Flak use caracteres no imprimibles e incluso caracteres de varios bytes (lo que hace que la codificación sea relevante). Sin embargo, este quine, y los no imprimibles, combinados con el tamaño del quine (93919 caracteres codificados como 102646 bytes de UTF-8), hacen que sea bastante difícil colocar el programa en esta publicación.

Sin embargo, el programa es muy repetitivo y, como tal, se comprime muy bien. Para que todo el programa esté disponible literalmente de Stack Exchange, hay un xxdhexdump reversible de una gzipversión comprimida de la quine completa oculta detrás del colapsable a continuación:

Mostrar fragmento de código

(Sí, es tan repetitivo que incluso puedes ver las repeticiones después de que se ha comprimido).

La pregunta dice: "También recomendaría no ejecutar su programa en TIO. No solo es TIO más lento que el intérprete de escritorio, sino que también expirará en aproximadamente un minuto. Sería extremadamente impresionante si alguien lograra un puntaje lo suficientemente bajo para ejecutar su programa antes de que TIO expire ". ¡Yo puedo hacer eso! Se tarda unos 20 segundos en ejecutarse en TIO, utilizando el intérprete Ruby: ¡ Pruébelo en línea!

El programa (legible)

Ahora que he dado una versión del programa que las computadoras pueden leer, intentemos una versión que los humanos puedan leer. He convertido los bytes que componen la quine en la página de códigos 437 (si tienen el bit alto establecido) o imágenes de control Unicode (si son códigos de control ASCII), agregué espacios en blanco (cualquier espacio en blanco preexistente se convirtió para controlar imágenes) ), codificado en longitud de ejecución utilizando la sintaxis «string×length», y algunos bits con gran cantidad de datos elididos:

␠
(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                («()×35» («()×44» («()×44» («()×44» («()×44» («()×45»
                … much more data encoded the same way …
                («()×117»(«()×115»(«()×117»
                «000010101011┬â┬ … many more comment characters … ┬â0┬â┬à00␈␈
                )[({})(
                    ([({})]({}{}))
                    {
                        ((()[()]))
                    }{}
                    {
                        {
                            ({}(((({}())[()])))[{}()])
                        }{}
                        (({}))
                        ((()[()]))
                    }{}
                )]{}
                %Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'×almost 241»
                ,444454545455┬ç┬ … many more comment characters … -a--┬ü␡┬ü-a␡┬ü
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

(El "casi 241" se debe a que a la copia 241 le falta el final ', pero por lo demás es idéntico a los otros 240).

Explicación

Sobre los comentarios

Lo primero que hay que explicar es, ¿qué pasa con los caracteres no imprimibles y otra basura que no son comandos de Mini-Flak? Puede pensar que agregar comentarios al quine solo hace las cosas más difíciles, pero esta es una competencia de velocidad (no una competencia de tamaño), lo que significa que los comentarios no perjudican la velocidad del programa. Mientras tanto, Brain-Flak y, por lo tanto, Mini-Flak, simplemente vuelcan el contenido de la pila a la salida estándar; si tuviera que asegurarse de que la pila contenga sololos personajes que componían los comandos de tu programa, tendrías que pasar ciclos limpiando la pila. Tal como está, Brain-Flak ignora a la mayoría de los personajes, por lo que siempre que nos aseguremos de que los elementos de la pila de basura no sean comandos válidos de Brain-Flak (lo que lo convierte en un políglota Brain-Flak / Mini-Flak), y no son negativos o externos. En el rango Unicode, podemos dejarlos en la pila, permitir que se impriman y colocar el mismo carácter en nuestro programa en el mismo lugar para retener la propiedad quine.

Hay una manera particularmente importante en que podemos aprovechar esto. La quine funciona mediante el uso de una cadena de datos larga, y básicamente toda la salida de la quine se produce formateando la cadena de datos de varias maneras. Solo hay una cadena de datos, a pesar de que el programa tiene varias piezas; entonces necesitamos poder usar la misma cadena de datos para imprimir diferentes partes del programa. El truco "los datos basura no importan" nos permite hacer esto de una manera muy simple; almacenamos los caracteres que componen el programa en la cadena de datos agregando o restando un valor ao de su código ASCII. Específicamente, los caracteres que constituyen el inicio del programa se almacenan como su código ASCII + 4, los caracteres que forman la sección que se repite casi 241 veces como su código ASCII - 4,cada carácter de la cadena de datos con un desplazamiento; si, por ejemplo, lo imprimimos con 4 agregados a cada código de caracteres, obtenemos una repetición de la sección repetida, con algunos comentarios antes y después. (Esos comentarios son simplemente las otras secciones del programa, con códigos de caracteres desplazados para que no formen comandos válidos de Brain-Flak, porque se agregó el desplazamiento incorrecto. Tenemos que esquivar los comandos de Brain-Flak, no solo Mini- Comandos antiaéreos, para evitar violar la parte de fuente restringida de la pregunta; la elección de las compensaciones fue diseñada para garantizar esto).

Debido a este truco de comentarios, en realidad solo necesitamos poder generar la cadena de datos formateada de dos maneras diferentes: a) codificada de la misma manera que en la fuente, b) como códigos de caracteres con un desplazamiento especificado agregado a cada código. Esa es una gran simplificación que hace que la longitud agregada valga totalmente la pena.

Estructura del programa

Este programa consta de cuatro partes: la introducción, la cadena de datos, el formateador de la cadena de datos y la salida. La introducción y la salida son básicamente responsables de ejecutar la cadena de datos y su formateador en un bucle, especificando el formato apropiado cada vez (es decir, si codificar o compensar, y qué compensación usar). La cadena de datos es solo datos, y es la única parte de la línea para la cual los caracteres que la componen no se especifican literalmente en la cadena de datos (hacerlo obviamente sería imposible, ya que tendría que ser más largo que sí mismo); Por lo tanto, está escrito de una manera que es particularmente fácil de regenerar a partir de sí mismo. El formateador de la cadena de datos está hecho de 241 partes casi idénticas, cada una de las cuales formatea un dato específico del 241 en la cadena de datos.

Cada parte del programa se puede producir a través de la cadena de datos y su formateador de la siguiente manera:

  • Para producir el outro, formatee la cadena de datos con desplazamiento +8
  • Para producir el formateador de cadena de datos, formatee la cadena de datos con desplazamiento +4, 241 veces
  • Para producir la cadena de datos, formatee la cadena de datos codificándola en el formato fuente
  • Para producir la introducción, formatee la cadena de datos con desplazamiento -4

Entonces, todo lo que tenemos que hacer es observar cómo funcionan estas partes del programa.

La cadena de datos

(«()×35» («()×44» («()×44» («()×44» («()×44» («()×45» …

Necesitamos una codificación simple para la cadena de datos, ya que tenemos que poder invertir la codificación en código Mini-Flak. ¡No puedes ser mucho más simple que esto!

La idea clave detrás de esta quine (aparte del truco de comentarios) es notar que básicamente solo hay un lugar donde podemos almacenar grandes cantidades de datos: las "sumas de valores de retorno de comando" dentro de los diversos niveles de anidamiento de la fuente del programa. (Esto se conoce comúnmente como la tercera pila, aunque Mini-Flak no tiene una segunda pila, por lo que "pila de trabajo" es probablemente un mejor nombre en el contexto de Mini-Flak.) Las otras posibilidades para almacenar datos serían la pila principal / primera (que no funciona porque ahí es donde debe ir nuestra salida, y no podemos mover la salida más allá del almacenamiento de una manera remotamente eficiente), y codificada en un bignum en un solo elemento de pila (que no es adecuado para este problema porque lleva un tiempo exponencial para extraer datos de él); cuando los eliminas, la pila de trabajo es la única ubicación restante.

Para "almacenar" datos en esta pila, utilizamos comandos no balanceados (en este caso, la primera mitad de un (…)comando), que se equilibrarán más adelante en el formateador de cadenas de datos. Cada vez que cerramos uno de estos comandos dentro del formateador, empujará la suma de un dato tomado de la cadena de datos y los valores de retorno de todos los comandos en ese nivel de anidamiento dentro del formateador; podemos asegurar que este último se agregue a cero, por lo que el formateador simplemente ve valores individuales tomados de la cadena de datos.

El formato es muy simple: (seguido de n copias de (), donde n es el número que queremos almacenar. (Tenga en cuenta que esto significa que solo podemos almacenar números no negativos, y el último elemento de la cadena de datos debe ser positivo).

Un punto poco intuitivo acerca de la cadena de datos es en qué orden se encuentra. El "inicio" de la cadena de datos es el final más cercano al inicio del programa, es decir, el nivel de anidamiento más externo; esta parte se formatea en último lugar (ya que el formateador se ejecuta desde los niveles de anidación más internos a los más externos). Sin embargo, a pesar de estar formateado en último lugar, se imprime primero, porque el intérprete Mini-Flak imprime los valores introducidos en la pila primero. El mismo principio se aplica al programa en su conjunto; primero debemos formatear el outro, luego el formateador de la cadena de datos, luego la cadena de datos, luego la introducción, es decir, el reverso del orden en que están almacenados en el programa.

El formateador de cadena de datos

)[({})(
    ([({})]({}{}))
    {
        ((()[()]))
    }{}
    {
        {
            ({}(((({}())[()])))[{}()])
        }{}
        (({}))
        ((()[()]))
    }{}
)]{}

El formateador de la cadena de datos está formado por 241 secciones que tienen un código idéntico (una sección tiene un comentario marginalmente diferente), cada una de las cuales formatea un carácter específico de la cadena de datos. (No podríamos usar un bucle aquí: necesitamos un desequilibrado )para leer la cadena de datos haciendo coincidir su desequilibrado (, y no podemos poner uno de esos dentro de un {…}bucle, la única forma de bucle que existe. Entonces, en su lugar, " desenrolle "el formateador, y simplemente haga que la introducción / outro emita la cadena de datos con el desplazamiento del formateador 241 veces).

)[({})( … )]{}

La parte más externa de un elemento formateador lee un elemento de la cadena de datos; La simplicidad de la codificación de la cadena de datos conduce a una pequeña complejidad al leerla. Comenzamos cerrando lo que no coincide (…)en la cadena de datos, luego negamos ( […]) dos valores: el dato que acabamos de leer de la cadena de datos ( ({})) y el valor de retorno del resto del programa. Copiamos el valor de retorno del resto del elemento formateador con (…)y agregamos la copia a la versión negada con {}. El resultado final es que el valor de retorno del elemento de cadena de datos y el elemento formateador juntos es el dato menos el dato menos el valor de retorno más el valor de retorno, o 0; Esto es necesario para que el siguiente elemento de cadena de datos produzca el valor correcto.

([({})]({}{}))

El formateador utiliza el elemento de la pila superior para saber en qué modo está (0 = formato en formato de cadena de datos, cualquier otro valor = el desplazamiento con el que se generará). Sin embargo, solo después de leer la cadena de datos, el dato está en la parte superior del formato en la pila, y los queremos al revés. Este código es una variante más corta del código de intercambio Brain-Flak, tomando a arriba b a b arriba a  +  b ; no solo es más corto, también es (en este caso específico) más útil, porque el efecto secundario de agregar b a a no es problemático cuando b es 0, y cuando b no es 0, hace el cálculo de compensación para nosotros.

{
    ((()[()]))
}{}
{
    …
    ((()[()]))
}{}

Brain-Flak solo tiene una estructura de flujo de control, por lo que si queremos algo más que un whilebucle, tomará un poco de trabajo. Esta es una estructura "negativa"; si hay un 0 en la parte superior de la pila, lo elimina, de lo contrario, coloca un 0 en la parte superior de la pila. (Funciona de manera bastante simple: siempre que no haya un 0 en la parte superior de la pila, empuje 1 - 1 a la pila dos veces; cuando haya terminado, haga estallar el elemento de la pila superior).

Es posible colocar código dentro de una estructura negada, como se ve aquí. El código solo se ejecutará si la parte superior de la pila no es cero; así que si tenemos dos estructuras negadas, suponiendo que los dos elementos superiores de la pila no sean ambos cero, se cancelarán entre sí, pero cualquier código dentro de la primera estructura se ejecutará solo si el elemento superior de la pila no es cero, y el código dentro la segunda estructura se ejecutará solo si el elemento de la pila superior era cero. En otras palabras, esto es el equivalente de una declaración if-then-else.

En la cláusula "entonces", que se ejecuta si el formato no es cero, en realidad no tenemos nada que hacer; lo que queremos es empujar los datos + desplazamiento a la pila principal (para que pueda salir al final del programa), pero ya está allí. Entonces, solo tenemos que lidiar con el caso de codificar el elemento de cadena de datos en forma de origen.

{
    ({}(((({}())[()])))[{}()])
}{}
(({}))

Así es como lo hacemos. La {({}( … )[{}()])}{}estructura debe ser familiar como un bucle con un número específico de iteraciones (que funciona moviendo el contador del bucle a la pila de trabajo y manteniéndolo allí; estará a salvo de cualquier otro código, porque el acceso a la pila de trabajo está vinculado a el nivel de anidamiento del programa). El cuerpo del bucle es ((({}())[()])), que hace tres copias del elemento de la pila superior y agrega 1 al más bajo. En otras palabras, transforma un 40 en la parte superior de la pila en 40 por encima de 40 por encima de 41, o visto como ASCII, (en ((); la ejecución de este repetidamente hará (en (()en (()()en (()()()y así sucesivamente, y por lo tanto es una forma sencilla de generar nuestra cadena de datos (suponiendo que hay una (en la parte superior de la pila ya).

Una vez que hayamos terminado con el bucle, (({}))duplica la parte superior de la pila (de modo que ahora comience en ((()…lugar de (()…. La (siguiente copia del formateador de cadena de datos usará el encabezado para formatear el siguiente carácter (lo expandirá en (()(()…luego (()()(()…, y así sucesivamente, entonces esto genera la separación (en la cadena de datos).

%Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'

Hay un último interés en el formateador de cadena de datos. OK, así que esto es solo el outro desplazado 4 puntos de código hacia abajo; sin embargo, ese apóstrofe al final puede parecer fuera de lugar. '(punto de código 39) cambiaría a +(punto de código 43), que no es un comando Brain-Flak, por lo que puede haber adivinado que está ahí para algún otro propósito.

La razón por la que esto está aquí es porque el formateador de la cadena de datos espera que ya haya un (en la pila (no contiene un 40 literal en ninguna parte). los'en realidad se encuentra al comienzo del bloque que se repite para formar el formateador de la cadena de datos, no al final, por lo que después de que los caracteres del formateador de la cadena de datos se hayan introducido en la pila (y el código está a punto de pasar a imprimir la cadena de datos ), el outro ajusta el 39 en la parte superior de la pila en un 40, listo para que el formateador (el formateador en sí mismo esta vez, no su representación en la fuente) lo use. Es por eso que tenemos "casi 241" copias del formateador; a la primera copia le falta su primer carácter. Y ese carácter, el apóstrofe, es uno de los únicos tres caracteres en la cadena de datos que no corresponde al código Mini-Flak en algún lugar del programa; está ahí simplemente como un método para proporcionar una constante.

La introducción y outro

(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                …
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

La introducción y la salida son conceptualmente la misma parte del programa; La única razón por la que hacemos una distinción es que el outro debe imprimirse antes que la cadena de datos y su formateador (para que se imprima después de ellos), mientras que la introducción debe imprimirse después de ellos (imprimir antes de ellos).

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

Comenzamos colocando dos copias de 8 en la pila. Este es el desplazamiento para la primera iteración. La segunda copia se debe a que el bucle principal espera que haya un elemento basura en la parte superior de la pila sobre el desplazamiento, dejado atrás de la prueba que decide si existe el bucle principal, por lo que necesitamos colocar un elemento basura allí para que no tira el elemento que realmente queremos; una copia es la forma más segura (por lo tanto, la más rápida de generar) para hacerlo.

Hay otras representaciones del número 8 que no son más largas que esta. Sin embargo, cuando se busca el código más rápido, esta es definitivamente la mejor opción. Por un lado, usar ()()()()es más rápido que, digamos, (()()){}porque a pesar de que ambos tienen 8 caracteres de longitud, el primero es un ciclo más rápido, porque (…)se cuenta como 2 ciclos, pero ()solo como uno. Sin embargo, guardar un ciclo es insignificante en comparación con una consideración mucho mayor para una quine : (y )tiene puntos de código mucho más bajos que {y }, por lo que generar el fragmento de datos para ellos será mucho más rápido (y el fragmento de datos ocupará menos espacio en el código, también).

{{} … }{}{}

El bucle principal. Esto no cuenta las iteraciones (es un whilebucle, no un forbucle, y utiliza una prueba para salir). Una vez que sale, descartamos los dos elementos superiores de la pila; el elemento superior es un 0 inofensivo, pero el elemento a continuación será el "formato para usar en la próxima iteración", que (siendo un desplazamiento negativo) es un número negativo, y si hay números negativos en la pila cuando el Mini -El programa Flak sale, el intérprete falla al intentar generarlos.

Debido a que este ciclo utiliza una prueba explícita para salir, el resultado de esa prueba se dejará en la pila, por lo que lo descartamos como lo primero que hacemos (su valor no es útil).

(({})[(()()()())])

Este código empuja 4 y f  - 4 sobre un elemento de pila f , mientras deja ese elemento en su lugar. Estamos calculando el formato para la próxima iteración por adelantado (mientras tenemos las 4 constantes a la mano), y simultáneamente colocamos la pila en el orden correcto para las siguientes partes del programa: usaremos f como formato para esta iteración, y el 4 es necesario antes de eso.

(({})( … )[{}])

Esto guarda una copia de f  - 4 en la pila de trabajo, para que podamos usarlo en la próxima iteración. (El valor de f todavía estará presente en ese punto, pero estará en un lugar incómodo en la pila, e incluso si pudiéramos maniobrarlo al lugar correcto, tendríamos que pasar ciclos restando 4 de él, y ciclos de impresión del código para hacer esa resta. Mucho más fácil simplemente almacenarlo ahora).

{{}{}((()[()]))}{}

Una prueba para ver si el desplazamiento es 4 (es decir, f  - 4 es 0). Si es así, estamos imprimiendo el formateador de la cadena de datos, por lo que debemos ejecutar la cadena de datos y su formateador 241 veces en lugar de solo una vez en este desplazamiento. El código es bastante simple: si f  - 4 no es cero, reemplace el f  - 4 y el 4 en sí mismo con un par de ceros; luego, en cualquier caso, haga estallar el elemento de la pila superior. Ahora tenemos un número sobre f en la pila, ya sea 4 (si queremos imprimir esta iteración 241 veces) o 0 (si queremos imprimirlo solo una vez).

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

Este es un tipo interesante de constante Brain-Flak / Mini-Flak; la línea larga aquí representa el número 60. Puede estar confundido por la falta de (), que normalmente están por todas partes en las constantes de Brain-Flak; Este no es un número regular, sino un número de la Iglesia, que interpreta los números como una operación de duplicación. Por ejemplo, el número de la Iglesia para 60, visto aquí, hace 60 copias de su entrada y las combina todas en un solo valor; en Brain-Flak, lo único que podemos combinar son números regulares, por suma, por lo que terminamos agregando 60 copias de la parte superior de la pila y multiplicando así la parte superior de la pila por 60.

Como nota al margen, puede usar un buscador de números de Subcarga , que genera números de Iglesia en la sintaxis de Subcarga, para encontrar el número apropiado en Mini-Flak también. Los números de baja carga (que no sean cero) usan las operaciones "duplicar el elemento superior de la pila" :y "combinar los dos elementos superiores de la pila" *; ambos existen esas operaciones en Brain-Flak, por lo que sólo traduce :a ), *a {}, anteponga una {}, y añadir una cantidad suficiente (al inicio de equilibrio (esto es usar una mezcla extraña de la chimenea principal y la pila de trabajo, pero funciona).

Este fragmento de código en particular usa el número de iglesia 60 (efectivamente un fragmento "multiplicar por 60"), junto con un incremento, para generar la expresión 60 x  + 1. Entonces, si obtuvimos un 4 del paso anterior, esto nos da un valor de 241, o si tuviéramos un 0, solo obtenemos un valor de 1, es decir, esto calcula correctamente el número de iteraciones que necesitamos.

La elección de 241 no es casual; fue un valor elegido para ser a) aproximadamente la longitud a la que el programa terminaría de todos modos yb) 1 más de 4 veces un número redondo. Los números redondos, 60 en este caso, tienden a tener representaciones más cortas como números de la Iglesia porque tiene más flexibilidad en los factores para copiar. El programa contiene relleno más adelante para aumentar exactamente la longitud hasta 241.

{
    ({}(
        …
    )[{}()])
}{}

Este es un bucle for, como el visto anteriormente, que simplemente ejecuta el código dentro de él varias veces igual a la parte superior de la pila principal (que consume; el contador del bucle se almacena en la pila de trabajo, pero la visibilidad de eso está relacionado con el nivel de anidación del programa y, por lo tanto, es imposible que otra cosa que el bucle for mismo interactúe con él). En realidad, esto ejecuta la cadena de datos y su formateador 1 o 241 veces, y como ahora hemos extraído todos los valores que estábamos usando para nuestro cálculo de flujo de control desde la pila principal, tenemos el formato para usar encima, listo para El formateador a utilizar.

(␀␀!S␠su! … many more comment characters … oq␝qoqoq)

El comentario aquí no está completamente sin interés. Por un lado, hay un par de comandos Brain-Flak; la )al final se genera de forma natural como un efecto secundario de la forma en que las transiciones entre los diversos segmentos de la obra programa, por lo que el (al comienzo se añadió manualmente para equilibrar (y a pesar de la longitud de la comentario dentro, poniendo un comentario dentro de un ()comando sigue siendo un ()comando, por lo que todo lo que hace es agregar 1 al valor de retorno de la cadena de datos y su formateador, algo que el bucle for ignora por completo).

Más notablemente, esos caracteres NUL al comienzo del comentario claramente no son compensaciones de nada (incluso la diferencia entre +8 y -4 no es suficiente para convertir un (a NUL). Esos son rellenos puros para llevar la cadena de datos de 239 elementos a 241 elementos (que se amortizan fácilmente: tomaría mucho más de dos bytes generar 1 frente a 239 en lugar de 1 frente a 241 al calcular el número de iteraciones requeridas ) Se usó NUL como el carácter de relleno porque tiene el punto de código más bajo posible (haciendo que el código fuente de la cadena de datos sea más corto y, por lo tanto, más rápido de salida).

{}({}())

Suelte el elemento de la pila superior (el formato que estamos usando), agregue 1 al siguiente (el último carácter que se generará, es decir, el primer carácter que se imprimirá, de la sección del programa que acabamos de formatear). Ya no necesitamos el formato anterior (el nuevo formato se esconde en la pila de trabajo); y el incremento es inofensivo en la mayoría de los casos, y cambia la 'representación de origen del formateador de cadena de datos en un ((que se requiere en la pila para la próxima vez que ejecutemos el formateador, para formatear la cadena de datos en sí). Necesitamos una transformación como esa en el outro o intro, porque forzar cada elemento del formateador de cadena de datos para comenzar (lo haría un poco más complejo (ya que necesitaríamos cerrar (y luego deshacer su efecto), yde alguna manera necesitaríamos generar un extra en (algún lugar porque solo tenemos casi 241 copias del formateador, no todas 241 (por lo que es mejor que un personaje inofensivo como 'el que falta).

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

Finalmente, la prueba de salida del bucle. La parte superior actual de la pila principal es el formato que necesitamos para la próxima iteración (que acaba de salir de la pila de trabajo). Esto lo copia y agrega 8 a la copia; el valor resultante se descartará la próxima vez alrededor del ciclo. Sin embargo, si acabamos de imprimir la introducción, el desplazamiento fue -4, por lo que el desplazamiento para la "próxima iteración" será -8; -8 + 8 es 0, por lo que el ciclo saldrá en lugar de continuar en la iteración después.

cuenta temporal de ais523
fuente
16

128,673,515 ciclos

Pruébalo en línea

Explicación

La razón por la cual las minas de Miniflak están destinadas a ser lentas es la falta de acceso aleatorio de Miniflak. Para evitar esto, creo un bloque de código que toma un número y devuelve un dato. Cada dato representa un solo carácter como antes y el código principal simplemente consulta este bloque para cada uno a la vez. Esto esencialmente funciona como un bloque de memoria de acceso aleatorio.

Este bloque de código tiene dos requisitos.

  • Debe tomar un número y generar solo el código de caracteres para ese carácter

  • Debe ser fácil reproducir la tabla de búsqueda poco a poco en Brain-Flak

Para construir este bloque, en realidad reutilicé un método de mi prueba de que Miniflak está Turing completo. Para cada dato hay un bloque de código que se ve así:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Esto resta uno del número en la parte superior de la pila y si el cero empuja %s el dato debajo de él. Como cada pieza disminuye el tamaño en uno si comienza con n en la pila, obtendrá el enésimo dato.

Esto es agradable y modular, por lo que puede ser escrito por un programa fácilmente.

Luego tenemos que configurar la máquina que realmente traduce esta memoria en la fuente. Este consta de 3 partes como tales:

(([()]())())
{({}[(
  -Look up table-
 )]{})
 1. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}(([{}]))(()()()()()))]{})}{}

 2. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}
      (({}[(
      ({}[()(((((()()()()()){}){}){}))]{}){({}[()(({}()))]{}){({}[()(({}((((()()()){}){}){}()){}))]{}){({}[()(({}()()))]{}){({}[()(({}(((()()()()())){}{}){}))]{}){([(({}{}()))]{})}}}}}{}
      (({}({}))[({}[{}])])
     )]{}({})[()]))
      ({[()]([({}({}[({})]))]{})}{}()()()()()[(({}({})))]{})
    )]{})}{}

 3. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}
     (({}(({}({}))[({}[{}])][(
     ({}[()(
      ([()](((()()[(((((((()()()){})())){}{}){}){})]((((()()()()())){}{}){})([{}]([()()](({})(([{}](()()([()()](((((({}){}){}())){}){}{}))))))))))))
     )]{})
     {({}[()(((({})())[()]))]{})}{}
     (([(((((()()()()){}){}()))){}{}([({})]((({})){}{}))]()()([()()]({}(({})([()]([({}())](({})([({}[()])]()(({})(([()](([({}()())]()({}([()](([((((((()()()())()){}){}){}()){})]({}()(([(((((({})){}){}())){}{})]({}([((((({}())){}){}){}()){}()](([()()])(()()({}(((((({}())())){}{}){}){}([((((({}))){}()){}){}]([((({}[()])){}{}){}]([()()](((((({}())){}{}){}){})(([{}](()()([()()](()()(((((()()()()()){}){}){}()){}()(([((((((()()()())){}){}())){}{})]({}([((((({})()){}){}){}()){}()](([()()])(()()({}(((((({}){}){}())){}){}{}(({})))))))))))))))))))))))))))))))))))))))))))))))
     )]{})[()]))({()()()([({})]{})}{}())
    )]{})}{}

   ({}[()])
}{}{}{}
(([(((((()()()()){}){}())){}{})]((({}))([()]([({}())]({}()([()]((()([()]((()([({})((((()()()()){}){}()){})]()())([({})]({}([()()]({}({}((((()()()()()){}){}){}))))))))))))))))))

La máquina consta de cuatro partes que se ejecutan en orden comenzando con 1 y terminando con 3. Las he etiquetado en el código anterior. Cada sección también usa el mismo formato de tabla de búsqueda que uso para la codificación. Esto se debe a que todo el programa está contenido en un bucle y no queremos ejecutar cada sección cada vez que lo ejecutamos, por lo que colocamos la misma estructura RA y consultamos la sección que deseamos cada vez.

1

La sección 1 es una sección de configuración simple.

El programa le dice a las primeras consultas la sección 1 y el dato 0. El dato 0 no existe, por lo que en lugar de devolver ese valor, simplemente disminuye la consulta una vez para cada dato. Esto es útil porque podemos usar el resultado para determinar la cantidad de datos, que serán importantes en futuras secciones. La Sección 1 registra el número de datos al negativizar el resultado y consulta la Sección 2 y el último dato. El único problema es que no podemos consultar la sección 2 directamente. Como queda otro decremento, necesitamos consultar una sección 5. no existente. De hecho, este será el caso cada vez que consultemos una sección dentro de otra sección. Ignoraré esto en mi explicación, sin embargo, si está buscando un código, solo recuerde 5 significa volver a una sección y 4 significa ejecutar la misma sección nuevamente.

2

La Sección 2 decodifica los datos en los caracteres que forman el código después del bloque de datos. Cada vez que espera que la pila aparezca así:

Previous query
Result of query
Number of data
Junk we shouldn't touch...

Asigna cada resultado posible (un número del 1 al 6) a uno de los seis caracteres Miniflak válidos ( (){}[]) y lo coloca debajo del número de datos con el mensaje "Basura que no debemos tocar". Esto nos da una pila como:

Previous query
Number of data
Junk we shouldn't touch...

A partir de aquí, debemos consultar el siguiente dato o, si los hemos consultado, pasar a la sección 3. La consulta anterior no es en realidad la consulta exacta enviada, sino la consulta menos el número de datos en el bloque. Esto se debe a que cada dato disminuye la consulta en uno, por lo que la consulta sale bastante destrozada. Para generar la siguiente consulta, agregamos una copia del número de datos y restamos uno. Ahora nuestra pila se ve así:

Next query
Number of data
Junk we shouldn't touch...

Si nuestra próxima consulta es cero, hemos leído toda la memoria necesaria en la sección 3, por lo que agregamos el número de datos a la consulta nuevamente y colocamos un 4 en la parte superior de la pila para pasar a la sección 3. Si la siguiente consulta no es cero, pon un 5 en la pila para ejecutar la sección 2 nuevamente.

3

La Sección 3 crea el bloque de datos al consultar nuestra RAM tal como lo hace la sección 3.

En aras de la brevedad, omitiré la mayoría de los detalles de cómo funciona la sección 3. Es casi idéntico a la sección 2, excepto que en lugar de traducir cada dato en un carácter, traduce cada uno en un largo fragmento de código que representa su entrada en la RAM. Cuando se completa la sección 3, le dice al programa que salga del ciclo.

Una vez que se ha ejecutado el bucle, el programa solo necesita presionar el primer bit de la línea ([()]())(()()()()){({}[(. Lo hago con el siguiente código que implementa técnicas estándar de complejidad de Kolmogorov.

(([(((((()()()()){}){}())){}{})]((({}))([()]([({}())]({}()([()]((()([()]((()([({})((((()()()()){}){}()){})]()())([({})]({}([()()]({}({}((((()()()()()){}){}){}))))))))))))))))))

Espero que esto haya quedado claro. Por favor comente si está confundido acerca de algo.

Asistente de trigo
fuente
¿Aproximadamente cuánto tarda en ejecutarse? Tiempos en TIO.
Pavel
@Pavel No lo ejecuto en TIO porque sería increíblemente lento, uso el mismo intérprete que TIO (el rubí ). Tarda unos 20 minutos en ejecutarse en un antiguo servidor de rack al que tengo acceso. Se tarda unos 15 minutos en Crain-Flak, pero Crain-Flak no tiene indicadores de depuración, por lo que no puedo anotarlo sin ejecutarlo en el intérprete de Ruby.
Wheat Wizard
@Pavel Lo ejecuté nuevamente y lo cronometré. Se tardó 30m45.284sen completarse en un servidor de gama baja (aproximadamente el equivalente a un escritorio moderno promedio) usando el intérprete ruby.
Wheat Wizard el