Les bandes circulaires sont-elles passionnantes?

32

Un dérivé de Brainfuck

Définissons un langage de programmation simple de type Brainfuck . Il a une bande de cellules bidirectionnelle et chaque cellule contient un bit. Tous les bits sont initialement 0. Il y a une tête mobile sur la bande, initialement à la position 0. Un programme est une chaîne sur les caractères <>01!, exécutée de gauche à droite, avec la sémantique suivante:

  • < déplace la tête d'un pas vers la gauche.
  • > déplace la tête d'un pas vers la droite.
  • 0 met 0 dans la cellule courante.
  • 1 met 1 dans la cellule courante.
  • ! retourne la cellule actuelle.

Il n'y a pas de boucles, donc un programme de n caractères se termine après exactement n étapes. Un programme est ennuyeux si toutes les cellules contiennent 0 à la fin de l'exécution et excitant s'il y en a au moins un. circulaire.

Un exemple de programme

Considérez le programme 1>>>!<<<<0>!>>>!. Sur une bande infinie, l'exécution se déroule comme suit:

     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

À la fin, toutes les cellules sont à 0, donc ce programme est ennuyeux. Maintenant, exécutons le même programme sur une bande circulaire de longueur 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

Cette fois, il y a une cellule de valeur 1, donc le programme est passionnant! Nous voyons que si un programme est ennuyeux ou excitant dépend de la taille de la bande.

La tâche

Votre entrée est une chaîne non vide <>01!qui représente un programme dans le langage de programmation ci-dessus. Un tableau de caractères est également un format d'entrée acceptable. Le programme est garanti d'être ennuyeux lorsqu'il est exécuté sur une bande infinie. Votre sortie sera la liste des longueurs de bande sur lesquelles le programme est passionnant. Notez que vous devez uniquement tester le programme sur des bandes plus courtes que la longueur du programme.

La solution avec le nombre d'octets le plus bas dans chaque langue est la gagnante. Les règles de standard s'appliquent.

Cas de test

> : []
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
la source
1
Pouvons-nous choisir des caractères distincts et cohérents au lieu de <>01!?
M. Xcoder
1
Un tableau d'instructions est-il une entrée acceptable?
Arnauld
@ Mr.Xcoder Non, vous devez utiliser ces caractères exacts.
Zgarb
@Arnauld Un tableau de caractères est assez proche d'une chaîne, je vais le permettre.
Zgarb

Réponses:

6

Haskell, 119 octets

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]

Essayez-le en ligne!

La fonction #est l'interpréteur d'une seule commande c. L'ensemble du programme pest exécuté en folding #avec la bande de départ dans p. fs'exécute ppour chaque bande et conserve celles où la somme des cellules est d'au moins 1.

nimi
la source
n<-[1..length p] ... 0<$[1..n]semble assez long, il doit y avoir un chemin plus court.
nimi
Je ne peux pas voir un chemin plus court. Le problème que je vois est que vous avez réellement besoin de la valeur de ncomme résultat, donc si vous avez construit 0<$[1..n]une manière différente (par exemple avec scanr(:)), vous devez en prendre length. (J'ai également essayé d'utiliser 1(à remplacer lengthpar sum) ou False(à utiliser orpour le test) au lieu de 0, mais cela n'a pas été plus court.)
Ørjan Johansen
@ ØrjanJohansen: oui, j'ai essayé n<-init$scanr(:)[]$0<$p ... nce qui est plus court de 2 octets, mais il retourne une liste de bandes de départ au lieu de leur longueur, par exemple [[0],[0,0,0]]. Avec un peu de flexion des règles, les bandes peuvent être considérées comme des nombres unaires, alors peut-être que ça va.
nimi
init$peut être remplacé en mettant une [0]liste initiale, mais elle n'est toujours pas assez courte. Je pense que l'unaire n'est autorisé que pour les langues sans représentation plus naturelle des nombres .
Ørjan Johansen
4

Stax , 56 54 43 38 35 octets CP437

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

42 octets une fois déballés,

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

Exécutez et déboguez en ligne!

-2 octets par commentaire de @recursive

Explication

J'utiliserai la version avec un préfixe i(ie i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a) pour expliquer et j'expliquerai pourquoi le ipeut être supprimé

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

Code pour exécuter le programme:

{|(}                                 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
la source
1
J'ai ajouté un cas de test de tous les chiffres pour valider votre ichèque.
Zgarb
0]*peut être remplacé par z(. De plus, si vous changez la chaîne en "<>!", Alors 0et 1donnera l'index -1, de sorte que votre liste de blocs n'a besoin que de 4 blocs, au lieu de 5. Cela fonctionnera puisque les gestionnaires 0et 1sont de toute façon identiques.
récursif le
@recursive Bon point pris.
Weijun Zhou
2

Rouge , 243 octets

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]]]

Essayez-le en ligne!

Mise en œuvre simple et verbeuse. L'indexation 1 de Red ne me permet pas de réduire le nombre d'octets en utilisant l'arithmétique modulaire pour parcourir les bandes circulaires.

Ungolfed

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
la source
2

Python 2 , 139 135 133 132 131 131 octets

-3 octets grâce à M. 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)

Essayez-le en ligne!

Barre
la source
131 octets?
M. Xcoder
2

Rétine , 121 octets

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

Essayez-le en ligne! Explication:

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

Créez un tableau de bandes de chaque longueur jusqu'à la longueur du programme d'entrée.

{

Boucle jusqu'à ce que le programme soit consommé.

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

Si le caractère suivant du programme est 0 ou 1, remplacez le premier caractère de chaque ligne par ce caractère.

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

Si c'est un, !basculez le premier caractère sur chaque ligne.

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

S'il s'agit d'un >ou <alors faites pivoter la ligne. (Plus facile que de bouger la tête.)

)`¶¶.
¶¶

Supprimez l'instruction et terminez la boucle.

G`1

Ne gardez que les lignes excitantes.

%`.

Comptez la longueur de chaque ligne.

Neil
la source
2

JavaScript (ES6), 126 118 octets

Sauvegardé 3 octets grâce à @ user71546

Prend l'entrée comme un tableau de chaînes de 1 caractère.

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):[]

Essayez-le en ligne!

Arnauld
la source
En remplaçant t.some(x=>x)?par à la +t.join``?place, vérifiez le tableau sous forme de chiffres (et 0 indique une bande entièrement nulle), mais 3 octets de moins.
Shieru Asakoto
2

APL (Dyalog Unicode) , 79 64 54 octets ( SBCS d'Adám )

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

Essayez-le en ligne!

-15 merci à Adám (oublié monadique ).
-10 grâce à ngn .

Erik le golfeur
la source
64
Adám
@ Adám Hm, on dirait que ce n'est pas optimal (par exemple, vous n'avez pas besoin de ). Je vais l'examiner et mettre à jour. :)
Erik the Outgolfer
Mais si vous supprimez le, vous aurez besoin d'un ;, non?
2018
@ Adám non , pourquoi le feriez-vous?
Erik the Outgolfer
1

MATL , 46 39 octets

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

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Comment ça marche

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
la source
1

APL (Dyalog Unicode) , 192 78 octets

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

Essayez-le en ligne! (résultat non aplati)

Essayez-le en ligne! (aplati)

Après un certain temps passé à me cogner la tête contre le mur, j'ai décidé de faire un Tradfn au lieu d'un Dfn. Voilà le résultat. Des gens plus intelligents que moi pourront peut-être jouer au diable.

Surprise, surprise, quelqu'un de plus intelligent que moi a joué au golf. Merci Adám pour 114 octets.

Il a dit:

Notez qu'il s'agit de votre programme exact, sauf en utilisant l'indexation au lieu de l'intérieur: Ifs et collapsing: For-loops to {_} ¨ tout en donnant un argument de gauche pour remplacer le global.

La fonction suppose ⎕IO←0.


Comment?

(Cette explication utilise une version "non golfée" pour faciliter la lecture)

⊂{                                   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é
la source
1
Enregistrez un octet en faisant t←l⍴0be t←l⍴i←0et en supprimant la ligne au-dessus. Vous pouvez également en enregistrer un autre en remplaçant t[i|⍨≢t]←1-t[i|⍨≢t]par t[i|⍨≢t]←~t[i|⍨≢t].
Zacharý
2
@ Zacharý à droite, et économisez encore 112 octets supplémentaires . Exactement le même code, juste un peu joué au golf.
2018 à
Ouais, c'est juste gol "un peu". Vous n'avez pas besoin du s?
Zacharý
@ Zacharý Qu'est-ce que c'est ? C'est une fonction tacite.
2018
@ Zacharý Je considérerais celle-ci plutôt jolie, n'est-ce pas?
J.Sallé
0

C (clang) , 171 octets

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);}

Essayez-le en ligne!

J'ai dû utiliser clang, car l'utilisation char*p,t[l=strlen(S)]comme expression d'initialisation pour une raison quelconque fait penser à GCC que je veux déclarer strlenau lieu de l'appeler.

Assez simple: exécute le programme sur des bandes circulaires de longueur décroissante, produisant n'importe quelle longueur qui a entraîné un 1 quelque part sur la bande.

Essayé de raccourcir l'enchevêtrement des opérateurs ternaires, mais a fini par avoir besoin de plus de parenthèses que ce qui était sain.

gastropner
la source
Suggérer i=0,bzero(t,l)au lieu de memset(t,i=0,l)et *p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0)au lieu de*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1)
plafondcat