Y a-t-il des parenthèses déguisées?

12

Quelqu'un nous a donné une chaîne, mais tous les caractères ressemblant à des crochets ont été changés en caractères normaux, et nous ne savons pas lesquels, ni même combien. Tout ce que nous savons, c'est que s'il y L1,L2,L3,...,LNavait différents types de crochets gauche et R1,R2,R3,...,RNdifférents types correspondants de crochets droits, tous étant distincts (2N caractères de crochets distincts), une chaîne serait valide si elle fait partie de (+ est la concaténation normale des chaînes):

  • L1+X+R1,, L2+X+R2...,, LN+X+RNoù Xest une chaîne valide,

  • X+Y, où Xet Ysont des chaînes valides,

  • Tout caractère unique qui n'est pas un caractère de parenthèse.

  • La chaîne vide

Nous savons qu'ils ont commencé avec une chaîne valide avant de changer les crochets, et ils ne les ont pas transformés en caractères qui existaient déjà dans la chaîne. Il existait également au moins une paire pour chaque support. Pouvez-vous reconstruire quels caractères étaient à l'origine des paires de crochets gauche et droit (trouver les conditions suivantes Liet Riles respecter)?

Sortez les paires de caractères qui étaient des crochets. Par exemple, s'il (){}[]s'agissait en fait de caractères entre crochets, vous pouvez générer (){}[]ou {}[]()ou [](){}, etc. Il peut y avoir plusieurs façons de le faire pour une chaîne, il vous suffit d'en renvoyer un de sorte qu'il n'y ait pas d'affectation de crochets avec plus de paires (voir exemples). Notez que la chaîne de sortie doit toujours avoir une longueur paire.

Exemples:

abcc- cne peut pas être une parenthèse, car il n'y a pas d'autre caractère avec deux occurrences, mais abpeut être une paire de parenthèses, donc vous sortiriez exactement ab.

fffff - toute chaîne avec au plus un caractère ne peut pas avoir de parenthèses, vous devez donc retourner la chaîne vide ou ne rien produire.

aedbedebdcecdec - cette chaîne ne peut pas avoir de crochets car il y a 1 a, 2 bs, 3 cs, 4 ds et 5 es, donc deux caractères n'apparaissent pas le même nombre de fois, ce qui est obligatoire pour avoir des crochets.

abcd- les affectations possibles sont ab, cd, abcd, cdab, adbc, bcad, ac, ad, bcet bd, (ainsi que la cession vide, qui tous ont) , mais vous devez retourner l' un des, vous devez donc retourner les affectations plus longues abcd, cdab, adbcou bcad.

aabbcc, abc- ces deux ont ab, acet bcque des paires valides. Vous devez retourner une de ces paires, peu importe laquelle.

abbac- a et b ont le même nombre de caractères, mais ils ne peuvent pas réellement fonctionner, car l'un d'eux se produit à la fois à gauche et à droite de toutes les occurrences de l'autre. Ne retournez rien.

aabcdb- cdet ables deux paires de supports précis, de sorte que la sortie soit cdabou abcd.

abcdacbd- une seule paire peut être réalisée à la fois, mais ab, ac, bd, cdet adsont toutes les paires possibles que vous pouvez revenir. Peu importe la paire que vous choisissez, il y a une instance où un seul autre personnage est en lui, ce qui interdit toutes les autres paires, sauf dans le cas de ad, où les autres paires bcet cbne sont pas possibles seules non plus, et ne peuvent donc pas être possibles avec ad.

C'est le golf de code, donc le code le plus court en octets gagne. L'entrée est de STDIN si possible pour votre langue. Si ce n'est pas possible, indiquez la méthode de saisie dans votre réponse.

code-golf string balanced-string Melon fricatif
la source
1
pour l'entrée abcd, la sortie adbcserait également acceptable, non?
Patrick Roberts
Oui, je l'ai ajouté à l'exemple.
Fricative Melon

Réponses:

4

Rubis, 373 octets

i=gets.chomp
b=[*(i.chars.group_by{|x|x}.group_by{|x,y|y.size}.map{|x|s=x[1].size
x[1][0...s-s%2].map{|x|x[0]}*''}*'').chars.each_slice(2)]
puts [*[*b.size.downto(1).map{|n|b.combination(n).map{|t|[t*'',(h=Hash[t]
s=[]
o=1
i.each_char{|c|s.push(c)if h.keys.include?c
(o=false if s.empty?||!h[s.pop].eql?(c))if h.values.include?c}
o ?s.empty?: o)]}}.find{|x|x[0][1]}][0]][0]

Ceci utilise une version golfée de l'analyseur de pile ici .

Cela peut probablement être simplifié davantage, mais je ne pense pas que mon cerveau puisse plus gérer.

Tous les cas de test: http://ideone.com/gcqDkK

Avec des espaces: http://ideone.com/pLrsHg

Non golfé (principalement): http://ideone.com/oM5gKX

Défi glacé
la source