Gibt es Klammern in der Verkleidung?

12

Jemand hat uns eine Zeichenkette gegeben, aber alle Klammer-ähnlichen Zeichen wurden in normale Zeichen umgewandelt, und wir wissen nicht, welche oder wie viele es waren. Alles was wir wissen ist, dass wenn L1,L2,L3,...,LNverschiedene Arten von linken Klammern und R1,R2,R3,...,RNverschiedene entsprechende Arten von rechten Klammern vorhanden wären, die alle verschieden sind (2N verschiedene Klammerzeichen), eine Zeichenkette gültig wäre, wenn sie eine von (+ ist normale Zeichenkettenverkettung) ist:

  • L1+X+R1,, L2+X+R2...,, LN+X+RNwo Xist eine gültige Zeichenfolge,

  • X+Y, wo Xund Ysind gültige Zeichenfolgen,

  • Jedes einzelne Zeichen, das kein Klammerzeichen ist.

  • Die leere Zeichenfolge

Wir wissen, dass sie mit einer gültigen Zeichenfolge begonnen haben, bevor sie die Klammern geändert haben, und sie haben sie nicht in Zeichen geändert, die bereits in der Zeichenfolge vorhanden waren. Auch für jede Klammer gab es mindestens ein Paar. Können Sie rekonstruieren, welche Zeichen ursprünglich linke und rechte Klammerpaare waren (finden Sie die Liund Rinach den gegebenen Bedingungen)?

Geben Sie die Zeichenpaare aus, die Klammern waren. Wenn es sich beispielsweise (){}[]tatsächlich um eckige Klammern handelt, können Sie (){}[]oder {}[]()oder [](){}usw. ausgeben . Es gibt möglicherweise mehrere Möglichkeiten, dies für eine Zeichenfolge zu tun. Sie müssen nur eine zurückgeben, sodass keine eckige Klammer mit mehr Paaren vorhanden ist (siehe Beispiele). Beachten Sie, dass die Ausgabezeichenfolge immer eine gerade Länge haben sollte.

Beispiele:

abcc- ckann keine Klammer sein, da es kein anderes Zeichen mit zwei Vorkommen gibt, sondern abkann ein Klammerpaar sein, sodass Sie genau ausgeben würden ab.

fffff - Jeder String mit höchstens einem Zeichen darf keine eckigen Klammern enthalten. Sie würden also den leeren String zurückgeben oder nichts ausgeben.

aedbedebdcecdec - Diese Zeichenfolge darf keine eckigen Klammern enthalten, da es 1 a, 2 bs, 3 cs, 4 ds und 5 es gibt, sodass keine zwei Zeichen gleich oft vorkommen. Dies ist eine Voraussetzung für eckige Klammern.

abcd- mögliche Zuordnungen sind ab, cd, abcd, cdab, adbc, bcad, ac, ad, bcund bd, (sowie die leere Zuordnung, die alle von ihnen haben) , aber Sie müssen eine der längsten Zuweisungen zurückkehren, so dass Sie zurückkehren müssen abcd, cdab, adbc, oder bcad.

aabbcc, abc- diese haben beide ab, acund bcals gültige Paare. Sie müssen eines dieser Paare zurückgeben, egal welches.

abbac- a und b haben die gleiche Zeichenanzahl, können aber nicht funktionieren, da eines von ihnen links und rechts von allen Vorkommen des anderen vorkommt. Nichts zurückgeben.

aabcdb- cdund absind die genau zwei Klammerpaare, also entweder cdaboder ausgeben abcd.

abcdacbd- nur ein Paar auf einmal erreicht werden, aber ab, ac, bd, cd, und adwerden alle möglichen Paare können Sie zurückkommen . Egal , welches Paar Sie sich entscheiden, hat es eine Instanz , wo eine einzige andere Zeichen in ihm ist, die alle anderen Paare verbietet, außer im Fall ad, wo die anderen Paare bcund cbsind nicht möglich allein entweder, und so nicht möglich sein kann , mit ad.

Dies ist Code Golf, also gewinnt der kürzeste Code in Bytes. Die Eingabe erfolgt von STDIN, wenn dies für Ihre Sprache möglich ist. Wenn dies nicht möglich ist, geben Sie in Ihrer Antwort die Eingabemethode an.

Frikative Melone
quelle
1
für abcddie eingabe adbcwäre die ausgabe auch akzeptabel, oder?
Patrick Roberts
Ja, ich habe es dem Beispiel hinzugefügt.
Fricative Melone

Antworten:

4

Ruby, 373 Bytes

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]

Dieser verwendet eine golfed Version des Stapels Parser hier .

Es kann wahrscheinlich weiter vereinfacht werden, aber ich glaube nicht, dass mein Gehirn mehr damit fertig wird.

Alle Testfälle: http://ideone.com/gcqDkK

Mit Leerzeichen: http://ideone.com/pLrsHg

Ungolfed (meistens): http://ideone.com/oM5gKX

Icy Defiance
quelle