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

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

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

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안써도 좋았을걸..