Supports de verrouillage

30

Écrivez un programme ou une fonction qui accepte une chaîne de huit octets contenant l'un de chacun des caractères ()[]{}<>disposés de manière à ce que les quatre types de parenthèses respectifs correspondent. Par exemple, l' ]<([){}>entrée n'est pas valide car les crochets ne correspondent pas (bien que tous les autres le soient).

Imprimer ou renvoyer un entier de 0à 6qui indique combien des six paires possibles des quatre types de parenthèses sont verrouillées. Les paires de types de parenthèses sont considérées comme verrouillées si exactement une parenthèse d'un type se produit entre les parenthèses de l'autre type. Ainsi , ([)]et [(])sont verrouillés , mais ()[], [](), ([])et [()]ne sont pas.

Le code le plus court en octets gagne.

Exemples d'entrées / sorties

()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6
Loisirs de Calvin
la source

Réponses:

17

CJam, 18 ans

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

Merci isaacg pour quelques idées de golf :)
Essayez-le en ligne ou essayez tous les exemples

Explication:

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
la source
1
Oh, vous êtes donc le gars qui a créé CJam ?? Tu me dois toutes les réponses que j'ai perdues qui ont été battues par les réponses de CJam! ;)
kirbyfan64sos
6
@ kirbyfan64sos bien, tu ferais mieux de commencer à l'apprendre aussi si tu veux gagner :)
aditsu
9
7~f&? J'aime déjà cette réponse, et je n'ai même pas lu le reste.
Dennis
11

Python 2, 163 octets

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

Cela examine la substance entre chaque paire de supports correspondants et compte le nombre de supports individuels gauche ou droit présents. La somme de ces derniers divisée par deux est la sortie.

Je suis sûr qu'il pourrait être joué beaucoup plus par de meilleurs golfeurs que moi.

Loisirs de Calvin
la source
31
Eh bien, c'est arrivé. Calvin a publié une réponse. La fin des temps est à nos portes.
Alex A.
4

GNU sed -r, 147

La sortie est unaire selon cette méta-réponse .

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

Remarque: remplacez-les \tpar des tabcaractères réels pour obtenir le score correct. Cependant, le programme fonctionnera dans les deux cas avec GNU sed.

Essayez-le en ligne .

Traumatisme numérique
la source
3

Perl, 77 octets

76 code + 1 interrupteur

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

Prend l'entrée de STDIN et le programme doit être redémarré pour chaque entrée.

Explication

  1. Remplacez tous les supports de fermeture par leurs homologues ouverts ( y/.../.../).
  2. Ensuite, pour chaque caractère de la chaîne d'entrée ( for$x...), incrémentez un compteur pour le caractère ( $h{$x}++).
  3. Si c'est la deuxième fois que nous voyons le caractère, obtenez la distance entre les deux occurrences ( length $1) et supprimez les deux occurrences de ce caractère de la chaîne. Par exemple, si la chaîne était ([{([{<<, il y a deux caractères [et {entre les deux (s. Une fois les (s traités, la chaîne devient [{[{<<et nous ajoutons 2 au nombre total ( $z) de crochets de verrouillage.
  4. Le résultat est tiré de $z( $_=$z)
svsd
la source
3

Pyth, 20 octets

JmC/CdTzlsm@FPcsJd{J

Suite de tests

JmC/CdTz: Tout d'abord, cela convertit chaque paire de symboles en un seul caractère en mappant chaque caractère d'entrée à son code de caractère (Cd ) divisé par 10 ( / T), qui est le même pour chaque paire mais différent entre toutes les paires. Le nombre résultant est reconverti en personnage à des fins qui seront révélées plus tard ( C). La liste résultante de caractères est enregistrée dans J.

lsm@FPcsJd{J: Maintenant, nous cartographions les caractères uniques dans J( {J). Nous commençons par couper la chaîne formée par concaténation en Jutilisant le caractère courant comme délimiteur ( csJd). Une paire de crochets chevauche la paire actuelle si elle apparaît dans le deuxième groupe et le premier ou le troisième groupe. Pour éviter le double comptage, nous comptons simplement le premier et le deuxième cas de groupe. Donc, nous supprimons le troisième groupe ( P) et prenons l'intersection des groupes restants ( @F). Enfin, nous concaténons les caractères de chevauchement ( s) et imprimons la longueur du resut ( l).

isaacg
la source
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)

Librement basé sur ma solution CJam.

aditsu
la source
3

Retina , 128 108 64 62 55 octets

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

<empty>représente une ligne de fin vide. À des fins de comptage, placez chaque ligne dans un fichier distinct et remplacez le \npar des caractères de saut de ligne réels. Pour plus de commodité, vous pouvez utiliser ce code équivalent avec l' -sindicateur d'un seul fichier:

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

La sortie est unaire .

Explication

Le premier (indique à Retina d'exécuter le code entier dans une boucle jusqu'à ce qu'une itération cesse de changer la chaîne. Dans ce cas, il répétera toujours quatre fois, une fois pour chaque type de support.

T`)]>}`([<{

Cela transforme simplement chaque support de fermeture en support d'ouverture correspondant, afin que nous puissions faire correspondre les supports correspondants avec une simple référence arrière plus tard. (Cette étape devient un no-op après la première itération. Elle est uniquement incluse dans la boucle, car elle Tnécessitait déjà un backtick, donc l'ajout (ne coûte qu'un au lieu de deux octets.)

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

Cela remplace la paire de crochets la plus à gauche par des sauts de ligne. Nous utilisons \Dpour distinguer les parenthèses des 1s que nous ajoutons plus tard dans la boucle pour le comptage. À (.*)la fin, une seule paire est remplacée (car les correspondances ne peuvent pas se chevaucher).

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

Le regex entier est dans un lookahead, donc cela correspond à une position . Plus précisément, il correspond à une position pour chaque paire de supports qui a été séparée par les autres supports que nous venons de transformer en nouvelles lignes. A 1est inséré dans chacune de ces positions. Nous pouvons simplement laisser les 1s là, car ils n'affectent aucun des autres regex (car les \Ds garantissent que nous ne les faisons pas correspondre accidentellement).

\n
<empty>

Enfin, nous supprimons les sauts de ligne (c'est-à-dire les espaces réservés pour le type actuel de crochets) - cela signifie que nous avons réduit le problème restant à une chaîne de longueur 6 contenant seulement 3 types de crochets, mais sinon cela fonctionne exactement de la même manière.

À la fin, seuls les 1s que nous avons insérés seront laissés, et leur montant correspond exactement au nombre de crochets de verrouillage.

Martin Ender
la source
2

JavaScript (ES7), 121117 octets

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

Sensationnel. C'était amusant. J'ai esquissé une idée de réponse lorsque ce défi est apparu pour la première fois, mais il faisait plus de 150 octets et je ne voulais pas faire l'effort de le jouer au golf. J'ai rencontré cette idée dans mon carnet hier et j'ai décidé de ne pas y penser tant que je ne l'aurais pas entièrement jouée. J'ai fini par écrire deux algorithmes entièrement nouveaux, dont le premier s'est retrouvé plusieurs octets plus court après avoir joué à environ 25 octets avec des tonnes de piratage de bits.

Comment ça marche

Nous avons d' abord définir des variables aet bà0 . aest un tableau binaire 4 bits dont les paires de parenthèses nous sommes actuellement à l'intérieur, etb est un tableau binaire de 16 bits dont les paires de parenthèses sont liées ensemble.

Ensuite, boucle de nous à travers chaque caractère cdans x, et chaque omble chevalier ddans '0123'. Nous déterminons d'abord le type de support cavec e=c.charCodeAt()/26-1|0. Les codes de caractères décimaux de chaque type de parenthèse sont les suivants:

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

En divisant par 26, en soustrayant 1 et le plancher, nous les mappons respectivement à 0, 1, 2 et 3.

Ensuite, nous vérifions si ce nombre est égal à la valeur actuelle de d. Si c'est le cas, nous entrons ou sortons du dtype de parenthèse e, donc nous retournons le dbit aavec a^=1<<d. Si ce n'est pas le cas, mais que nous sommes à l'intérieur du dtype de parenthèse e, nous devons retourner le ebit dans la dsection 4 bits de b. Cela se fait comme suit:

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

(a>>d&1)Renvoie le dbit e a. Si nous sommes à l'intérieur du dtype de parenthèse, cela renvoie 1; sinon, elle renvoie 0. Ensuite, nous la décalons à gauche par d*4+ebits et XOR bpar le résultat. Si nous sommes à l'intérieur du dtype de parenthèse, ce XORs le d*4+ee bit deb ; sinon, cela ne fait rien.

À la fin de tout le bouclage, bcontiendra un nombre de 1 bits égal au double de la valeur de retour souhaitée. Mais nous devons encore déterminer le nombre de bits. C'est là qu'intervient la sous-fonction f:

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

Si yest 0, cela renvoie simplement 0. Sinon, il prend le dernier bit de yavec y%2, puis ajoute à nouveau le résultat de l'exécution de tout sauf du dernier bit ydans la fonction. Par exemple:

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

Nous parcourons bcette fonction et divisons le résultat par 2, et voici notre réponse.

ETHproductions
la source
1

Oracle SQL 11.2, 206 octets

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;

Non-golfé:

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
la source