SICP solution exercise 2.25

Solution for exercise 2.25 of SICP:

(define nil '())

;(1 3 (5 7) 9)
(define a
  (list 1 3 (list 5 7) 9))
(car (cdr (car (cdr (cdr a)))))

;((7))
(define b
  (cons (cons 7 nil) nil))
(car (car b))

(define c
  (list (list 7)))
(car (car c))

;(1 (2 (3 (4 (5 (6 7))))))
(define d
  (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr d))))))))))))
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.24

Solution for exercise 2.24 of SICP:

(define nil '())
(list 1 (list 2 (list 3 4)))

; result printed by the interpreter
; (1 (2 (3 4)))

; As an aside: the expression expressed with cons
; (cons 4 nil)
; (cons 3 (cons 4 nil))
; (cons 2 (cons (cons 3 (cons 4 nil)) nil))
(cons 1 (cons (cons 2 (cons (cons 3 (cons 4 nil)) nil)) nil))

The box and pointer structure:

The interpretation as a tree:

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.23

Solution for exercise 2.23 of SICP:

; The value returned by the call to for-each (not illustrated above) can be something arbitrary,
; such as true. Give an implementation of for-each.

(define nil '())

(define (for-each-alt proc list)
  (define (for-each-iter proc list dump)
    (if (null? list)
        #t
        (for-each-iter proc (cdr list) (proc (car list)))))
  (for-each-iter proc list nil))
  
;; test
(for-each-alt (lambda (x) (newline) (display x)) (list 1 2 3 4))
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.22

Solution for exercise 2.22 of SICP:

(define nil '())

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

(define (square-list-1 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items nil))

;; test
(square-list-1 (list 1 2 3 4 5))

;The results appear in reverse order because every new 'cons ...' 
;puts the square result IN FRONT of the previous calculated 
;squares in 'answer'.

(define (square-list-2 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons answer (square (car things))))))
  (iter items nil))

; test
(square-list-2 (list 1 2 3 4 5))

;The result of this second test is not a list because 
;the second argument of 'cons ...' is not empty and not
;itself produced by 'cons ...'
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.21

Solution for exercise 2.21 of SICP:

(define nil '())

;; definition map
(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

;; definition 1
(define (square-list-1 items)
  (if (null? items)
      nil
      (cons (* (car items) (car items)) (square-list-1 (cdr items)))))

;; definition 2
(define (square-list-2 items)
  (map (lambda (x) (* x x)) items))


;; test
(square-list-1 (list 1 2 3 4))
(square-list-2 (list 1 2 3 4))
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.20

Solution for exercise 2.20 of SICP:

(define nil '())

(define (mapc proc cond-proc items)
  (if (null? items)
      nil
      (if (cond-proc (car items))
          (cons (proc (car items)) (mapc proc cond-proc (cdr items)))
          (mapc proc cond-proc (cdr items)))))

(define (same-parity . w)
  (let ((odd-even
    (if (odd? (car w))
        odd?
        even?)))
    (mapc (lambda (x) x) odd-even
        w)))

;;;; tests
(same-parity 1 4 7 5 4 8 9 12 15)
(same-parity 2 4 7 5 4 8 9 12 15)
(same-parity 2)
(same-parity 7)
(same-parity 2 6 4 8 12 18)
(same-parity 1 5 9 3 11 17)
(same-parity 18 12 8 3 4 6 2)
(same-parity 17 11 3 4 9 5 1)
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.19

Solution for exercise 2.19 of SICP:

(define us-coins1 (list 50 25 10 5 1))
(define us-coins2 (list 25 50 1 5 10))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define (except-first-denomination list-coins)
  (cdr list-coins))

(define (first-denomination list-coins)
  (car list-coins))

(define (no-more? list-coins)
  (null? list-coins))

;;;;;;;;;;; test ;;;;;;;;;;

(cc 100 us-coins1)
(cc 95 us-coins1)
(cc 74 us-coins1)
(cc 27 us-coins1)
(cc 12 us-coins1)
(cc 7 us-coins1)
(cc 3 us-coins1)

(cc 100 us-coins2)
(cc 95 us-coins2)
(cc 74 us-coins2)
(cc 27 us-coins2)
(cc 12 us-coins2)
(cc 7 us-coins2)
(cc 3 us-coins2)

; The order of the coins list doesn't affect the answer produced by cc.
; This is because the sum of the recursive calls in the algorithm will always consider
; all possible combinations of coins, regardless of the list order of the coins.
Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.18

Solution for exercise 2.18 of SICP:

(define (reverse a)
  (if (null? a)
      (list )
      (append (reverse (cdr a)) (cons (car a) (list )))))

(define a (list 25 16 9 4 1))
(reverse a)

(define b (list 3))
(reverse b)

(define c (list 3 4))
(reverse c)

(define d (list 8 4 6))
(reverse d)

(define e (list ))
(reverse e)

Posted in SICP | Tagged , | Leave a comment

SICP solution exercise 2.17

Solution for exercise 2.17 of SICP:

(define (last-pair a)
  (if (null? (cdr a))
      a
      (last-pair (cdr a)))) 
      
(define a
  (list 23 72 149 34))

(define b
  (list 5 23 44 93 156))

(last-pair a)
(last-pair b)

Posted in SICP | Tagged , | Leave a comment

SICP solution for exercise 2.9

Solution for exercise 2.9 of SICP:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

(define (div-interval x y)
  (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))

(define (make-interval a b) (cons a b))

; Define selectors upper-bound and lower-bound to complete 
; the implementation.
(define (lower-bound x)
  (car x))

(define (upper-bound x)
  (cdr x))

; Define a corresponding subtraction procedure, called
; sub-interval.
(define (sub-interval x y)
  (add-interval x
                (make-interval (- (upper-bound y))
                               (- (lower-bound y)))))

; width
(define (width x)
  (/ (- (upper-bound x) (lower-bound x)) 2))

; test
(define a (make-interval 3 9))
(define b (make-interval 6 10))

; proof for addition and subtraction
; width = (upper-boud - lower-bound)/2
; for an interval a and b this means
; wa = (ua - lb)/2
; wb = (ub - lb)/2
; also for an interval a+b: 
; (1) w(a+b) = (u(a+b) - l(a+b))/2
; from the definition of add and sub (where subtraction was 
; defined as addition of the 'negative') we know that:
;
; (2) u(a+b) = ua + ub and l(a+b) = la + lb
;
; with some elaboration we can find that:
; (3) wa + wb = ((ua + ub) - (la + lb))/2
;
; which means that wa + wb = w(a+b)
;
;
; add and subtract
; (width a) + (width b) equals (width (add-interval a b))
; (width a) + (width b) equals (width (sub-interval a b))
(+ (width a) (width b))
(width (add-interval a b))
(width (sub-interval a b))
;
;
;
; multiply and divide
; (width a) * (width b) does not equal (width (mul-interval a b))
; (width a) * (width b) does not equal (width (div-interval a b))
(* (width a) (width b))
(width (mul-interval a b))
(width (div-interval a b))
Posted in SICP | Tagged , | Leave a comment