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 등을 미리 다 띄워놓고 언제든지 스위치해서 하는게 제일인가 싶기도 하고.

Living Clojure -- Week 3, Day 5

4Clojure로 몸풀기하는 3주 과정의 마지막 날이다. 다음 주 부터는 한문제 당 이틀씩 진행하는 카타가 진행될 예정.

마지막 문제는 77번, Anagram Finder.
(= (__ ["meat" "mat" "team" "mate" "eat"])
   #{#{"meat" "team" "mate"}})
(= (__ ["veer" "lake" "item" "kale" "mite" "ever"])
   #{#{"veer" "ever"} #{"lake" "kale"} #{"mite" "item"}})

Seq[String] => Set[Set[String]] 함수, 내부 Set안의 단어들은 모두 Anagram이다.
Anagram은 구성글자들의 구성이 같으며 배치만 다른 것을 말한다.

각 단어들을 group-by letter-frequency 로 Map[Freq, Set[String]] 으로 만든다음 value set만 취하면 된다.

;; 79
(fn [words]
  (set (filter #(> (count %) 1) (map set (vals (group-by (comp sort seq) words))))))

내부/외부를 set으로 바꿔주는게 귀찮을 뿐이지 어려울 건 없는것 같다. Freq는 그냥 sort한 값으로 했다.

Threading으로 변경하고, (sort)는 입력을 자동으로 seq으로 변환하므로 (comp sort seq)는 불필요.

;; 63
(fn [w]
  (->> w
       (group-by sort)
       vals
       (filter #(> (count %) 1))
       (map set)
       set))

쓰레딩 대신, 그냥 인라인 호출

;; 62
(fn [w]
  (set (map set (filter #(> (count %) 1) (vals (group-by sort w))))))


#() 으로 바꿀 수 있다.

;; 59
#(set (map set (filter %1  (vals (group-by sort %2))))) #(> (count %) 1)

Living Clojure -- Week 3, Day 4

오늘은 간단하게 한 문제. 늘 빠지지 않는 Prime Number 관련 문제다.

문제 67, Prime Numbers
(= (__ 2) [2 3])
(= (last (__ 100)) 541)

n개의 Prime number를 반환하는 함수를 작성하는 것.
함수형 프로그래밍에서는 에라토스테네스의 체 방법이 자주 등장한다. (Haskell 홈페이지에 나와 있기도 하다.)

<http://haskell.org>

"체"를 naiive하게 풀어낸 코드.

;; 146

(fn [n] 

  (let [from (fn [n] (map #(+ n %) (range)))

        sieve (fn s[ps]

                (let [p (first ps)]

                  (lazy-seq (cons p (s (filter #(not= 0 (mod % p)) (rest ps)))))))]

    (take n (sieve (from 2)))))

솟수를 찾아나가는 (loop/recur) 코드.

;;98

(fn [n] 

  (loop [x 2

         a []]

    (cond

     (= (count a) n) a

     (some #(= 0 (mod x %)) a) (recur (inc x) a)

     :else (recur (inc x) (conj a x)))))

여기선 (cond)보다 (if)가 간결하다.

;; 93

(fn [n] 

  (loop [x 2

         a []]

    (if (= (count a) n)

      a

      (if (some #(= 0 (mod x %)) a)

        (recur (+ 1 x) a)

    (recur (+ 1 x) (conj a x))))))

마지막 (recur) 두 개는 하나로 합칠 수 있다.

;; 81

(fn [n] 

  (loop [x 2

         a []]

    (if (= (count a) n)

      a

      (recur (+ 1 x)

             (if (some #(= 0 (mod x %)) a)

               a

               (conj a x))))))

문제의 호출 형식을 이용하여 loop 인자를 함수로 옮겼다.

;; 74

(fn [x a n] 

  (if (= (count a) n)

    a

    (recur (+ 1 x)

           (if (some #(= 0 (mod x %)) a)

               a

               (conj a x))

           n))) 

2

[]

Code Golf - 4Clojure 53번 문제

4Clojure의 53번 문제로 Code Golf를 즐기고 있다.  (지난 글)

마지막 스코어가 101글자, 도저히 더 못줄이겠다 싶었는다.

;; 101
(fn [& x]
  (#(case (count %) 1 [] %)
    (nth
      (filter #(apply < %)
               (mapcat seq
                       (iterate #(mapcat (juxt butlast rest) %)
                                x)))
      0)))
그런데, 점심 시간에 동료들에게 Code Golf를 소개하다가 방법이 떠올랐다! 불편한 모바일 브라우저에서 타이핑하여 성공! 이제 98!

;; 98
(fn [m & x]
  (#(case (count %) 1 [] %)
    (nth 
      (filter #(apply < %)
               (m seq
                  (iterate #(m (juxt butlast rest) %)
                            x)))
      0))) mapcat


(let[])바인딩 대신 첫 인자로 함수를 넘겨받는 방법으로 두번 사용된 mapcat을 하나 줄일 수 있었다.

Living Clojure -- Week 3, Day 3

오늘은 interleave란 함수를 소개하는 것으로 시작한다.

문제 43, Reverse Interleave
(= (__ [1 2 3 4 5 6] 2) '((1 3 5) (2 4 6)))

두번째 인자로 주어진 갯수의 리스트로 분리해내는 함수다. 말그대로 interleave의 반대방향함수다. (정확히 역함수는 아니다)

2주전에 풀었던 코드는 이제  막 loop/recur만 사용하는 수준. accumulator에 n개만큼 나누어놓고 다시 map vector로 첫 머리를 가져온다. 처음 건 partition이고 두번째 건 transpose.

;; 110
(fn [list n]
  (->> (loop [acc []
              list list]
         (if (empty? list)
           acc
           (recur (conj acc (take n list)) (drop n list))))
       (apply map vector)))


앞부분을 partition으로 바꾸면,

;;48
(fn [list n]
  (->> (partition n list)
       (apply map vector)))


#()을 적용하여...

;;32
#(apply map vector (partition %2 %1))


문제 50번, Split by Type
(= (set (__ [1 :a 2 :b 3 :c])) #{[1 2 3] [:a :b :c]})

타입이 같은 것들끼리 묶어서 set으로 만들어준다. group-by의 value만 취한 것과 같다.

2주전 기본 풀이는 (into #{})으로 set을 만들고, (map type)으로 오리지널 리스트를 다시 각 타입으로 filter한 것이다. 뭔가 매우 비효율적인것 같음. ㅠ.ㅠ

;; 73
(fn [list]
  (into #{}
        (->> (map type list)
             (map (fn [t]
                    (filter #(= t (type %)) list))))))

group-by를 사용하면,
;;27
#(set(vals(group-by type %)))

그런데 가만보니 문제가 요구한 건 seq면 충분하다. (set)으로 변환하니까.

;;22
#(vals(group-by type %))

Living Clojure -- Week 3, Day 2

문제 46, Flipping out

(= 3 ((__ nth) 2 [1 2 3 4 5]))

주어진 함수의 두 인자 위치를 바꾼 새로운 함수를 반환하는 flip 함수를 만드는 문제. Haskell에는 이미 flip이라는 함수가 있다. curry/uncurry/compose 와 함께 대표적인 higher order function 일거다.

;; 20
(fn [f]
  (fn [a b]
    (f b a)))

(fn)을 #()으로 줄여쓸 수 있으나, #()는 nesting이 안되는 문제가 있다.

;; 14
#(fn[a,b](% b a))
;; 15
(fn[f]#(f %2 %1))


문제 44, Rotate Sequence
(= (__ -2 [1 2 3 4 5]) '(4 5 1 2 3))
(= (__ 2 [1 2 3 4 5]) '(3 4 5 1 2))
(= (__ 1 '(:a :b :c)) '(:b :c :a))

이어지는 sequence를 right shift시키는 문제. 예시들을 봐도 그렇지만 vector와 list등 sequential이 입력으로 들어올 수 있고, 출력은 sequence(아마도 vector?)다.

(mod)는 음의 입력을 양으로 바꿔는 점을 이용하면 쉬운 거 같다. 나머진 drop/take로 이어붙이면 된다.

;; 66
(fn [n list]
  (let [p (mod n (count list))]
    (concat (drop p list) (take p list))))

;; 65 -- drop/take 는 (split-at) 로 바꿀 수 있다.
(fn [n list]
  (let [p (mod n (count list))
        [t d] (split-at p list)]
    (concat d t)))

;; 64 -- 모두 inline
(fn [n list]
  (apply concat (reverse (split-at (mod n (count list)) list))))

# 51 -- #() 사용
#(mapcat seq (reverse (split-at (mod %1 (count %2)) %2)))

# 49 -- (apply concat) 대신 (mapcat seq) 을 이용하여 flatten할수도 있다.
#(mapcat seq (reverse (split-at (mod %1 (count %2)) %2)))

# 46 -- (reverse) 대신 (rseq) 을 이용할 수 있다. reverse는 not lazy, rseq는 constant time
#(mapcat seq (rseq (split-at (mod %1 (count %2)) %2)))

Living Clojure -- Week 3, Day 1

3주차만 하면 4Cloure 문제풀이는 끝난다. Code Golf 하는 재미가 있었는데, 벌써 아쉬움이 ..

Living Clojure에서 제시하는 이번주 주요 토픽은...

• Control flow
• Recursion
• Data transformation

자, 3주차 1일째 시작!

문제 95, To Tree or not to Tree

(= (__ '(:a (:b nil nil) nil))

   true)

(= (__ '(:a (:b nil nil)))

   false)

시퀀스가 이진트리인지 확인하는 함수를 작성하는 문제. 각 노드는 nil이거나 양쪽 자식이 모두 있어야 한다.

위의 예는 :a 루트에 왼쪽 자식만 :b 가 있는 경우를 제대로 표현한 것과 그렇지 않은 것을 보여준다. 즉, root 뒤에 딱 두개의 요소만 있는지 확인하는 문제다.

(fn f[s]

  (if (nil? s) true

    (let [[root left right & more] (seq s)]

      (if (empty? more) (and (f left) (f right))

        false))))

틀린답. 두번째 if에서 sequence가 3개를 넘는지만 체크하므로 틀린 답이다. sequence에서 두번째/세번째 요소를 가져오는 방법을 binding(destructuring)으로 풀고 싶은데, 그러자면 core.match 라이브러리를 사용해야 하나보다. 

아하! if-let이 있지 않을까? 있다! https://clojuredocs.org/clojure.core/if-let

(fn f[s]

  (if (nil? s) true

    (if-let [[root left right] (seq s)]

      (and (f left) (f right))

      false)))

If-let binding 패턴이 맞지 않을 때 else 브랜치를 타겠거니 했으나 그렇게 동작하지는 않는 모양이다.

;;98

(fn f[s]

  (cond 

   (nil? s) true

   (not (sequential? s)) false

   (= 3 (count s)) (and (f (second s)) (f (nth s 2)))

   :else false))

두번째 sequential? 체크를 빼먹어서 틀렸다가 바로잡았다. 타입을 런타임 체크로 따져줘야 한다는 점이 매우 번거롭다.

;; 72

(fn f[s]

  (or 

   (nil? s)

   (and (sequential? s) (= 3 (count s)) (f (second s)) (f (nth s 2)))))

문제 96, Beauty is Symmetry

(= (__ '(:a (:b nil nil) (:b nil nil))) true)

(= (__ '(:a (:b nil nil) nil)) false)

이진트리에서 좌우가 대칭인지 판별하는 함수를 작성하는 문제.

tree-seq로 sequence를 만들어 reverse와 같은지 볼 수 있지 않을까? 하지만 tree-seq는 부모먼저 자식 나중이다. 만약 sequence로 만들어서 풀고 싶다면 in order 로 sequence를 만들어야 한다.

(fn [t]

  (let [in-order (fn f[t] (if (nil? t) [] (concat (f (second t)) (vector (first t)) (f (nth t 2)))))

        s1 (in-order t)

        s2 (reverse s1)]

    (= s1 s2)))

in-order 로컬함수를 만들어서 구현해봤다.

;; 97

(fn [r]

  (let [i (fn f[t] (if (nil? t) [] (concat (f (second t)) [(first t)] (f (nth t 2)))))

        s (i r)

        t (reverse s)]

    (= s t)))

혹은 전체를 mirror해서 같은지 비교할 수도 있지 않을까?

;; 59

#(= % ((fn m[t]

         (if (nil? t) nil

           [(nth t 0) (m (nth t 2)) (m (nth t 1))])) %))

nil? 체크를 C처럼 쓸수 있는 건 다행인지 불행인지 -.-;

;; 50

#(= % ((fn m[t]

         (if t

           [(nth t 0) (m (nth t 2)) (m (nth t 1))])) %))

nth를 desctructuring으로 바꿀 수 있다. (if-let/when-let)

;; 43

#(= % ((fn m[t]

         (if-let [[t l r] t]

           [t (m r) (m l)])) %))

Clojure의 lazy

http://clojure.org/lazy 를 보면 초기 lazy-cons 로 구현하던 lazy sequence를 lazy-seq을 이용하게 바꾼 내용을 설명하고 있다.

평가 지연을 위해 람다를 사용하되 어떻게 클로져에 담긴 레퍼런스를 관리할것인가..

Lazy를 구현하려면 이정도의 고민은 해줘야 하나 싶다.

Living Clojure -- Week 2, Day 5

하루 빼먹어서 곧바로 이어 진행한다. 게다가 한문제라니!!! :-)

97번 Pascal's Triangle

(= (map __ (range 1 6))
   [     [1]
        [1 1]
       [1 2 1]
      [1 3 3 1]
     [1 4 6 4 1]])

파스칼 삼각형의 n 번째 줄을 계산하는 함수를 작성하는 것이다.

n번째 줄은 n-1번째 줄에 의존적이다. pair-wise sum 양쪽 끝에 1을 추가하면 된다.

(fn f[n]
  (if (= n 1) [1]
    (let [prev (f (dec n))]
      (conj
       (into [1] (map + prev (rest prev)))
       1))))

쥐어짜기!

• (if)의 else branch가 없으면 nil이며, nil은 올바른 sequence값이다. (빈 시퀀스)
• 원하는 결과타입이 있다면 into가 효과적이다. 첫 인자로 타입이 결정되고 두번째 인자는 무엇이든 시퀀스가 올수 있어서 편리하다. 
• (conj) 등은 컬렉션 타입에 의존적이다!!!

;;64
(fn f[n]
  (if (> n 0)
    (let [p (conj (f (dec n)) 0)]
      (into [1] (map + p (rest p))))))

그러나 마음같아선 이런 함수를 lazy sequence로 만들고 싶다. iterate가 제격이다.

(def pascal (iterate (fn [prev]
                       (into [1] (map + prev (rest (conj prev 0))))) []))

그러면 문제처럼 (map __ (range 1 6)) 할 것을 (take 6 parcal)처럼 만들수도 있다.
덕분에 생각지도 않게 더 줄어버렸다.

;; 55
(fn [n]
  (nth (iterate
     #(into [1] (map + % (rest (conj % 0))))
     []) n))

partial로 더 줄일 수 있다. (1글자지만 -.-)

;; 54
(partial nth (iterate
              #(into [1] (map + % (rest (conj % 0))))
              []))

Living Clojure -- Week 2, Day 4

문제 88 Symmetric Difference
(= (__ #{1 2 3 4 5 6} #{1 3 5 7}) #{2 4 6 7})

공통요소를 제거한 집합을 구하는 문제.
이건 이미 있을 것 같다. 그걸 쓰지 말라는 말은 없다.
(union에서 intersection을 diff) 혹은 (diff 두번한 것을 union)하는 것인데,
생각보다 길어질 것 같다.

직접 구현해보는 것도 연습이 될것 같다.

Clojure도 그렇고 Scala도 그렇고 함수형 프로그래밍 언어에서 특이한 점은 Set/Map 역시 '함수'라는 점이다. Set은 요소의 포함 여부를 알려주는 함수이며 Map은 키->값의 함수이다.

clojure.set 네임스페이스에 difference, union, intersection 등이 정의되어 있지만 Set이 함수라는 점을 이용하면 difference는 remove, union은 into, intersection은 filter라는 기본 함수로 구현 가능하다. 물론 이렇게 되면 into를 빼고 remove/filter의 결과가 Lazy sequence가 되기 때문에 set 함수로 다시 set을 만들어줘야 한다.

(union a b) == (into a b)
(intersection a b) == (set (filter a b))
(difference a b) == (set (remove b a))

into의 첫 인자만 set이면 되기 때문에 diff두번을 union하는 것이 Code Golf에는 유리해보인다. :-)

#(into (set (remove %1 %2)) (remove %2 %1))


100번 Least Common Multiple
(== (__ 5 3 7) 105)
(== (__ 3/4 1/6) 3/2)

최소공배수 문제지만 ratio를 처리할 수 있어야 한다.
그런데, 3/4 와 1/6 의 LCM이 왜 3/2일까? Wikipedia를 살펴보니 예가 나온다.

각 수를 소수(prime)의 지수(exponent)로 표시했을 때 LCM은 각 솟수별 지수의 큰값을 선택하면 된다.

3/4 = 2^-2 * 3^1
1/6 = 2^-1 * 3^-1
LCM(3/4,1/6) = 2^-1 * 3^1 = 3/2

그럼 이문제는 다시 각 수를 소수/지수 쌍으로 표현(소인수분해)하고, 이를 merge하면서 키(소수)가 충돌하면 큰 값을 선택하라는 얘긴가 싶다.

ratio를 소인수분해하려면 denom과numer를 각각 소인수분해한 다음 위(numer)에서 아래(denom)의 지수를 빼주면 된다.

(그런데, 이방법, 소인수분해 말고는 없을까? 말로만 적고보면 매우 귀찮아 보이는데.. 소수도 있어야 하고 말이지. ㅠ.ㅠ)

로제타코드의 소인수분해를 참고하여..

하려 했으나, 아무래도 소인수분해는 아닌거 같아서 더 기본적인 방법도 고려해보니,
유클리드 방법의 GCD가 ratio에도 적용되고, 그렇다면 LCM(a,b) = a*b / GCD 이므로 더 간단해질 것 같다.

(fn [a b]
  (let [gcd (loop [a a b b]
              (if (= a 0) b
                (if (< a b)
                  (recur (- b a) a)
                  (recur (- a b) b))))]
    (/ (* a b) gcd)))

그런데 주어진 문제에는 항이 여럿인 경우도 있다.  GCD를 여러항에 대해 fold시키면 될듯.

(fn [& x]
  (let [gcd (fn [a b]
              (if (= a 0) b
                (if (< a b)
                  (recur (- b a) a)
                  (recur (- a b) b))))]
    (/ (apply * x) (reduce gcd x))))

한두타 더 줄이기 :-)

(fn [& x]
  (let [g (fn [a b]
              (cond (= a 0) b
                (<= a b) (recur (- b a) a)
                    :else (recur b a)))]
    (/ (apply * x) (reduce g x))))

마지막 쥐어짜기 인라인!

(fn [& x]
    (/
     (apply * x)
     (reduce (fn [a b]
               (cond (= a 0) b
                (<= a b) (recur (- b a) a)
                     :else (recur b a)))
             x)))

4Clojure Problem 53

둘째날 진도 빼느라 54번까지 진행했었다. 54번에서 중단하게 된 계기가 바로 53번 문제.

문제 53, Longest Increasing Sub-Seq
(= (__ [1 0 1 2 3 0 4 5]) [0 1 2 3])
(= (__ [7 6 5 4]) [])

이 문제는 설명을 읽어보면 일반적인  Longest Increasing Subsequence문제와 조금 다르다.

• 이어진 subsequence만 대상으로 한다.
• subsequence는 길이가 1보다 커야 한다. 그러한 답이 없으면 []

이 문제는 리스트의 헤드로부터 Increasing subsequence를 어떻게 구하나.. 하는 작은 문제를 놓고 많이 고민했다. 말하자면 (takeWhile increasing sequence) 처럼 하고 싶은 건데.. increasing은 이전 값을 알아야 가능하므로 쉽지 않았다. 그래서 조금 억지스럽게 (map vector s (rest s))로 이웃 값들을 짝으로 만들어주고, 짝의 리스트에 대해 (takeWhile < ..)를 하면 increasing 부분만 가져오는 것이 가능하다. (그런다음 다시 (map second) 로 짝을 해체하고, 맨 앞에 첫 요소를 빼먹지 말고 붙여줘야 한다.)

그런데 이 방법으로 억지스럽게 풀고나니 Code Golf에서 매우매우 하위권..

이번에는 accumulator를 두개 사용한 loop/recur로 풀고, 이를 다시 억지로 글자수 줄이기를 해봤다.

;; 198
(fn r[s]
  (let [e empty?
        f first
        r rest
        c conj
        n count
        x (loop [a []
                 u []
                 s s]
             (if (e s)
               (if (e u)
                 a
                 (c a u))
               (if (or (e u) (< (last u) (f s)))
                 (recur a (c u (f s)) (r s))
                 (recur (c a u) [(f s)] (r s)))))]
    (reduce #(if (and (< (n %1) (n %2)) (< 1 (n %2)))
                        %2
                        %1) [] x)))

그러나 여전히 최빈값보다 못한 수준이다. 뭔가 접근이 잘못된 것 같다.

새로운 방식을 고민하기 위해 Haskell로 다시 시도하여 cyclic list와 iterate를 이용하는 방법을 구현해본 다음, 이를 다시 Clojure로 옮겨보았다.

두 방법 모두 consecutive subsequence를 가장 긴 것(자기 자신)부터 한 요소씩 줄여나가며 만들어내면서 처음으로 increasing 조건을 만족하는 것을 찾는 것이다.

list -> list of subsequences -> filter increasing -> first 처럼.. (마지막에 요소가 1개인 경우 처리 필요)

list of subsequences를 구할때 cyclic list와 iterate를 이용하는 두 가지 방법을 써본것이다.

cyclic list는 쉽지 않았는데 아래의 이유 때문이다.

1. let binding에서는 [s ... s] 처럼 재귀정의가 안되며,
2. lazy-seq 생성함수를 이용하더라도 mapcat이나 concat 혹은 flatten에 lazy가 적용되지 않는다. 

컴파일이 안되는 let 재귀 코드

(fn r[x]

  (let [s (lazy-seq (cons x (mapcat (juxt butlast rest) s)))

        g (fn [x] )

        y (filter #(every? identity (map < % (rest %))) s)

        z (first y)]

    (if (= 1 (count z)) [] z)))

컴파일은 되지만 StackOverflowError 발생하는 코드

(fn [x]

  (let [s ((fn g[] (lazy-seq (cons x (mapcat (juxt butlast rest) (g))))))

        y (filter #(every? identity (map < % (rest %))) (s))

        z (first y)]

    (if (= 1 (count z)) [] z)))

iterate방법은 Clojure로 옮기기에 비교적 쉬울 것 같다.

;; 185
(fn [x]
  (let [f (fn [x] (cons (butlast (first x)) (map rest x)))
        s (apply concat (iterate f [x]))
        incr (fn [x] (every? identity (map < x (rest x))))
        some? (fn [f x] (first (filter f x)))
y (some? incr s)]
    (if (= 1 (count y)) [] y)))

조금 단축되었다. ^^ 그런데 가만 보니 iterate는 무한 시퀀스이며 여기에  apply concat 적용하는 것이 가능한 모양이다.

아래의 방법들로 최대한 줄여보았다.

• inline
• #(%)
• sorted => #(apply < %)

;; 113
(fn [x]
  (#(if(= 1(count %))[]%)
    (first
     (filter #(apply < %)
             (apply concat
                    (iterate #(conj (mapv butlast %) (rest (last %)))
                             [x]))))))

->> 를 쓰면 조금더 읽기 쉽다.

;; 121
(fn [x]
  (let [y (->> [x]
               (iterate #(conj (mapv butlast %) (rest (last %))))
               (apply concat)
               (filter #(apply < %))
               first)]
    (if (= 1 (count y)) [] y)))

그런데 마지막 if문은 더 간결하게 바꾸고 싶은데 어렵다.


-- 업데이트  9월 8일 --

(apply concat) 대신 (mapcat seq)을 사용할 수 있다.

;; 111
(fn [x]
  (#(if(= 1(count %))[]%)
    (first
     (filter #(apply < %)
             (mapcat seq
                    (iterate #(conj (mapv butlast %) (rest (last %)))
                             [x]))))))

(if (= 1(count %) [] %) 는 case로, (first)는 (nth 0)로 바꿀 수 있다.

;; 109
(fn [x]
  (#(case (count %) 1 [] %)
    (nth
     (filter #(apply < %)
             (mapcat seq
                    (iterate #(conj (mapv butlast %) (rest (last %)))
                             [x])))
     0)))

(mapv/last) 대신 (map/first)를 사용할 수 있다. 여기서 (first) 대신 (nth 0)를 사용하면

;;108
(fn [x]
  (#(case (count %) 1 [] %)
    (nth
     (filter #(apply < %)
             (mapcat seq
                    (iterate #(conj (map rest %) (butlast (nth % 0)))
                             [x])))
     0)))

(into)와 vector의 IFn을 이용하면..
;; 107
(fn [x]
  (#(case (count %) 1 [] %)
    (nth
     (filter #(apply < %)
             (mapcat seq
                    (iterate #(into [(butlast (% 0))] (map rest %))
                             [x])))
     0)))

iterate 각 step에서 중복을 허용하면(매우 비효율적이겠지만..)
;; 102
(fn [x]
  (#(case (count %) 1 [] %)
    (nth
     (filter #(apply < %)
             (mapcat seq
                    (iterate #(mapcat (juxt butlast rest) %)
                             [x])))
     0)))

인자를 [& x]로 받으면 [x]대신 x를 사용할 수 있다.
;; 101
(fn [& x]
  (#(case (count %) 1 [] %)
    (nth
     (filter #(apply < %)
             (mapcat seq
                    (iterate #(mapcat (juxt butlast rest) %)
                             x)))
     0)))