Twoim zadaniem będzie wzięcie zbalansowanego łańcucha i liczby całkowitej reprezentującej odległość Levenshteina (liczba znaków, które należy wstawić, usunąć lub zmienić, aby przekształcić jeden łańcuch w drugi) i musisz znaleźć liczbę zrównoważonych łańcuchów o tej odległości z oryginalnego ciągu (tj. sąsiedztwo tego ciągu).
Zastrzeżenia
Zrównoważone ciągi znaków będą się składały tylko z postaci
()<>[]{}
Zostaniesz poproszony o znalezienie dzielnic tylko dla pozytywnych, równych odległości
Wejście i wyjście jest elastyczne. Tak długo, jak pobierzesz wszystkie właściwe dane i podasz prawidłową odpowiedź bez naruszania jakichkolwiek luk, jestem zadowolony z twojej odpowiedzi.
Jeśli chcesz, możesz podzielić wszystkie liczby całkowite przez 2.
To jest golf golfowy, więc celem jest zminimalizowanie liczby bajtów w odpowiedzi
Inspiracją było to CMC i ta odpowiedź
Przypadki testowe
Case | Distance | Size of Neighborhood
--------------------------------------------
() | 2 | 18
({}) | 2 | 33
(()) | 2 | 32
<> | 4 | 186
[][] | 4 | 688
<(){}> | 4 | 1379
{} | 6 | 2270
[]{}[] | 6 | 41097
Oto kilka małych przykładów z faktycznymi okolicami:
(), 2 :
{'', '<>', '()[]', '()()', '(())', '([])', '()<>', '{}', '{()}', '<>()', '(){}', '{}()', '<()>', '(<>)', '[()]', '[]()', '({})', '[]'}
({}), 2 :
{'([]{})', '()', '{}', '<({})>', '({<>})', '<{}>', '({()})', '(<>{})', '({}<>)', '({[]})', '(({}))', '({{}})', '({}[])', '{({})}', '({})()', '{}({})', '(())', '()({})', '([])', '<>({})', '({}{})', '({}){}', '({})<>', '(<{}>)', '({})[]', '((){})', '[{}]', '{{}}', '[]({})', '(<>)', '({}())', '([{}])', '[({})]'}
(()), 2 :
{'(())[]', '<>(())', '()', '{}(())', '{()}', '({()})', '{(())}', '(([]))', '(({}))', '(()[])', '(())<>', '((()))', '([])', '((<>))', '()(())', '(<()>)', '([()])', '[(())]', '(()){}', '(())()', '(()())', '(<>())', '(()<>)', '((){})', '<(())>', '<()>', '([]())', '(<>)', '({}())', '[()]', '({})', '[](())'}
<>, 4 :
{'<><<>>', '(<>)<>', '[<>][]', '<<><>>', '(){<>}', '(<>)()', '[<()>]', '<({})>', '<>()<>', '<[<>]>', '[][]<>', '<>[]<>', '<><><>', '[]<{}>', '[]<<>>', '[]<><>', '{<><>}', '[{<>}]', '<(<>)>', '(())<>', '{}<>{}', '()(<>)', '{()<>}', '(())', '{<>{}}', '(<><>)', '([])<>', '[]<[]>', '<{}<>>', '<><()>', '{()}<>', '{{}}<>', '{<>()}', '<<>>()', '{<<>>}', '<()>()', '<[]>()', '<>[<>]', '(<>())', '{}<>()', '(()<>)', '[{}]', '{{}}', '[]()', '[(<>)]', '<{}[]>', '<<>>[]', '{}<()>', '<>', '[()]<>', '<()><>', '[[]]<>', '[{}]<>', '[]<>[]', '()[<>]', '[]<>()', '{<>}{}', '{<[]>}', '<>(<>)', '(<>)[]', '<{}>()', '{}<><>', '{<>}()', '{[]}', '{[]}<>', '<<<>>>', '[]<()>', '<<[]>>', '<<{}>>', '[[]]', '()()<>', '[]{<>}', '<><[]>', '[[]<>]', '<{}()>', '<{<>}>', '<[]{}>', '{}<{}>', '<{}>[]', '()<<>>', '(<()>)', '[]{}', '{{}<>}', '{}()', '()<>[]', '<{}><>', '{[<>]}', '<><{}>', '<(())>', '<><>{}', '[()]', '<<>>{}', '{}{}<>', '[<<>>]', '<[][]>', '(<<>>)', '<[]><>', '[<>]<>', '[<>[]]', '[{}<>]', '{()}', '{<>[]}', '[]{}<>', '{(<>)}', '(<[]>)', '()[]<>', '<>{<>}', '{[]<>}', '(<>{})', '({}<>)', '[<><>]', '<><>()', '{}[<>]', '<{[]}>', '<<()>>', '<<>{}>', '([<>])', '<[]()>', '()()', '([])', '[[<>]]', '((<>))', '[](<>)', '(){}<>', '[()<>]', '<([])>', '<()()>', '[][]', '<<>[]>', '[<[]>]', '({})<>', '<{{}}>', '<[{}]>', '<{}{}>', '{}(<>)', '<<>><>', '[<>()]', '[][<>]', '({})', '{}[]<>', '{}<[]>', '<[()]>', '()[]', '<()>[]', '{{<>}}', '(<>){}', '{}{}', '({<>})', '{<()>}', '{}{<>}', '[]()<>', '<[]>[]', '(<>[])', '<[]>{}', '{}()<>', '()<[]>', '()<{}>', '{}<<>>', '<{}>{}', '{}[]', '()<>{}', '<()<>>', '[<>{}]', '{<>}[]', '<<>()>', '<><>[]', '{<{}>}', '<()[]>', '()<><>', '[<>]()', '()<>()', '{}<>[]', '<{()}>', '(<{}>)', '(){}', '()<()>', '<(){}>', '{<>}<>', '<[[]]>', '[]<>{}', '([]<>)', '<[]<>>', '[<>]{}', '<()>{}', '<>{}<>', '[<{}>]'}
źródło
Odpowiedzi:
Mathematica,
187173 bajtówFunkcja czystej siły brutalnej.
#
reprezentuje pierwszy argument (ciąg początkowy) i#2
reprezentuje drugi argument (odległość).Characters@" ()[]<>{}"
to lista możliwych znaków (w tym" "
)Tuples[Characters@" ()[]<>{}",StringLength@#+#2]
to lista wszystkich krotek tych znaków o długości co najwyżej oryginalnej długości łańcucha plus odległość.Tuples[Characters@" ()[]<>{}",StringLength@#+#2]/." "->""
zastępuje wszystkie" "
znaki pustym ciągiem.""<>#&/@(...)
łączy wszystkie listy znaków w ciągi znaków.Następnie
Select
wszystkie takie ciągi, które są zrównoważone i które mają odpowiedniąEditDistance
funkcję z następującą funkcją:Następnie używamy
Union
do usuwania duplikatów i pobieraniaLength
.źródło