Consejos para jugar golf en brainfuck

23

¿Qué consejos generales tienes para jugar al golf en Brainfuck? Estoy buscando ideas que se puedan aplicar a los problemas de golf de código en general que sean al menos algo específicos para el brainfuck (por ejemplo, "eliminar comentarios" no es una respuesta). Por favor, publique un consejo por respuesta.

RAM
fuente

Respuestas:

25

Poner un consejo por respuesta sería demasiadas respuestas.

  • Aprende a pensar en Brainfuck. Es muy diferente a cualquier otra cosa. Lee y escribe, reescribe y reescribe muchos programas de brainfuck. El lenguaje no te da mucho con qué trabajar, por lo que es importante usar lo que te da de manera flexible y eficiente. No permita que ninguna abstracción se interponga entre usted y el idioma, entre y lidie con eso.

  • Póngase muy cómodo con el control de flujo no destructivo. Para salir de un ciclo de decisión, en lugar de poner a cero la celda inicial copiándola en otro lugar y luego volviéndola a copiar después de abandonar el ciclo, a menudo es mejor mover el puntero a un cero preexistente cercano. Sí, esto significa que el puntero estará en diferentes lugares dependiendo de si atravesó el bucle, pero también significa que esos lugares probablemente tengan diferentes disposiciones de ceros y no ceros cercanos, que puede usar para resincronizar la ubicación del puntero usando otro bucle. Esta técnica es fundamental para una buena programación de Brainfuck, y varias formas de ella serán constantemente útiles.

  • Eso y el hecho de que cada >o <costes significa que los detalles de diseño de memoria son importantes. Pruebe tantas variaciones de su diseño como tenga paciencia. Y recuerde, su diseño de memoria no tiene que ser un mapeo rígido de datos a ubicaciones. Puede transformarse en el curso de la ejecución.

  • A mayor escala, considere e incluso intente implementar una variedad de algoritmos diferentes. Inicialmente no será obvio exactamente qué algoritmo será el mejor; puede que ni siquiera sea obvio qué enfoque básico será el mejor, y probablemente será algo diferente de lo que sería mejor en un lenguaje normal.

  • Si está tratando con datos grandes o de tamaño variable, vea si hay alguna forma de que pueda tratarlos localmente, sin tener que hacer un seguimiento de cuán grande es o su ubicación numérica dentro de él.

  • Los mismos datos pueden ser dos cosas diferentes. (Muy a menudo, un número o carácter y también un marcador posicional distinto de cero. Pero vea random.b , donde un contador de bits se duplica como el valor de una celda de un autómata celular).

  • El mismo código puede hacer dos cosas diferentes, y es mucho más fácil hacerlo en un lenguaje donde el código es tan genérico como <+<. Esté atento a tales posibilidades. De hecho, puede notar ocasionalmente, incluso en lo que parece ser un programa bien escrito, que hay pequeñas porciones que podrían eliminarse por completo, sin agregar nada, y la cosa, por casualidad, todavía funcionaría sin problemas.

  • En la mayoría de los idiomas, utiliza un compilador o un intérprete con frecuencia para verificar el comportamiento de su programa. El lenguaje Brainfuck exige un mayor control conceptual; si necesita un compilador que le diga qué hace su programa, no tiene una comprensión lo suficientemente firme de su programa, y ​​probablemente deba mirarlo un poco más, al menos si desea tener una imagen lo suficientemente clara de El halo conceptual de programas similares para ser bueno en el golf. Con práctica, estará produciendo una docena de versiones de su programa antes de intentar ejecutar una, y en ese momento estará 95% seguro de que su versión más corta se ejecutará correctamente.

  • ¡Buena suerte! Muy pocas personas se molestan en escribir Brainfuck de manera concisa, pero creo que esa es la única forma en que el lenguaje puede justificar la atención continua, como una forma de arte increíblemente oscura.

Daniel Cristofani
fuente
3
Leer esto me hace querer probar la programación en Brainfuck ahora ..
Claudiu
Mierda, pensé que reconocía tu nombre. ¡Gran fanático de tus programas de brainfuck, especialmente tu autointerpretador súper corto!
Jo King
"De vez en cuando puede notar ... que hay pequeñas porciones que podrían eliminarse por completo, sin agregar nada, y la cosa, por casualidad, todavía funcionaría sin problemas". Esto es muy cierto, especialmente para un principiante. Hasta donde puedo recordar, solo escribí una respuesta en BF, sin embargo, su historial de revisiones contiene al menos 3 instancias en las que estaba jugando con el programa y dije al azar: "¡Oye, el programa todavía funciona si elimino este bit! "
ETHproductions
"Pruebe tantas variaciones de su diseño como tenga paciencia", o puede
usar la
9

Algunos consejos aquí:

Constantes:

La página de constantes de Esolangs tiene una lista extremadamente útil de las formas más cortas para crear valores específicos. Me encuentro consultando esta página al menos dos veces por programa.

El comienzo de todo:

+++[[<+>>++<-]>]

Esto configura la cinta en el formato 3 * n ^ 2, que se ve como

3 6 12 24 48 96192128 0 0 '

¿Por qué es esto tan importante?

Bajemos la lista:

  • 3 y 6 son aburridos
  • 12: Cerca de 10 (nueva línea) o 13 (retorno de carro). También se puede usar para el contador de 0-9
  • 24: cerca de 26, el número de letras en el alfabeto
  • 48: ASCII para 0
  • 96: Cerca de 97, ASCII para a
  • 196 y 128: 196-128 = 64, cerca de 65, el ASCII para A.

A partir de este algoritmo, estamos al comienzo de prácticamente todas las secuencias en el rango ASCII, junto con un contador para cada una y una nueva línea de fácil acceso.

Un ejemplo práctico:

Imprimir todas las letras mayúsculas y minúsculas y dígitos.

Con algoritmo:

+++[[<+>>++<-]>]<<[-<->]<<<<++[->>+.>+.<<<]<--[>>.+<<-]

Sin:

+++++++++++++[->+++++++>++>+++++>++++>+<<<<<]>+++++>[-<+.>>.+<]>>---->---[-<.+>]

Pasamos la mayoría de los bytes simplemente inicializando la cinta en el segundo ejemplo. Algo de esto se compensa con los movimientos adicionales en el primer ejemplo, pero este método claramente tiene la ventaja.

Un par de otros algoritmos interesantes en la misma línea:

3 * 2 ^ n + 1:

+++[[<+>>++<-]+>]
Tape: 4 7 13 25 49 65 197 129 1 0'

Esto compensa los valores en 1, lo que logra algunas cosas. Hace que el 12 sea un retorno de carro, el 64 el comienzo real del alfabeto en mayúsculas y el 24 más cerca del 26.

2 ^ n:

+[[<+>>++<-]>]
Tape: 1 2 4 8 16 32 64 128

Debido a que 64 es bueno para letras mayúsculas, 32 es el ASCII para el espacio y 128 puede usarse como el contador para 26 (130/5 = 26). Esto puede ahorrar bytes en ciertas situaciones donde no se necesitan dígitos y letras minúsculas.

Elija la implementación que se adapte a la pregunta:

  • Las células negativas son casi siempre útiles, y no hay razón para evitarlas (a menos que no cambie su bytecount)
  • Casi exactamente lo mismo con las celdas de ajuste, aún más porque muchas constantes usan el ajuste.
  • Los tamaños de celdas arbitrarias son útiles para secuencias matemáticas infinitas, como calcular la secuencia de Fibonacci infinitamente ( +[[-<+>>+>+<<]>]) o procesar números más grandes / negativos. La desventaja es que algunos métodos comunes, como [-]y [->+<]no se puede confiar en ellos, en caso de que el número sea negativo.
  • EOF como 0, -1 o sin cambio. Por lo general, es preferible 0, ya que puede recorrer una entrada completa sin verificaciones adicionales. -1 es útil al recorrer estructuras de matriz. Todavía no he encontrado un uso para ningún cambio :(.

Lleve un registro de lo que está pasando:

En todo momento debe tener comentarios sobre dónde debe estar el puntero en relación con los datos que lo rodean, y asegúrese de conocer el rango de valores posibles de cada celda. Esto es especialmente importante cuando ha dividido el puntero antes de un bucle, ya que después querrá unir las dos posibilidades.

En cualquier momento, mi código está plagado de comentarios en cada línea que se ve así:

*0 *dat a_1 ?  0' !0 0*
 or
*0 *dat 0' ap1 0  !0 0*

Un consejo adicional es asignar símbolos a significados especiales. En el ejemplo anterior, 'es donde está el puntero, *significa repetición en esa dirección, ?significa una celda con valor desconocido, !0significa una celda que no es cero, _es un sustituto -y pes un sustituto de +.orimplica que la cinta podría parecerse a cualquiera de las representaciones, y debe manejarse como tal.

Su esquema de símbolos no necesariamente tiene que ser el mismo que el mío (que tiene algunos defectos), solo tiene que ser consistente. Esto también es extremadamente útil al depurar, porque puede ejecutarlo hasta ese punto y comparar la cinta real con la que debería tener, lo que puede señalar posibles fallas en su código.

Jo King
fuente
5

Mi principal consejo sería no lo hagas.

OK, bien, quieres algo más útil que eso. BF ya es un lenguaje muy conciso, pero lo que realmente te mata es la aritmética, que efectivamente debe hacerse en unario. Vale la pena leer la página de constantes en Esolang para elegir exactamente cómo escribir números grandes de manera eficiente y explotar el ajuste siempre que sea posible.

El acceso a la memoria también es muy costoso. Como estás leyendo una cinta, debes tener en cuenta dónde se mueve tu cabeza en un momento dado. A diferencia de otras lenguas en las que sólo se puede escribir a, b, c, en bf se tiene que mover de forma explícita la cabeza algún número de bytes hacia la izquierda o la derecha, por lo que debe ser consciente de donde se almacenan qué. Estoy bastante seguro de que organizar tu memoria de la manera óptima es NP-hard, así que buena suerte con eso.

ymbirtt
fuente
5

En esta respuesta, me referiré a una celda específica en la cinta muchas veces. No importa qué celda sea, pero es la misma celda en toda la respuesta. Para los fines de esta publicación, llamaré a esa celda "Todd".

Al intentar establecer una celda en un valor constante, a veces vale la pena no terminarla de inmediato. Por ejemplo, supongamos que desea que Todd contenga 30. Más adelante en su código (que puede modificar el valor de Todd pero nunca lo lee) vuelve a Todd. Si el valor de Todd es 0, el programa se cierra. De lo contrario, el valor de Todd se imprime para siempre.

De acuerdo con la página esolangs.org de constantes de brainfuck (que probablemente podría ser el tema de una propina por sí solo), la forma más corta de obtener 30 es >+[--[<]>>+<-]>+. Ese encabezado >solo está ahí para garantizar que no se modifique nada a la izquierda del puntero, pero en este caso asumiremos que no nos importa y lo descartaremos. Usando ese código, su código se vería así:

+[--[<]>>+<-]>+(MISC. CODE)(GO TO TODD)[.]

Puedes pensar en el primer fragmento de código como este:

(SET TODD TO 30)(MISC. CODE)(GO TO TODD)[.]

Pero recordar los dos últimos caracteres en ese pedazo: >+. Es tan válido pensarlo de esta manera:

(SET TODD TO 29)(GO TO TODD)(ADD 1 TO TODD)(MISC. CODE)(GO TO TODD)[.]

Tenga en cuenta que usted (GO TO TODD)dos veces! En su lugar, podría escribir su código de esta manera:

(SET TODD TO 29)(MISC. CODE)(GO TO TODD)(ADD 1 TO TODD)[.]
+[--[<]>>+<-](MISC. CODE)(GO TO TODD)+[.]

Suponiendo que el número de bytes que necesita (GO TO TODD)es el mismo antes, ¡un movimiento menos == un byte menos! A veces, el hecho de que su posición inicial haya cambiado le quita ese beneficio, pero no siempre.

metro subterráneo
fuente
0

Un pequeño consejo para desafíos sin aportes. Puede usarlo en ,lugar de [-], si necesita borrar la celda rápidamente, ya que la mayoría de los intérpretes (incluido el TIO.run one) configurará el contenido de la celda para que la representación EOF sea cero. Esto hace que los programas sean un poco inportables, pero de todos modos, ¿a quién le importa en el golf de código?

Krzysztof Szewczyk
fuente