src/sicp/ex1_14.clj

   1 (ns sicp.ex1_14
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.14: tree of (count-changes 11)
   6 (comment
   7   See the notebook (sorry, don't have the time to scan it and put it on the web)
   8   for the tree representation.
   9 )
  10
  11 ;; order of size and computation
  12 ;; see PDF, but below is the trace tree.
  13 ;; (comment
  14 ;; user> (use 'clojure.contrib.trace)
  15 ;; nil
  16 ;; user> (dotrace [count-change cc] (count-change 11))
  17 ;; TRACE t2609: (count-change 11)
  18 ;; TRACE t2610: |    (cc 11 5)
  19 ;; TRACE t2611: |    |    (cc 11 4)
  20 ;; TRACE t2612: |    |    |    (cc 11 3)
  21 ;; TRACE t2613: |    |    |    |    (cc 11 2)
  22 ;; TRACE t2614: |    |    |    |    |    (cc 11 1)
  23 ;; TRACE t2615: |    |    |    |    |    |    (cc 11 0)
  24 ;; TRACE t2615: |    |    |    |    |    |    => 0
  25 ;; TRACE t2616: |    |    |    |    |    |    (cc 10 1)
  26 ;; TRACE t2617: |    |    |    |    |    |    |    (cc 10 0)
  27 ;; TRACE t2617: |    |    |    |    |    |    |    => 0
  28 ;; TRACE t2618: |    |    |    |    |    |    |    (cc 9 1)
  29 ;; TRACE t2619: |    |    |    |    |    |    |    |    (cc 9 0)
  30 ;; TRACE t2619: |    |    |    |    |    |    |    |    => 0
  31 ;; TRACE t2620: |    |    |    |    |    |    |    |    (cc 8 1)
  32 ;; TRACE t2621: |    |    |    |    |    |    |    |    |    (cc 8 0)
  33 ;; TRACE t2621: |    |    |    |    |    |    |    |    |    => 0
  34 ;; TRACE t2622: |    |    |    |    |    |    |    |    |    (cc 7 1)
  35 ;; TRACE t2623: |    |    |    |    |    |    |    |    |    |    (cc 7 0)
  36 ;; TRACE t2623: |    |    |    |    |    |    |    |    |    |    => 0
  37 ;; TRACE t2624: |    |    |    |    |    |    |    |    |    |    (cc 6 1)
  38 ;; TRACE t2625: |    |    |    |    |    |    |    |    |    |    |    (cc 6 0)
  39 ;; TRACE t2625: |    |    |    |    |    |    |    |    |    |    |    => 0
  40 ;; TRACE t2626: |    |    |    |    |    |    |    |    |    |    |    (cc 5 1)
  41 ;; TRACE t2627: |    |    |    |    |    |    |    |    |    |    |    |    (cc 5 0)
  42 ;; TRACE t2627: |    |    |    |    |    |    |    |    |    |    |    |    => 0
  43 ;; TRACE t2628: |    |    |    |    |    |    |    |    |    |    |    |    (cc 4 1)
  44 ;; TRACE t2629: |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 4 0)
  45 ;; TRACE t2629: |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
  46 ;; TRACE t2630: |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 3 1)
  47 ;; TRACE t2631: |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 3 0)
  48 ;; TRACE t2631: |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
  49 ;; TRACE t2632: |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 2 1)
  50 ;; TRACE t2633: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 2 0)
  51 ;; TRACE t2633: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
  52 ;; TRACE t2634: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 1 1)
  53 ;; TRACE t2635: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 1 0)
  54 ;; TRACE t2635: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
  55 ;; TRACE t2636: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 0 1)
  56 ;; TRACE t2636: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
  57 ;; TRACE t2634: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
  58 ;; TRACE t2632: |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
  59 ;; TRACE t2630: |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
  60 ;; TRACE t2628: |    |    |    |    |    |    |    |    |    |    |    |    => 1
  61 ;; TRACE t2626: |    |    |    |    |    |    |    |    |    |    |    => 1
  62 ;; TRACE t2624: |    |    |    |    |    |    |    |    |    |    => 1
  63 ;; TRACE t2622: |    |    |    |    |    |    |    |    |    => 1
  64 ;; TRACE t2620: |    |    |    |    |    |    |    |    => 1
  65 ;; TRACE t2618: |    |    |    |    |    |    |    => 1
  66 ;; TRACE t2616: |    |    |    |    |    |    => 1
  67 ;; TRACE t2614: |    |    |    |    |    => 1
  68 ;; TRACE t2637: |    |    |    |    |    (cc 6 2)
  69 ;; TRACE t2638: |    |    |    |    |    |    (cc 6 1)
  70 ;; TRACE t2639: |    |    |    |    |    |    |    (cc 6 0)
  71 ;; TRACE t2639: |    |    |    |    |    |    |    => 0
  72 ;; TRACE t2640: |    |    |    |    |    |    |    (cc 5 1)
  73 ;; TRACE t2641: |    |    |    |    |    |    |    |    (cc 5 0)
  74 ;; TRACE t2641: |    |    |    |    |    |    |    |    => 0
  75 ;; TRACE t2642: |    |    |    |    |    |    |    |    (cc 4 1)
  76 ;; TRACE t2643: |    |    |    |    |    |    |    |    |    (cc 4 0)
  77 ;; TRACE t2643: |    |    |    |    |    |    |    |    |    => 0
  78 ;; TRACE t2644: |    |    |    |    |    |    |    |    |    (cc 3 1)
  79 ;; TRACE t2645: |    |    |    |    |    |    |    |    |    |    (cc 3 0)
  80 ;; TRACE t2645: |    |    |    |    |    |    |    |    |    |    => 0
  81 ;; TRACE t2646: |    |    |    |    |    |    |    |    |    |    (cc 2 1)
  82 ;; TRACE t2647: |    |    |    |    |    |    |    |    |    |    |    (cc 2 0)
  83 ;; TRACE t2647: |    |    |    |    |    |    |    |    |    |    |    => 0
  84 ;; TRACE t2648: |    |    |    |    |    |    |    |    |    |    |    (cc 1 1)
  85 ;; TRACE t2649: |    |    |    |    |    |    |    |    |    |    |    |    (cc 1 0)
  86 ;; TRACE t2649: |    |    |    |    |    |    |    |    |    |    |    |    => 0
  87 ;; TRACE t2650: |    |    |    |    |    |    |    |    |    |    |    |    (cc 0 1)
  88 ;; TRACE t2650: |    |    |    |    |    |    |    |    |    |    |    |    => 1
  89 ;; TRACE t2648: |    |    |    |    |    |    |    |    |    |    |    => 1
  90 ;; TRACE t2646: |    |    |    |    |    |    |    |    |    |    => 1
  91 ;; TRACE t2644: |    |    |    |    |    |    |    |    |    => 1
  92 ;; TRACE t2642: |    |    |    |    |    |    |    |    => 1
  93 ;; TRACE t2640: |    |    |    |    |    |    |    => 1
  94 ;; TRACE t2638: |    |    |    |    |    |    => 1
  95 ;; TRACE t2651: |    |    |    |    |    |    (cc 1 2)
  96 ;; TRACE t2652: |    |    |    |    |    |    |    (cc 1 1)
  97 ;; TRACE t2653: |    |    |    |    |    |    |    |    (cc 1 0)
  98 ;; TRACE t2653: |    |    |    |    |    |    |    |    => 0
  99 ;; TRACE t2654: |    |    |    |    |    |    |    |    (cc 0 1)
 100 ;; TRACE t2654: |    |    |    |    |    |    |    |    => 1
 101 ;; TRACE t2652: |    |    |    |    |    |    |    => 1
 102 ;; TRACE t2655: |    |    |    |    |    |    |    (cc -4 2)
 103 ;; TRACE t2655: |    |    |    |    |    |    |    => 0
 104 ;; TRACE t2651: |    |    |    |    |    |    => 1
 105 ;; TRACE t2637: |    |    |    |    |    => 2
 106 ;; TRACE t2613: |    |    |    |    => 3
 107 ;; TRACE t2656: |    |    |    |    (cc 1 3)
 108 ;; TRACE t2657: |    |    |    |    |    (cc 1 2)
 109 ;; TRACE t2658: |    |    |    |    |    |    (cc 1 1)
 110 ;; TRACE t2659: |    |    |    |    |    |    |    (cc 1 0)
 111 ;; TRACE t2659: |    |    |    |    |    |    |    => 0
 112 ;; TRACE t2660: |    |    |    |    |    |    |    (cc 0 1)
 113 ;; TRACE t2660: |    |    |    |    |    |    |    => 1
 114 ;; TRACE t2658: |    |    |    |    |    |    => 1
 115 ;; TRACE t2661: |    |    |    |    |    |    (cc -4 2)
 116 ;; TRACE t2661: |    |    |    |    |    |    => 0
 117 ;; TRACE t2657: |    |    |    |    |    => 1
 118 ;; TRACE t2662: |    |    |    |    |    (cc -9 3)
 119 ;; TRACE t2662: |    |    |    |    |    => 0
 120 ;; TRACE t2656: |    |    |    |    => 1
 121 ;; TRACE t2612: |    |    |    => 4
 122 ;; TRACE t2663: |    |    |    (cc -14 4)
 123 ;; TRACE t2663: |    |    |    => 0
 124 ;; TRACE t2611: |    |    => 4
 125 ;; TRACE t2664: |    |    (cc -39 5)
 126 ;; TRACE t2664: |    |    => 0
 127 ;; TRACE t2610: |    => 4
 128 ;; TRACE t2609: => 4
 129 ;; 4
 130 ;; )
 131
 132
 133 ;; TODO: orders of growth in space and number of steps.