Une activité que je fais parfois quand je m'ennuie est d'écrire deux ou trois personnages par paires. Je trace ensuite des lignes (sur les sommets jamais en dessous) pour relier ces personnages. Par exemple, je pourrais écrire puis dessiner les lignes comme :$abcbac$

Ou je pourrais écrire$abbcac$

Une fois que j'ai tracé ces lignes, j'essaie de dessiner des boucles fermées autour de morceaux afin que ma boucle ne coupe aucune des lignes que je viens de dessiner. Par exemple, dans la première, la seule boucle que nous puissions dessiner est tout autour, mais dans la seconde, nous pouvons dessiner une boucle uniquement autour de s (ou de tout le reste).$b$

Si nous jouons avec cela pendant un moment, nous verrons que certaines chaînes ne peuvent être dessinées que pour que les boucles fermées contiennent toutes les lettres, voire aucune (comme dans notre premier exemple). Nous appellerons ces chaînes des chaînes bien liées.

Notez que certaines chaînes peuvent être dessinées de plusieurs manières. Par exemple, peut être dessiné des deux manières suivantes (et une troisième non incluse):$bbbb$

ou

Si l’un de ces moyens peut être dessiné de telle sorte qu’une boucle fermée puisse contenir certains des caractères sans croiser aucune des lignes, la chaîne n’est pas bien liée. (donc n'est pas bien lié)$bbbb$

Tâche

Votre tâche consiste à écrire un programme pour identifier les chaînes bien liées. Votre entrée consistera en une chaîne dans laquelle chaque caractère apparaît un nombre pair de fois et votre sortie doit être l’une des deux valeurs cohérentes distinctes, l’une si les chaînes sont bien liées et l’autre dans le cas contraire.

En outre votre programme doit être une chaîne bien liée sens

• Chaque caractère apparaît un nombre pair de fois dans votre programme.

• Il devrait sortir la valeur de vérité une fois passé lui-même.

Votre programme doit être capable de produire la sortie correcte pour toute chaîne composée de caractères à partir de fichiers ASCII imprimables ou de votre propre programme. Chaque caractère apparaissant un nombre pair de fois.

Les réponses seront notées sous forme de longueurs en octets, moins d'octets étant meilleurs.

Allusion

Une chaîne n'est pas bien liée si et seulement si une sous-chaîne stricte non vide et contiguë existe de sorte que chaque caractère apparaisse un nombre pair de fois dans cette sous-chaîne.

Cas de test

abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False

Regex (ECMAScript 2018 ou .NET), 140 126 118 100 98 82 octets

^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)

Ceci est beaucoup plus lent que la version à 98 octets, car il ^\1reste du regard et est donc évalué après. Voir ci-dessous pour un simple switcheroo qui regagne la vitesse. Mais pour cette raison, les deux TIO ci-dessous sont limités à la réalisation d'un ensemble de cas de test plus petit qu'auparavant, et celui du .NET est trop lent pour vérifier sa propre expression rationnelle.

Essayez-le en ligne! (ECMAScript 2018)
Essayez - le en ligne! (.NET)

Pour supprimer 18 octets (118 → 100), j'ai volé sans vergogne une optimisation vraiment intéressante de la regex de Neil qui évite d'avoir à regarder dans le négat (donnant une regex sans restriction de 80 octets). Merci Neil!

Cela est devenu obsolète quand il a perdu 16 octets supplémentaires (98 → 82) grâce aux idées de Jaytea qui ont abouti à une regex sans restriction de 69 octets! C'est beaucoup plus lent, mais c'est du golf!

Notez que les (|(no-ops pour rendre la regex bien liée ont pour résultat de le faire évaluer très lentement sous .NET. Ils n'ont pas cet effet dans ECMAScript car les correspondances facultatives de largeur nulle sont traitées comme des correspondances .

ECMAScript interdit l'utilisation de quantificateurs dans les assertions, ce qui rend plus difficile la pratique du golf pour les besoins des sources restreintes . Cependant, à ce stade, il est si bien joué que je ne pense pas que le fait de lever cette restriction en particulier ouvrirait de nouvelles perspectives pour le golf.

Sans les caractères supplémentaires nécessaires pour le faire passer les restrictions ( 101 69 octets):

^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))

C'est lent, mais cette édition simple (pour seulement 2 octets supplémentaires) récupère toute la vitesse perdue et plus encore:

^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))

^
(?!
    (.*)               # cycle through all starting points of substrings;
                       # \1 = part to exclude from the start
    (.+)               # cycle through all ending points of non-empty substrings;
                       # \2 = the substring
    (.*$)              # \3 = part to exclude from the end
    (?<!               # Assert that every character in the substring appears a total
                       # even number of times.
        ^\2            # Assert that our substring is not the whole string. We don't
                       # need a $ anchor because we were already at the end before
                       # entering this lookbehind.
    |                  # Note that the following steps are evaluated right to left,
                       # so please read them from bottom to top.
        ^\1            # Do not look further left than the start of our substring.
        (?=
            # Assert that the number of times the character \8 appears in our
            # substring is odd.
            (
                (
                    ((?!\8).)*
                    (\8|\3$) # This is the best part. Until the very last iteration
                             # of the loop outside the {2} loop, this alternation
                             # can only match \8, and once it reaches the end of the
                             # substring, it can match \3$ only once. This guarantees
                             # that it will match \8 an odd number of times, in matched
                             # pairs until finding one more at the end of the substring,
                             # which is paired with the \3$ instead of another \8.
                ){2}
            )*$
        )
        .*(.)+         # \8 = cycle through all characters in this substring
        # Assert (within this context) that at least one character appears an odd
        # number of times within our substring. (Outside this negative lookbehind,
        # that is equivalent to asserting that no character appears an odd number
        # of times in our substring.)
        \3             # Skip to our substring (do not look further right than its end)
    )
)

Je l'ai écrit à l'aide de lookahead moléculaire ( 103 69 octets) avant de le convertir en lookbehind de longueur variable:

^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))

^
(?!
    .*(?*(.+)(.*$))       # cycle through all non-empty substrings;
                          # \1 = the current substring;
                          # \2 = the part to exclude from the end
    (?!                   # Assert that no character in the substring appears a
                          # total even number of times.
        ^\1$              # Assert that our substring is not the whole string
                          # (i.e. it's a strict substring)
    |
        (?*(.)+.*\2$)    # \3 = Cycle through all characters that appear in this
                          # substring.
        # Assert (within this context) that this character appears an odd number
        # of times within our substring.
        (
            (
                ((?!\3).)*
                (\3|\2$)
            ){2}
        )*$
    )
)

Et pour aider à rendre ma regex elle-même bien liée, j'ai utilisé une variante de la regex ci-dessus:

(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1

Utilisé avec regex -xml,rs -o, ceci identifie une sous-chaîne stricte de l'entrée qui contient un nombre pair de chaque caractère (s'il en existe un). Bien sûr, j'aurais pu écrire un programme non-regex pour le faire pour moi, mais où serait-il amusant de le faire?

Gelée, 20 octets

ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ

Essayez-le en ligne!

La première ligne est ignorée. C'est seulement là pour satisfaire la condition que chaque personnage apparaisse un nombre pair de fois.

La première ligne suivante Ġregroupe les indices en fonction de leur valeur. Si nous prenons ensuite la longueur de chaque sous-liste dans la liste résultante ( Ẉ), nous obtenons le nombre de fois que chaque caractère apparaît. Pour vérifier si l'un d'entre eux est non-égal, nous obtenons le dernier résultat Ḃde chaque décompte et demandons s'il existe Ẹune valeur de vérité (non nulle).

Par conséquent, ce lien d'assistance indique si une sous-chaîne ne peut pas être encerclée.

Dans le lien principal, nous prenons toutes les sous-chaînes de input ( Ẇ), Ṗopons de la dernière (afin de ne pas vérifier si la chaîne entière peut être encerclée), et exécutons helper link ( Ç) sur €chaque sous-chaîne. Le résultat est alors de savoir si Ạ11 sous-chaînes ne peuvent pas être encerclées.

J , 34 octets

2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\

Essayez-le en ligne!

-8 octets grâce à FrownyFrog

original

J , 42 octets

(*#'.,012&|@~#')=1#.[:,([:*/0=2&|@#/.~)\.\

Essayez-le en ligne!

explication

(*#'.,012&|@~#') = 1 #. [: , ([: */ 0 = 2&|@#/.~)\.\

(*#'.,012&|@~#')                                       NB. this evaluates to 1
                                                       NB. while supplying extra
                                                       NB. chars we need.  hence...
                 =                                     NB. does 1 equal...
                   1 #.                                NB. the sum of...
                        [: ,                           NB. the flatten of...
                             (                  )\.\   NB. the verb in parens applied
                                                       NB. to every suffix of every
                                                       NB. prefix, ie, all contiguous 
                                                       NB. substrings
                             ([: */ 0 = 2&|@#/.~)      NB. def of verb in paren:
                                             /.~       NB. when we group by each
                                                       NB. distinct char...
                              [: */                    NB. is it the case that
                                                       NB. every group...
                                           @#          NB. has a length...
                                    0 = 2&|            NB. divisible by 2...

Python 3.8 (version préliminaire) , 66 octets

lambda l,b={id}:len({str(b:=b^{c})for(c)in l})<len(l)#,<^fmnost{}#

Essayez-le en ligne!

L'ère des expressions d'affectation est à nos portes. Avec PEP 572 inclus dans Python 3.8, le golf ne sera plus jamais pareil. Vous pouvez installer la version préliminaire 3.8.0a1 du développeur ici .

Les expressions d’affectation vous permettent :=d’affecter une variable en ligne lors de l’évaluation de cette valeur. Par exemple, (a:=2, a+1)donne (2, 3). Cela peut bien sûr être utilisé pour stocker des variables en vue de leur réutilisation, mais nous allons maintenant un peu plus loin et l’utilisons comme un accumulateur dans une compréhension.

Par exemple, ce code calcule les sommes cumulées [1, 3, 6]

t=0
l=[1,2,3]
print([t:=t+x for x in l])

Notez que, à chaque passage dans la compréhension de liste, la somme cumulée test augmentée de xet que la nouvelle valeur est stockée dans la liste produite par la compréhension.

De la même manière, b:=b^{c}met à jour le jeu de caractères bpour indiquer s'il inclut ou non un caractère cet correspond à la nouvelle valeur de b. Ainsi, le code [b:=b^{c}for c in l]itère sur les caractères cdans let accumule le jeu de caractères vu un nombre impair de fois dans chaque préfixe non vide.

Cette liste est vérifiée pour les doublons en en faisant une compréhension d'ensemble et en vérifiant si sa longueur est inférieure à celle de s, ce qui signifie que certaines répétitions ont été réduites . Si tel est le cas, la répétition signifie que dans la partie sobservée entre ces moments, chaque caractère a rencontré un nombre pair de nombres, ce qui rend la chaîne non bien liée. Python n'autorise pas les ensembles d'ensembles à être superflus. Par conséquent, les ensembles internes sont convertis en chaînes.

L'ensemble best initialisé sous la forme d'un argument facultatif et est modifié avec succès dans l'étendue de la fonction. Je craignais que cela ne rende la fonction non réutilisable, mais elle semble se réinitialiser entre les exécutions.

Pour la restriction de source, les caractères non appariés sont insérés dans un commentaire à la fin. Écrire for(c)in lplutôt que d’ for c in lannuler gratuitement les parens supplémentaires. Nous avons mis iddans le set initialb , ce qui est inoffensif puisqu'il peut commencer comme n'importe quel jeu, mais le jeu vide ne peut pas être écrit ainsi {}car Python créera un dictionnaire vide. Puisque les lettres iet dsont parmi celles qui ont besoin d'être appariées, on peut y mettre la fonction id.

Notez que le code produit des booléens annulés afin qu'il se donne correctement False.

Python 2 , 74 octets

bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)

Essayez-le en ligne!

Parcourt la chaîne en gardant une trace Pdu jeu de caractères vu un nombre impair de fois jusqu'à présent. La liste dstocke toutes les valeurs passées de P, et si vous voyez le courant Pdéjà dansd , cela signifie que dans les caractères vus depuis, chaque caractère est apparu un nombre pair de fois. Si c'est le cas, vérifiez si nous avons parcouru toute l'entrée: si c'est le cas, acceptez-la, car toute la chaîne est appariée comme prévu et sinon, refusez.

Parlons maintenant de la restriction de source. Les personnages ayant besoin d'être associés sont placés dans divers endroits inoffensifs, soulignés ci-dessous:

bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)
_____              _              _      _    _    ___        ___    

Lors f<sde l' 0appariement d'un f, l'évaluateur tire parti du nom de la fonction, de fsorte qu'il est défini (au moment de l'appel de la fonction).0^0 absorption d'un ^symbole.

Le 0in P={0}est regrettable: in Python {}évalue un dict vide plutôt qu'un ensemble vide comme nous le souhaitons, et ici nous pouvons insérer n'importe quel élément non-character et ce sera inoffensif. Je ne vois rien d’autre à mettre dans, cependant, et ai mis dans un 0et le dupliqué dans bmn0, coûtant 2 octets. Notez que les arguments initiaux sont évalués lorsque la fonction est définie, les variables que nous définissons nous-mêmes ne peuvent donc pas être insérées ici.

Perl 6 , 76 octets

*.comb[^*X+(^*).map(^*)].grep({$_&[&]($_)}).none.Bag{*}.none%2#*^+XBob2rec%#

Essayez-le en ligne!

Quel que soit le lambda qui retourne une jonction None de None, qui peut être booléifiée à une valeur vérité / falsey. Je recommanderais toutefois de ne pas supprimer le ?résultat booléifiant le résultat, sinon la sortie devient plutôt volumineuse .

Cette solution est un peu plus complexe que nécessaire, en raison de plusieurs fonctions impliquées soient découplées, par exemple .., all, >>, %%etc. Sans la restriction source, cela pourrait être 43 octets:

*.comb[^*X.. ^*].grep(?*).one.Bag{*}.all%%2

Essayez-le en ligne!

Explication:

*.comb                     # Split the string to a list of characters
      [^*X+(^*).map(^*)]   # Get all substrings, alongside some garbage
                        .grep({$_&[&]($_)})        # Filter out the garbage (empty lists, lists with Nil values)
                                           .none                 # Are none of
                                                .Bag{*}          # The count of characters in each substring
                                                       .none%2   # All not divisible by 2

                                               #*^+XBob2rec%#    And garbage to even out character counts

Perl 5 -p, 94, 86, 78 octets

m-.+(?{$Q|=@q&grp,$\|=$&eq$_^!grep+/^/&(@m=$g=~/\Q$_/g),($g=$&)=~/./g})(?!)-}{

ouput 0 si bien lié 1 sinon.

78 octets

86 octets

94 octets

Comment ça marche

• -pavec }{fin astuce pour sortir $\à la fin
• m-.+(?{.. })(?!)-, pour exécuter du code sur toutes les sous-chaînes non vides ( .+correspond à la chaîne entière en premier, et après l'exécution du code entre (?{.. })retour en raison d'un échec forcé(?!)
• $Q|=@q&grp, ordures en raison de la restriction de source
• $\|=entier au niveau du bit ou assignation, s'il y a presque un 1, $\sera 1 (vrai), par défaut il est vide (faux)
• $&eq$_ le cas où la chaîne est la chaîne entière est bitored ^ avec "aucune occurrence de caractère impair"
• ($g=$&)=~/./gcopier la sous-chaîne correspondante dans $g(parce que sera surchargée après la prochaine correspondance d'expression régulière) et renvoyer le tableau de caractères de la sous-chaîne.
• /^/ ordures qui évalue à 1
• grep1 &(@m=$g=~/\Q$_/g),pour chaque caractère de la sous-chaîne obtient le tableau de caractères en $gcorrespondance, le tableau en scalaire est évalué à sa taille et greple filtrage des caractères avec une occurrence étrange 1&xéquivaut àx%2==1

Retina , 150 à 96 octets

^(?!(.*)(.+)(.*)$(?<!^\2|^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

Essayez-le en ligne! Link inclut les cas de test, y compris lui-même. Edit: Classez légèrement la regex originale avec l’aide de @Deadcode, puis remontez-le légèrement moins extravagamment pour conserver la présentation source. Explication:

^(?!(.*)(.+)(.*)$

Affirmez qu'il n'existe aucune sous-chaîne \3correspondant aux contraintes suivantes.

(?<!^\2|

Affirmez que la sous-chaîne n'est pas la chaîne originale complète.

^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

Affirmez qu'il n'y a pas de caractère \6tel que:

• il n'apparaît pas entre le caractère lui-même (exclusif) et la fin de la sous-chaîne
• il apparaît un nombre pair de fois entre le début de la sous-chaîne et lui-même (exclusif)

Afin de passer la contrainte de mise en page source, j'ai remplacé ((((par (?:(^?(?:(et ((avec (|(. Il me restait encore une contrainte de source ))et les caractères !()1<{}restants, alors j'ai changé un +en {1,}et inséré l'inutile (?!,<)?pour consommer le reste.

C # (compilateur interactif Visual C #) , 208 206 200 198 octets

x=>!x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&!Enumerable.Repeat(x.Count,x.Count*x.Count).Where(
(l,i)=>i%l>0&!x.Skip(i/l).Take(i%l).GroupBy(c=>c).Any(g=>g.Count()%2>0)
).Any()/*>!oyAnC0EmeablR*WhiS/T*/

Essayez-le en ligne!

-2 octets grâce à @KevinCruijssen!

Finalement, je l'ai eu en dessous de 200, alors je pourrais peut-être jouer au golf pour le moment :) J'ai fini par créer un deuxième TIO pour tester les choses sur la base d'une réponse précédente.

Essayez-le en ligne!

Les choses qui ont rendu cette tâche difficile:

• L'opérateur d'égalité ==n'a pas été autorisé
• L'incrément / assignation de l'opérateur ++n'était pas autorisé
• All()Fonction Linq n'était pas autorisée

Code commenté ci-dessous:

// anonymous function that takes an IList as input
x=>
  // the first condition makes sure the string even
  // counts of each character
  !x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&
  // the second condition generates all proper substrings of x
  // and tests for any that contain even character counts
  // the string length `l` is repeated `l*l` times
  !Enumerable.Repeat(x.Count,x.Count*x.Count)
    .Where((l,i)=>
      // check that the substring length is greater than 0
      i%l>0&
      // use skip/take to generate a substring
      // and check for a character count thats odd
      // negate the result meaning we have found
      // a substring that invalidates the input
      !x.Skip(i/l).Take(i%l)
        .GroupBy(c=>c).Any(g=>g.Count()%2>0)
    )
    // if any invalid substrings are found
    // then the result in invalid
    // the comment string at the end is needed
    // to make the program well-linked
    .Any()/*>!oyAnC0EmeablR*WhiS/T*/

Python 2 , 108 octets

lambda d,e=enumerate:min(max(d[l:l+b].count(k)%2for(k)in d)for b,c in e(d[2:],2)for l,f in e(d) )#b =:x+.%2#

Essayez-le en ligne!

-2 grâce à Ørjan Johansen .

Brachylog , 16 octets

sᶠb∋p~j&sᶠb∋p~j&

Essayez-le en ligne!

Imprime false.pour les cas de vérité et true.pour les cas de faux. La version de TIO est trop lente à gérer elle-même, mais elle est clairement bien liée puisque c'est une chaîne avec des caractères uniques répétés deux fois.

Explication

    Input is a string: "abcacbaa"
sᶠ  Find all substrings: ["abcacbaa","abcacba","abcacb",..,"a"]
b   Behead (now the proper substrings remain): ["abcacba","abcacb",..,"a"]
∋   Take one of them: "abcacb"
p   Permute it: "abcabc"
~j  It is some string repeated twice: "abc"
&   Get the input again: "abcacbaa"
    Then repeat the above.
    If the constraints can be satisfied, the result is true, otherwise false.

05AB1E , 22 à 20 octets

Œε¢Pà}KŒIKεSIS¢ÈP}àÈ

Les sorties 1 si la chaîne est bien liée, et0 si la chaîne n'est pas bien liée.

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

Explication:

Le programme de base est ŒsKεsS¢ÈP}à( 11 octets ), qui sort 0s'il est bien lié et 1s'il n'est pas bien lié. La fin È(is_even) est un semi-no-op qui inverse la sortie, donc 1pour les chaînes bien liées et 0pour les chaînes non bien liées. Les autres parties ne permettent pas de se conformer aux règles du challenge.

Œε¢Pà}K         # No-ops: substrings, map, count, product, maximum, close map, remove
                # Due to the last remove, we're back at the (implicit) input again
Π              # Take the substrings of the input
 IK             # Remove the input itself from that list of substrings
   ε            # Map each substring to:
    S           #  No-op: transform the substring into a list of characters
     IS         #  Get the input-string as a list of characters
       ¢        #  Count the occurrence of each character in the current substring
        È       #  Check which counts are even (1 if truthy; 0 if falsey)
         P      #  Take the product of that
          }à    # After the map: check if any are truthy by taking the maximum
            È   # Semi no-op: check if this maximum is even (0 becomes 1; 1 becomes 0)
                # (and output the result implicitly)