Su tarea será tomar una cadena equilibrada y un número entero que represente una distancia de Levenshtein (el número de caracteres que deben insertarse, eliminarse o cambiarse para convertir una cadena en otra) y debe encontrar el número de cadenas equilibradas con esa distancia de la cadena original (es decir, la vecindad de esa cadena).
Estipulaciones
Las cadenas equilibradas consistirán solo en los caracteres
()<>[]{}
Solo se le pedirá que encuentre vecindarios para distancias pares positivas
La entrada y salida es flexible. Siempre que tome todos los datos correctos y envíe la respuesta correcta sin violar ninguna laguna, estoy contento con su respuesta.
Puede elegir dividir todas sus entradas enteras entre 2 si lo desea.
Este es el código de golf, por lo que el objetivo es minimizar el número de bytes en su respuesta
Esto fue inspirado por este CMC y esta respuesta
Casos de prueba
Case | Distance | Size of Neighborhood
--------------------------------------------
() | 2 | 18
({}) | 2 | 33
(()) | 2 | 32
<> | 4 | 186
[][] | 4 | 688
<(){}> | 4 | 1379
{} | 6 | 2270
[]{}[] | 6 | 41097
Aquí hay algunos pequeños ejemplos con los vecindarios reales incluidos:
(), 2 :
{'', '<>', '()[]', '()()', '(())', '([])', '()<>', '{}', '{()}', '<>()', '(){}', '{}()', '<()>', '(<>)', '[()]', '[]()', '({})', '[]'}
({}), 2 :
{'([]{})', '()', '{}', '<({})>', '({<>})', '<{}>', '({()})', '(<>{})', '({}<>)', '({[]})', '(({}))', '({{}})', '({}[])', '{({})}', '({})()', '{}({})', '(())', '()({})', '([])', '<>({})', '({}{})', '({}){}', '({})<>', '(<{}>)', '({})[]', '((){})', '[{}]', '{{}}', '[]({})', '(<>)', '({}())', '([{}])', '[({})]'}
(()), 2 :
{'(())[]', '<>(())', '()', '{}(())', '{()}', '({()})', '{(())}', '(([]))', '(({}))', '(()[])', '(())<>', '((()))', '([])', '((<>))', '()(())', '(<()>)', '([()])', '[(())]', '(()){}', '(())()', '(()())', '(<>())', '(()<>)', '((){})', '<(())>', '<()>', '([]())', '(<>)', '({}())', '[()]', '({})', '[](())'}
<>, 4 :
{'<><<>>', '(<>)<>', '[<>][]', '<<><>>', '(){<>}', '(<>)()', '[<()>]', '<({})>', '<>()<>', '<[<>]>', '[][]<>', '<>[]<>', '<><><>', '[]<{}>', '[]<<>>', '[]<><>', '{<><>}', '[{<>}]', '<(<>)>', '(())<>', '{}<>{}', '()(<>)', '{()<>}', '(())', '{<>{}}', '(<><>)', '([])<>', '[]<[]>', '<{}<>>', '<><()>', '{()}<>', '{{}}<>', '{<>()}', '<<>>()', '{<<>>}', '<()>()', '<[]>()', '<>[<>]', '(<>())', '{}<>()', '(()<>)', '[{}]', '{{}}', '[]()', '[(<>)]', '<{}[]>', '<<>>[]', '{}<()>', '<>', '[()]<>', '<()><>', '[[]]<>', '[{}]<>', '[]<>[]', '()[<>]', '[]<>()', '{<>}{}', '{<[]>}', '<>(<>)', '(<>)[]', '<{}>()', '{}<><>', '{<>}()', '{[]}', '{[]}<>', '<<<>>>', '[]<()>', '<<[]>>', '<<{}>>', '[[]]', '()()<>', '[]{<>}', '<><[]>', '[[]<>]', '<{}()>', '<{<>}>', '<[]{}>', '{}<{}>', '<{}>[]', '()<<>>', '(<()>)', '[]{}', '{{}<>}', '{}()', '()<>[]', '<{}><>', '{[<>]}', '<><{}>', '<(())>', '<><>{}', '[()]', '<<>>{}', '{}{}<>', '[<<>>]', '<[][]>', '(<<>>)', '<[]><>', '[<>]<>', '[<>[]]', '[{}<>]', '{()}', '{<>[]}', '[]{}<>', '{(<>)}', '(<[]>)', '()[]<>', '<>{<>}', '{[]<>}', '(<>{})', '({}<>)', '[<><>]', '<><>()', '{}[<>]', '<{[]}>', '<<()>>', '<<>{}>', '([<>])', '<[]()>', '()()', '([])', '[[<>]]', '((<>))', '[](<>)', '(){}<>', '[()<>]', '<([])>', '<()()>', '[][]', '<<>[]>', '[<[]>]', '({})<>', '<{{}}>', '<[{}]>', '<{}{}>', '{}(<>)', '<<>><>', '[<>()]', '[][<>]', '({})', '{}[]<>', '{}<[]>', '<[()]>', '()[]', '<()>[]', '{{<>}}', '(<>){}', '{}{}', '({<>})', '{<()>}', '{}{<>}', '[]()<>', '<[]>[]', '(<>[])', '<[]>{}', '{}()<>', '()<[]>', '()<{}>', '{}<<>>', '<{}>{}', '{}[]', '()<>{}', '<()<>>', '[<>{}]', '{<>}[]', '<<>()>', '<><>[]', '{<{}>}', '<()[]>', '()<><>', '[<>]()', '()<>()', '{}<>[]', '<{()}>', '(<{}>)', '(){}', '()<()>', '<(){}>', '{<>}<>', '<[[]]>', '[]<>{}', '([]<>)', '<[]<>>', '[<>]{}', '<()>{}', '<>{}<>', '[<{}>]'}
fuente
Respuestas:
Mathematica,
187173 bytesFuerza bruta función pura.
#
representa el primer argumento (cadena de inicio) y#2
representa el segundo argumento (distancia).Characters@" ()[]<>{}"
es la lista de posibles personajes (incluidos" "
)Tuples[Characters@" ()[]<>{}",StringLength@#+#2]
es la lista de todas las tuplas de esos caracteres con una longitud como máximo la longitud de la cadena original más la distancia.Tuples[Characters@" ()[]<>{}",StringLength@#+#2]/." "->""
reemplaza todos los" "
caracteres con la cadena vacía.""<>#&/@(...)
une todas esas listas de personajes en cadenas.A continuación, tenemos
Select
todas esas cadenas que están equilibradas y que tienen lo apropiadoEditDistance
con la siguiente función:A continuación, usamos
Union
para eliminar los duplicados y tomar elLength
.fuente