SICP in Clojure: Chapter 1, Exercise 14

This is my Clojure solution to Chapter 1, Exercise 14:

(ns sicp.ch1.ex14
  (:require [clojure.java.io :as io]
            [clojure.shell :as shell]
            [clojure.string :as s]))

(defn first-denomination
  [kinds-of-coins]
  (condp = kinds-of-coins
    1 1
    2 5
    3 10
    4 25
    5 50))

(def ^{:dynamic true :private true} *writer* nil)

(defn- cc
  [amount kinds-of-coins prev-call calls]
  (let [this-call (inc (count @calls))
        step [prev-call this-call]]
    (when (some? *writer*)
      (.write *writer* (str (s/join " -> " step) \newline)))
    (swap! calls conj step)
    (cond (zero? amount) 1
          (or (neg? amount) (zero? kinds-of-coins)) 0
          :else (+ (cc amount
                       (dec kinds-of-coins)
                       this-call
                       calls)
                   (cc (- amount
                          (first-denomination kinds-of-coins))
                       kinds-of-coins
                       this-call
                       calls)))))

(defn count-change
  [amount & {:keys [dot-file] :or [dot-file false]}]
  (let [calls (atom [])]
    (if dot-file
      (with-open [writer (io/writer "/tmp/cc.dot")]
        (binding [*writer* writer]
          (.write *writer* "digraph {\n")
          (let [answer (cc amount 5 0 calls)]
            (.write *writer* "}\n")
            answer)))
      (cc amount 5 0 calls))))

(count-change 100) ; => 292

(count-change 11 :dot-file true) ; => 4

;; draw the call graph

(shell/sh "/usr/local/bin/dot" "-Kdot" "-Tsvg" "/tmp/cc.dot" "-O")

(shell/sh "/usr/bin/open" "/tmp/cc.dot.svg")

;; if n is the amount to be changed and k is the number of
;; denominations then: the space complexity (or the maximum height of
;; the tree) is O(n + k) the time complexity (or the number of nodes
;; in the tree) is O(n^k)

SICP in Clojure: Chapter 1, Exercise 13

This is my Clojure solution to Chapter 1, Exercise 13:

(ns sicp.ch1.ex13)

(defn fib
  [n]
  (if (< n 2)
    n
    (+ (fib (- n 1)) (fib (- n 2)))))

(def phi (/ (+ 1 (Math/sqrt 5)) 2))

(def psi (/ (- 1 (Math/sqrt 5)) 2))

(defn fib-exact
  [n]
  (Math/round (/ (- (Math/pow phi n) (Math/pow psi n))
                 (Math/sqrt 5))))

(every? #(= (fib %) (fib-exact %)) (range 10)) ; => true

;; assume f(n) = (phi^n - psi^n)/5^-2
;; assume f(n + 1) = (phi^(n + 1) - psi^(n + 1)/5^-2
;; prove that f(n + 2) = (phi^(n + 2) - psi^(n + 2)/5^-2 where
;; f(n + 2) = f(n + 1) + f(n)