¿Son emocionantes las cintas circulares?

32

Un derivado de Brainfuck

Definamos un lenguaje de programación simple similar a Brainfuck . Tiene una cinta de celdas bidireccional, y cada celda contiene un bit. Todos los bits son inicialmente 0. Hay una cabeza móvil en la cinta, inicialmente en la posición 0. Un programa es una cadena sobre los caracteres <>01!, ejecutada de izquierda a derecha, con la siguiente semántica:

  • < mueve la cabeza un paso hacia la izquierda.
  • > mueve la cabeza un paso hacia la derecha.
  • 0 pone 0 en la celda actual.
  • 1 pone 1 en la celda actual.
  • ! voltea la celda actual.

No hay bucles, por lo que un programa de n caracteres termina después de exactamente n pasos. Un programa es aburrido si todas las celdas contienen 0 al final de la ejecución, y emocionante si hay al menos uno 1. Tenga en cuenta que el tamaño de la cinta no está especificado, por lo que, dependiendo de la implementación, puede ser bidireccional infinito o circular.

Un programa de ejemplo

Considera el programa 1>>>!<<<<0>!>>>!. En una cinta infinita, la ejecución se realiza de la siguiente manera:

     v
00000000000000  Put 1
     v
00000100000000  Move by >>>
        v
00000100000000  Flip
        v
00000100100000  Move by <<<<
    v
00000100100000  Put 0
    v
00000100100000  Move by >
     v
00000100100000  Flip
     v
00000000100000  Move by >>>
        v
00000000100000  Flip
        v
00000000000000

Al final, todas las celdas son 0, por lo que este programa es aburrido. Ahora, ejecutemos el mismo programa en una cinta circular de longitud 4.

v
0000  Put 1
v
1000  Move by >>>
   v
1000  Flip
   v
1001  Move by <<<< (wrapping around at the edge)
   v
1001  Put 0
   v
1000  Move by > (wrapping back)
v
1000  Flip
v
0000  Move by >>>
   v
0000  Flip
   v
0001

Esta vez, hay una celda con valor 1, ¡así que el programa es emocionante! Vemos que si un programa es aburrido o emocionante depende del tamaño de la cinta.

La tarea

Su entrada es una cadena no vacía <>01!que representa un programa en el lenguaje de programación anterior. Una matriz de caracteres también es un formato de entrada aceptable. Se garantiza que el programa será aburrido cuando se ejecuta en una cinta infinita. Su salida será la lista de longitudes de cinta en las que el programa es emocionante. Tenga en cuenta que solo necesita probar el programa en cintas que son más cortas que la longitud del programa.

La solución con el recuento de bytes más bajo en cada idioma es la ganadora. Aplican reglas estándar de .

Casos de prueba

> : []
110 : []
1>0<! : [1]
0>>1>0<<>! : [1]
1>>>!<<<<0>!>>>! : [2, 4]
!<!<><<0>!>!<><1!>>0 : [2]
>>!>><>001>0<1!<<!>< : [1, 2, 3]
1!><<!<<<!!100><>>>! : [1, 3]
!!1>!>11!1>>0<1!0<!<1><!0<!<0> : [3, 4]
<><<>>!<!!<<<!0!!!><<>0>>>>!>> : [1, 2, 4]
0>>><!<1><<<0>!>>!<<!!00>!<>!0 : [3]
0000!!!!><1<><>>0<1><<><<>>!<< : []
!>!>!>!>!>1>!>0<!<!<!<0<!<0<!<!<!<1>!>0<<! : [1, 2, 5, 7]
<!!>!!><<1<>>>!0>>>0!<!>1!<1!!><<>><0<<!>><<!<<!>< : [1, 2, 4, 5]
!>1<<11<1>!>!1!>>>0!!>!><!!00<><<<0<<>0<<!<<<>>!!> : [1, 2, 3, 5, 6]
Zgarb
fuente
1
¿Podemos elegir personajes distintos y consistentes en lugar de <>01!?
Sr. Xcoder
1
¿Es una matriz de instrucciones una entrada aceptable?
Arnauld
@ Mr.Xcoder No, debe usar estos caracteres exactos.
Zgarb
@Arnauld Una matriz de caracteres está lo suficientemente cerca de una cadena, lo permitiré.
Zgarb

Respuestas:

6

Haskell, 119 bytes

t#'<'=last t:init t
(h:t)#c|c<'#'=1-h:t|c>'='=t++[h]|1<2=read[c]:t
f p=[n|n<-[1..length p],sum(foldl(#)(0<$[1..n])p)>0]

Pruébalo en línea!

La función #es el intérprete para un solo comando c. Todo el programa pse ejecuta folding #con la cinta de inicio en p. fse ejecuta ppara cada cinta y mantiene aquellas donde la suma de las celdas es al menos 1.

nimi
fuente
n<-[1..length p] ... 0<$[1..n]parece bastante largo, debe haber un camino más corto.
nimi
No puedo ver un camino más corto. El problema que veo es que realmente necesitas el valor de ncomo resultado, por lo que si construiste 0<$[1..n]una forma diferente (digamos con scanr(:)), deberías tomarla length. (También intentado usar 1(para reemplazar lengtha sum) o False(para usar orpara la prueba) en vez de 0, pero no salió más corta.)
Ørjan Johansen
@ ØrjanJohansen: sí, intenté n<-init$scanr(:)[]$0<$p ... nque es 2 bytes más corto, pero devuelve una lista de cintas de inicio en lugar de su longitud, por ejemplo [[0],[0,0,0]]. Con un poco de flexión de reglas, podría ver las cintas como números unarios, así que tal vez esté bien.
nimi
init$se puede reemplazar poniendo una [0]lista inicial, pero aún así no se acortó lo suficiente. Creo que el unario solo está permitido para idiomas sin una representación numérica más natural .
Ørjan Johansen
4

Stax , 56 54 43 38 35 bytes CP437

è¥%►BΣ░ÜY⌂y(â&.═ªê►V½▲y▌)▀♫♂╣ª?√»!#

42 bytes cuando está desempaquetado,

%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a

¡Ejecute y depure en línea!

-2 bytes por comentario por @recursive

Explicación

Usaré la versión con un prefijo i(es decir i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a) para explicar y explicaré por qué ise puede eliminar

i               Suppress implicit eval
                    This prevents the test case "110" from being interpreted as a number
                    However, this can be removed because a program containing only numbers cannot be exciting and the output will be empty anyway.
                    This is based on the fact that the program is boring on non-circular tapes
 %f             Filter range [1..n] with the rest of this program
                    Where n is the length of the input
                    Implicit output the array after filtering, one element per line
   z(           Initialize the tape
     y{  F      Run the program
          |a    Any cell is non-zero

Código para ejecutar el programa:

{|(}                                 Block to rotate left by one element
    {|)}                             Block to rotate right by one element
        {B!s+}                       Block to perform logical not on the element at index 0
              {0_]e&}                Block to obtain current instruction,
                                         Convert it to a number
                                         And assign to element at index 0

                     4l              Pack the 4 blocks in an array
                       s"<>! "I      Find the index of current instruction in string, if not found, the index will be -1
                                         And when indexed with -1, it wraps around to the 4th element.

                               @!    And execute the corresponding block.
Weijun Zhou
fuente
1
Agregué un caso de prueba de todos los dígitos para validar su icheque.
Zgarb
0]*puede ser reemplazado con z(. Además, si se cambia la cadena en "<>!", A continuación, 0y 1dará índice de -1, por lo que la forma en la lista de bloqueo sólo necesita 4 cuadras, en lugar de 5. Esto funciona ya que las 0y 1los controladores son de todas formas idénticas.
recursivo
@recursivo Buen punto tomado.
Weijun Zhou
2

Perl 5 ( -F), 101 bytes

map{$,=@a=(0)x$_;map{$,+=/>/-/</;$a[$,%@a]=$&if/0|1/;$a[$,%@a]=!$a[$,%@a]if/!/}@F;say if@a~~/1/}1..@F

Pruébalo en línea!

Xcali
fuente
2

Rojo , 243 bytes

func[p][repeat n length? p[b: copy[]insert/dup b 0 n i: 1
parse p[any["<"(i: i - 1 if i < 1[i: n])|">"(i: i + 1 if i > n[i: 1])|"0"(b/(i): 0)|"1"(b/(i): 1)|"!"(b/(i): either b/(i) = 0[1][0])|
skip]]s: 0 foreach c b[s: s + c]if s > 0[print n]]]

Pruébalo en línea!

Prety implementación detallada y sencilla. La indexación 1 de Red no me permite reducir el recuento de bytes mediante el uso de la aritmética modular para recorrer las cintas circulares.

Sin golf

f: func[p][ 
    repeat n length? p[
        b: [] 
        insert/dup b 0 n
        i: 1
        parse p[
            some [
                 "<" (i: i - 1 if i < 1[i: n])
               | ">" (i: i + 1 if i > n[i: 1])
               | "0" (b/(i): 0)
               | "1" (b/(i): 1)
               | "!" (b/(i): either b/(i) = 0 [1][0])
               | skip 
            ]
        ]
        s: 0
        foreach c b[s: s + c]
        if s > 0 [print n]
    ]
]
Galen Ivanov
fuente
2

Python 2 , 139 135 133 132 131 bytes

-3 bytes gracias al Sr. Xcoder

def f(p):i=0;exec"i+=1;s=[0]*i\nfor c in p:c=ord(c)-61;s=c>-2and s[c:]+s[:c]or[[s.pop(0)^1,0,1][c%7]]+s\nif 1in s:print i\n"*len(p)

Pruébalo en línea!

Barra
fuente
131 bytes?
Sr. Xcoder
2

Retina , 121 bytes

.+
$.&*0¶$&
\G0
0$`¶
{ms`^.(?=.*¶¶(0|1))
$1
"¶¶!"&mT`d`10`^.
"¶¶>"&`(.)(.*)¶
$2$1¶
"¶¶<"&`(.*)(.)¶
$2$1¶
)`¶¶.
¶¶
G`1
%`.

Pruébalo en línea! Explicación:

.+
$.&*0¶$&
\G0
0$`¶

Cree una matriz de cintas de cada longitud hasta la longitud del programa de entrada.

{

Bucle hasta que se consuma el programa.

ms`^.(?=.*¶¶(0|1))
$1

Si el siguiente carácter en el programa es un 0 o 1, cambie el primer carácter en cada línea a ese carácter.

"¶¶!"&mT`d`10`^.

Si es un, !entonces alternar el primer carácter en cada línea.

"¶¶>"&`(.)(.*)¶
$2$1¶
"¶¶<"&`(.*)(.)¶
$2$1¶

Si es un >o, <luego gire la línea. (Más fácil que mover la cabeza).

)`¶¶.
¶¶

Elimine la instrucción y finalice el ciclo.

G`1

Mantenga solo las líneas emocionantes.

%`.

Cuenta la longitud de cada línea.

Neil
fuente
2

JavaScript (ES6), 126 118 bytes

Guardado 3 bytes gracias a @ user71546

Toma la entrada como una matriz de cadenas de 1 carácter.

f=(s,l=0,p=0,t=[])=>s[l++]?s.map(c=>1/c?t[p%l]=+c:c>'='?p++:c>';'?p+=l-1:t[p%l]^=1)&&+t.join``?[l,...f(s,l)]:f(s,l):[]

Pruébalo en línea!

Arnauld
fuente
Sustituyendo t.some(x=>x)?en su +t.join``?lugar, verifique la matriz como dígitos (y 0 indica una cinta completamente cero), pero 3 bytes menos.
Shieru Asakoto
2

APL (Dyalog Unicode) , 79 64 54 bytes ( SBCS de Adám )

⍸⊂{∨/⍎⍕(↓',',⍨5 3'0@11@1~@1 1⌽¯1⌽')['01!<'⍳⌽⍺]⍵}¨0=,\

Pruébalo en línea!

-15 gracias a Adám (se olvidó de lo monádico ).
-10 gracias a ngn .

Erik el Outgolfer
fuente
64
Adám
@ Adám Hm, parece que eso no es óptimo (por ejemplo, no necesita ). Lo investigaré y actualizaré. :)
Erik the Outgolfer
Pero si quita el necesitará un ;, ¿no?
Adám
@ Adám no , ¿por qué lo harías?
Erik the Outgolfer
1

MATL , 46 39 bytes

f"@:~G"@59>?@61-YS}@33=?t1)~}@U]1(]]a?@

Pruébalo en línea! O verificar todos los casos de prueba .

Cómo funciona

f             % Push indices of nonzero chars of (implicit) input string: gives
              % [1 2 ... n] where n is input length
"             % For each k in [1 2 ... n]. These are the possible tape lengths
  @:~         %   Push array of k zeros. This is the tape, in its initial state
  G           %   Push input string
  "           %   For each char in the input string
    @59>?     %     If code point of current char exceeds 59 (so it is '<' or '>')
      @61-    %       Push code point minus 61: gives -1 for '<', or 1 for '>'
      YS      %       Circularly shift the tape by that amount. Instead of moving
              %       the head, we shift the tape and keep the head at entry 1
    }         %     Else
      @33=?   %       If code point of current char is 33 (so it is '!')
        t1)   %         Duplicate the array representing the tape, and get its
              %         first entry
        ~     %         Logical negate
      }       %       Else
        @U    %         Push current char (it is '0' or '1') converted to number
      ]       %       End
      1(      %       Write (either 0, 1 or old value negated) at entry 1
    ]         %     End
  ]           %   End
  a?          %   If the tape contains at least a nonzero value
    @         %     Push tape length, k
              %   End (implicit)
              % End (implicit)
              % Display (implicit)
Luis Mendo
fuente
1

APL (Dyalog Unicode) , 192 78 bytes

⊂{t/⍵⊣⍵{t[m]←('01!'⍳⍵)⊃0 1,e,⍨~et[m←⍺|ii+←¯1 1 0⊃⍨'<>'⍳⍵]}¨⍺⊣i←⊃t←⍬⍳⍺}¨1+⍳∘≢

Pruébalo en línea! (resultado no aplanado)

Pruébalo en línea! (aplanado)

Después de pasar algún tiempo golpeando mi cabeza contra la pared, decidí hacer un Tradfn en lugar de un Dfn. Este es el resultado. Las personas más inteligentes que yo pueden jugar al golf.

Sorpresa, sorpresa, alguien más inteligente que yo hice campo de los diablos de esto. Gracias Adám por 114 bytes.

Él dijo:

Tenga en cuenta que es su programa exacto, excepto que usa la indexación en lugar del interno: Ifs y colapso: For-loops a {_} ¨ mientras da un argumento izquierdo para reemplazar el global.

La función asume ⎕IO←0.


¿Cómo?

(Esta explicación utiliza una versión "sin golf" para facilitar la lectura)

⊂{                                   Enclose
      i←⊃t←⍬⍳⍺                       Assign a vector of 0s to t (the tape), then assign the first 0 to i.
      t/⍵⊣⍵{                         Use  as left argument for the nested function, then compress the result into t. If there is a 1 anywhere in t, the result will be a vector of the result. If not, the result is an empty vector.
          i+←¯1 1 0⊃⍨'<>'⍳⍵          Map the string '<>' to the argument (which is the BF program). That yields 0 for <, 1 for >, and 2 for anything else.
                                     The resulting vector will then be used as the argument for  to add -1 (index 0), 1 (index 1) or 0 (index 2) to the variable i.
          et[m←⍺|i]                 Assign i mod  (left arg) to m, and use it to index t. Then, assign the value to e.
          t[m]←('01!'⍳⍵)⊃0 1,e,⍨~e   Map the string '01!' to ⍵. As before, this yields 0 for 0, 1 for 1, 2 for ! and 3 for anything else.
                                     Then, concatenate (not e) with e, then concatenate that with the vector 0 1. This is used as argument to be picked from, and it is assigned to t[m].
      }¨⍺                            Do that for each argument
  1+⍳∘≢                            And do that for each possible tape length from 1 to the length of the input.
J. Sallé
fuente
1
Ahorre un byte haciendo t←l⍴0be t←l⍴i←0y eliminando la línea que se encuentra sobre él. También puede guardar otro cambiando t[i|⍨≢t]←1-t[i|⍨≢t]a t[i|⍨≢t]←~t[i|⍨≢t].
Zacharý
2
@ Zacharý a la derecha, y además guarda 112 bytes adicionales . Exactamente el mismo código, solo jugué un poco.
Adám
Sí, es solo un poco "un poco". ¿No necesitas el s?
Zacharý
@ Zacharý ¿Qué s? Es una función tácita.
Adám
@ Zacharý Consideraría que esta es una bonita Adám'd, ¿verdad?
J. Sallé
0

C (clang) , 171 bytes

l,i;f(S){for(char*p,t[l=strlen(S)];l;memchr(t,1,l)&&printf("%d ",l),l--)for(memset(t,i=0,l),p=S;*p;p++)*p==60?i=i?i-1:l-1:*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1);}

Pruébalo en línea!

Tuve que usar clang, ya que usarlo char*p,t[l=strlen(S)]como la expresión de inicialización por alguna razón hace que GCC piense que quiero declarar en strlenlugar de llamarlo.

Bastante sencillo: ejecuta el programa en cintas circulares de longitud decreciente, generando cualquier longitud que resulte en un 1 en algún lugar de la cinta.

Intenté acortar la maraña de los operadores ternarios, pero terminé necesitando más paréntesis de los sanos.

gastropner
fuente
Sugerir en i=0,bzero(t,l)lugar de memset(t,i=0,l)y en *p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0)lugar de*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1)
ceilingcat