이번 문제는 같은 길이의 단어로 구성되어있는 사전에서, 한 단어에서 다른 단어로 한 글자씩 바꿔가며 변형해 나가는 과정을 알아내는 것이 과제이다.
심화문제에서 최단/최장 경로를 구하는 것까지 나와서, 처음에는 사전 데이터를 그래프로 구성하려고 했다. 그러면 기존의 알고리즘을 이용해 경로를 찾아내기 수월할 테니. 그러나, 수천 개에 달하는 사전데이터를 그래프로 구성하는데 예상보다 시간이 많이 걸렸고, 이걸 최적화 해보겠다고 삽질하다가, 방법을 선회해야만 했다.
1. 미리 존재하는 파일로부터 사전을 구성한다. read_dic/1
2. 주어진 단어 A, B로 부터 중간단어를 하나씩 구한다. replace_word/3
3. 중간단어가 사전에 존재하는지 확인하고, 존재한다면 결과에 저장하고 그렇지 않으면 다음 순서의 중간단어를 구해서 2의 과정을 반복한다. find_path/6
4. 마지막의 중간단어가 B와 동일하면 경로를 구한 것이고, 그렇지 않으면 해당하는 경로가 존재하지 않는 것이다.
5. 단어 A, B의 길이가 다르면, word_length_mismatch를 반환하고, 4자리나 5자리 단어가 아니면, no_dictionary_exist를 반환한다. find_path/2
6. 각 사전은 word4.txt와 word5.txt로 존재한다고 가정한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
-module(insight). -export([find_path/2]). % compose dictionary from file load_dic(Filename) -> {ok, File} = file:open(Filename, [read]), try read_line(File, []) after file:close(File) end. read_line(File, L) -> case io:get_line(File, "") of eof -> L; Word -> NewWord = re:replace(Word, "\n", "", [global, {return, list}]), read_line(File, [NewWord | L]) end. % replace character from From of index Index to To of index Index replace_word(From, To, Index) -> {Result, _} = lists:mapfoldl( fun(Elm, Idx) -> case Idx of Index -> {lists:nth(Idx, To), Idx + 1}; _ -> {Elm, Idx + 1} end end, 1, From), Result. find_path(_, _, _, _, 0, Acc) -> % failed to find path lists:reverse([impossible | Acc]); % find path successfully find_path(_, _, LastWord, LastWord, _, [LastWord | T]) -> lists:reverse([LastWord | T]); % skip if NewFrom is equal to LastWord find_path(Dic, _, LastWord, To, Index, [LastWord | T]) -> NewIndex = Index - 1, NewFrom = replace_word(LastWord, To, NewIndex), find_path(Dic, LastWord, NewFrom, To, NewIndex, [LastWord | T]); find_path(Dic, PrevFrom, From, To, Index, Acc) -> case lists:member(From, Dic) of true -> NewIndex = length(From), NewFrom = replace_word(From, To, NewIndex), NewAcc = [From | Acc]; false -> NewIndex = Index - 1, NewFrom = replace_word(PrevFrom, To, NewIndex), NewAcc = Acc end, find_path(Dic, PrevFrom, NewFrom, To, NewIndex, NewAcc). find_path(From, To) when length(From) /= length(To) -> word_length_mismatched; find_path(From, To) when length(From) == 4 -> find_path(load_dic("word4.txt"), From, From, To, 4, []); find_path(From, To) when length(From) == 5 -> find_path(load_dic("word5.txt"), From, From, To, 5, []); find_path(_, _) -> no_dictionary_exist. |
출력예
74> insight:find_path("wean", "zein").
["wean",impossible]
75> insight:find_path("damp", "like").
["damp","dame","dime","dike","like"]
76> insight:find_path("damp", "damp2").
word_length_mismatched
77> insight:find_path("damp", "damp").
["damp"]