한 문제를 이틀에 걸쳐 살펴보도록 권장하는데, 그러기가 쉽지 않다.
이번 카타는 여우, 거위, 옥수수를 강 건너로 옮기는 유명한 문제다.
:you 가 없을 때 여우는 거위를, 거위는 옥수수를 먹어버리고, 강을 건너는 배에는 :you 가 하나만 가지고(데리고) 탈 수 있다. 안전하게 모두를 옮길 수 있는 순서를 찾으라는 문제다.
주어진 초기 상태는 [[:fox :goose :corn :you] [:boat] []] 로 표현되어 있다. 이쪽/배/건너쪽을 각각 벡터로 표현하고 전체를 다시 벡터로 묶어 놓았다.
구현할 함수는 (river-crossing-plan)인데, 변화하는 상태를 다시 벡터(혹은 리스트)로 묶어서 반환하면 된다.
[[[:fox :goose :corn :you] [:boat] []]
... <<-- 여기를 채워야 함
[[] [:boat] [:fox :goose :corn :you]]]
알고리즘을 표현하는 건 간단했다. 이런문제는 대개 bfs/dfs/backtrack으로 풀게 마련이다. 이 때 backtrack은 어려운 것이 다시 방문할 수 있다는 점이 걸린다. 그래서 이미 방문한 상태값을 기억해야 하는데 backtrack에서 이 상태마저 리셋되면 안되기 때문이다. 그러면 bfs의 방법이 남는데, 그러자면 다음 방문지를 queue에 쌓아둬야 한다.
(defn bfs [node seen? to-visit]
(cond (solved? node) node
(seen? node) (recur (first to-visit) seen (rest to-visit))
:else (recur node
(conj seen node)
(into to-visit (remove seen? (next-nodes node))))))
대충 위와 같다. 이 문제의 경우는 지나간 경로를 trace로 남겨야 하므로 node 대신 trace를 받아야 한다. to-visit 역시 다음 위치만이 아니라 다음 위치까지의 trace를 남겨야 한다. seen은 node만 가져도 된다.
대략 여기까지는 금방 뼈대를 잡았는데, next-nodes를 구하는 것이 쉽지 않았다. 규칙은 간단하다. :you가 여우/거위/옥수수를 가지고 이동하거나 :you만 이동할 수 있다는 것. (처음에는 이 규칙을 잘못이해하여 한번에 하나 즉, :you만 이동하거나 :you가 물건을 가져오거나 내려놓는 정도로도 될거라 생각했는데 그러면 올바른 해답을 구할 수 없었다.)
결국은 아래처럼 조금은 지저분해보이는 코드로 마무리 되었다.
클로져의 set을 함수로 보는 기능이 매우 편리했고, conj/disj 의 기능도 매우 편리했다. 하지만...
(defn search [trace seen to-visit]
(let [cur (last trace)]
(cond (end? cur) trace
(seen cur) (recur (first to-visit) seen (rest to-visit))
:else (recur trace (conj seen cur) (concat to-visit (next-moves trace seen))))))
위 함수에 등장하는 타입들을 적어보면...
이번 카타는 여우, 거위, 옥수수를 강 건너로 옮기는 유명한 문제다.
:you 가 없을 때 여우는 거위를, 거위는 옥수수를 먹어버리고, 강을 건너는 배에는 :you 가 하나만 가지고(데리고) 탈 수 있다. 안전하게 모두를 옮길 수 있는 순서를 찾으라는 문제다.
주어진 초기 상태는 [[:fox :goose :corn :you] [:boat] []] 로 표현되어 있다. 이쪽/배/건너쪽을 각각 벡터로 표현하고 전체를 다시 벡터로 묶어 놓았다.
구현할 함수는 (river-crossing-plan)인데, 변화하는 상태를 다시 벡터(혹은 리스트)로 묶어서 반환하면 된다.
[[[:fox :goose :corn :you] [:boat] []]
... <<-- 여기를 채워야 함
[[] [:boat] [:fox :goose :corn :you]]]
알고리즘을 표현하는 건 간단했다. 이런문제는 대개 bfs/dfs/backtrack으로 풀게 마련이다. 이 때 backtrack은 어려운 것이 다시 방문할 수 있다는 점이 걸린다. 그래서 이미 방문한 상태값을 기억해야 하는데 backtrack에서 이 상태마저 리셋되면 안되기 때문이다. 그러면 bfs의 방법이 남는데, 그러자면 다음 방문지를 queue에 쌓아둬야 한다.
(defn bfs [node seen? to-visit]
(cond (solved? node) node
(seen? node) (recur (first to-visit) seen (rest to-visit))
:else (recur node
(conj seen node)
(into to-visit (remove seen? (next-nodes node))))))
대충 위와 같다. 이 문제의 경우는 지나간 경로를 trace로 남겨야 하므로 node 대신 trace를 받아야 한다. to-visit 역시 다음 위치만이 아니라 다음 위치까지의 trace를 남겨야 한다. seen은 node만 가져도 된다.
대략 여기까지는 금방 뼈대를 잡았는데, next-nodes를 구하는 것이 쉽지 않았다. 규칙은 간단하다. :you가 여우/거위/옥수수를 가지고 이동하거나 :you만 이동할 수 있다는 것. (처음에는 이 규칙을 잘못이해하여 한번에 하나 즉, :you만 이동하거나 :you가 물건을 가져오거나 내려놓는 정도로도 될거라 생각했는데 그러면 올바른 해답을 구할 수 없었다.)
결국은 아래처럼 조금은 지저분해보이는 코드로 마무리 되었다.
클로져의 set을 함수로 보는 기능이 매우 편리했고, conj/disj 의 기능도 매우 편리했다. 하지만...
(defn search [trace seen to-visit]
(let [cur (last trace)]
(cond (end? cur) trace
(seen cur) (recur (first to-visit) seen (rest to-visit))
:else (recur trace (conj seen cur) (concat to-visit (next-moves trace seen))))))
위 함수에 등장하는 타입들을 적어보면...
- trace 는 vector
- seen 은 set
- to-visit 은 list
그리고 trace가 담는 node/state는 다시 set의 vector이다. 이렇게 set/vector/list를 모두 사용하게 되니 매우 조심스러워지고 런타임 오류가 나는일이 많았다. 아직은 디버거에 익숙하지 않아 print에 의존하니 쉽지도 않고..
타입이 맞지 않아 발생하는 런타임 오류는 결국 해결하게는 되지만 그 과정이 매우 번거롭다.
예를 들어 (into ...)는 첫 인자의 타입을 유지해주지만 (concat)은 결과는 비슷해도 vector 두개를 붙여서 결과가 lazy sequence (list처럼 동작하는)가 되어버린다. map/filter를 거쳐도 vector가 lazy sequence가 되어버린다.
(apply conj a other)로 이어붙이는 실수도 있었는데, 이 경우 other가 비어있으면 런타임 오류가 난다.
5주-1일차에는 이문제를 이어가되 Core Logic을 알아보라고 힌트를 던져놓았다. 이건 아마도 Prolog스타일을 지원할 것 같은데, 이문제는 어떻게 풀수 있을까? 그건 다음주에 계속~
댓글 없음:
댓글 쓰기