Finde eine ausgeglichene Nachbarschaft

10

Ihre Aufgabe besteht darin, eine und eine Ganzzahl zu verwenden, die einen Levenshtein-Abstand darstellen (die Anzahl der Zeichen, die eingefügt, gelöscht oder geändert werden müssen, um eine Zeichenfolge in eine andere zu verwandeln), und Sie müssen die Anzahl der ausgeglichenen Zeichenfolgen mit diesem Abstand ermitteln von der ursprünglichen Zeichenfolge (dh der Nachbarschaft dieser Zeichenfolge).

Bestimmungen

  • Ausgewogene Zeichenfolgen bestehen nur aus den Zeichen ()<>[]{}

  • Sie werden nur gebeten, Nachbarschaften für positive, gleichmäßige Entfernungen zu finden

  • Ein- und Ausgabe ist flexibel. Solange Sie alle richtigen Daten aufnehmen und die richtige Antwort ausgeben, ohne Lücken zu verletzen, bin ich mit Ihrer Antwort zufrieden.

  • Sie können alle Ihre ganzzahligen Eingaben durch 2 teilen, wenn Sie möchten.

  • Dies ist daher besteht das Ziel darin, die Anzahl der Bytes in Ihrer Antwort zu minimieren

Dies wurde von dieser CMC und dieser Antwort inspiriert

Testfälle

   Case   | Distance | Size of Neighborhood
--------------------------------------------
    ()    |    2     |         18
   ({})   |    2     |         33
   (())   |    2     |         32
    <>    |    4     |        186
   [][]   |    4     |        688
  <(){}>  |    4     |        1379
    {}    |    6     |        2270
  []{}[]  |    6     |        41097

Hier sind einige kleine Beispiele mit den tatsächlichen Nachbarschaften:

(), 2 :
{'', '<>', '()[]', '()()', '(())', '([])', '()<>', '{}', '{()}', '<>()', '(){}', '{}()', '<()>', '(<>)', '[()]', '[]()', '({})', '[]'}

({}), 2 :
{'([]{})', '()', '{}', '<({})>', '({<>})', '<{}>', '({()})', '(<>{})', '({}<>)', '({[]})', '(({}))', '({{}})', '({}[])', '{({})}', '({})()', '{}({})', '(())', '()({})', '([])', '<>({})', '({}{})', '({}){}', '({})<>', '(<{}>)', '({})[]', '((){})', '[{}]', '{{}}', '[]({})', '(<>)', '({}())', '([{}])', '[({})]'}

(()), 2 :
{'(())[]', '<>(())', '()', '{}(())', '{()}', '({()})', '{(())}', '(([]))', '(({}))', '(()[])', '(())<>', '((()))', '([])', '((<>))', '()(())', '(<()>)', '([()])', '[(())]', '(()){}', '(())()', '(()())', '(<>())', '(()<>)', '((){})', '<(())>', '<()>', '([]())', '(<>)', '({}())', '[()]', '({})', '[](())'}

<>, 4 :
{'<><<>>', '(<>)<>', '[<>][]', '<<><>>', '(){<>}', '(<>)()', '[<()>]', '<({})>', '<>()<>', '<[<>]>', '[][]<>', '<>[]<>', '<><><>', '[]<{}>', '[]<<>>', '[]<><>', '{<><>}', '[{<>}]', '<(<>)>', '(())<>', '{}<>{}', '()(<>)', '{()<>}', '(())', '{<>{}}', '(<><>)', '([])<>', '[]<[]>', '<{}<>>', '<><()>', '{()}<>', '{{}}<>', '{<>()}', '<<>>()', '{<<>>}', '<()>()', '<[]>()', '<>[<>]', '(<>())', '{}<>()', '(()<>)', '[{}]', '{{}}', '[]()', '[(<>)]', '<{}[]>', '<<>>[]', '{}<()>', '<>', '[()]<>', '<()><>', '[[]]<>', '[{}]<>', '[]<>[]', '()[<>]', '[]<>()', '{<>}{}', '{<[]>}', '<>(<>)', '(<>)[]', '<{}>()', '{}<><>', '{<>}()', '{[]}', '{[]}<>', '<<<>>>', '[]<()>', '<<[]>>', '<<{}>>', '[[]]', '()()<>', '[]{<>}', '<><[]>', '[[]<>]', '<{}()>', '<{<>}>', '<[]{}>', '{}<{}>', '<{}>[]', '()<<>>', '(<()>)', '[]{}', '{{}<>}', '{}()', '()<>[]', '<{}><>', '{[<>]}', '<><{}>', '<(())>', '<><>{}', '[()]', '<<>>{}', '{}{}<>', '[<<>>]', '<[][]>', '(<<>>)', '<[]><>', '[<>]<>', '[<>[]]', '[{}<>]', '{()}', '{<>[]}', '[]{}<>', '{(<>)}', '(<[]>)', '()[]<>', '<>{<>}', '{[]<>}', '(<>{})', '({}<>)', '[<><>]', '<><>()', '{}[<>]', '<{[]}>', '<<()>>', '<<>{}>', '([<>])', '<[]()>', '()()', '([])', '[[<>]]', '((<>))', '[](<>)', '(){}<>', '[()<>]', '<([])>', '<()()>', '[][]', '<<>[]>', '[<[]>]', '({})<>', '<{{}}>', '<[{}]>', '<{}{}>', '{}(<>)', '<<>><>', '[<>()]', '[][<>]', '({})', '{}[]<>', '{}<[]>', '<[()]>', '()[]', '<()>[]', '{{<>}}', '(<>){}', '{}{}', '({<>})', '{<()>}', '{}{<>}', '[]()<>', '<[]>[]', '(<>[])', '<[]>{}', '{}()<>', '()<[]>', '()<{}>', '{}<<>>', '<{}>{}', '{}[]', '()<>{}', '<()<>>', '[<>{}]', '{<>}[]', '<<>()>', '<><>[]', '{<{}>}', '<()[]>', '()<><>', '[<>]()', '()<>()', '{}<>[]', '<{()}>', '(<{}>)', '(){}', '()<()>', '<(){}>', '{<>}<>', '<[[]]>', '[]<>{}', '([]<>)', '<[]<>>', '[<>]{}', '<()>{}', '<>{}<>', '[<{}>]'}
Ad-hoc-Garf-Jäger
quelle
2
Versuchen Sie, einen Brain-Flak-Brute-Forcer zu machen? : D
mbomb007
@ mbomb007 Ich habe alle Ihre Ratschläge berücksichtigt. Danke für die Hilfe!
Ad-hoc-Garf-Jäger
Verwandte >: D
mbomb007
Verbunden.
Martin Ender

Antworten:

3

Mathematica, 187 173 Bytes

Length@Union@Select[""<>#&/@(Tuples[Characters@" ()[]<>{}",StringLength@#+#2]/." "->""),sFixedPoint[StringReplace["()"|"[]"|"{}"|"<>":>""],s]==""&&EditDistance[s,#]==#2]&

Brute Force reine Funktion. #repräsentiert das erste Argument (Startzeichenfolge) und #2repräsentiert das zweite Argument (Abstand).

Characters@" ()[]<>{}"ist die Liste der möglichen Zeichen (einschließlich " ")

Tuples[Characters@" ()[]<>{}",StringLength@#+#2] ist die Liste aller Tupel dieser Zeichen mit einer Länge von höchstens der ursprünglichen Zeichenfolgenlänge plus dem Abstand.

Tuples[Characters@" ()[]<>{}",StringLength@#+#2]/." "->""Ersetzt alle " "Zeichen durch die leere Zeichenfolge.

""<>#&/@(...) fügt all diese Zeichenlisten zu Zeichenfolgen zusammen.

Als nächstes haben wir Selectalle solche Saiten, die ausgeglichen sind und die entsprechende EditDistancemit der folgenden Funktion haben:

s                                                                                                 String s
                                                                                                 maps to
  FixedPoint[StringReplace["()"|"[]"|"{}"|"<>":>""],s]                                              the fixed point of cancelling out pairs of brackets
                                                      ==                                             equals
                                                        ""                                          the empty string
                                                          &&                                        and
                                                            EditDistance[s,#]==#2                   the distance from s to # is #2

Als nächstes Unionlöschen wir die Duplikate und nehmen die Length.

Genisis
quelle