-module(p2_2).
-compile(export_all).
-include_lib("eunit/include/eunit.hrl").
두 단어가 주어지면 첫 단어를 한 번에 한 문자씩만 다른 단어로 바꾸는 것을 반복하여 두 번째 단어를 만드는 과정을 출력하는 문제이다. 입력으로는 사전 파일과 단어 두 개가 주어진다.
우선 사전 파일에서 단어를 읽는다.
read_words(FileName) ->
{ok, Device} = file:open(FileName, [read]),
get_all_lines_as_word(Device, []).
get_all_lines_as_word(Device, Words) ->
case io:get_line(Device, "") of
eof -> file:close(Device), lists:reverse(Words);
Line ->
Word = string:strip(string:strip(Line, right, $\r), right, $\n),
get_all_lines_as_word(Device, [Word|Words])
end.어떤 단어가 주어졌을 때 한 글자만 바꾸어서 만들 수 있는 단어를 알아야 한다. 두 단어가 주어졌을 때 두 단어가 몇 글자 다른지 알아낸다. 이를 이용해 전체 단어 중에서 한 글자만 다른 이웃 단어들을 구한다.
word_distance(W1, W2) ->
lists:sum(lists:map(fun({C1, C2}) ->
if C1 =:= C2 -> 0 ; true -> 1 end
end,
lists:zip(W1, W2))).
word_distance_test_() ->
[?_assertMatch(0, word_distance("aaa", "aaa")),
?_assertMatch(1, word_distance("aaa", "aab")),
?_assertMatch(2, word_distance("aaa", "abc"))
].
neighbor_words(Word, Words) ->
lists:filter(fun(X) -> word_distance(Word, X) =:= 1 end, Words).
neighbor_words_test_() ->
[?_assertMatch([], neighbor_words("aaa", [])),
?_assertMatch(["aab", "baa"], neighbor_words("aaa", ["aaa", "aab", "baa"]))
].단어 두 개가 주어졌을 때 첫 단어를 시작점으로 하고, 한 글자씩 바꾸어서 두 번째 단어와 일치할 때까지 탐색하여 그 때까지의 경로를 구하면 된다. 간단한 깊이 우선 탐색으로 경로를 구한다.
path_dfs(_Src, Dest, _Words, [[Dest|_]=Path|_]) ->
lists:reverse(Path);
path_dfs(_Src, _Dest, _Words, []) ->
[];
path_dfs(Src, Dest, Words, [Path|Remaining]) ->
[H|L] = Path,
States = case lists:member(H, L) of
true -> Remaining;
_ -> lists:map(fun(N) -> [N|Path] end,
neighbor_words(H, Words)) ++ Remaining
end,
path_dfs(Src, Dest, Words, States).
path_dfs(Src, Dest, Words) ->
path_dfs(Src, Dest, Words, [[Src]]).
path_dfs_test_() ->
[?_assertMatch(["aaa"], path_dfs("aaa", "aaa", ["aaa", "aab"])),
?_assertMatch(["aaa", "aab"], path_dfs("aaa", "aab", ["aaa", "aab"])),
?_assertMatch([], path_dfs("aaa", "aac", ["aaa", "aab"])),
?_assertMatch(["aaa", "aba", "abc"], path_dfs("aaa", "abc", ["aaa", "aba", "abc"]))
].
path_dfs_example_test_() ->
[?_assertMatch(["aa", "ab", "ac", "cc"], path_dfs("aa", "cc", ["aa", "ab", "ac", "cc"])),
?_assertMatch([], path_dfs("aa", "ac", ["aa", "ab", "bc", "cc"])),
?_assertMatch(["aa", "ab", "bb", "bc", "cc"], path_dfs("aa", "cc", ["aa", "ab", "bb", "bc", "cc", "dd"]))
].위와 같이 깊이 우선 탐색으로 예로 주어진 "damp"에서 "like"까지 경로를 구하면 길이가 1581인 경로가 나온다.
심화문제 1. 가장 짧은 경로를 찾으려면 가까운 후보들부터 탐색하는 너비 우선 탐색을 해야 한다.
path_bfs(_Src, Dest, _Words, [[Dest|_]=Path|_]) ->
lists:reverse(Path);
path_bfs(_Src, _Dest, _Words, []) ->
[];
path_bfs(Src, Dest, Words, [Path|Remaining]) ->
[H|L] = Path,
States = case lists:member(H, L) of
true -> Remaining;
_ -> Remaining ++ lists:map(fun(N) -> [N|Path] end,
neighbor_words(H, Words))
end,
path_bfs(Src, Dest, Words, States).
path_bfs(Src, Dest, Words) ->
path_bfs(Src, Dest, Words, [[Src]]).
path_bfs_test_() ->
[?_assertMatch(["aaa"], path_bfs("aaa", "aaa", ["aaa", "aab"])),
?_assertMatch(["aaa", "aab"], path_bfs("aaa", "aab", ["aaa", "aab"])),
?_assertMatch([], path_bfs("aaa", "aac", ["aaa", "aab"])),
?_assertMatch(["aaa", "aba", "abc"], path_bfs("aaa", "abc", ["aaa", "aba", "abc"]))
].
path_bfs_example_test_() ->
[?_assertMatch(["aa", "ac", "cc"], path_bfs("aa", "cc", ["aa", "ab", "ac", "cc"])),
?_assertMatch([], path_bfs("aa", "ac", ["aa", "ab", "bc", "cc"])),
?_assertMatch(["aa", "ab", "bb", "bc", "cc"], path_bfs("aa", "cc", ["aa", "ab", "bb", "bc", "cc", "dd"]))
]."damp"에서 "like"까지의 가장 짧은 경로는 "damp","dame","dime","dike","like"로 길이는 4이다. 그런데 깊이 우선 탐색보다 실행 속도가 더 느리다. 이웃 단어들의 수가 많아서 그런 것 같다. 속도를 빠르게 하려면 가능성 없는 후보들은 방문하지 않도록 가지를 쳐야 한다. 처음 단어에서 멀리 떨어진 단어가 더 가까운 단어로 연결되어 있을 수도 있는데 이 경로를 택하면 최단 경로보다 무조건 길어지므로 더 이상 다음 단계들을 방문할 필요가 없다.
path_bfs_prune(_Src, Dest, _Words, [[Dest|_]=Path|_], _Breadcrumb) ->
lists:reverse(Path);
path_bfs_prune(_Src, _Dest, _Words, [], _Breadcrumb) ->
[];
path_bfs_prune(Src, Dest, Words, [Path|Remaining], Breadcrumb) ->
[H|L] = Path,
States = case lists:member(H, L) or lists:member(H, Breadcrumb) of
true -> Remaining;
_ -> Remaining ++ lists:map(fun(N) -> [N|Path] end,
neighbor_words(H, Words))
end,
path_bfs_prune(Src, Dest, Words, States, [H|Breadcrumb]).
path_bfs_prune(Src, Dest, Words) ->
path_bfs_prune(Src, Dest, Words, [[Src]], []).
path_bfs_prune_test_() ->
[?_assertMatch(["aaa"], path_bfs_prune("aaa", "aaa", ["aaa", "aab"])),
?_assertMatch(["aaa", "aab"], path_bfs_prune("aaa", "aab", ["aaa", "aab"])),
?_assertMatch([], path_bfs_prune("aaa", "aac", ["aaa", "aab"])),
?_assertMatch(["aaa", "aba", "abc"], path_bfs_prune("aaa", "abc", ["aaa", "aba", "abc"])),
?_assertMatch(["damp","dame","dime","dike","like"], path_bfs_prune("damp", "like", read_words("word4.txt")))
].
path_bfs_prune_example_test_() ->
[?_assertMatch(["aa", "ac", "cc"], path_bfs_prune("aa", "cc", ["aa", "ab", "ac", "cc"])),
?_assertMatch([], path_bfs_prune("aa", "ac", ["aa", "ab", "bc", "cc"])),
?_assertMatch(["aa", "ab", "bb", "bc", "cc"], path_bfs_prune("aa", "cc", ["aa", "ab", "bb", "bc", "cc", "dd"]))
].가지치기를 하지 않으면 30초 쯤 걸렸는데 가지치기를 하면 2초 정도면 최단 경로를 구할 수 있다.
심화문제 2. 가장 긴 경로를 찾으려면 모든 경로를 다 조사해서 가장 긴 경로를 찾아야 한다.
path_longest(_Src, _Dest, _Words, [], Longest) ->
lists:reverse(Longest);
path_longest(Src, Dest, Words, [[Dest|_]=Path|Remaining], Longest) ->
path_longest(Src, Dest, Words, Remaining,
case length(Path) > length(Longest) of
true -> Path;
_ -> Longest
end);
path_longest(Src, Dest, Words, [Path|Remaining], Longest) ->
[H|L] = Path,
States = case lists:member(H, L) of
true -> Remaining;
_ -> lists:map(fun(N) -> [N|Path] end,
neighbor_words(H, Words)) ++ Remaining
end,
path_longest(Src, Dest, Words, States, Longest).
path_longest(Src, Dest, Words) ->
path_longest(Src, Dest, Words, [[Src]], []).
path_longest_test_() ->
[?_assertMatch(["aaa"], path_longest("aaa", "aaa", ["aaa", "aab"])),
?_assertMatch(["aaa", "aab"], path_longest("aaa", "aab", ["aaa", "aab"])),
?_assertMatch([], path_longest("aaa", "aac", ["aaa", "aab"])),
?_assertMatch(["aaa", "aba", "abc"], path_longest("aaa", "abc", ["aaa", "aba", "abc"])),
?_assertMatch(["aa", "ab", "ac", "cc"], path_longest("aa", "cc", ["aa", "ab", "ac", "cc"]))
].모든 경로를 다 조사하려면 엄청난 시간이 필요하다. 하지만 탐색 대상을 줄일 수 있는 방법이 딱히 생각나지 않는다. 이웃 단어들을 찾는 시간을 줄여서 속도를 개선해봤지만 큰 효과는 없었다.
words_to_graph([], _, Graph) ->
Graph;
words_to_graph([H|L], All, Graph) ->
Neighbors = neighbor_words(H, All),
words_to_graph(L, All, gb_trees:enter(H, Neighbors, Graph)).
words_to_graph(Words) ->
words_to_graph(Words, Words, gb_trees:empty()).
words_to_graph_test_() ->
[?_assertMatch([{"aaa",["aab"]},
{"aab",["aaa"]}],
gb_trees:to_list(words_to_graph(["aaa", "aab"])))
].
path_longest_graph(_Src, _Dest, _Graph, [], Longest) ->
lists:reverse(Longest);
path_longest_graph(Src, Dest, Graph, [[Dest|_]=Path|Remaining], Longest) ->
path_longest_graph(Src, Dest, Graph, Remaining,
if length(Path) > length(Longest) -> Path ; true -> Longest end);
path_longest_graph(Src, Dest, Graph, [Path|Remaining], Longest) ->
[H|L] = Path,
States = case lists:member(H, L) of
true -> Remaining;
_ -> lists:map(fun(N) -> [N|Path] end,
gb_trees:get(H, Graph)) ++ Remaining
end,
path_longest_graph(Src, Dest, Graph, States, Longest).
path_longest_graph(Src, Dest, Words) ->
path_longest_graph(Src, Dest, words_to_graph(Words), [[Src]], []).
path_longest_graph_test_() ->
[?_assertMatch(["aaa"], path_longest_graph("aaa", "aaa", ["aaa", "aab"])),
?_assertMatch(["aaa", "aab"], path_longest_graph("aaa", "aab", ["aaa", "aab"])),
?_assertMatch([], path_longest_graph("aaa", "aac", ["aaa", "aab"])),
?_assertMatch(["aaa", "aba", "abc"], path_longest_graph("aaa", "abc", ["aaa", "aba", "abc"])),
?_assertMatch(["aa", "ab", "ac", "cc"], path_longest_graph("aa", "cc", ["aa", "ab", "ac", "cc"]))
].