조금씩, 천천히, 그리고 꾸준히

  이 한문제 푼다고  4시간 정도 걸린 것 같다. -_-;

  문제에 있는 코드를 보면   n X n 체스보드 판에 n개의 퀸을 배치하는 순열을 생성하고 그걸 safe?라는 술어(predicate) 함수로 필터링하는 식으로 되어있다.
 퀸을 보드의 세로줄에 놓는 모든 경우를 생성하는 순열은 금방 만들었고 safe?를 판단하는 함수도 쉽게 만들었다. 그런데 이 두개를 합치려니까 결과가 안나왔다.   알고보니 depth를 착각했던 게 원인이었다.

  거두절미하고 코드는 다음과 같다. 혹시나 답을 보기 원치 않은 분을 위해서 여백을 넣었다.


















(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (enumerate-interval start end)
  (if (> start end)
      null
      (cons start (enumerate-interval (+ start 1) end))))

(define (flatmap proc seq)
  (accumulate append null (map proc seq)))

; answer
(define empty-board
  null)

(define (adjoin-position new-row k rest-of-queens)
  (accumulate cons rest-of-queens (list (list new-row k))))


(define (safe? k positions)
  (define (invalid? pos1 pos2)
    (or (equal? (car pos1) (car pos2))
        (equal? (cadr pos1) (cadr pos2))
        (equal? (abs (- (car pos1) (car pos2)))
                (abs (- (cadr pos1) (cadr pos2))))))
  (define a (car positions))
  (define b (cdr positions))
  (null? (filter
          (lambda (x) (invalid? a x))
          b)))

; problem
(define (queens board-size)
  (define (queen-cols k)
    (define safe (lambda (positions) (safe? k positions)))
    (if (= k 0)
        (list empty-board)
        (filter
         safe
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

;test-case
(equal? (list (list 3 2) (list 2 7) (list 1 3))
        (adjoin-position 3 2 (list (list 2 7) (list 1 3))))

(equal? (list (list (list 1 1)))
        (queens 1))
(equal? null
        (queens 2))
(equal? null
        (queens 3))
(define queens-4
  (list (list (list 3 4) (list 1 3) (list 4 2) (list 2 1)) (list (list 2 4) (list 4 3) (list 1 2) (list 3 1))))
(equal? queens-4
        (queens 4))



 

감격의 눈물... 흑흑...

Scheme 함수형 언어이고, 결정적으로 전위 표기법이다. 그래서 적응하기가 무척 힘들었는데 어느 순간 무척 친숙해 졌다.
문제를 푸는데 TDD를 적용하니 수월하게 넘어갔다. TDD가 없었으면 이 책을 읽고 언어를 익히는데 몇배는 힘들었을 것이다.
(조악하게 나마 임시 테스트 함수를 만들어서 썼다.)

1장에서 다루는 것은 abstaction이다. 특별한 사례에서 공통점을 뽑아 일반적인 방식을 찾아 나가는 것이다.

연습문제 1.32을 풀고 나니 왜 이 책이 사랑받는지 알 것 같다. 아니 안다기 보다는 맛을 약간 본 셈이다.
컴퓨터 공학자나 프로그래머치고 이책을 고전으르 꼽는 사람이 많다. 컴공 서적 Top 100에 드는 책이기도 하다.

이 책 덕분인지 파이썬에서 함수형표현을 쓰게 되었다. 그리고 시야가 약간 넓어졌다.

열심히 산을 오르고 중간 목적지에 도달했다. 정말 기쁘다.^^