Trouvez un quartier équilibré

10

Votre tâche sera de prendre une et un entier représentant une distance Levenshtein (le nombre de caractères qui doivent être insérés, supprimés ou modifiés pour transformer une chaîne en une autre) et vous devez trouver le nombre de chaînes équilibrées avec cette distance à partir de la chaîne d'origine (c'est-à-dire le voisinage de cette chaîne).

Stipulations

  • Les chaînes équilibrées se composeront uniquement des caractères ()<>[]{}

  • Il vous sera seulement demandé de trouver des quartiers pour des distances égales positives

  • L'entrée et la sortie sont flexibles. Tant que vous prenez toutes les données appropriées et que vous sortez la bonne réponse sans violer les lacunes, je suis satisfait de votre réponse.

  • Vous pouvez choisir de diviser toutes vos entrées entières par 2 si vous le souhaitez.

  • C'est du donc l'objectif est de minimiser le nombre d'octets dans votre réponse

Cela a été inspiré par ce CMC et cette réponse

Cas de test

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

Voici quelques petits exemples avec les quartiers réels inclus:

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

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

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

<>, 4 :
{'<><<>>', '(<>)<>', '[<>][]', '<<><>>', '(){<>}', '(<>)()', '[<()>]', '<({})>', '<>()<>', '<[<>]>', '[][]<>', '<>[]<>', '<><><>', '[]<{}>', '[]<<>>', '[]<><>', '{<><>}', '[{<>}]', '<(<>)>', '(())<>', '{}<>{}', '()(<>)', '{()<>}', '(())', '{<>{}}', '(<><>)', '([])<>', '[]<[]>', '<{}<>>', '<><()>', '{()}<>', '{{}}<>', '{<>()}', '<<>>()', '{<<>>}', '<()>()', '<[]>()', '<>[<>]', '(<>())', '{}<>()', '(()<>)', '[{}]', '{{}}', '[]()', '[(<>)]', '<{}[]>', '<<>>[]', '{}<()>', '<>', '[()]<>', '<()><>', '[[]]<>', '[{}]<>', '[]<>[]', '()[<>]', '[]<>()', '{<>}{}', '{<[]>}', '<>(<>)', '(<>)[]', '<{}>()', '{}<><>', '{<>}()', '{[]}', '{[]}<>', '<<<>>>', '[]<()>', '<<[]>>', '<<{}>>', '[[]]', '()()<>', '[]{<>}', '<><[]>', '[[]<>]', '<{}()>', '<{<>}>', '<[]{}>', '{}<{}>', '<{}>[]', '()<<>>', '(<()>)', '[]{}', '{{}<>}', '{}()', '()<>[]', '<{}><>', '{[<>]}', '<><{}>', '<(())>', '<><>{}', '[()]', '<<>>{}', '{}{}<>', '[<<>>]', '<[][]>', '(<<>>)', '<[]><>', '[<>]<>', '[<>[]]', '[{}<>]', '{()}', '{<>[]}', '[]{}<>', '{(<>)}', '(<[]>)', '()[]<>', '<>{<>}', '{[]<>}', '(<>{})', '({}<>)', '[<><>]', '<><>()', '{}[<>]', '<{[]}>', '<<()>>', '<<>{}>', '([<>])', '<[]()>', '()()', '([])', '[[<>]]', '((<>))', '[](<>)', '(){}<>', '[()<>]', '<([])>', '<()()>', '[][]', '<<>[]>', '[<[]>]', '({})<>', '<{{}}>', '<[{}]>', '<{}{}>', '{}(<>)', '<<>><>', '[<>()]', '[][<>]', '({})', '{}[]<>', '{}<[]>', '<[()]>', '()[]', '<()>[]', '{{<>}}', '(<>){}', '{}{}', '({<>})', '{<()>}', '{}{<>}', '[]()<>', '<[]>[]', '(<>[])', '<[]>{}', '{}()<>', '()<[]>', '()<{}>', '{}<<>>', '<{}>{}', '{}[]', '()<>{}', '<()<>>', '[<>{}]', '{<>}[]', '<<>()>', '<><>[]', '{<{}>}', '<()[]>', '()<><>', '[<>]()', '()<>()', '{}<>[]', '<{()}>', '(<{}>)', '(){}', '()<()>', '<(){}>', '{<>}<>', '<[[]]>', '[]<>{}', '([]<>)', '<[]<>>', '[<>]{}', '<()>{}', '<>{}<>', '[<{}>]'}
Ad Hoc Garf Hunter
la source
2
Vous essayez de faire un forceur brutal Brain-Flak? : D
mbomb007
@ mbomb007 J'ai pris en compte tous vos conseils. Merci pour l'aide!
Ad Hoc Garf Hunter
Connexe >: D
mbomb007
En relation.
Martin Ender

Réponses:

3

Mathematica, 187 173 octets

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

Fonction pure de la force brute. #représente le premier argument (chaîne de départ) et #2représente le deuxième argument (distance).

Characters@" ()[]<>{}"est la liste des caractères possibles (y compris " ")

Tuples[Characters@" ()[]<>{}",StringLength@#+#2] est la liste de tous les tuples de ces caractères dont la longueur correspond au maximum à la longueur de la chaîne d'origine plus la distance.

Tuples[Characters@" ()[]<>{}",StringLength@#+#2]/." "->""remplace tous les " "caractères par la chaîne vide.

""<>#&/@(...) joint toutes ces listes de caractères en chaînes.

Ensuite, nous avons Selecttoutes ces chaînes qui sont équilibrées et qui ont la fonction appropriée EditDistanceavec la fonction suivante:

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

Ensuite, nous utilisons Unionpour supprimer les doublons et prendre le Length.

ngenisis
la source