이번 문제는 같은 길이의 단어로 구성되어있는 사전에서, 한 단어에서 다른 단어로 한 글자씩 바꿔가며 변형해 나가는 과정을 알아내는 것이 과제이다.

심화문제에서 최단/최장 경로를 구하는 것까지 나와서, 처음에는 사전 데이터를 그래프로 구성하려고 했다. 그러면 기존의 알고리즘을 이용해 경로를 찾아내기 수월할 테니. 그러나, 수천 개에 달하는 사전데이터를 그래프로 구성하는데 예상보다 시간이 많이 걸렸고, 이걸 최적화 해보겠다고 삽질하다가, 방법을 선회해야만 했다.

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로 존재한다고 가정한다.

출력예

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"]

문제는 인사이트의 블로그에서 확인할 수 있듯이,
팩토리얼(!)의 결과값에서, 마지막에 연속되는 0의 개수와 0이 아닌 첫번째 숫자를 알아내는 것이다.

사실, 이전 문제를 낑낑대며 풀고, 다른 사람들의 풀이 법을 보니, 완전 삽질했구나 싶었다. 더구나 이미 얼랭을 사용한 사람이 있다니…OTL

그러나 이건 좀 쉽다! 한 15분 걸린 것 같다. Erlang도 조금 익숙해 졌고…

1. 팩토리얼식의 각 값을 순차적으로 곱한다. last/1
1.1 1의 과정 중, 마지막 0의 수를 세어 누적한다. countzero/1
1.2 1의 과정 중, 0이 아닌 마지막 수를 다음 곱셈에 사용하고, 나머지 숫자는 버린다.

출력예

Eshell V5.9.1  (abort with ^G)
1> c(insight2).
{ok,insight2}
2> insight2:last(1).
{0,1}
3> insight2:last(10).
{2,8}
4> insight2:last(100).
{24,6}
5> insight2:last(2012).
{490,2}
6> insight2:last(10000).
{2444,2}
7> 

구독하던 인사이트 출판사 블로그에서 이벤트를 하는 것을 발견하고, 간만에 알고리즘 문제에 도전~

문제는 블로그에서 확인할 수 있듯이, 주어진 집합을 하나이상의 집합으로 나누는 모든 방법을 출력하는 것이다.

뭔가, 효율적으로 이를 구하는 방법이 존재할 것 같아서 계속 고민해 봤으나, 원초적인 알고리즘을 만드는 일을 수학자가 할 일이라고 생각해서, 그냥 딱 떠오르는 방법으로 코딩 해 버렸다.

1. 입력 받은 N으로 리스트를 집합을 구한다. makelist/1
2. 1에서 만든 집합에서, 가능한 모든 부분집합을 구한다. subsets/1
3. 2에서 구한 부분집합의 조합 중, 각 원소가 한 개씩만 존재하는 조합만 고른다. combinations/1

평소 사용하던 언어로 하는 것은 시시할 것 같아, 도무지 사용할 일이 없을 것 같았던 Erlang으로 시도. 머리가 더 아팠다.

출력예

1> c(insight).
{ok,insight}
2> insight:combinations(3).
[[0],[1],[2]]
[[0,1],[2]]
[[0,2],[1]]
[[0],[1,2]]
[[0,1,2]]
ok
3> insight:combinations(4).
[[0],[1],[2],[3]]
[[0,1],[2],[3]]
[[0,2],[1],[3]]
[[0],[1,2],[3]]
[[0,1,2],[3]]
[[0,3],[1],[2]]
[[0],[1,3],[2]]
[[0,1,3],[2]]
[[0],[1],[2,3]]
[[0,1],[2,3]]
[[0,2,3],[1]]
[[0,2],[1,3]]
[[0,3],[1,2]]
[[0],[1,2,3]]
[[0,1,2,3]]
ok
4>

중요: Erlang은 인사이트의 책으로 처음 배웠다.