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) 등으로 명시적 변환이 있어야 (=) 비교를 할 수 있다.

아래는 최종 코드

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 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)])) %))

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)))

Living Clojure -- Week 2, Day 3

갈수록 문제수가 줄어든다. 단순히 문제만 풀지 말라는 얘기인 듯..


문제 107 Simple clojures

(= [1 8 27 64] (map (__ 3) [1 2 3 4]))

Math/pow를 사용했더니 타입이 달라서 테스트가 실패한다. ClojureScript라면 될거 같다.

cljs.user=> (= 8 (.pow js/Math 2 3))
true

직접 pow를 구현하자니 안그래도 (fn)식이 다시 (fn)을 반환해야 해서 그냥 (repeat)을 이용하기로..

(fn [n] (fn [m] (reduce * (repeat n m))))

또는 partial을 이용하여

partial (fn [n m] (reduce * (repeat n m)))

그밖에,

partial (fn [n m] (reduce * (apply repeat [n m])))
partial (fn [& x] (-> apply * (apply repeat x)))
partial (fn [& x] (->> x (apply repeat) (apply *)))
..

그래도 (fn [n] #(apply * (repeat n %))) 이게 제일 간단한 듯.

(fn[n]#(int(Math/pow % n)))
partial #(int(Math/pow %2 %1))



문제 90 Cartesian Product

(= (__ #{1 2 3} #{4 5})
   #{[1 4] [2 4] [3 4] [1 5] [2 5] [3 5]})

이건, Korean Clojure User Group에서도 논의되었던 (for)의 동작을 알면 간단한 문제

(fn [as bs] (into #{} (for [a as b bs] [a b])))

#()을 사용하면

#(into #{} (for [a %1 b %2] [a b]))

into #{}를 사용할 필요도 없을 것 같다.

#(set (for [a %1 b %2] [a b]))

이건, sequence를 모나드로 보면 간단히 flatMap/map/vector다

(fn [as bs] (set (mapcat (fn[a] (map (fn[b] [a b]) bs)) as)))
(fn [as bs] (set (mapcat (fn[a] (mapcat (fn[b] (vector [a b])) bs)) as)))

(fn)이 세번이나 중첩되어서 보기 흉하다.

Haskell에서는 이미 liftM2로 추상화되어 있어서 굳이 list comprehension을 쓸 필요도 없다.

cp = liftM2 (,)

Living Clojure -- Week 2, Day 2

다시 50번대
문제 51 Advanced Destructuring
(= [1 2 [3 4 5] [1 2 3 4 5]] (let [[a b & c :as d] __] [a b c d]))

그러고보면 Destructuring은 Scala/Haskell에서 패턴매치에 적용되어 있는 것이고, JavaScript에도 변수바인딩시에 Destructuring을 사용할 수 있게 되었다.



와우, 이제 80번대!
문제 83 A Half-Truth
(= false (__ false false))

이건 좀,,, 뭐랄까? 암튼 특이한 문제다. 모두 참이면 안되고 일부만 참인지 확인하는 함수를 작성하는 것.

(fn [& x] (and (not (reduce #(and %1 %2) x)) (reduce #(or %1 %2) x)))
그냥 말 그대로를 옮겼다. 여기서 (apply and xs) 같이 시도했다가 apply 에 매크로를 사용할 수 없다는 오류를 만났고, 다시 (reduce and xs) 를 시도했다가 역시 매크로를 사용할 수 없다는 오류를 만났다. 매크로는 마치 함수처럼 사용하지만 함수가 아니라는 점! 매크로는 강력하지만 매크로인걸 알고 써야 한다는 점이 함정이다.

and나 or에 해당하는 함수가 있다면 조금더 간단했을까?



다시 60번대, 기준이 뭘까?
문제 66 Greatest Common Divisor
(= (__ 1023 858) 33)

이건 유클리드법인가? 결국 재귀로 풀 수 있다.
(fn gcd[a b]
  (cond (= a 0) b
        (> a b) (recur (- a b) b)
        :else (recur (- b a) a)))

:else를 몰라서 Scheme에서처럼 else를 사용해서 오류.
하는김에 Scheme의 cond와 비교하자면 Scheme은 좀더 syntax tree가 깊다. 조건-값 쌍을 한번더 괄호로 감싸준다. 즉 각 브랜치가 하나의 리스트로 표현되는데, Clojure에서는 그걸 펼쳐놓았다. cond도 매크로!


오늘은 달랑 세문제!

Living Clojure -- Week 2, Day 1

여전히 4Clojure 문제 풀이가 이어진다.

문제 26 Fibonacci Sequence
(= (__ 3) '(1 1 2))

첫 풀이,
(fn [n]
  (loop [i 0
         a 1
         b 1
         seq []]
    (if (< i n)
      (recur (inc i) b (+ a b) (conj seq a))
      seq)))

이번에도 lazy-seq을 이용하여 풀어보았다. n개 추출은 take로 처리할 수 있다.
#(take % ((fn r[a b] (lazy-seq (cons a (r b (+ a b))))) 1 1))

직접 lazy를 만드는 대신 iterate를 이용할 수도 있다.
#(take % (map first (iterate (fn[[a b]][b (+ a b)]) [1 1])))


문제 29 Get the Caps
(= (__ "HeLlO, WoRlD!") "HLOWRD")

첫 풀이,
(fn [s]
  (apply str (filter #(Character/isUpperCase %)  s)))

Character/isUpperCase 라고 static method를 참조할 수 있는데, 왜 함수 자리에 그대로 쓰면 안될까?


문제 48 Intro to some
(= __ (some #{2 7 6} [5 6 7 8]))

some은 bool 함수가 아니다! (some f coll) == (first (filter identity (map f coll))) 즉, f가 map함수이면서 첫번째 logical true value를 반환한다.


문제 42 Factorial Fun
(= (__ 5) 120)

첫풀이
(fn [n]
  (apply * (range 2 (inc n))))

Threading 연습
#(->> (range %) (map inc) (apply *))


문제 52 Intro to Destructuring
(= [2 4] (let [[a b c d e f g] (range)] __))

clojure.org 의 binding forms를 읽어보는 것이 좋다.



처음에 진도를 많이 뺄 것 처럼 하다가 계속 멤돌고 있는 것 같음.

Living Clojure -- Week 1, Day 5

이번에도 모두 2일차 진행하며 풀어봤던 문제들이다. 한번에 쭈욱~ 달릴 수 있는 것을 길게 늘여놓았구나 싶다.

문제 30, 이어진 중복 제거.
(= (apply str (__ "Leeeeeerrroyyy")) "Leroy")

loop/recur로 풀수 있는 문제지만 accumulator의 last를 비교해야 한다는 점이 조금 거슬린다. 이건 아마도 Haskell느낌? 하지만 Clojure의 vector는 last도 효율적이니까!
(fn [list]
  (loop [list list
         acc []]
    (if (empty? list)
      acc
      (if (= (last acc) (first list))
        (recur (rest list) acc)
        (recur (rest list) (conj acc (first list)))))))

이미 있는 sequence함수를 사용한다면 reduce로 쉽게 구현된다.

reduce (fn[a b](if (= (last a) b) a (conj a b))) []

그런데 만약 map/filter 등의 sequence함수들처럼 lazy sequence를 반환해야 한다면 어떻게 할 수 있을까? 단순히loop/recur + accumulator로는 안될 것이다.

Rx의 distinctUntilChanged와 같다! 직접 마지막 요소를 keep해도 되지만 drop-while을 이용하면 편리하다. 그리고 오히려 더 간단하다!

(fn duc[coll]
  (lazy-seq
   (when-let [s (seq coll)]
     (let [f (first s)]
       (cons f (duc (drop-while #(= % f) (rest s))))))))

laziness를 확인하려면 함수에 (range) 와 같은 무한시퀀스를 적용시키고 앞에서 (take 5)처럼 가져오면 된다. 첫번째 코드는 undefined이며 두번째는 잘 동작한다.


31번, 이어진 같은 값 묶기.
(= (__ [1 1 2 1 1 1 3 3]) '((1 1) (2) (1 1 1) (3 3)))

아무 생각없이 loop/recur로 작성하면 된다. 이 문제는 내가 가끔 연습문제로 소개하는 개미수열의 하위 문제이기도 하다. (take-while/drop-while)을 이용하면 간단하다. 물론 자주 등장하기 때문에 (split-with)가 이미 있다!

이문제도 lazy sequence를 반환하도록 하려면 lazy-seq을 이용해야 한다.
(fn pack[coll]
  (lazy-seq
   (when-let [s (seq coll)]
     (let [f (first s)
           [hd tl] (split-with #(= % f) s)]
       (cons hd (pack tl))))))

그런데 Code Golf를 보니 엄청 짧은 답들이 많다. 어떻게 한 것일까?

laziness 제거하고 77
(fn p[c]
  (when-let[s (seq c)]
    (let [f (first s)
          [t d](split-with #(= % f) s)]
      (cons t (p d)))))

50글자 이내의 답들이 있는 걸보면 vector를 가정한 것이 아닐까 싶다.

67글자
(fn p[c](if(seq c)(let[[t d] (split-with #(= % (c 0)) c)](cons t(p (vec d))))))

에구, 더는 안되겠다!


41번, n번째마다 버리기.
(= (__ [1 2 3 4 5 6 7 8] 3) [1 2 4 5 7 8])

이건 오히려 loop/recur가 더 어렵겠다. 이미 있는 partition(-all)을 이용하면 간단하다.
(fn[c n](apply concat (partition-all (dec n) n c)))


45번, iterate.
(= __ (take 5 (iterate #(+ 3 %) 1)))

간단하니 넘어가고..


33번, replicate.
(= (__ [1 2 3] 2) '(1 1 2 2 3 3))

두번씩 반복한 32번 문제의 일반화!
(fn[c n](mapcat #(repeat n %) c))            



이렇게 1주일이 지났다. 함수형 프로그래밍 언어들의 연습문제들이 서로 비슷하다. 비슷한 문제들이기 때문에 언어적인 부분을 비교해보기 좋다.

Living Clojure -- Week 1, Day 4

둘째날 진도 빼면서 풀었던 문제들이다!

20번, 끝에서 두번째.
(= (__ (list 1 2 3 4 5)) 4)
재귀를 작성할 수도 있겠지만 함수 합성으로 풀 수도 있다.

24번, 모두 더하기.
(= (__ [1 2 3]) 6)
apply + 가 가장 간단한 답이 아닐지.. 그런데 Code Golf에는 더 짧은 답도 많다. 어떻게 풀었을까?

25번, 홀수만.

(= (__ #{1 2 3 4 5}) '(1 3 5))

이런 문제는 그냥 스킵할까 싶기도 하다. 

27번, 팔린드롬.

(false? (__ '(1 2 3 4 5)))

(true? (__ "racecar"))

처음엔 모두 loop/recur재귀로 풀었는데, 이미 있는 reverse를 활용하면 간단한 문제다. 다만 문자열에 대해 조금 이해해야 한다. reverse는 seq에 대해 동작한다. string은 ISeq이지만 sequence는 아니다. 그래서 reverse하고난 결과는 sequence로 바뀐다. string과 sequence를 비교하면 항상 다르다고 나온다. 즉, 둘다 sequence가 되도록 해줘야!

32번, 두번씩.

(= (__ [1 2 3]) '(1 1 2 2 3 3))

flatMap의 clojure식 이름인 mapcat을 이용하면 간단하다. 이 문제에서 인상적인건, #() 함수 리터럴. 결과값이 단순히 값이 되는 경우에는 사용할 수 없다는 점이 아쉽다. #([% %]) 는 올바르지 않다. 괄호가 함수리터럴을 나타내는 동시에 application 폼으로도 해석되기 때문이다. #(identity[% %])처럼 함수를 첫 요소로 넣어줘야 하는데 identity가 너무 길다. 화살표람다식은 간단히 x->x 혹은 x=>x라고 할 수 있는데... Clojure에서는 (fn[x]x)라고 해봤자 똑같이 8글자다!

이미 풀어봤던 문제들이긴 하지만 블로그에 옮기다보니 몇가지 생각해볼거리도 추가하게 되었다. 

Living Clojure -- Week 1, Day 3

4Clojure 문제를 순서대로 진행하는 것이 아니라 듬성 듬성 진행한다.

37번 regular expression 문제.
(re-seq)함수는 첫번째 인자인 정규표현식으로 두번째 인자인 문자열에서 검색하여 찾은 것을 lazy sequence로 반환하는 모양이다. ***seq 인 함수들이 모두 같은 목적을 가진다고 볼 수 있겠다. (tree-seq)처럼...

어제 54번까지 풀면서  37번은 해 버렸음.


57번 단순 재귀 문제.
((fn foo [x] (when (> x 0) (conj (foo (dec x)) x))) 5) 의 결과를 물어보는데..

이 문제는 Clojure의 기초를 조금 알아야 한다.

• (fn)폼에서도 이름(옵셔널)을 줘서 재귀함수를 작성할 수 있음 (JavaScript와 마찬가지)
• (when)매크로는 조건을 만족하지 않을 때 nil값
• (conj nil x)은 '(x), 즉 vector가 아닌 list. 여기서 nil은 말하자면 빈 리스트. (이부분은 앞으로도 자주 헷갈릴 것 같다. Scheme 언어들은 nil과 '()이 같다. 그런데 Clojure에서는 nli과 '()이 다르지만 conj나 into처럼 collection자리에 쓰이는 경우는 nil이 '() 의미로 사용된다.)
• 리스트에서 (conj coll x) == (cons x coll)과 같아서 앞에 x를 붙인다.

68번 loop/recur 재귀 문제.

(loop [x 5 result []]

  (if (> x 0)

    (recur (dec x) (conj result (+ 2 x)))

    result)))

accumulator를 이용하는 일반적인 linear recursion이다.


71번 (->)
(= (__ (sort (rest (reverse [2 5 4 1 3 6]))))
   (-> [2 5 4 1 3 6] (reverse) (rest) (sort) (__))
   5)
처음엔 (sort(rest(reverse...)))의 결과를 말하라는 건줄 착각했다. 가만보니 해당 식을 (->)매크로로 바꿔쓸 수 있음을 보여주는 문제이고, 5라는 값이 나오는 함수 아무거나 넣어주면 된다.


72번 (->>)
(= (__ (map inc (take 3 (drop 2 [2 5 4 1 3 6]))))
   (->> [2 5 4 1 3 6] (drop 2) (take 3) (map inc) (__))
   11)
이번에도 11을 반환하는 아무 함수. 참, 인자는 하나 있어야 한다.  하스켈로 보자면 \_->11

reduce +를 사용할 수도 apply +를 사용할 수도 있다. (fn[_]11)


145번 (for)
(= __ (for [x (range 40)
            :when (= 1 (rem x 4))]
        x))

(for)폼의 다양한 모양을 확인해보라는 문제. 특히 세번째 코드를 만들어낸 출제자가 참 신기하다. :let, :while, :when 등이 있으나, map/filter/reduce 등의 기본에 익숙하면 그냥 이걸 쓰는게 나을지도.

(= __ (for [x (iterate #(+ 4 %) 0)
            :let [z (inc x)]
            :while (< z 40)]
        z))
(= __ (for [[x y] (partition 2 (range 20))]
        (+ x y)))

Living Clojure -- Week 1, Day 2

Living Clojure의 Day2 과정은 4Clojure 문제 중에서 아래의 것들을 풀어보는 것이다.

• problem 13  (= __ (rest [10 20 30 40]))
• problem 14  (= __ ((fn add-five [x] (+ x 5)) 3))
• problem 15  (= (__ 11) 22)
• problem 16  (= (__ "Dave") "Hello, Dave!")
• problem 17  (= __ (map #(+ % 5) '(1 2 3)))
• problem 18  (= __ (filter #(> % 5) '(3 4 5 6 7)))
• problem 35  (= __ (let [x 5] (+ 2 x)))
• problem 36  
• (= 10 (let __ (+ x y)))
• (= 4 (let __ (+ y z)))
• (= 1 (let __ z))

2일차니까 어려운 문제는 없이 기본적인 내용들이었다. 하지만 2일차 하루 쉬었다 한것도 있고 하여 13번부터 정주행하여 54번까지 풀어버렸다.

54번까지 푸는 중에 간혹 어려운 문제들도 있었다.

특히 28번 문제는 좀 까다로웠는데, flatten을 직접 구현하는 것. 어려웠던 이유는 문제가 요구한 것이 (fn) 익명 함수를 구현하는 것이었고, loop/recur가 아닌 일반 재귀라면 쉬울 것을 아는 것이 loop/recur뿐이라 tail recursion으로 구현하려다 보니 꽤나 힘들었다. 

하지만 (fn) 역시 이름을 가질 수 있고, 그러니 재귀가 가능하다. 연습문제 푸는 차원이라면 굳이 loop/recur안써도 좋았을걸..