SICP solution exercise 2.35

Solution for exercise 2.35 of SICP:

(define nil '())

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

(define (count-leaves t)
  (accumulate +
              0 
              (map (lambda (x)
                     (if (pair? x)
                         (count-leaves x)
                         1))
                   t)))
;-------------------- tests --------------------

(define x (cons (list 5 6) (cons (list 7 8 ) (list 9 10))))
(define y (list (list 4 5) (list 6 7)))
(define z (cons (list 11 12) (list 13 14)))
(define t (list 15 16))
(define s (cons (list 17 18) (cons (list (list 19 20) (list 21 22)) (list 23 24))))

x
y
z
t
s

(count-leaves x)
(count-leaves y)
(count-leaves z)
(count-leaves t)
(count-leaves s)

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.34

Solution for exercise 2.34 of SICP:

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

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))
;-------------------- tests --------------------

;1 + 3x + 5x^3 + x^5 at x = 2
(horner-eval 2 (list 1 3 0 5 0 1))

;1 + 3x + 2x^2 + 5x^3 + +3x^4 + x^5 at x = 2
(horner-eval 2 (list 1 3 2 5 3 1))

;2 - 4x + 5x^2 + 7x^3 at x = 2
(horner-eval 2 (list 2 -4 5 7))

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.33

Solution for exercise 2.33 of SICP:

(define nil '())

(define (square x)
  (* x x))

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

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) nil sequence))

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

;--------------------tests-------------------------

(map square (list 1 2 3))
(append (list 1 2 3) (list 4 5 6))
(length (list 5 6 7 8 9))

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.32

Solution for exercise 2.32 of SICP:

(define nil '())

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map 
                      (lambda (x)
                        (cons (car s) x))
                      rest)))))

(define a (list ))
(define b (list 1 2 3))
(define c (list 1 2 3 4))

;;; tests
(subsets a)
(subsets b)
(subsets c)

;;; explanation
; The set of all subsets consists of the subsets that contain 
; the car of the original set and those subsets that don't 
;(the latter being called rest).
; By recursively appending the rest and combinations of the car 
; and the distinct elements of the rest we get the complete set
; of all subsets.
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.31

Solution for exercise 2.31 of SICP:

(define (square x)
  (* x x))

(define (tree-map function tree)
  (map (lambda (subtree)
         (if (pair? subtree)
             (tree-map function subtree)
             (function subtree)))
  tree)) 
  

(define (square-tree tree) (tree-map square tree))

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.30

Solution for exercise 2.30 of SICP:

;Define square-tree directly (i.e., without using any
;higher-order procedures) 
(define nil '())

(define (square-tree-direct tree)
  (cond ((null? tree) nil)
        ((not (pair? tree))
         (* tree tree))
        (else (cons (square-tree-direct (car tree))
                    (square-tree-direct (cdr tree))))))

(square-tree-direct
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))

;Define square-tree by using map and recursion.
(define (square-tree-map tree)
  (map (lambda (subtree)
         (if (pair? subtree)
             (square-tree-map subtree)
             (* subtree subtree)))
  tree))

(square-tree-map
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))


Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.29

Solution for exercise 2.29 of SICP:

(define (make-mobile left right)
  (list left right))

(define (make-branch length structure)
  (list length structure))

;a.  Write the corresponding selectors
; * left-branch and 
; * right-branch,
;   which return the branches of a mobile, 
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (car (cdr mobile)))

; * branch-length and
; * branch-structure,
;   which return the components of a branch.
(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (car (cdr branch)))

;;;; tests
(define b5
  (make-branch 10 6))

(define b6
  (make-branch 10 7))

(define m3
  (make-mobile b5 b6))

(define b3
  (make-branch 10 m3))

(define b4
  (make-branch 10 5))

(define m2
  (make-mobile b3 b4))

(define b1
  (make-branch 10 3))

(define b2
  (make-branch 10 m2))

(define m1
  (make-mobile b1 b2))

;b.  Using your selectors, define a procedure total-weight 
;    that returns the total weight of a mobile.
(define (total-weight structure)
  (if (pair? structure)
      (+ (total-weight (branch-structure (left-branch structure)))
         (total-weight (branch-structure (right-branch structure))))
      structure))

;;;; tests
(total-weight m1)
(total-weight m2)
(total-weight m3)

;c.  A mobile is said to be balanced if the torque applied by its top-left 
;branch is equal to that applied by its top-right branch (that is, if the 
;length of the left rod multiplied by the weight hanging from that rod is 
;equal to the corresponding product for the right side) and if each of the 
;submobiles hanging off its branches is balanced. Design a predicate that 
;tests whether a binary mobile is balanced.
(define (torque branch)
  (* (branch-length branch)
     (total-weight (branch-structure branch))))

;;;; tests
(torque b1)
(torque b2)

(define (balanced? structure)
  (if (pair? structure)
      (and (equal? (torque (left-branch structure))
                   (torque (right-branch structure)))
           (balanced? (branch-structure (left-branch structure)))
           (balanced? (branch-structure (right-branch structure))))
       #t))
           
(define m4
  (make-mobile 
   (make-branch 1 30)
   (make-branch 2 (make-mobile 
                   (make-branch 3 5)
                   (make-branch 2 10)))))

m4
(balanced? m4)

(define m5
  (make-mobile
   (make-branch 2 (make-mobile
                   (make-branch 6 5)
                   (make-branch 3 10)))
   (make-branch 3 (make-mobile
                   (make-branch 2 5)
                   (make-branch 2 5)))))

m5
(balanced? m5)

;d.  Suppose we change the representation of mobiles so that the constructors are
;(define (make-mobile left right)
;  (cons left right))
;(define (make-branch length structure)
;  (cons length structure))

;How much do you need to change your programs to convert to the new representation?
;Answer: the implementation of right-branch and branch-structure must change

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.28

Solution for exercise 2.28 of SICP:

;Write a procedure fringe that takes as 
;argument a tree (represented as a list) and returns a list 
;whose elements are all the leaves of the tree arranged in 
;left-to-right order.
;For example,
(define nil '())
(define x (list (list 1 2) (list 3 4)))
x

(define (fringe x)
  (cond ((null? x) x)
        ((not (pair? x)) (list x))
        (else (append (fringe (car x)) (fringe (cdr x))))))

(fringe x)
;(1 2 3 4)

(fringe (list x x))
;(1 2 3 4 1 2 3 4)

(display '--------tests--------)
(newline)

; tests
(define y (list 1 2 3))
y
(fringe y)

(define z (list 1 (list 2 3)))
z
(fringe z)

(define p (list 1 2 (list 3 4 (list 5 6))))
p
(fringe p)

(define q (list 1 2 (list 3 4 (list 5 6)) (list 7 8 ) 9 10))
q
(fringe q)

(define c (list 1 2 3))
(define d (list 4 5 6))
(define e (list c d))
e
(fringe e)

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.27

Solution for exercise 2.27 of SICP:

;Modify your reverse procedure of exercise 2.18 to produce
;a deep-reverse procedure that takes a list as argument and returns as its value 
;the list with its elements reversed and with all sublists deep-reversed as well.
;For example,
(define x (list (list 1 2) (list 3 4)))

x
;((1 2) (3 4))

(reverse x)
;((3 4) (1 2))

(define (deep-reverse a)
  (cond ((null? a) a)
        ((not (pair? a)) a)
        (else (append (deep-reverse (cdr a)) (list (deep-reverse (car a)))))))

(deep-reverse x)
;((4 3) (2 1))

(display '--------tests--------)
(newline)

; tests
(define y (list 1 2 3))
y
(reverse y)
(deep-reverse y)

(define z (list 1 (list 2 3)))
z
(reverse z)
(deep-reverse z)

(define p (list 1 2 (list 3 4 (list 5 6))))
p
(reverse p)
(deep-reverse p)


(define q (list 1 2 (list 3 4 (list 5 6)) (list 7 8 ) 9 10))
q
(reverse q)
(deep-reverse q)

(define c (list 1 2 3))
(define d (list 4 5 6))
(define e (list c d))
e
(reverse e)
(deep-reverse e)

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.26

Solution for exercise 2.26 of SICP:

;Suppose we define x and y to be two lists:

(define x (list 1 2 3))
(define y (list 4 5 6))

;What result is printed by the interpreter in response 
;to evaluating each of the following expressions:

(append x y)
;(1 2 3 4 5 6)

(cons x y)
;((1 2 3) 4 5 6)

(list x y)
;((1 2 3) (4 5 6))

Posted in SICP | Tagged , | Leave a comment