Generieren Sie alle Klammern der Länge n

16

Eine *()[]geschweifte Klammer ist eine Zeichenfolge, die aus den Zeichen besteht, in denen geschweifte Klammern richtig übereinstimmen:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

Dies ist eine gültige geschweifte Klammer:

((())***[]**)****[(())*]*

Das sind aber nicht:

)(
**(**[*](**)
**([*)]**

Ihre Aufgabe ist es, ein Programm (oder eine Funktion) zu schreiben, das bei einer positiven Ganzzahl neine Zahl als Eingabe verwendet und alle gültigen geschweiften Klammern der Länge ausgibt (oder zurückgibt) n.

Spezifikationen

  • Sie können die Zeichenfolgen in beliebiger Reihenfolge ausgeben.
  • Sie können als Liste oder als durch ein anderes Zeichen getrennte Zeichenfolge ausgeben.
  • Ihr Programm muss 0 korrekt behandeln. Es gibt 1 möglichen Klammer-String der Länge 0, der der leere String ist "".
  • Das ist , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .

Testfälle

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
Esolanging Fruit
quelle
3
Die Anzahl der Einträge in der Ausgabe ist A025235
Gabriel Benamy
@ GabrielBenamy Ah. Ich fragte mich, ob das schon einmal angeschaut worden war. Interessant.
Esolanging Fruit
2
Was ist die Gewinnbedingung? Ich nehme das kürzeste Programm an (Code Golf).
Zgarb
Verbunden.
Martin Ender
1
Da alle davon ausgehen, dass es sich um Codegolf handelt, werde ich die Herausforderung entsprechend kennzeichnen (da sonst alle vorhandenen Antworten etwas sinnlos wären). Wenn Sie ein anderes Gewinnkriterium beabsichtigen, können Sie eine neue Herausforderung veröffentlichen.
Martin Ender

Antworten:

3

Gelee, 29 Bytes

-3 Bytes dank @JonathanAllan

Bitte benachrichtigen Sie mich, wenn es Probleme / Fehler / Fehler oder Bytes gibt, die ich beseitigen kann!

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

Probieren Sie es online!

Die vorherigen Lösungen, die ich hatte:

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

Erklärung (Mein bester Versuch einer Beschreibung):

Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter
Zacharý
quelle
Sie können drei Bytes mit Filtering ( “[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ) speichern
Jonathan Allan
15

Prolog, 69 Bytes

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

Eine der interessantesten Eigenschaften von Prolog ist, dass es in vielen Fällen in der Lage ist, ein Programm rückwärts auszuführen. Anstatt beispielsweise zu testen, ob etwas wahr ist, können Sie alle Lösungen generieren, für die es wahr ist, und statt die Länge einer Zeichenfolge zu überprüfen, können Sie alle Zeichenfolgen mit einer bestimmten Länge generieren. (Eine weitere nette Eigenschaft von Prolog ist, dass nach dem Ende jeder Prädikatdefinition Leerzeichen erforderlich sind und eine neue Zeile so billig wie ein Leerzeichen eingefügt werden kann; daher sind auch Golfprogramme oft ziemlich lesbar.)

Das Obige definiert ein Prädikat (das Äquivalent einer Funktion), bdas prüft, ob eine Zeichenfolge eine bestimmte Länge hat und eine "Klammerzeichenfolge" ist, wie in der Frage definiert. Insbesondere geschieht dies über die Grammatik- / Regex- / Mustervergleichsunterstützung von Prolog, die einen netten, kurzen Zucker für die Definition dieser Art von Ausdruck liefert (anscheinend ist dies Standard / portabel, aber ich war mir dessen nicht bewusst, als ich die Antwort ursprünglich schrieb, und daher Angenommen, die Antwort würde nur für eine Prolog-Implementierung funktionieren, anscheinend jedoch für jede Implementierung, die den Standards entspricht. Das Programm kann ziemlich direkt ins Englische übersetzt werden; In den ersten beiden Zeilen steht "an s ist eine leere Zeichenfolge oder ein e gefolgt von einem s ; ein eist ein Sternchen oder ein s in Klammern oder ein s in eckigen Klammern. "Die dritte Zeile kann interpretiert werden als" Das b von N kann A sein, wenn A eine Liste mit der Länge N ist und A ein s gefolgt von einer Null ist Zeichenfolge. "

Ich habe eine gewisse Sorgfalt zu schreiben s(und damit b) , so dass sie in genau einer Art und Weise jeweils „Klammer Zeichenfolge“ entsprechen (das ist der Grund , dass beide sund eexistieren müssen, anstatt sie in ein Prädikat Gruppierung). Dies macht sie beide vollständig umkehrbar; Auf diese Weise bkönnen alle "Klammerzeichenfolgen" einer bestimmten Länge generiert werden. Außerdem kann geprüft werden, ob eine Zeichenfolge eine Klammerzeichenfolge einer bestimmten Länge ist. Sie kann auch in dritter Richtung verwendet werden, um die Länge einer Klammer zu ermitteln string, aber das ist mit ziemlicher Sicherheit die am wenigsten nützliche Arbeitsweise). Die Implementierung ist rekursiv, z. B. um ein s zu generieren, generiert der Code alle möglichen e s, die nicht länger als die erforderliche Länge der Ausgabe sind, und hängt alle möglichen s ans, die in den verbleibenden Raum zu ihnen passen; Da ich die Länge des Arguments im Voraus festgelegt habe (innerhalb von b ), weiß die Prolog-Engine, dass keine Ausgabe generiert werden kann, die länger als die angegebene Länge ist, sodass die Rekursion beendet werden kann.

Hier ist ein Beispiel des laufenden Programms:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

quelle
Die Syntax, die erforderlich ist, um anzugeben, ob Sie das Programm "vorwärts" oder "rückwärts" ausführen möchten, dürfte einige Kosten verursachen. Perl zahlt 1 Byte für jedes bisschen von so etwas
Sparr
Nun, Sie könnten eine Regel erstellen, dass Argumente am Ende immer den Rückgabewert darstellen, und dann die Reihenfolge der Argumente umkehren, um anzugeben, in welche Richtung Sie das Programm ausführen. Es ist ziemlich üblich, dass Golfsprachen herausfinden, was sie tun sollten, indem sie sich teilweise ansehen, ob sie irgendwelche Eingaben erhalten haben, und dies ist ein vergleichbares Prinzip. Im Allgemeinen ist es jedoch schwierig, Regeln zu erstellen, die für jede mögliche Sprache gelten. Das Ausführen von Builtins wie lengthund in appendbeiden Richtungen ist ein grundlegender Teil der Sprache, und Benutzerfunktionen tun dies oftmals auch.
Oh, hmm. Ich nahm an, dass es in Ihrem Beispiel Hinweise gab, die das fragliche Verhalten auslösten.
Sparr
Nein, es liegt ganz an den Argumenten. Im obigen Programm schreibe ich length(A,N); Wenn Ngegeben ist und Anicht (was passiert, wenn das Prädikat auf die im Programm angeforderte Weise verwendet wird), lengthwird eine Liste Amit Nunbekannten Elementen erstellt. Mit messen die Länge einer Liste ist wahrscheinlich häufiger verwendet (obwohl mit ihm „rückwärts“ in Prolog - Programmierung ziemlich üblich ist). Die meisten Prädikate funktionieren im Endeffekt auf die gleiche Weise (der einzige Grund, warum sie dies nicht tun, ist, dass der Versuch, sie umzukehren, eine Endlosschleife erzeugt, was ziemlich häufig vorkommt). length
1
@ ais523 -->und DCGs sind im Allgemeinen Standard-ISO-Prolog .
Fatalize
5

Haskell, 101 94 Bytes

7 Bytes von Zgarb gespeichert!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Fast unkompliziert, der Definition folgend, aber mit dem ""Fall verschoben.

Verwenden:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(Die zweite Berechnung dauert auf einer langsamen Maschine weniger als eine Sekunde.)

Ich möchte auch das Ergebnis eines anderen Ansatzes mitteilen, den ich mir ausgedacht habe, als ich über die Generierung von Funktionen nachgedacht habe. Es definiert eine Liste b von Listen mit Zeichenfolgen, b!!ndie alle geschweiften Zeichenfolgen der Länge enthalten n. Ebenso u!!nenthält alle Atome der Größe n-1. Eine nette Sache ist, dass der Code keine Zahlen verwendet. Es ist nicht vollständig golfen: uund ikönnte inline sein, und es verpasst sicherlich ein paar andere Golfmöglichkeiten. Leider sieht es nicht so aus, als ob es kürzer als die erste Version sein könnte, aber es wird length $ b !! 10noch schneller berechnet .

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)
Christian Sievers
quelle
Mit b$n-kund zwei Bytes speichern b$n-2. Auch in der letzten Zeile können Sie tun a:b<-["()","[]"]und zurückkehren a:s++b.
Zgarb
Oh, ich wollte verwenden ["()","[]"], konnte aber nicht sehen, wie ich die Codegröße damit verbessern kann. Vielen Dank!
Christian Sievers
4

Mathematica, 116 Bytes

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Erläuterung

Characters@"*([)]"

Suchen Sie die Zeichen der Zeichenfolge "*([)]"und geben Sie die List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Finden Sie die Tupel der obigen Liste mit Länge n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Unbenannte Boolesche Funktion, um festzustellen, ob das Tupel ausgeglichen ist:

#/."*"->Nothing

Löschen Sie alle "*"in der Eingabe.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Löschen Sie wiederholt alle aufeinander folgenden Vorkommen von "("und ")"oder "["und, "]"bis sich die Eingabe nicht mehr ändert.

... =={}

Überprüfen Sie, ob das Ergebnis leer ist List.

Select[ ... , ... ]

Suchen Sie die Tupel, die Truebei Anwendung der Booleschen Funktion angegeben werden.

#<>""&/@

Wandle jedes ListZeichen in Strings um.

JungHwan min
quelle
2
Etwas unerwartet {x=a___,"(",")",y=b___}|{x,"[","]",y}scheint zu funktionieren.
Martin Ender
4

Python 2, 128 Bytes

n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

Schrauben Sie rekursive reguläre Ausdrücke - wir verwenden Pythons Parser! Um zu überprüfen, ob es sich beispielsweise *(**[])*um eine geschweifte Klammer handelt, gehen Sie wie folgt vor:

  1. Machen Sie einen String wie "*", (0,"*","*", [0,0] ,0) ,"*", wo jedes zweites Zeichen von vier ein Zeichen aus den Klammer-Strings ist, und die restlichen Zeichen sind Leim dies ein potentieller Python Ausdruck zu machen.

  2. eval es.

  3. Wenn dies keinen Fehler auslöst, drucken Sie s[1::4](die Klammerzeichen).

Die Klebstoff - Zeichen werden gepflückt , so dass die Zeichenfolge ich mache , ist ein gültiger Python - Ausdruck , wenn und nur wenn jedes zweites Zeichen aus vier Ausbeuten ein gültiges Klammer-string nehmen.

Lynn
quelle
2

PHP, 149 Bytes

for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

Verwendet die gute alte Methode alle möglichen und dann Filter zu generieren. Verwenden Sie wie:

php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4
user59178
quelle
1

Python, 134 Bytes

from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

repl.it

Unbenannte Funktion, die eine Liste gültiger Längenzeichenfolgen zurückgibt n.
Formulare alle Längen nTupel der Charaktere *()[], so dass sie in Strings verbindet mit map(''.join,...)und Filter für diejenigen , die Klammern durch das Entfernen der „Paare“ ausgeglichen hat "*", "()"und "[]"wiederum nZeiten und überprüfen, ob das Ergebnis ist eine leere Zeichenfolge ( nZeiten sind übertrieben, vor allem für "*"aber ist Golfspieler).

Jonathan Allan
quelle
1

Netzhaut , 78 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

Probieren Sie es online!

Erläuterung

Ich generiere alle möglichen Zeichenfolgen der Länge 5 und filtere dann die ungültigen heraus.

.+
$*

Dies wandelt die Eingabe in eine unäre um und verwendet sie 1als Ziffer.

+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

Dies ersetzt wiederholt ( +) das erste ( 1) in jeder Zeile ( %) in der Weise, dass fünf Kopien der Zeile erstellt werden, eine für jedes mögliche Zeichen. Dazu werden die Präfix- und Suffix-Ersetzungen verwendet $`und $'der Rest jeder Zeile erstellt.

Diese Schleife stoppt, wenn keine Einsen mehr zu ersetzen sind. Zu diesem Zeitpunkt haben wir alle möglichen Längenketten N, eine in jeder Zeile.

%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

Diese beiden Stufen werden für jede Zeile separat ausgeführt ( %). Die erste Stufe dupliziert einfach die Zeile mit einem ;, um die beiden Kopien zu trennen.

Die zweite Stufe ist ein andere Schleife ( +), die immer wieder entfernt [], ()oder *von der ersten Kopie des Strings, oder entfernt ein Semikolon am Anfang der Leitung (was nur möglich ist , nachdem die Saite vollständig verschwunden ist ).

A`;

Gültige Zeichenfolgen sind Zeichenfolgen, vor denen kein Semikolon mehr angezeigt wird. Wir verwerfen daher einfach alle Zeilen ( A), die ein Semikolon enthalten.

Martin Ender
quelle
Ich habe es online mit Eingabe 5 versucht: ok. Mit Eingabe 6 bekam ich eine Fehlerseite
edc65 30.11.16
@ edc65 Funktioniert für mich, aber natürlich ist dieser Ansatz nicht gerade effizient, daher dauert es einige Sekunden. Welche Art von Fehlerseite meinst du?
Martin Ender
Eingabe 5: Antwort in 3 Sek. Eingabe 6: Nach 7 Sekunden erhalte ich im Ausgabefeld die HTML-Quelle der wahrscheinlich Fehlerseite von meinem Proxy. Wenn es ein Timeout ist, dann ist es ein sehr kurzes Timeout ... Ich habe versucht, einen richtigen Testfall für Eingabe 6 zu erhalten, da meine Antwort bis Eingabe 5 in Ordnung zu sein scheint, aber für 6 oder mehr falsch
edc65 30.11.16
@ edc65 Es dauert definitiv länger als 7 Sekunden und TIOs Timeout beträgt eine Minute. Ich habe den Fehler, den Sie beschreiben, noch nie gesehen. Vielleicht lohnt es sich, ihn im TIO-Chat aufzurufen (oder wenn Sie Gitter oder GitHub bevorzugen ). Als Referenzausgabe erhalte ich für Eingabe 6 Folgendes : pastebin.com/WmmPPmrc (Eingabe 7 dauert mehr als eine Minute.)
Martin Ender
1

Python 3.5, 146 Bytes

import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

Sehr lang im Vergleich zu anderen Antworten, aber die kürzeste, die ich derzeit finden konnte. Sie hat die Form einer anonymen Lambda-Funktion und muss daher im Format aufgerufen werden

print(<Function Name>(<Integer>))

Gibt einen Python Satz von ungeordneten Strings , die alle möglichen spangen Saiten der Eingabelänge.

Wenn die obige Funktion beispielsweise benannt wird G, führt das Aufrufen G(3)zu der folgenden Ausgabe:

{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

Probieren Sie es online! (Ideone)


Wenn jedoch, wie ich, Sie die Dinge zu vereinfachen mit Einbauten nicht wirklich ein Fan von sind, dann hier ist meine eigene ursprüngliche Antwort nicht verwendet keine externen Bibliotheken Permutationen zu finden, und zur Zeit auf einem sattes steht 288 237 Bytes :

import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

Wie die konkurrierende Antwort hat auch diese die Form einer Lambda-Funktion und muss daher auch im Format aufgerufen werden

print(<Function Name>(<Integer>))

Und gibt eine Python- Liste mit unsortierten Zeichenfolgen aus, die alle geschweiften Zeichenfolgen der eingegebenen Länge darstellen. Wenn beispielsweise das Lambda als aufgerufen G(3)würde, wäre diesmal die Ausgabe wie folgt:

['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

Auch dies ist man auch viel schneller als meine andere Antwort, in der Lage , alle Klammer-Strings der Länge zu finden 11in etwa 115 Sekunden , die die Länge 10in etwa 19 Sekunden die der Länge, 9in etwa 4 Sekunden , und das die Länge 8in Auf meinem Computer dauert die Eingabe etwa 0,73 Sekunden , während meine konkurrierende Antwort bei einer Eingabe von deutlich länger als 115 Sekunden dauert 6.

Probieren Sie es online! (Ideone)

R. Kap
quelle
0

05AB1E, 23 Bytes

…[(*.∞sãʒ'*м„()„[]‚õ:õQ

Einige dieser Funktionen wurden möglicherweise implementiert, nachdem die Frage gestellt wurde. Anregungen sind willkommen!

Probieren Sie es online!

Wie?

…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string
Zacharý
quelle
Ich kenne 05AB1E nicht, aber könnte das nicht *auch im Entfernungs-Array sein? Und könnte der õQScheck durch so etwas wie NICHT ersetzt werden?
Esolanging Fruit
Der erste Vorschlag speichert keine Bytes: '*м„()„[]‚õ:vs „()„[]‚'*«õ:(nicht getestet), da kein Befehl zum Verketten von 3 Werten AFAIK vorhanden ist. Der zweite wird nicht funktionieren, da es kein NOT gibt, das so auf einer Saite funktioniert, AFAIK. (Wo AFAIK "soweit ich weiß" darstellt)
Zacharý