Ayons une fonction qui prend une chaîne et supprime toutes les paires de caractères identiques adjacents. Par exemple$f$

$f(a\color{red}{bb}ba\color{red}{cc}) = aba$

Notez que lorsque deux paires se chevauchent, nous n'en supprimons qu'une seule.

Nous appellerons une chaîne parfaitement appariée si une application répétée donne finalement la chaîne vide. Par exemple, la chaîne au-dessus de n'est pas parfaitement appariée car si nous appliquons à nouveau , nous obtenons toujours . Cependant, une chaîne comme est parfaitement appariée car si nous appliquons trois fois, nous obtenons la chaîne videf a b a e a b b c c a d d e $abbbacc$$f$$aba$$eabbccadde$$f$

$f(ea\color{red}{bbcc}a\color{red}{dd}e) = eaae$

$f(e\color{red}{aa}e) = ee$

$f(\color{red}{ee}) =$

Votre tâche consiste à écrire un code informatique parfaitement couplé qui prend une chaîne (ASCII imprimable) et décide s'il est parfaitement couplé. Le bytestring de votre source doit être lui-même une chaîne parfaitement appariée , bien que votre code ne doive pas nécessairement être limité à ASCII imprimable.

Vous pouvez générer deux valeurs distinctes: une pour le cas où l'entrée est parfaitement appariée et une autre pour les cas où elle ne l'est pas.

Il s'agit d'une question de code-golf, donc les réponses seront notées en fonction de la taille en octets de leur source, moins d'octets étant meilleurs.

Cas de test

$abbbacc \rightarrow \mathrm{False}\\ abcba \rightarrow \mathrm{False}\\ abab \rightarrow \mathrm{False}\\ abbbaabacc \rightarrow \mathrm{True}\\ eabbccadde \rightarrow \mathrm{True}\\ bbbb \rightarrow \mathrm{True}$

Haskell, 146 124 octets

((""##))
a===bb=bb==a
((aa:bb))##((cc:dd))|aa===cc=bb##dd|1==1=((cc:aa:bb))##dd
a##""=""===a
""##cc=((cc!!00:cc!!00:""))##cc

Sans commentaires. Renvoie soit Trueou False.

Essayez-le en ligne!

Edit: -22 octets grâce à @Cat Wizard

Python 2 , 94 octets

ss=''

for cc in input():ss=[cc+ss,ss[1:]][cc==ss[:1]]

print''==ss##tnirp[,+[=:)(tupni nirof=

Essayez-le en ligne!

L'étape de mise à jour entière ss=[cc+ss,ss[1:]][cc==ss[:1]]s'annule juste =[+,[.

05AB1E , 26 24 22 20 18 octets

-2 octets grâce aux ovs . Renvoie 0 si la chaîne est parfaitement appariée, 1 sinon.

ΔγʒgÉ}JJ}ĀqqĀÉgʒγΔ

Essayez-le en ligne!

ΔγʒgÉ} JJ} ĀqqĀÉgʒγΔ - Programme complet.
Δ} - Jusqu'à ce que le résultat ne change plus:
 γʒ} - Divisez la chaîne en morceaux de caractères égaux et filtrez par:
   gÉ - La longueur est-elle étrange?
      JJ - Et après le filtrage, réunissez les pièces, mais faites-le
                     deux fois pour économiser 2 octets, comme dans les versions précédentes.
         Ā - Vérifiez si le résultat est vide
          q - Terminer (quitter) l'exécution. Le reste du code est ignoré.
           qĀÉgʒγΔ - Refléter la partie non appariée pour aider à la mise en page source.

Versions précédentes

Celui-ci repose uniquement sur un comportement indéfini (il n'y a donc pas de "code mort"), et génère [['0']] pour les chaînes parfaitement appariées et [['1']] pour les chaînes non parfaitement adaptées:

ΔγεDgÉ£}JJ}ĀĀ£ÉgDεγΔ 

Et la version de 22 octets, expliquée, qui est juste ce qui précède mais n'abuse pas de l'UB et donne des valeurs sensées .

ΔγεDgÉ£}JJ}ĀqqĀ£ÉgDεγΔ – Full program.
Δ         }            – Until fixed point is reached (starting from the input value):
 γε    }                 – Group equal adjacent values, and for each chunk,
   DgÉ                     – Duplicate, get its length mod by 2.
      £                    – And get the first ^ characters of it. This yields the
                             first char of the chunk or "" respectively for odd-length
                             and even-length chunks respectively.
         JJ                – Join the result to a string, but do this twice to help
                             us with the source layout, saving 2 bytes.
            Ā           – Check if the result is an empty string.
             q          – Terminate the execution. Any other commands are ignored.
              qĀ£ÉgDεγΔ – Mirror the part of the program that isn't otherwise removed
                          anyways. This part forgoes }JJ} because that substring will
                          always be trimmed by the algorithm anyway.

Cubix , 54 octets

U#;[email protected]>??>i..??O.@1^^...u--u.u!ww;..#..U..;..;!^^!

Ne produit rien si la chaîne est parfaitement appariée et 1sinon.
Essayez-le ici

Cubifié

      U # ;
      ! u 1
      @ . O
i > ? ? > i . . ? ? O .
@ 1 ^ ^ . . . u - - u .
u ! w w ; . . # . . U .
      . ; .
      . ; !
      ^ ^ !

Explication

La plupart des caractères sont nécessaires pour coupler parfaitement le code. En remplaçant ceux par .(no-op), nous obtenons

      U # ;
      ! u 1
      @ . O
i . ? . > i . . ? . . .
. . ^ . . . . u - . . .
. . . w ; . . . . . . .
      . ; .
      . ; !
      ^ ^ !

Cela peut être divisé en trois étapes:

• Vérifiez la chaîne vide (la gauche iet la ?).
• Boucle, jetant des personnages sur la pile et faisant apparaître des doublons (tout en bas et à droite).
• Vérifiez si la pile est vide (le truc en haut).

V , 20 , 18 octets

òóˆ±òø‚

::‚øò±ˆóò

Essayez-le en ligne!

Hexdump:

00000000: f2f3 88b1 f2f8 820a 0a3a 3a82 f8f2 b188  .........::.....
00000010: f3f2                                     ..                   ....

Sorties 0 pour vérité, 1 pour fausse. Merci à nmjcman101 pour avoir économisé indirectement 2 octets.

ò        ò        " Recursively...
 ó                "   Remove...
  <0x88>          "     Any printable ASCII character
        ±         "     Followed by itself
          ø       " Count...
           <0x82> "   The number of non-empty strings

::<0x82>øò±<0x88>óò      " NOP to ensure that the code is paired

R , 142 126 octets

Logique plus stricte et quelques octets de commentaires golfés par @Giuseppe

f=function(x,p="(.)\\1")"if"(grepl(p,x),f(sub(p,"",x)),!nchar(x))##x(rahcn!,x,,p(bus(f,)x,p(lperg("fi")"1\\).("=p,x(noitcnuf=f

Essayez-le en ligne!

f=function(x,p="(.)\\1")"if"(nchar(x),"if"(grepl(p,x),f(sub(p,"",x)),0),1)##)1,)0,xp(bus(f,)x,p(lperg("fi",)x(rahcn("fi")"1).("=p,x(noitcnuf=f

Original:

Essayez-le en ligne!

Fonction détecteur récursif suivie d'un commentaire avec tous les caractères de la fonction dans l'ordre inverse.

APL (Dyalog) , 38 octets

''≡{'(.)\1'⎕R''⊢⍵}⍣≡⍝⍝≡⍣}⍵⊢R⎕'1\).('{≡

Essayez-le en ligne!

Rétine , 28 26 octets

+`(.)\1

C`^$

$^`C1\).(`+

Essayez-le en ligne!

Sorties `C1\).(`+0`C1\).(`+pour fausse et `C1\).(`+1`C1\).(`+pour cas véridiques.

Brain-Flak , 228 200 octets

(()){{{}([]<<{{(({}<<>>)<<>>[({})]){{{{}(<<<<>>()>>)((<<>>))}}}{}{}<<>>{}<<>>}}{}<<>>>>[[]])}}{}(<<({{(())(<<()>>)}}<<>>)>>){{{{}{}}((){{}{}{}{}{}}(()())())[[]((){{}{}}())[]]((){{}{}}[[][]]()){{}{}}}}

Essayez-le en ligne!

C'est un peu une preuve de concept. Cela pourrait probablement être plus court. Il n'utilise cependant aucun commentaire.

Sorties 0,0si l'entrée est parfaitement appariée et 0,1si l'entrée ne l'est pas.

sed 4.2.2 , 34 octets

:;:t;ss((..??\??))\1ss1;t;/..??/cc

Essayez-le en ligne!

Les chaînes appariées donnent une sortie vide, celles non appariées donnent ct:

La version palindromique triviale est à 32 :;ss(.)\1ss;t;/./cc/./;t;1\).(;:. L'ancienne solution a été :;ss((..??\??))\1ss1;t;;/./cc/./t:(modifiée parce que la version actuelle est cmoins utilisée , edit: yay maintenant il n'y a qu'un seul caractère après c: D)

(notez qu'il ;s'agit du séparateur d'instructions)

: déclare une étiquette vide

:t déclare l'étiquette t

ss((..??\??))\1ss1est une substitution, dans sed, vous pouvez changer le délimiteur en une substitution, et c'est ce que j'ai fait en le changeant s, donc ce que cela fait est de remplacer le premier (comme indiqué par le 1à la fin)

• match de ((..??\??))\1

  • . n'importe quel personnage
  • .?? suivi d'un caractère facultatif facultatif
  • \?? et une option ?
  • suivi de la même chose juste à côté

• avec rien

Maintenant, cette substitution est associée à elle-même, donc les ;s avant et après sont également annulés

t et retournez sur l'étiquette jusqu'à ce qu'il n'y ait plus de substitutions réussies

/..?/si .(caractère générique) suivi d' .?un caractère facultatif correspond

• cc changer le tampon en c

Brain-Flak , 112 110 108 octets

(()){{}({<<(({}<<>>)<<>>[({})]){{((<<>>)<<>>)}}{}{##{

}<<>>>>{}<<>>}<<>>)}{}((){{<<>>[[]]}})##}{}])}{([)}(}

Essayez-le en ligne!

Ceci est basé sur ma réponse de Est-ce que les crochets correspondent? .

J'ai essayé de ne pas utiliser de commentaires, mais je suis resté coincé en essayant de faire la {}paire de nilades pop ( ). Le problème réside dans la façon la plus simple de coupler une paire de supports est de l'entourer dans une autre paire du même type. Bien que cela soit facile pour les autres nilades, la {...}monade crée des boucles. Pour quitter la boucle, vous devez appuyer sur un 0, mais une fois que vous avez quitté la boucle, vous devez ensuite faire apparaître le 0, ce qui aggrave le problème.

La solution pré-appariée de 66 octets est:

(()){{}({<(({}<>)<>[({})]){((<>)<>)}{}{}<>>{}<>}<>)}{}((){<>[[]]})

Essayez-le en ligne!

Sorties 1ou 1,0si l'entrée est un appariement parfait, 0,0sinon.

Version sans commentaire, 156 octets

(()){{{}({<<(({}<<>>)<<>>[({{}((<<[[]]>>)){}}{}(<<[]>>){{}{}}{})]){{((<<>>)<<>>)}}{{}{}{}}{}{}<<>>>>{}<<>>}<<>>)}}{{}{}}{}((){<<>>[[]]})(<<()()>>){{}{}{}}{}

Essayez-le en ligne!

Comme l'a souligné Cat Wizard, la première réponse ne fonctionne pas pour tous les interprètes, car tous ne gèrent pas les #commentaires. Cette version ne contient aucun commentaire.

Japt, 24 22 octets

Sorties falsepour véridique et truepour falsey.

&&!!e"(.)%1"PP"1%).("e

Essayez-le

Brain-Flak , 96 octets

{<<>>(({})<<>>[(([{}<<>>]))]){((<<[[]]>>))}{}{}{}{}<<>>}<<>>{{{}{}{}{}{}}((<<>>){{}{}}){{{}}}}{}

Essayez-le en ligne!

Ne produit rien si l'entrée est parfaitement appariée, et 0sinon.

Version (d'origine) non parfaitement appariée:

{<>(({})<>[({}<>)]){((<()>))}{}{}{}<>}<>{((<>))}{}

Essayez-le en ligne!

Haskell , 66 octets

null.foldr((%))"";;cc%((r:t))|cc==r=t;;t%s=t:s--s:t=s%=r|t:dlof.un

Essayez-le en ligne!

L'assistant Cat a enregistré 6 octets.

Ajouter ++ , 146 octets

D,g,@~~,L2_|*;;*|_2L,@,g,D
D,ff,@^^,BG€gBF;;FBg€GB,@D1:?:

xx:?

aa:1
`bb
Bxx;;B
Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy

O;;O:,B,`,|,`,>$,`,*W`

Essayez-le en ligne!

Fait amusant: c'était 272 octets bien avant le début de l'explication, maintenant il bat Java.

Sorties Truepour cordes parfaitement équilibrées et Falseautres

À ma grande satisfaction, cela bat la version ennuyeuse de palindromisation de 2 octets, pour éviter que le résultat ne soit imprimé deux fois. J'ai également cherché à avoir le moins de code mort possible, néanmoins il reste quelques sections commentées et le code se termine avec un code d'erreur de 1 , après avoir imprimé la valeur correcte.

NB : Un bug avec les BFcommandes a été corrigé pendant le développement de cette réponse.

Comment ça marche

$\mathit{ff}$$g$$\mathit{ff}$$\mathit{ff}$$g$$S$$\mathit{ff}(S)$$S$

$S$$abbbaabacc$$[[a], [bbb], [aa], [b], [a], [cc]]$$g$et remplacez les sous-listes par le résultat de la fonction.

$g$$2$$x$$[a]$$[bb]$$[ccc]$

$x$$x > 2$$x - 2$$x$*

$g(s)$$s$BF^D,ff,@^^,$g$$r$$r$;;

$\mathit{ff}$$g$$\mathit{ff}$

• $\mathit{xx}$$\mathit{ff}$
• $\mathit{yy}$$\mathit{ff}$
• $\mathit{aa}$
• $\mathit{bb}$$\mathit{yy}$

$g$$\mathit{xyab}$$g$

€$\mathit{abc}${...}$g${...}$\mathit{gg}$$\mathit{ff}$$g$

D,gg,@~~,L2_|*;;*|_2L,@D             (NB: -2 bytes)
D,ff,@^^,BG€{gg}BF;;FB}gg{€GB,@D?:   (NB: +6 bytes)

qui est de 4 octets de plus.

$x = 5$$x = 15$

x+10 ; Explicit argument
+10  ; Implicit argument, as x is active

$x$`

$\mathit{ff}$$g$$\mathit{xx}$xx:?$\mathit{xx}$$\mathit{aa}$aa:1$1$$\mathit{xx}$$\mathit{bb}$

`bb
Bxx

$\mathit{bb}$$\mathit{xx}$$\mathit{aa} := 1$$\mathit{bb} := \neg \neg \mathit{xx}$

Ensuite, nous entrons dans notre boucle while:

Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy

Une boucle while est une construction dans Add ++: elle opère directement sur le code, plutôt que sur les variables. Les constructions prennent une série d'instructions de code, séparées avec ,lesquelles elles opèrent. Les instructions while et if prennent également une condition directement avant la première ,qui consiste en une seule instruction valide, telle qu'une commande infixe avec des variables. Une chose à noter: la variable active ne peut pas être omise de la condition.

aa*bb$\mathit{aa}$$\mathit{bb}$$\mathit{yy}$$\mathit{ff}(x)$

`yy,$ff>xx

$\mathit{aa}$

• 1) La nouvelle valeur n'est pas égale à l'ancienne valeur (boucle unique)
• 2) La nouvelle valeur n'est pas la chaîne vide

L'un des plus gros inconvénients d'Add ++ est le manque d'instructions composées, ce qui nécessite d'avoir une deuxième variable de boucle. Nous attribuons nos deux variables:

Avec le code

`aa,xx|yy,`bb,Byy

|B $\mathit{xx}$$\mathit{yy}$xx:yy

$\mathit{ff}$$\mathit{aa}$$\mathit{bb}$

$\mathit{aa}$$\mathit{x} = \mathit{y}$$\mathit{aa}$$\mathit{yy}$$\mathit{bb}$$\mathit{aa}$

Nous arrivons ensuite à notre déclaration finale:

O

$\mathit{bb}$

• $\mathit{aa} = 1$$\mathit{bb} = \mathrm{False}$$\mathrm{False}$
• $\mathit{aa} = \mathrm{True}$$\mathit{bb} = \mathrm{False}$$\mathrm{False}$
• $\mathit{aa} = \mathrm{False}$$\mathit{bb} = \mathrm{True}$$\mathrm{True}$

$\mathit{bb}$$\mathit{bb}$$\mathrm{True}$$\mathrm{False}$

JavaScript (ES6), 76 octets

Renvoie un booléen.

ff=ss=>ss==(ss=ss.replace(/(.)\1/,''))?!ss:ff(ss)//)(:!?,/1\).(/(ecalper.=(>

Essayez-le en ligne!

Suggéré par @Shaggy: 58 octets en retournant une chaîne vide pour un appariement parfait ou en lançant une erreur sinon.

Wolfram Language (Mathematica) , 70 64 octets

{#//.{aa___,bb__,bb_,cc___}:>{aa,cc}}=={{}}(**(,{>:}_,{.#{&)**)&

Essayez-le en ligne!

Sans commentaires, 92 octets

((#//.bb_:>StringReplace[00[ecalpeRgnirtS>aa__:_.#&];bb,{{,}};00>00;00;aa:_~~aa_:>""]))==""&

Essayez-le en ligne!

Lua , 178 octets

p=...S={}for a in p:gmatch"."do E=S[#S]~=a;S[E and#S+1 or#S]=E and a or X end;print(#S==0)--)0S#(tnirp;dne X ro a dna E=]S#ro 1+S#dna E[S;a=~]S#[S=E od"."hctamg:p ni a rof}{=S.=p

Essayez-le en ligne!

Bien que ce soit une solution terriblement longue, cela fait un peu usage des bizarreries spécifiques à Lua. Il s'agit en fait d'un algorithme de pile de force brute minimisé. Le programme est rendu compliqué par le fait que les modèles de Lua ne permettent pas de remplacer les paires et que l'expression régulière n'est pas intégrée.

Explication:

p=... -- command-line argument
S={} -- the stack
for c in p:gmatch"." do -- shorter than "for i=1,#p do ..."
    E=S[#S]~=c -- check whether we have the right letter on top of stack
    -- could've saved some bytes by doing == instead of ~=
    -- but the double negation is necessary for ternary operator
    -- to work with nil values
    S[E and #S+1 or #S]=E and c or X -- Lua's awesome "ternary operator"
end
-- i'm sure there is a better way to output this (table indexing?)
print(#S==0)

Gol> <> , 30 octets

1ll1**F:}}:{=Q{~~||lzBBzl{Q={F

Essayez-le en ligne!

Tout ce qui suit le premier Best un excès de code et n'est pas exécuté. Une fonction qui renvoie le haut de la pile comme 1si l'entrée était un appariement parfait, 0sinon.

Explication:

1       Push 1 as the end string marker
 ll1**  Push n, where n (len+1)*(len+2), 
        This is larger than the amount of steps needed to determine pairing
      F           |  Repeat that many times
       :}}:{=        Compare the first two characters of the string
             Q   |   If they are equal
              {~~    Pop both of them
        String is also rotated by 1
        If the string becomes empty, the 1 is compared to itself and removed.
                   lzB   Return whether the length of the stack is 0
                      Bzl{Q={F  Excess code to match unpaired symbols

Cubix , 30 octets

1O@;??;@ii??O;>>;;;..1Wcc1??1W

Essayez-le en ligne!

Sort 1si la chaîne est parfaitement appariée et rien d'autre.

Cubifié

      1 O @
      ; ? ?
      ; @ i
i ? ? O ; > > ; ; ; . .
1 W c c 1 ? ? 1 W . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Simplifié

      1 O @
      ; ? .
      . @ .
i ? . . . . > ; ; ; . .
. W c . . . ? 1 W . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

La logique et la structure générale sont les mêmes que dans la réponse de Mnemonic, mais sans vérification explicite de la chaîne vide.

Haskell , 92 octets

gg""

gg((aa:cc:bb))dd|aa==cc=gg bb dd

gg  aa""=""==aa

gg  aa((bb:c))=gg((bb:aa))c--c:=c:|

Essayez-le en ligne!

La réponse de @ nimi est plutôt cool, elle n'utilise aucun commentaire. Celui-ci est plus court mais utilise un commentaire.

La réponse de @ xnor est également plutôt cool, elle utilise des commentaires et est plus courte que celle-ci.

Python 2 , 114 octets

import re

e=lambda i,nn=1:e(*re.subn('(.)\\1','',i))if nn else''==i##ieslef'1).('(nbus.er*(e:1=,i adbmal=r tropmi

Essayez-le en ligne!

Renvoie Trueles chaînes parfaitement appariées, Falsesinon.

(En fait, il ne parvient pas à se vérifier, car (.)il ne correspondra pas aux sauts de ligne dans le code!

Il s'agit d'une version parfaitement appariée de:

import re;p=lambda s,n=1:p(*re.subn('(.)\\1','',s))if n else''==i

pour lequel une perfectionnement «paresseux» code + '##' + f(code[::-1])donnerait 120 octets. (Autrement dit, renommer les variables, etc. pour introduire plus de paires réduites dans la moitié des commentaires du code a sauvé 6 octets.)

re.subnest une variante peu connue re.subqui retourne un tuple (new_string, number_of_substitutions_made). C'est assez bon pour trouver des points de correction de substitution regex!

Gelée , 26 24 22 octets

ẠƬµF€ḂLḣgŒŒgḣLḂ$$€FµƬẠ

Essayez-le en ligne!

Étrangement semble fonctionner sans déplacer le code en arrière vers un lien inutilisé.

Renvoie 0 si l'entrée est parfaitement appariée, 1 sinon.

Code actif:

ŒgḣLḂ$$€FµƬẠ
Œg            Group runs 'abbbcc'->['a','bbb','cc']
       €      For each of these strings:
      $       Monad{
     $            Monad{
   L                  Find the length...
    Ḃ                 ...mod 2. 
                      } -> [1, 1, 0] in this example.
  ḣ               Take this many characters from the string.
                  } -> [['a'], ['b'], []]
        F     Flatten -> ['a', 'b']
          Ƭ   Repeat...
         µ    The last monadic chain until a fixed point is reached.
           Ạ  All. If it is not a perfectly paired string, all elements in the 
              result of Ƭ will be nonempty and 1 is returned.
              If it is perfectly paired, the last element is [] which is falsy
              and 0 is returned.

Attaché , 82 octets

{0=#Fixpoint[{Replace[_,/"(.)\\1",""]},_]}??}]_,}],"1).("/,_[ecalpeR{[tniopxiF#=0{

Essayez-le en ligne!

Rien d'incroyable ici. Fixpointune fonction qui supprime les paires consécutives.

Java 8, 158 156 154 octets

n->{for(;n.matches(".*(.)\\1.*");n=n.replaceAll("(.)\\1",""));return  n.isEmpty();}//};)(ytpmEsi.ruter;,"1).("(Aecalper.n=n;)"*.1).(*."(sehctam.n;(rof{>-n

Renvoie un booléen ( true/ false).

-2 octets grâce à @raznagul .

Essayez-le en ligne.

Explication:

n->{                              // Method with String parameter and boolean return-type
  for(;n.matches(".*(.)\\1.*");   //  Loop as long as the String still contains pairs
    n=n.replaceAll("(.)\\1","")); //   Remove all pairs
  return  n.isEmpty();}           //  Return whether the String is empty now
//};)(ytpmEsi.ruter;,"1).("(Aecalper.n=n;)"*.1).(*."(sehctam.n;(rof{>-n
                                  // Comment reversed of the source code,
                                  // minus the pairs: '\\';'ll';'\\';'""))';'n  n';'//'