Verriegelungsklammern

30

Schreiben Sie ein Programm oder eine Funktion, die eine 8-Byte-Zeichenfolge enthält, die eines der Zeichen enthält, die so ()[]{}<>angeordnet sind, dass die vier jeweiligen Klammertypen übereinstimmen. Beispielsweise ]<([){}>ist eine Eingabe ungültig, da die eckigen Klammern nicht übereinstimmen (obwohl alle anderen dies tun).

Eine Ganzzahl ausgeben oder zurückgeben von 0bis gibt an 6, wie viele der sechs möglichen Paare der vier Klammertypen miteinander verbunden sind. Klammerpaare gelten als verriegelt, wenn genau eine Klammer eines Typs zwischen den Klammern des anderen Typs steht. So ([)]und [(])verriegelt sind , sondern ()[], [](), ([]), und [()]sind es nicht.

Der kürzeste Code in Bytes gewinnt.

Ein- / Ausgabebeispiele

()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6
Calvins Hobbys
quelle

Antworten:

17

CJam, 18

l7~f&_f{\/~;&}s,2/

Danke isaacg für ein paar Golfideen :)
Probieren Sie es online aus oder probieren Sie alle Beispiele

Erläuterung:

l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters
aditsu
quelle
1
Oh, also bist du der Typ, der CJam erschaffen hat? Sie schulden mir für alle Antworten, die ich verloren habe und die von CJam-Antworten geschlagen wurden! ;)
kirbyfan64sos
6
@ kirbyfan64sos gut, du solltest besser anfangen, es auch zu lernen, wenn du gewinnen willst :)
aditsu
9
7~f&? Diese Antwort gefällt mir bereits und ich habe den Rest noch nicht einmal gelesen.
Dennis
11

Python 2, 163 Bytes

def f(b,e='([{<)]}>',q=range(4)):
 b=[b[b.index(e[j])+1:b.index(e[j+4])]for j in q]
 print sum(sum(abs(b[k].count(e[j])-b[k].count(e[j+4]))for j in q)for k in q)/2

Dabei wird das Zeug zwischen jedem Paar übereinstimmender Klammern betrachtet und die Anzahl der einzelnen vorhandenen linken oder rechten Klammern gezählt. Die Summe von diesen geteilt durch zwei ist die Ausgabe.

Ich bin sicher, es könnte viel mehr von besseren Golfern als ich gespielt werden.

Calvins Hobbys
quelle
31
Nun, es ist passiert. Calvin hat eine Antwort gepostet. Die Endzeiten stehen vor der Tür.
Alex A.
4

GNU sed -r, 147

Die Ausgabe ist gemäß dieser Meta-Antwort unär .

y/([{</)]}>/
s/.*/\t& & & & /
:b
y/)]}>/]}>)/
s/\S*>(\S*)>\S* /\1\t/
t
s/\S* //
:
s/(\t\S*)(\S)(\S*)\2(\S*\t)/\1\3\4/
t
s/\S *$/&/
tb
s/\s//g
s/../1/g

Hinweis: Ersetzen Sie diese \tdurch die tatsächlichen tabZeichen, um die richtige Punktzahl zu erhalten. Das Programm wird jedoch so oder so mit GNU sed funktionieren.

Probieren Sie es online aus .

Digitales Trauma
quelle
3

Perl, 77 Bytes

76 Code + 1 Schalter

perl -pe 'y/)]}>/([{</;for$x(/./g){$h{$x="\\$x"}++&&s!$x(.*)$x!$z+=length$1,$1!e}$_=$z'

Übernimmt die Eingabe von STDIN und das Programm muss für jede Eingabe neu gestartet werden.

Erläuterung

  1. Ersetzen Sie alle schließenden Klammern durch ihre offenen Gegenstücke ( y/.../.../).
  2. Erhöhen Sie dann für jedes Zeichen in der Eingabezeichenfolge ( for$x...) einen Zähler für das Zeichen ( $h{$x}++).
  3. Wenn Sie das Zeichen zum zweiten Mal sehen, ermitteln Sie den Abstand zwischen den beiden Vorkommen ( length $1) und entfernen Sie beide Vorkommen dieses Zeichens aus der Zeichenfolge. Wenn die Zeichenfolge beispielsweise war ([{([{<<, gibt es zwei Zeichen [und {zwischen den beiden Zeichen (. Nachdem die (s verarbeitet wurden, wird die Zeichenfolge zu [{[{<<und wir addieren 2 zur Gesamtzahl ( $z) der ineinandergreifenden Klammern.
  4. Das Ergebnis stammt von $z( $_=$z)
svsd
quelle
3

Pyth, 20 Bytes

JmC/CdTzlsm@FPcsJd{J

Testsuite

JmC/CdTz: Zunächst wird jedes Symbolpaar in ein einzelnes Zeichen konvertiert, indem jedes eingegebene Zeichen seinem Cddurch 10 ( / T) geteilten Zeichencode zugeordnet wird. Dieser Code ist für jedes Paar gleich, unterscheidet sich jedoch zwischen allen Paaren. Die sich ergebende Zahl wird zurück in ein Zeichen umgewandelt, um später enthüllt zu werden ( C). Die resultierende Liste der Zeichen wird in gespeichert J.

lsm@FPcsJd{J: Jetzt ordnen wir die eindeutigen Zeichen in J( {J) zu. Wir beginnen mit dem Zerhacken der Zeichenfolge, die durch Verketten Jmit dem aktuellen Zeichen als Begrenzer ( csJd) gebildet wird. Ein Klammerpaar überlappt das aktuelle Paar, wenn es in der zweiten Gruppe und entweder in der ersten oder in der dritten Gruppe erscheint. Um Doppelzählungen zu vermeiden, werden nur der erste und der zweite Gruppenfall gezählt. Also entfernen wir die dritte Gruppe ( P) und nehmen den Schnittpunkt der verbleibenden Gruppen ( @F). Schließlich verketten wir die Überlappungszeichen ( s) und drucken die Länge des Resuts ( l).

isaacg
quelle
3

Python 3, 107

t=0
s=""
for x in input():s+=chr(ord(x)&~7)
for x in s:a=s.split(x);t+=len(set(a[0])&set(a[1]))
print(t//2)

Basiert lose auf meiner CJam-Lösung.

aditsu
quelle
3

Retina , 128 108 64 62 55 Bytes

(T`)]>}`([<{
(\D)(.*)\1(.*)
\n$2\n$3
(?=(\D).*\n.*\1)
1
\n
<empty>

Wobei <empty>eine leere abschließende Zeile darstellt. Platzieren Sie zu Zählzwecken jede Zeile in einer separaten Datei und ersetzen Sie die \ndurch die tatsächlichen Zeilenvorschubzeichen. Zur Vereinfachung können Sie diesen entsprechenden Code mit dem -sFlag aus einer einzelnen Datei verwenden:

(T`)]>}`([<{
(\D)(.*)\1(.*)
#$2#$3
(?=(\D)[^#]*#[^#]*\1)
1
#
<empty>

Die Ausgabe ist unär .

Erläuterung

Der erste (Befehl weist Retina an, den gesamten Code in einer Schleife auszuführen, bis eine Iteration aufhört, die Zeichenfolge zu ändern. In diesem Fall wird es für jeden Klammertyp immer viermal wiederholt.

T`)]>}`([<{

Dadurch wird einfach jede schließende Klammer in die entsprechende öffnende Klammer umgewandelt, sodass wir später die entsprechenden Klammern mit einem einfachen Rückverweis abgleichen können. (Diese Phase wird nach der ersten Iteration zu einem No-Op. Sie ist nur in der Schleife enthalten, da Tbereits ein Backtick erforderlich ist. Das Hinzufügen (kostet also nur eins statt zwei Bytes.)

(\D)(.*)\1(.*)
\n$2\n$3

Dadurch werden die am weitesten links stehenden Klammern durch Zeilenumbrüche ersetzt. Wir verwenden \D, um Klammern von den 1s zu unterscheiden, die wir später in der Schleife zum Zählen hinzufügen. Das (.*)am Ende stellt sicher, dass nur ein Paar ersetzt wird (da sich Übereinstimmungen nicht überlappen können).

(?=(\D).*\n.*\1)
1

Die gesamte Regex befindet sich in einem Lookahead, dies entspricht also einer Position . Genauer gesagt entspricht es einer Position für jedes Klammerpaar, das durch die anderen Klammern getrennt wurde, die wir gerade in Zeilenumbrüche umgewandelt haben. A 1wird in jede dieser Positionen eingefügt. Wir können die 1s einfach dort lassen, weil sie keine der anderen regulären Ausdrücke beeinflussen (weil die \Ds sicherstellen, dass wir sie nicht versehentlich zuordnen ).

\n
<empty>

Schließlich entfernen wir die Zeilenumbrüche (dh die Platzhalter für den aktuellen Klammertyp). Dies bedeutet, dass wir das verbleibende Problem auf eine Zeichenfolge mit der Länge 6 reduziert haben, die nur drei Klammertypen enthält, ansonsten funktioniert es jedoch genauso.

Am Ende 1bleiben nur die von uns eingegebenen s übrig, und ihre Anzahl entspricht genau der Anzahl der ineinandergreifenden Klammern.

Martin Ender
quelle
2

JavaScript (ES7), 121 bis 117 Byte

x=>(a=b=0,[for(c of x)for(d of'1234')(e=c.charCodeAt()/26|0)==d?a^=1<<d:b^=(a>>d&1)<<d*4+e],f=y=>y&&y%2+f(y>>1))(b)/2

Wow. Das hat Spaß gemacht. Ich skizzierte eine Antwortidee, als diese Herausforderung zum ersten Mal herauskam, aber sie war über 150 Byte lang und ich wollte mich nicht anstrengen, um Golf zu spielen. Ich bin gestern auf diese Idee in meinem Notizbuch gestoßen und habe beschlossen, nicht aufzuhören, darüber nachzudenken, bis ich sie vollständig ausprobiert habe. Am Ende habe ich zwei völlig neue Algorithmen geschrieben, von denen der erste einige Bytes kürzer ausfiel, nachdem ich mit Tonnen von Bit-Hacking etwa 25 Bytes abgelegt hatte.

Wie es funktioniert

Zuerst setzen wir Variablen aund bbis 0. aist ein 4-Bit-Binärarray, in dem sich Klammernpaare befinden, und bist ein 16-Bit-Binärarray, in dem Klammernpaare miteinander verknüpft sind.

Als nächstes durchlaufen wir jedes Zeichen cin xund jedes Zeichen din '0123'. Zuerst bestimmen wir, um welche Art von Klammer es sich chandelt e=c.charCodeAt()/26-1|0. Die Dezimalzeichencodes der einzelnen Klammertypen lauten wie folgt:

() => 40,41
<> => 60,62
[] => 91,93
{} => 123,125

Durch Teilen durch 26, Subtrahieren von 1 und Flooring ordnen wir diese jeweils 0, 1, 2 und 3 zu.

Als nächstes prüfen wir, ob diese Zahl dem aktuellen Wert von entspricht d. Wenn dies der Fall ist, geben wir entweder den dTyp der dritten Klammer ein oder verlassen ihn , und klappen das ddritte Bit amit ein a^=1<<d. Wenn es nicht, aber wir sind in der dth Haltewinkelart, müssen wir den Flip - ete Bit in dem dth 4-Bit - Abschnitt b. Das geht so:

b^=(a>>d&1)<<d*4+e

(a>>d&1)Gibt das dth-Bit in zurück a. Befinden wir uns innerhalb des dKlammer-Typs, wird 1 zurückgegeben. Andernfalls wird 0 zurückgegeben. Als Nächstes verschieben wir dies um d*4+eBits nach links und XOR bum das Ergebnis. Wenn wir uns innerhalb des dTyps der dritten Klammer befinden, ist diese XOR-Verknüpfung das dritte d*4+eBit von b; sonst macht es nichts.

Enthält am Ende der gesamten Schleife beine Anzahl von 1-Bit, die dem doppelten Wert des gewünschten Rückgabewerts entspricht. Aber wir müssen noch herausfinden, wie viele Bits das sind. Hier kommt die Unterfunktion ins fSpiel:

f=y=>y&&y%2+f(y>>1)

Wenn y0 ist, gibt dies einfach 0 zurück. Andernfalls nimmt es das letzte Bit von ymit y%2und fügt dann das Ergebnis der yerneuten Ausführung aller bis auf das letzte Bit durch die Funktion hinzu. Beispielsweise:

f(y)         => y && y%2 + f(y>>1)
f(0b1001101) =>       1  + f(0b100110) = 4
f(0b100110)  =>       0  + f(0b10011)  = 3
f(0b10011)   =>       1  + f(0b1001)   = 3
f(0b1001)    =>       1  + f(0b100)    = 2
f(0b100)     =>       0  + f(0b10)     = 1
f(0b10)      =>       0  + f(0b1)      = 1
f(0b1)       =>       1  + f(0b0)      = 1
f(0b0)       => 0                      = 0

Wir bdurchlaufen diese Funktion und teilen das Ergebnis durch 2, und es gibt unsere Antwort.

ETHproductions
quelle
1

Oracle SQL 11.2, 206 Bytes

WITH v AS(SELECT b,MIN(p)i,MAX(p)a FROM(SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p FROM DUAL CONNECT BY LEVEL<9)GROUP BY b)SELECT COUNT(*)FROM v x,v y WHERE x.i<y.i AND x.a<y.a AND y.i<x.a;

Nicht golfen:

WITH v AS( -- Compute min and max pos for each bracket type
           SELECT b,MIN(p)i,MAX(p)a 
           FROM   ( -- replace ending brackets by opening brakets and split the string  
                    SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p 
                    FROM DUAL 
                    CONNECT BY LEVEL<9
                  )
           GROUP BY b
         )
SELECT COUNT(*)
FROM   v x,v y
WHERE  x.i<y.i AND x.a<y.a AND y.i<x.a -- Apply restrictions for interlocking brackets  
Jeto
quelle