Answers to exercises from chapter 1 of SICP in Clojure

sicp.clj

(ns sicp)

;;;; Section 1.1 - The Elements of Programming


;;; Exercise 1.1


[10 12 8 3 6 'a 'b 19 false 4 16 6 16]


;;; Exercise 1.2


(def unreadable-digit (if (< (rand) 0.5) 3 5))
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 unreadable-digit)))))
   (* 3 (- 6 2) (- 2 7)))


;;; Exercise 1.3


(defn sum-of-square-of-two-biggest-numbers
  "A function that do what it says!"
  [& numbers]
  ;; Less efficient than what I used to do but much more generic
  (let [square #(* % %)
        sum-of-square #(->> %
                            (map square)
                            (apply +))]
    (->> numbers
         sort
         reverse
         (take 2)
         sum-of-square)))

;; ~0.76 ms on [5 4 3]

(defn fast-sum-of-square-of-two-biggest-numbers
  "A function that do what it says faster!"
  [x y z]
  ;; This is what I used to do
  (let [square #(* % %)
        sum-of-square #(+ (square %1) (square %2))]
    (cond (and (< x y) (< x z)) (sum-of-square y z)
          (and (< y x) (< y z)) (sum-of-square x z)
          :else                 (sum-of-square x y))))

;; ~0.42 ms on [5 4 3]


;;; Exercise 1.4


;; If b is over 0 then we add a and b else substract them.
;; What a boring exercise!


;;; Exercise 1.5


;; It will loop infinitely using applicative-order
;; while returning 0 using normal-order
;; I don't like explaining myself!


;;; Exercise 1.6


;; Infinite loop


;;; Exercise 1.7


(defn sqrt [x]
  (let [abs #(if (< % 0) (- %) %)
        average #(/ (+ %1 %2) 2)
        improve #(average % (/ x %))]
    (loop [guess 1.0]
      (if (< (abs (- guess (improve guess)))
             (abs (* guess 0.0001)))
        guess
        (recur (improve guess))))))


;;; Exercise 1.8


(defn cbrt [x]
  (let [abs #(if (< % 0) (- %) %)
        square #(* % %)
        improve #(/ (+ (/ x (square %)) (+ % %)) 3)]
    (loop [guess 1.0]
      (if (< (abs (- guess (improve guess)))
             (abs (* guess 0.0001)))
        guess
        (recur (improve guess))))))

;; So simple, yet it totally eluded me in the past!


;;;; Section 1.2 - Procedures and the Processes They Generate


;;; Exercise 1.9


;; The first one is recursive while the last is iterative.


;;; Exercise 1.10


(defn A [x y]
  (cond (= y 0) 0
        (= x 0) (* 2 y)
        (= y 1) 2
        :else (A (- x 1)
                 (A x (- y 1)))))

;; sicp> (A 1 10)
;; 1024
;; sicp> (A 2 4)
;; 65536
;; sicp> (A 3 3)
;; 65536

(defn expt [base pow]
  (reduce * (repeat pow base)))

;; (A 0 n) => (* 2 n)
;; (A 1 n) => (expt 2 n)
;; (A 2 n) => (expt 2 (h (dec n)))

;; (A 2 5) => a 19729 digits number!!!


;;; Exercise 1.11


(defn f-rec [n]
  (if (< n 3)
    n
    (+ (f-rec (dec n))
       (* 2 (f-rec (- n 2)))
       (* 3 (f-rec (- n 3))))))

;; I have absolutely no idea how I got there, just translated my old
;; Scheme version. Maybe actually (re)reading SICP would help me, but I
;; don't have time. Thanks younger me!
(defn f-ite [n]
  (let [f-ite* (fn f-ite* [a b c count]
                 (if (< count 3)
                   a
                   (f-ite* (+ a (* 2 b) (* 3 c))
                           a
                           b
                           (dec count))))]
    (if (< n 3)
      n
      (f-ite* 2 1 0 n))))


;;; Exercise 1.12


;; not recursive!
(defn pt [row col]
  (cond (and (= 0 row) (= 0 col)) 1
        (or (< col 0) (> col row)) 0
        :else (+ (pt (dec row) (dec col))
                 (pt (dec row) col))))