43 lines
3.8 KiB
Plaintext
43 lines
3.8 KiB
Plaintext
|
HW11 -- OPTIONAL (for your practice only -- solutions will be released on Tuesday)
|
||
|
|
|
||
|
|
Edit Distance (see updated final review solutions)
|
||
|
|
|
||
|
|
flip $ /nfs/farm/classes/eecs/fall2019/cs325-001/submit hw11 edit.py
|
||
|
|
|
||
|
|
Implement two functions:
|
||
|
|
* distance1(s, t): Viterbi-style (either top-down or bottom-up)
|
||
|
|
* distance2(s, t): Dijkstra-style (best-first)
|
||
|
|
|
||
|
|
For Dijkstra, you can use either heapdict or heapq (see review problem 7).
|
||
|
|
Given that this graph is extremely sparse (why?), heapq (ElogE) might be faster than heapdict (ElogV)
|
||
|
|
because the latter has overhead for hash.
|
||
|
|
|
||
|
|
They should return the same result (just return the edit distance).
|
||
|
|
|
||
|
|
We have 10 testcases (listed below); the first 5 test distance1(),
|
||
|
|
and the second 5 test distance2() on the same 5 string pairs.
|
||
|
|
|
||
|
|
My solutions (on flip2):
|
||
|
|
Testing Case 1 (open)... 0.001 s, Correct
|
||
|
|
Testing Case 2 (open)... 0.000 s, Correct
|
||
|
|
Testing Case 3 (open)... 0.012 s, Correct
|
||
|
|
Testing Case 4 (open)... 0.155 s, Correct
|
||
|
|
Testing Case 5 (open)... 0.112 s, Correct
|
||
|
|
Testing Case 6 (hidden)... 0.000 s, Correct
|
||
|
|
Testing Case 7 (hidden)... 0.000 s, Correct
|
||
|
|
Testing Case 8 (hidden)... 0.004 s, Correct
|
||
|
|
Testing Case 9 (hidden)... 0.009 s, Correct
|
||
|
|
Testing Case 10 (hidden)... 0.021 s, Correct
|
||
|
|
Total Time: 0.316 s
|
||
|
|
|
||
|
|
distance1("abcdefh", "abbcdfg") == 3
|
||
|
|
distance1("pretty", "prettier") == 3
|
||
|
|
distance1("aaaaaaadaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxaaaaaaaaaaaaaaaaaaaaaa") == 5
|
||
|
|
distance1('cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbxtwiqzvokqpkecyywrbvhlqgxzutdjfmvlhsezfbhfjbllmfhzlqlcwibubyyjupbwhztskyksfthkptxqlmhivfjbgclwsombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasomrhotoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwy', 'cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbtwiqzvokqpkecyywrbvhlqgxzutdjfmvlhsezfbhfjbllmfhzlqlcwibubyyjupbwhztskyksfthkptxqlmhivfbgclwsombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasonrhotoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwy') == 3
|
||
|
|
distance1('cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbtwiqzvokqpasdfkecyywrbvhlqgxzutdjfmvlhsezfbhbllmfhzlqlcwibubyyjupbwhztsxyksfthkptxqlmhivfjbgclhombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasomrttoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwydmbihjkvziitusmkjljrsbafytsinql', 'cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbtwiqzvokqpkecyywrbvhlqgxzutdjfmvlhsezfbhfjbllmfhzlqlcwibubyyjupbwhztskyksfthkptxqlmhivfjbgclwsombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasomrhotoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwydmbihjkvziitusmkjljrsbafytsinql') == 11
|
||
|
|
distance2("abcdefh", "abbcdfg") == 3
|
||
|
|
distance2("pretty", "prettier") == 3
|
||
|
|
distance2("aaaaaaadaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxaaaaaaaaaaaaaaaaaaaaaa") == 5
|
||
|
|
distance2('cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbxtwiqzvokqpkecyywrbvhlqgxzutdjfmvlhsezfbhfjbllmfhzlqlcwibubyyjupbwhztskyksfthkptxqlmhivfjbgclwsombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasomrhotoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwy', 'cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbtwiqzvokqpkecyywrbvhlqgxzutdjfmvlhsezfbhfjbllmfhzlqlcwibubyyjupbwhztskyksfthkptxqlmhivfbgclwsombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasonrhotoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwy') == 3
|
||
|
|
distance2('cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbtwiqzvokqpasdfkecyywrbvhlqgxzutdjfmvlhsezfbhbllmfhzlqlcwibubyyjupbwhztsxyksfthkptxqlmhivfjbgclhombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasomrttoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwydmbihjkvziitusmkjljrsbafytsinql', 'cpuyedzrwcbritzclzhwwabmlyresvewkdxwkamyzbtwiqzvokqpkecyywrbvhlqgxzutdjfmvlhsezfbhfjbllmfhzlqlcwibubyyjupbwhztskyksfthkptxqlmhivfjbgclwsombvytdztapwpzmdqfwwrhqsgztobeuiatcwmrzfbwhfnpzzasomrhotoqiwvexlgxsnafiagfewmopdzwanxswfsmbxsmsczbwsgnwydmbihjkvziitusmkjljrsbafytsinql') == 11
|