Living Clojure -- Week 5, Day 2 ~ Day 3

지난번 카타에서 Core Logic을 사용해보진 못했다. 숙제로 남겨놓고..
이번 카타는 더블릿(doublet)이란 단어 퍼즐이다.
사전의 단어들을 이용하여 주어진 두 단어를 연결하는 문제다. 두 단어를 연결하는 단어들 역시 사전에 있어야 하며 이웃한 단어들은 철자가 하나만 달라야 한다.

DOOR 와 LOCK 이란 단어가 있다면, DOOR -> BOOR -> BOOK -> LOOK -> LOCK 의 순서로 한번에 하나씩만 바꿔서 연결지을 수 있다.

BANK와 LOAN은, BANK -> BONK -> BOOK -> LOOK -> LOON -> LOAN 의 순서로 연결지을 수 있다.

그런데 이 문제는 Korean Clojure User Group에 누가 글을 오렸길래 미리 풀어봤다. 이전 카타와 마찬가지로 BFS(loop/recure)로 쉽게 풀리는 문제. 다만 풀어보는 중에 책에서 힌트라고 알려준 tree-seq 는 그것이 왜 힌트인지 잘 모르겠더라.

다시 생각해보면, bfs를 tree-seq로 쉽게 풀수 있지 않겠냐.. 라고 알려주는 것 같다. tree-seq는 tree구조로부터 seq를 만들어주는 adapter 함수이다. bfs는 사실 tree탐색 알고리즘이므로 bfs로 풀고자 하는 tree를 tree-seq로 접근하여 찾아라~ 라는 것이라고 짐작해보면서 이 문제는 일단 패스.

Living Clojure -- Week 4, Day 5 ~ Week 5, Day1

한 문제를 이틀에 걸쳐 살펴보도록 권장하는데, 그러기가 쉽지 않다.

이번 카타는 여우, 거위, 옥수수를 강 건너로 옮기는 유명한 문제다.
 :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스타일을 지원할 것 같은데, 이문제는 어떻게 풀수 있을까? 그건 다음주에 계속~

Living Clojure -- Week 4, Day 3 ~ Day 4

간단한 숫자/리스트 다루기 연습문제다.

6자리 수 중에 *2/*3/*4/*5/*6 한 것들이 모두 원래의 수랑 같은 숫자들로만 만들어진 하나의 수를 wonderland number라고 하고, 그것을 찾는 문제.

조건을 그대로 코드로 옮기기만 해도 충분하다.

(defn wonderland-number []
  (first (filter (fn [n]
           (and (hasAllTheSameDigits? n (* 2 n))
                (hasAllTheSameDigits? n (* 3 n))
                (hasAllTheSameDigits? n (* 4 n))
                (hasAllTheSameDigits? n (* 5 n))
                (hasAllTheSameDigits? n (* 6 n)))) (range 100000 999999))))

보너스 문제는 1000 이하의 수 중에서 자릿수 세제곱 합과 같은 수를 찾는 것이다. 역시 코드로 옮기기만 하면 된다.

(defn digits [n]
  (map #(- (int %) (int \0)) (str n)))
  
(def specialNumbersUnder1000
  (filter (fn [n]
            (= n (apply + (map (fn [d] (* d d d)) (digits n))))) (range 1 1000)))

뒤로 갈수록 문제들이 너무 단순해준다.

Living Clojure -- Week 4, Day 1

https://github.com/gigasquid/wonderland-clojure-katas 로 제공되는 코드를 베이스로 하여 문제를 푸는 것으로 형식이 바뀌었다.

1일차는 Alphabet Cipher 라고, 이상한 나라의 앨리스에 등장하는 암호화인 모양이다.

m :: Char -> Char -> Char 변환 맵과 key :: [Char] 변환 키 문자열이 주어졌을 때, encode :: [Char] -> [Char] 는 아래와 같이정의된다.

encode str = zipWith m (repeat key) str


테스트코드는 아래와 같이 주어졌고 이를 통과시키라는 문제다.

(ns alphabet-cipher.coder-test
  (:require [clojure.test :refer :all]
            [alphabet-cipher.coder :refer :all]))

(deftest test-encode
  (testing "can encode given a secret keyword"
    (is (= "hmkbxebpxpmyllyrxiiqtoltfgzzv"
           (encode "vigilance" "meetmeontuesdayeveningatseven")))
    (is (= "egsgqwtahuiljgs"
           (encode "scones" "meetmebythetree")))))

(deftest test-decode
  (testing "can decode an cyrpted message given a secret keyword"
    (is (= "meetmeontuesdayeveningatseven"
           (decode "vigilance" "hmkbxebpxpmyllyrxiiqtoltfgzzv")))
    (is (= "meetmebythetree"
           (decode "scones" "egsgqwtahuiljgs")))))

이 문제의 변환 맵은 아래와 같이 주어졌다.

   ABCDEFGHIJKLMNOPQRSTUVWXYZ
 A abcdefghijklmnopqrstuvwxyz
 B bcdefghijklmnopqrstuvwxyza
 C cdefghijklmnopqrstuvwxyzab
 D defghijklmnopqrstuvwxyzabc
 E efghijklmnopqrstuvwxyzabcd
 F fghijklmnopqrstuvwxyzabcde
 G ghijklmnopqrstuvwxyzabcdef
 H hijklmnopqrstuvwxyzabcdefg
 I ijklmnopqrstuvwxyzabcdefgh
 J jklmnopqrstuvwxyzabcdefghi
 K klmnopqrstuvwxyzabcdefghij
 L lmnopqrstuvwxyzabcdefghijk
 M mnopqrstuvwxyzabcdefghijkl
 N nopqrstuvwxyzabcdefghijklm
 O opqrstuvwxyzabcdefghijklmn
 P pqrstuvwxyzabcdefghijklmno
 Q qrstuvwxyzabcdefghijklmnop
 R rstuvwxyzabcdefghijklmnopq
 S stuvwxyzabcdefghijklmnopqr
 T tuvwxyzabcdefghijklmnopqrs
 U uvwxyzabcdefghijklmnopqrst
 V vwxyzabcdefghijklmnopqrstu
 W wxyzabcdefghijklmnopqrstuv
 X xyzabcdefghijklmnopqrstuvw
 Y yzabcdefghijklmnopqrstuvwx
 Z zabcdefghijklmnopqrstuvwxy

A = 0, B = 1, .. 이라고 보면 첫번째 값 + 두번째 값으로 매핑된다. 함수로 옮겨보면 아래와 같을 것이다.

(defn m [k c]
  (to-char (+ (to-int k) (to-int c))))

위의 haskell 코드 encode를 clojure로 옮겨보면,

(defn encode [key str]
 (apply str (map m (repeat key) str)))

decode는 반대로 동작하는 함수이다.

(defn decode [key str]
  (apply str (map rm (repeat key) str)))

여기서 rm을 새로 정의해야 한다.

c = a + b

위의 수식에서 a 와 c가 주어진 셈이므로.. b = c - a

(defn rm [k c]
  (to-char (- (to-int c) (to-int k))))

그런데 테스트코드를 보면 구현할 함수가 하나 더 있다.

(deftest test-decypher
  (testing "can extract the secret keyword given an cyrpted message and the original message"
    (is (= "vigilance"
           (decypher "opkyfipmfmwcvqoklyhxywgeecpvhelzg" "thequickbrownfoxjumpsoveralazydog")))
    (is (= "scones"
           (decypher "hcqxqqtqljmlzhwiivgbsapaiwcenmyu" "packmyboxwithfivedozenliquorjugs")))))


(decypher)는 암호화된 문장과 원래 문장을 주면 keystring 을 찾아주는 함수이다. c = a + b에서 c와 b를 줄테니 a를 찾으라는 것은 위의 rm과 마찬가지다. 자체로는 어려울 게 없는데, (repeat keystring) 으로 되어 있을 keystring의 반복 주기를 찾는 것이 핵심이다.

말하자면 "abcdabcdabc" 라는 문자열에서 "abcd" 를 찾는 것. 마구잡이 풀이로는 길이를 늘여가며 매치가 되는지 확인해볼 수 있을 것이다.

(defn unrepeat [str]
  (first (filter #(= str (repeat %)) (rest (inits str)))))

여기서 inits 는 "abc" 에서 ["", "a", "ab", "abc"] 를 반환하는 haskell의 inits와 같은 함수다.


구현 중 수정 사항!

• Clojure 에서 repeat 은 주어진 요소를 반복하는 것이며, sequence를 반복하는 것은 cycle이다. 따라서 unrepeat 대신 uncycle이 되어야~
• uncycle에서 무한 시퀀스를 문자열 혹은 유한 시퀀스랑 비교한 부분은 잘못되었다.
• prefix 를 비교하는 함수를 도입하거나
• 길이만큼 take n하고
• 비교 대상도 (seq s)로 변환해줘야 한다.
• uncycle은 시퀀스를 반환하므로 문자열로 변환해줘야 한다

Haskell에서는 문자열이 문자의 리스트이다. 따라서 문자열을 다루는 것이 일반적인 시퀀스 다루기와 다르지 않다. 그런데 Clojure는 문자열과 문자열로부터 얻은 문자 시퀀스가 다르기 때문에 (seq) (apply str) 등으로 명시적 변환이 있어야 (=) 비교를 할 수 있다.

아래는 최종 코드

Code Golf - 4Clojure 92번 문제

4Clojure 92번 문제는 Read Roman numerals.

로마표기수를 읽어들이는 함수를 작성하는 문제다.

(= 3999 (__ "MMMCMXCIX"))

빼기 표현에 주의해야 한다!

M = 1000
M = 1000
M = 1000
CM = 900  (C = -100, M = 1000)
XC = 90     (X = -10, C = 100)
IX = 9        (I = -1, X = 10)

(= 48 (__ "XLVIII"))

XL = 40  (X = -10, L = 50)

V = 5 

I = 1

I = 1

I = 1 

WWDC 2013년 공식 로고가 떠오른다. 

-- developer.apple.com에서

MMXIII = 2013

MM = 2000

X = 10

III = 3

일단 단순한 풀이는 빼기 규칙이 적용되느냐 아니냐를 결정하고 그런 다음 모두 더하는 것.

;; 130

(fn [roman]

  (let [m {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1}

        p (map (fn[a b]

                 (if (< (m a) (m b))

                   (- (m a))

                   (m a)))

               roman

               (rest roman))]

    (apply + (m (last roman)) p)))

이제 골프 시작~

zipmap은 keys와 vals로 map을 만드는 쉬운 방법이다. 그러나 이 경우는 코드가 더 길어진다.

기본적인 인라인으로 줄여보면,

;; 105

(fn [m r]

  (apply + 

         (m (last r))

         (map (fn [a b]

                (if (< (m a) (m b))

                  (- (m a))

                  (m a)))

              r

              (rest r)))) {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1}

m을 항상 적용하고 있으니 미리 적용시키면 될 것 같다.

;; 102

(comp

 (fn [r]

  (apply + 

         (last r)

         (map (fn [a b]

                (if (< a b)

                  (- a)

                  a))

              r

              (rest r)))) 

 #(map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1} %))

comp 이득이 없는 것 같아 다시 let 을 써 봤는데, 마찬가지. ㅠ.ㅠ

;; 103

(fn [x]

  (let [r (map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1} x)]

  (apply + 

         (last r)

         (map (fn [a b]

                (if (< a b)

                  (- a)

                  a))

              r

              (rest r))))) 

일단 #() 을 써서 줄이기

;; 100

(fn [x]

  (let [r (map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1} x)]

  (apply + 

         (last r)

         (map #(if (< %1 %2) (- %1) %1)

              r

              (rest r))))) 

%1 중복 제거하여 1을 줄일 수 있었다.

;; 99

(fn [x]

  (let [r (map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1} x)]

  (apply + 

         (last r)

         (map #((if (< %1 %2) - +) %1)

              r

              (rest r))))) 

#()의 중복을 피해서 더 줄일 수 있다.

;; 96

#(let [r (map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1} %2)]

  (apply + 

         (last r)

         (map %1

              r

              (rest r)))) #((if (< %1 %2) - +) %1)

comp를 써도 같은 길이를 구할 수 있다.

;; 96

(comp

 #(apply + 

         (last %)

         (map (fn [a b] (if (< a b) (- a) a))

              %

              (rest %)))

 #(map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1} %))

Code Golf - 4Clojure 73번 문제

73번 문제는 틱택토 판을 읽어 승자를 판별하는 함수를 작성하는 문제다.

(= :x (__ [[:x :e :o]
           [:x :e :e]
           [:x :e :o]]))

우선 마구잡이 풀이, 우선 :x가 이겼나 보고, 아니면 :o 가 이겼나 보고, 아니면 nil!
이겼는지는 row/col/diagonal이 모두 해당 플레이어인지 확인.

;; 294
(fn [board]
  (let [b2 (apply mapv vector board)
        d1 (map #(%1 %2) board [0 1 2])
        d2 (map #(%1 %2) board [2 1 0])
        win? (fn [p]
               (or (every? #(= p %) (board 0))
                   (every? #(= p %) (board 1))
                   (every? #(= p %) (board 2))
                   (every? #(= p %) (b2 0))
                   (every? #(= p %) (b2 1))
                   (every? #(= p %) (b2 2))
                   (every? #(= p %) d1)
                   (every? #(= p %) d2)))]
    (cond (win? :x) :x
         (win? :o) :o
          :else nil)))

Thinking Functionally with Haskell의 5장 Sudoku Solver와 비슷한 부분이 보인다. 결국은 3 rows, 3 cols, 2 diags 를 모두 구할 수 있으면 여기서 [:x :x :x]와 같은 것이 있는지 보면 되는거다.

collection에 요소가 있는지 확인하는 방법은 말그대로 set을 사용하면 된다. (set은 T => Bool 함수이기 때문)

;; 146
(fn [b]
  (let [c (apply mapv vector b)
        d (mapv #(%1 %2) b [0 1 2])
        e (mapv #(%1 %2) b [2 1 0])
        win? (fn [p]
               (some #{[p p p]} (concat b c [d e])))]
    (cond (win? :x) :x
         (win? :o) :o
          :else nil)))


가만 보면 원래 collection을 집합으로 보는 것이 낫겠다. 그리고 :else nil은 사족이다.

;; 136
(fn [b]
  (let [c (apply mapv vector b)
        d (mapv #(%1 %2) b [0 1 2])
        e (mapv #(%1 %2) b [2 1 0])
        win? (fn [p]
               ((set (concat b c [d e])) [p p p]))]
    (cond (win? :x) :x
         (win? :o) :o)))

그러고 보면 win?이란 함수는 set으로 처리가능하다.

;; 131
(fn [b]
  (let [c (apply map vector b)
        d (map #(%1 %2) b [0 1 2])
        e (map #(%1 %2) b [2 1 0])
        win? (set (concat b c [d e]))]
    (cond (win? [:x :x :x]) :x
         (win? [:o :o :o]) :o)))

일단 여기까지 하고 인라인, 인자 전달 등의 골프 기법 동원하여..

;; 110
(fn [a m b]
  (let [w (set (concat b
                       (apply m vector b)
                       [(m a b [0 1 2])
                        (m a b [2 1 0])]))]
    (cond (w [:x :x :x]) :x
         (w [:o :o :o]) :o))) #(%1 %2) map

Clojure 간단한 코드 실행해보기

요즘 꾸준하게 매일 조금씩 Clojure를 공부하고 있다. Living Clojure에서 추천하는 7주 과정 진도에 맞춰 이번주까지 4Clojure 문제를 주로 많이 풀었고 다음 주 부터는 몇가지 카타를 풀어볼 예정이다.

4Clojure 문제들은 함수를 하나 작성하는 것이 주된 것이고, 그러다보니 간단한 클로져 코드를 작성하고 결과를 확인해 볼 일이 많다. 그런데 아직은 이 과정이 뭔가 매끄럽지가 않다.

지금 시도해보는 방법들,

1. lein repl 

터미널에서 바로 repl을 뛰울 수 있는 간단한 방법. lein이 생각보다 실행되는데 시간이 걸린다. 게다가 repl까지~

또, repl은 IPython과 같은 상호작용성이 부족하다. 

2. emacs + cider + nrepl

아직 emacs가 익숙하지 않지만 단축키며 설정이며 하나둘씩 익혀보는 중. .clj파일로 저장하거나 직접 Clojure 모드로 설정을 바꾸고 나면 관련 단축키들을 사용할 수 있다. C-c M-j 라는 복잡한 단축키를 누르면 cider-nrepl도 연결되어 버퍼와 repl을 왔다갔다 하면서 조금씩 바꿔볼 수 있다. 단순히 repl만 있는 것 보단 낫다.

다만 emacs가 아직도 손에 익지 않아서 ㅠ.ㅠ 게다가 emacs를 띄우는 거나 repl 띄우는게 여전히 조금 무거운 느낌이다.  (맥에서는 그나마 조금 나은데, 윈도에서 이맥스는 처음 실행할 때 더 느린것 같음) 바로 뭔가 타이핑하고 결과 보고 .. 하려고 할때는 좀 ..

3. LightTable instarepl (http://lighttable.com/)

코드를 작성하는 중에도 인라인으로 실행 트레이스를 보여주는 건 매우 파워풀하다. repl의 진화된 형태. 단축키로 문서를 열어본다든지 자동완성이라든지.. 등등도 좋다.

다만 중간중간 LightTable이 먹통이 되기도 하고, 역시나 instarepl을 처음 띄우는 게 느리다. ㅠ.ㅠ  

안정성/성능 등에 아직은조금 문제가 있는 것 같음.

4. tryclj (http://www.tryclj.com/)

단순히 repl만 원한다면 이 방법이 제일 편한 것 같다. 로컬보다 리모트라니 -.-;;;  (물론 repl이어서 상호작용성에는 똑같은 단점이 있다)

이 밖에도 IntelliJ IDEA + Cursive 등의 방법도 있지만, 바로 뭔가 코드를 작성해보려는데 프로젝트 생성하고 REPL까지 띄우는 건 매우 번거롭다. 이미 이 과정이 선행되어 있다면 emacs보다 조금더 편한 방법이 아닐지..

이것 저것 느린걸 보면 내가 뭔가를 잘못 설정하고 쓰는 것이든가, 참을성이 부족하든가 둘 중 하난가 싶기도 하다. 그냥 repl하나, emacs하나, lighttable 등을 미리 다 띄워놓고 언제든지 스위치해서 하는게 제일인가 싶기도 하고.