Temukan Lingkungan yang seimbang

10

Tugas Anda adalah mengambil dan integer yang mewakili jarak Levenshtein (jumlah karakter yang harus dimasukkan, dihapus, atau diubah untuk membuat satu string menjadi string lain) dan Anda harus menemukan jumlah string seimbang dengan jarak itu dari string asli (yaitu lingkungan dari string itu).

Ketentuan

  • String seimbang hanya akan terdiri dari karakter ()<>[]{}

  • Anda hanya akan diminta menemukan lingkungan untuk jarak genap positif

  • Input dan output fleksibel. Selama Anda mengambil semua data yang tepat dan menampilkan jawaban yang benar tanpa melanggar celah apa pun, saya senang dengan jawaban Anda.

  • Anda dapat memilih untuk membagi semua input integer Anda dengan 2 jika Anda mau.

  • Ini adalah sehingga tujuannya adalah untuk meminimalkan jumlah byte dalam jawaban Anda

Ini terinspirasi oleh CMC ini dan jawaban ini

Testcases

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

Berikut adalah beberapa contoh kecil dengan lingkungan sebenarnya termasuk:

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

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

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

<>, 4 :
{'<><<>>', '(<>)<>', '[<>][]', '<<><>>', '(){<>}', '(<>)()', '[<()>]', '<({})>', '<>()<>', '<[<>]>', '[][]<>', '<>[]<>', '<><><>', '[]<{}>', '[]<<>>', '[]<><>', '{<><>}', '[{<>}]', '<(<>)>', '(())<>', '{}<>{}', '()(<>)', '{()<>}', '(())', '{<>{}}', '(<><>)', '([])<>', '[]<[]>', '<{}<>>', '<><()>', '{()}<>', '{{}}<>', '{<>()}', '<<>>()', '{<<>>}', '<()>()', '<[]>()', '<>[<>]', '(<>())', '{}<>()', '(()<>)', '[{}]', '{{}}', '[]()', '[(<>)]', '<{}[]>', '<<>>[]', '{}<()>', '<>', '[()]<>', '<()><>', '[[]]<>', '[{}]<>', '[]<>[]', '()[<>]', '[]<>()', '{<>}{}', '{<[]>}', '<>(<>)', '(<>)[]', '<{}>()', '{}<><>', '{<>}()', '{[]}', '{[]}<>', '<<<>>>', '[]<()>', '<<[]>>', '<<{}>>', '[[]]', '()()<>', '[]{<>}', '<><[]>', '[[]<>]', '<{}()>', '<{<>}>', '<[]{}>', '{}<{}>', '<{}>[]', '()<<>>', '(<()>)', '[]{}', '{{}<>}', '{}()', '()<>[]', '<{}><>', '{[<>]}', '<><{}>', '<(())>', '<><>{}', '[()]', '<<>>{}', '{}{}<>', '[<<>>]', '<[][]>', '(<<>>)', '<[]><>', '[<>]<>', '[<>[]]', '[{}<>]', '{()}', '{<>[]}', '[]{}<>', '{(<>)}', '(<[]>)', '()[]<>', '<>{<>}', '{[]<>}', '(<>{})', '({}<>)', '[<><>]', '<><>()', '{}[<>]', '<{[]}>', '<<()>>', '<<>{}>', '([<>])', '<[]()>', '()()', '([])', '[[<>]]', '((<>))', '[](<>)', '(){}<>', '[()<>]', '<([])>', '<()()>', '[][]', '<<>[]>', '[<[]>]', '({})<>', '<{{}}>', '<[{}]>', '<{}{}>', '{}(<>)', '<<>><>', '[<>()]', '[][<>]', '({})', '{}[]<>', '{}<[]>', '<[()]>', '()[]', '<()>[]', '{{<>}}', '(<>){}', '{}{}', '({<>})', '{<()>}', '{}{<>}', '[]()<>', '<[]>[]', '(<>[])', '<[]>{}', '{}()<>', '()<[]>', '()<{}>', '{}<<>>', '<{}>{}', '{}[]', '()<>{}', '<()<>>', '[<>{}]', '{<>}[]', '<<>()>', '<><>[]', '{<{}>}', '<()[]>', '()<><>', '[<>]()', '()<>()', '{}<>[]', '<{()}>', '(<{}>)', '(){}', '()<()>', '<(){}>', '{<>}<>', '<[[]]>', '[]<>{}', '([]<>)', '<[]<>>', '[<>]{}', '<()>{}', '<>{}<>', '[<{}>]'}
Ad Hoc Garf Hunter
sumber
2
Mencoba membuat brute-forcer Brain-Flak? : D
mbomb007
@ mbomb007 Saya telah memperhitungkan semua saran Anda. Terima kasih untuk bantuannya!
Ad Hoc Garf Hunter
Terkait >: D
mbomb007
Terkait
Martin Ender

Jawaban:

3

Mathematica, 187 173 byte

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

Brute force fungsi murni. #mewakili argumen pertama (string awal) dan #2mewakili argumen kedua (jarak).

Characters@" ()[]<>{}"adalah daftar karakter yang mungkin (termasuk " ")

Tuples[Characters@" ()[]<>{}",StringLength@#+#2] adalah daftar semua tuple dari karakter-karakter dengan panjang paling banyak panjang string asli ditambah jarak.

Tuples[Characters@" ()[]<>{}",StringLength@#+#2]/." "->""mengganti semua " "karakter dengan string kosong.

""<>#&/@(...) bergabung dengan semua daftar karakter tersebut menjadi string.

Selanjutnya kita Selectsemua string yang seimbang dan yang sesuai EditDistancedengan fungsi sebagai berikut:

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

Selanjutnya kita gunakan Unionuntuk menghapus duplikat dan mengambil Length.

ngenisis
sumber