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