Golunar / Unario es una forma de codificar todos válidos Brainfuck programas, pero no es una enumeración, ya que la mayoría de los números naturales no corresponden a un programa válido.
Para el propósito de este desafío, asuma una cinta doblemente infinita y sin comentarios, es decir, un programa Brainfuck es válido si y solo si consiste únicamente en los caracteres <>+-.,[]
y todos los corchetes izquierdo y derecho coinciden.
Por ejemplo, el programa vacía, ,[+][-].
, [>+<[--].]
y +[+[+][+[+]+]+]+.
son programas Brainfuck válida, mientras que ][
, y a[]
no lo son.
Tarea
Escriba un programa o función que acepte un programa Brainfuck válido como entrada y devuelva un número natural ( 1 , 2 , 3 , ...), con las siguientes restricciones:
La salida generada debe ser diferente para todos los programas válidos de Brainfuck.
Para cada número natural n , debe haber un programa Brainfuck válido que, cuando se proporciona como entrada, genera la salida n .
Reglas adicionales
Dado un programa Brainfuck de 100 o menos bytes, su programa o función debe finalizar en un minuto.
Esto significa que no puede iterar sobre todos los programas válidos de Brainfuck hasta que coincida con la entrada.
Aplican reglas estándar de código de golf .
fuente
Respuestas:
Python 3,
443158155154134131128124117116115 bytesVarios bytes gracias a Sp3000 y Mitch Schwartz: D
Cómo funciona esto:
Esto asigna todos los programas BF válidos a todos los programas BF posibles, válidos o no válidos, que no comienzan con una
[
relación uno a uno. Después de eso, el nuevo programa simplemente se convierte en octal.Aquí está la fórmula de mapeo:
[
caracteres. La tercera parte es el postfix más grande que consta de solo]
caracteres. La segunda parte es el medio.]
corchetes en la tercera parte que coincidan con los[
corchetes en la segunda parte. Estos también pueden ser recalculados más tarde.Si no comprende esta explicación, puede encontrar una explicación extendida en el chat a partir de aquí .
Como referencia, aquí están los primeros 20 programas:
Aquí están los primeros 1000 programas: http://pastebin.com/qykBWhmD
Aquí está el programa que usé para generarlos: http://ideone.com/e8oTVl
Aqui esta
Hello, World!
:fuente
Python 2, 157 bytes
Todavía se ve bastante golfable, pero estoy publicando esto por ahora. Utiliza la recursividad con un poco de almacenamiento en caché. Molesto,
D.get
no hace un corto circuito para el almacenamiento en caché, por lo que no puedo guardar 9 bytes de esa manera ...El mapeo prioriza primero la longitud, luego el orden lexicográfico sobre el orden
"][><.-,+"
(ver ejemplos de salida a continuación). La idea principal es comparar prefijos.La variable
o
realiza un seguimiento del número de[
paréntesis aún abiertos para el prefijo actual, mientras que la variabled
toma uno de los tres valores que indican:d = 1
: El prefijo actual es lexicográficamente anterior as
. Agregue todos los programas con este prefijo y longitud<= s
,d = -1
: El prefijo actual es lexicográficamente posterior as
. Agregue todos los programas con este prefijo y longitud< s
.d = 0
: El prefijo actual es un prefijo des
, por lo que podríamos cambiard
a 1 o -1 más adelante.Por ejemplo, si tenemos
s = "[-]"
y nuestro prefijo actual esp = "+"
, ya quep
es posterior a las
lexicografía, solo sabemos agregar los programas que comienzan con losp
cuales son estrictamente más cortos ques
.Para dar un ejemplo más detallado, supongamos que tenemos un programa de entrada
s = "-[]"
. La primera expansión recursiva hace esto:Nota cómo no utilizan los prefijos en la recursividad - todos nos preocupamos por ellos es capturado a través de las variables
d
,o
y el programa de entrada de la contraccións
. Notarás muchas repeticiones arriba: aquí es donde entra el almacenamiento en caché, lo que nos permite procesar programas de 100 caracteres dentro del límite de tiempo.Cuando
s
está vacío, miramos(d>=0 and o==0)
, que decide si devolver 1 (cuente este programa porque es lexicográficamente temprano / igual y el programa es válido), o 0 (no cuente este programa).Cualquier situación con
o < 0
retornos inmediatos0
, ya que cualquier programa con este prefijo tiene más de]
s[
, y por lo tanto no es válido.Las primeras 20 salidas son:
Usando el mismo ejemplo de Hello World que la respuesta de @ TheNumberOne:
fuente
Python 2, 505 (sin golf)
Disfruté desarrollando este enfoque, pero es posible que no me moleste en jugarlo porque no es competitivo en comparación con otros enfoques. Lo estoy publicando por el bien de la diversidad y el posible interés estético. Implica recursividad y un poco de matemática.
La función
f(n)
cuenta el número de programas válidos de duración de brainfuckn
.h(x)
asigna programas de longitudn
a[0..f(n)-1]
, yg(x)
es la función de clasificación biyectiva en cuestión.La idea principal es que un programa no vacío puede comenzar con
[
o con uno de los 6[]
caracteres no . En el primer caso, podemos iterar sobre las posibles ubicaciones de la coincidencia]
y la recurrencia en la parte cerrada y en la cola (donde cola significa la subcadena que sigue a la]
). En el último caso, podemos recurrir en la cola (donde cola significa soltar el primer carácter). Este razonamiento se puede usar tanto para contar como para calcular el rango.Los programas más cortos siempre tendrán un rango inferior que los programas más largos, y el patrón de paréntesis es un factor determinante secundario. Los no
[]
caracteres se ordenan según "+ - <>,". (que es arbitrario)Por ejemplo con
n=4
tenemos estos casos:donde
z
significa no[]
carácter yx
representa cualquier carácter, bajo la restricción de que]
tiene que coincidir con la inicial[
. Los programas se clasifican según ese orden, y recursivamente en lasx
subsecciones, con la sección izquierda priorizada sobre la sección derecha en los últimos casos. El cálculo del rango es similar a los sistemas de numeración de radix mixtos yf
es importante para calcular la "radix" actual.fuente
Esta respuesta es una prueba formal de la respuesta de TheNumberOne , Enumerar programas Brainf ** k válidos , donde puede ser un poco difícil entender los puntos finos por los que la enumeración es correcta. No es trivial entender por qué no hay algún programa no válido que se asigne a un número no cubierto por un programa válido.
A lo largo de esta respuesta, las mayúsculas se usan para denotar programas, y las variables en minúsculas se usan para funciones y enteros. ~ es el operador de concatenación.
Proposición 1:
Deje que la función f sea el programa descrito en esa respuesta. Entonces, para cada programa U existe un programa válido V tal que f (U) = f (V)
Definición 1:
Supongamos que g (X) sea el número
[
que aparece en el programa X y que h (X) sea el número]
que aparece.Definición 2:
Defina P (x) para que sea esta función:
Definición 3:
Dado un programa X, denote que X1 es su prefijo de
[
caracteres más grande , X2 su centro y X3 su sufijo de]
caracteres más grande .Prueba de proposición 1:
Si g (U) = h (U), entonces U es un programa válido, y podemos tomar V = U. (caso trivial).
Si g (U) <h (U), entonces podemos crear V al anteponer
[
símbolos n = h (U) - g (U) . Obviamente f (V) = f (U) ya que todos los[
símbolos en el prefijo se eliminan.Ahora considere g (U)> h (U). Definir T = U2 ~ U3. si g (T) <= h (T), entonces podemos construir V eliminando los
[
símbolos n = g (U) - h (U) .Entonces podemos suponer que h (T) <g (T). Construir V = T ~ P (g (T) - h (T)).
Necesitamos tres pequeños hechos para proceder:
Reclamación 1: g (U2) = g (T)
U3 no contiene ningún
[
símbolo por su definición. Como T = U2 ~ U3, sus[
símbolos están todos en la primera parte.Reclamación 2: h (U3) <g (T)
Esto se deduce de señalar que h (T) <g (T) y h (U3) <h (U3 ~ U2) = h (T).
Reclamación 3: h (V3) = g (U2) - h (U2)
Ahora mostramos que f (V) = f (U).
Esto completa la prueba. QED
Hagamos también la unicidad.
Proposición 2:
Sea U, V dos programas diferentes y válidos. Entonces f (U)! = F (V)
Esto es bastante sencillo en comparación con la propuesta anterior.
Supongamos que U2 = V2. Pero entonces la única forma de U y V pueden ser diffrent es mediante la adición o la eliminación de n
[
y]
símbolos para U1 y U3, respectivamente. Sin embargo, esto cambia la salida de f, ya que f contará el número de]
símbolos no coincidentes en el sufijo.Por lo tanto, U2! = V2.
Obviamente, esto lleva a una contradicción. Como U2 y V2 están literalmente contenidos en la salida de f (U) yf (V) respectivamente, no pueden diferir, excepto en el 'borde', el lugar donde U2 está concatenado con U3. Pero el primer y último símbolo de U2 y V2 no pueden ser
[
o]
por definición, mientras que esos son los únicos símbolos permitidos en U1, U3, V1, V3, respectivamente, y de nuevo respectivamente. Así obtenemos U2 = V2. QEDfuente