commit e1321500cc73b45fe0d5584ccb56170e925b551a parent ec81ef1ea7f9b86c1324cd577bc66160bc0912c5 Author: Yuval Langer <yuval.langer@gmail.com> Date: Mon, 27 Nov 2023 22:27:05 +0200 Fix more exercises. Diffstat:
| M | Makefile | | | 6 | +++--- |
| M | sicp/solutions/chapter-1/exercise-14.scm | | | 5 | +++++ |
| A | sicp/solutions/chapter-1/exercise-15.scm | | | 35 | +++++++++++++++++++++++++++++++++++ |
| M | sicp/solutions/chapter-1/exercise-16.scm | | | 122 | +++++++++++++++++++++++++++++-------------------------------------------------- |
| M | sicp/solutions/chapter-1/exercise-17.scm | | | 52 | ++++++++++++++++++++-------------------------------- |
| M | sicp/solutions/chapter-1/exercise-18.scm | | | 32 | +++++++++++++++----------------- |
| A | sicp/tests/chapter-1/exercise-14.scm | | | 4 | ++++ |
| A | sicp/tests/chapter-1/exercise-15.scm | | | 19 | +++++++++++++++++++ |
| A | sicp/tests/chapter-1/exercise-16.scm | | | 49 | +++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | sicp/tests/chapter-1/exercise-17.scm | | | 22 | ++++++++++++++++++++++ |
| A | sicp/tests/chapter-1/exercise-18.scm | | | 13 | +++++++++++++ |
11 files changed, 230 insertions(+), 129 deletions(-)
diff --git a/Makefile b/Makefile @@ -10,9 +10,9 @@ all: $(tests_logs) .PHONY: print_variables print_variables: - printf "%s\n" $(solutions) - printf "%s\n" $(tests) - printf "%s\n" $(tests_logs) + @printf "%s\n" $(solutions) + @printf "%s\n" $(tests) + @printf "%s\n" $(tests_logs) $(tests_logs): guile -L . `printf $@ | sed -E 's#(chapter-[0-9]*)-(exercise-[0-9]+).log#sicp/tests/\1/\2.scm#g'` diff --git a/sicp/solutions/chapter-1/exercise-14.scm b/sicp/solutions/chapter-1/exercise-14.scm @@ -22,3 +22,8 @@ ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50))) + +;;; XXX + +(count-change 11) +(cc 11 5) diff --git a/sicp/solutions/chapter-1/exercise-15.scm b/sicp/solutions/chapter-1/exercise-15.scm @@ -0,0 +1,35 @@ +(define-library (sicp solutions chapter-1 exercise-15) + (import (scheme base) + (scheme write)) + (export sine + sine-times) + + (begin + (define (cube x) (* x x x)) + + (define (p x) (- (* 3 x) (* 4 (cube x)))) + + (define (sine angle) + (if (not (> (abs angle) 0.1)) + angle + (p (sine (/ angle 3.0))))) + + (define (sine-times angle) + (let loop ((angle angle) + (times 1)) + (display (string-append "angle: " + (number->string angle) + "; times: " + (number->string times))) + (newline) + (if (not (> (abs angle) 0.0001)) + (cons angle + times) + (let* ((result (loop (/ angle 3.0) + (+ times 1))) + (approx (p (car result)))) + (display (string-append "approximation: " + (number->string approx))) + (newline) + (cons approx + (cdr result)))))))) diff --git a/sicp/solutions/chapter-1/exercise-16.scm b/sicp/solutions/chapter-1/exercise-16.scm @@ -1,77 +1,45 @@ - -#! - -1.16 - -!# - -(define (flatten a) - (cond - ((null? a) '()) - (else (append (car a) (flatten (cdr a)))))) - -(test-begin "flatten") -(test-equal (flatten '((1 2) (3 4) (5 6))) '(1 2 3 4 5 6)) -(test-end "flatten") - -(define (cartesian a b) - (define (cartesian' a-element b) - (cond - ((null? b) '()) - (else (cons (cons a-element (car b)) - (cartesian' a-element (cdr b)))))) - (cond - ((null? a) '()) - (else (flatten (map (cut cartesian' <> b) a))))) - -(test-begin "cartesian") -(test-equal - (cartesian '(1 2 3) - '(4 5 6)) - '((1 . 4) - (1 . 5) - (1 . 6) - (2 . 4) - (2 . 5) - (2 . 6) - (3 . 4) - (3 . 5) - (3 . 6))) -(test-end "cartesian") - -(define (fast-expt-recursive b n) - (cond ((= n 0) 1) - ((even? n) (square (fast-expt-recursive b (/ n 2)))) - (else (* b (fast-expt-recursive b (- n 1)))))) - -(define (fast-expt-iterative b n) - (define (f a b n) - (cond - ((= n 0) a) - ((even? n) (f a - (* b b) - (/ n 2))) - (else (f (* a b) - b - (1- n))))) - (f 1 b n)) - -(test-begin "1.16") -(test-equal (fast-expt-recursive 2 3) (fast-expt-iterative 2 3)) -;; 1 * 2**3 = -;; 2 * 2**2 = 2 * (2**1)**2 -;; 2 * -(test-equal (fast-expt-iterative 3 5) (fast-expt-recursive 3 5)) -;; a * b^n = -;; 1 * 3^5 = -;; 3 * 3^4 = -;; 3 * 3 * 3 * 3^2 -;; 3 * 3 * 3 * 3 * 3 -(test-equal (fast-expt-iterative 5 7) (fast-expt-recursive 5 7)) -;; 5**7 = -;; 5 * (5**3)**2 = -;; 5 * (5**2)**3 -;; 5 * 5**2 * 5**3 = -;; 5 * 5**2 * 5 * 5**2 = -(test-equal (fast-expt-iterative 7 11) (fast-expt-recursive 7 11)) -(test-end "1.16") +(define-library (sicp solutions chapter-1 exercise-16) + (import (scheme base) + (srfi :26)) + (export flatten + cartesian + fast-expt-recursive + fast-expt-iterative) + + (begin + (define (flatten a) + ;; Why...? + (cond + ((null? a) '()) + (else (append (car a) (flatten (cdr a)))))) + + + (define (cartesian a b) + ;; Why...? + (define (cartesian' a-element b) + (cond + ((null? b) '()) + (else (cons (cons a-element (car b)) + (cartesian' a-element (cdr b)))))) + (cond + ((null? a) '()) + (else (flatten (map (lambda (a-element) + (cartesian' a-element b)) + a))))) + + (define (fast-expt-recursive b n) + (cond ((= n 0) 1) + ((even? n) (square (fast-expt-recursive b (/ n 2)))) + (else (* b (fast-expt-recursive b (- n 1)))))) + + (define (fast-expt-iterative b n) + (define (f a b n) + (cond + ((= n 0) a) + ((even? n) (f a + (* b b) + (/ n 2))) + (else (f (* a b) + b + (- n 1))))) + (f 1 b n)))) diff --git a/sicp/solutions/chapter-1/exercise-17.scm b/sicp/solutions/chapter-1/exercise-17.scm @@ -1,36 +1,24 @@ +(define-library (sicp solutions chapter-1 exercise-17) + (import (scheme base)) + (export *-recursive + fast-*-recursive) -;; Exercise 1.17 + (begin + (define (*-recursive a b) + (if (= b 0) + 0 + (+ a (*-recursive a (- b 1))))) -(define (*-recursive a b) - (if (= b 0) - 0 - (+ a (*-recursive a (- b 1))))) + (define (double n) + (* 2 n)) -(define (double n) - (* 2 n)) + (define (halve n) + (/ n 2)) -(define (halve n) - (/ n 2)) - -(define (fast-*-recursive a b) - (cond - ((= b 0) 0) - ((even? b) (+ (double a) - (fast-*-recursive a - (- b 2)))) - (else (+ a (fast-*-recursive a (1- b)))))) - -(test-begin "1.17") -(test-equal (*-recursive 2 3) (fast-*-recursive 2 3)) -;; a * b = -;; 2 * 3 = odd b -;; 4 * 2 = even b -;; -(test-equal (* 3 5) (*-recursive 3 5)) -(test-equal (* 5 7) (*-recursive 5 7)) -(test-equal (* 7 11) (*-recursive 7 11)) - -(test-equal (* 3 5) (fast-*-recursive 3 5)) -(test-equal (* 5 7) (fast-*-recursive 5 7)) -(test-equal (* 7 11) (fast-*-recursive 7 11)) -(test-end "1.17") + (define (fast-*-recursive a b) + (cond + ((= b 0) 0) + ((even? b) (+ (double a) + (fast-*-recursive a + (- b 2)))) + (else (+ a (fast-*-recursive a (- b 1)))))))) diff --git a/sicp/solutions/chapter-1/exercise-18.scm b/sicp/solutions/chapter-1/exercise-18.scm @@ -1,19 +1,17 @@ -;; Exercise 1.18 +(define-library (sicp solutions chapter-1 exercise-18) + (import (scheme base)) + (export fast-*-iterative) -(define (fast-*-iterative a b) - (define (f result a b) - (cond - ((= b 0) result) - ((even? b) (f result - (double a) - (halve b))) - (else (f (+ result a) a (1- b))))) - (f 0 a b)) + (begin + (define (double x) (* 2 x)) + (define (halve x) (/ x 2)) -(test-begin "1.18") -(test-equal (* 3 5) (fast-*-iterative 3 5)) -;; 0 3 5 -;; -(test-equal (* 5 7) (fast-*-iterative 5 7)) -(test-equal (* 7 11) (fast-*-iterative 7 11)) -(test-end "1.18") + (define (fast-*-iterative a b) + (define (f result a b) + (cond + ((= b 0) result) + ((even? b) (f result + (double a) + (halve b))) + (else (f (+ result a) a (- b 1))))) + (f 0 a b)))) diff --git a/sicp/tests/chapter-1/exercise-14.scm b/sicp/tests/chapter-1/exercise-14.scm @@ -0,0 +1,4 @@ +(import (srfi :64)) + +(test-begin "chapter-1-exercise-14") +(test-end "chapter-1-exercise-14") diff --git a/sicp/tests/chapter-1/exercise-15.scm b/sicp/tests/chapter-1/exercise-15.scm @@ -0,0 +1,19 @@ +(define-library (sicp tests chapter-1 exercise-15) + (import (scheme base) + (scheme eval) + (scheme write) + (scheme inexact) + (srfi :64) + (sicp solutions chapter-1 exercise-15)) + + (begin + (test-begin "chapter-1-exercise-15") + + (sine-times 12.15) + + (test-approximate + (sin 12.15) + (sine 12.15) + 0.01) + + (test-end "chapter-1-exercise-15"))) diff --git a/sicp/tests/chapter-1/exercise-16.scm b/sicp/tests/chapter-1/exercise-16.scm @@ -0,0 +1,49 @@ +(define-library (sicp tests chapter-1 exercise-16) + (import (scheme base) + (srfi :64) + (sicp solutions chapter-1 exercise-16)) + + (begin + (test-begin "chapter-1-exercise-16") + + (test-group "flatten" + ;; Why...? + (test-equal + '(1 2 3 4 5 6) + (flatten '((1 2) (3 4) (5 6))))) + + (test-group "cartesian" + ;; Why...? + (test-equal + '((1 . 4) + (1 . 5) + (1 . 6) + (2 . 4) + (2 . 5) + (2 . 6) + (3 . 4) + (3 . 5) + (3 . 6)) + (cartesian '(1 2 3) + '(4 5 6)))) + + (test-group "fast-expt-recursive-versus-fast-expt-iterative" + (test-equal (fast-expt-iterative 2 3) (fast-expt-recursive 2 3)) + ;; 1 * 2**3 = + ;; 2 * 2**2 = 2 * (2**1)**2 + ;; 2 * + (test-equal (fast-expt-iterative 3 5) (fast-expt-recursive 3 5)) + ;; a * b^n = + ;; 1 * 3^5 = + ;; 3 * 3^4 = + ;; 3 * 3 * 3 * 3^2 + ;; 3 * 3 * 3 * 3 * 3 + (test-equal (fast-expt-iterative 5 7) (fast-expt-recursive 5 7)) + ;; 5**7 = + ;; 5 * (5**3)**2 = + ;; 5 * (5**2)**3 + ;; 5 * 5**2 * 5**3 = + ;; 5 * 5**2 * 5 * 5**2 = + (test-equal (fast-expt-iterative 7 11) (fast-expt-recursive 7 11))) + + (test-end "chapter-1-exercise-16"))) diff --git a/sicp/tests/chapter-1/exercise-17.scm b/sicp/tests/chapter-1/exercise-17.scm @@ -0,0 +1,22 @@ +(define-library (sicp tests chapter-1 exercise-17) + (import (scheme base) + (srfi :64) + (sicp solutions chapter-1 exercise-17)) + + (begin + (test-begin "chapter-1-exercise-17") + (test-equal (*-recursive 2 3) (fast-*-recursive 2 3)) + ;; a * b = + ;; 2 * 3 = odd b + ;; 4 * 2 = even b + ;; + + (test-equal (* 3 5) (*-recursive 3 5)) + (test-equal (* 5 7) (*-recursive 5 7)) + (test-equal (* 7 11) (*-recursive 7 11)) + + (test-equal (* 3 5) (fast-*-recursive 3 5)) + (test-equal (* 5 7) (fast-*-recursive 5 7)) + (test-equal (* 7 11) (fast-*-recursive 7 11)) + (test-end "chapter-1-exercise-17") + )) diff --git a/sicp/tests/chapter-1/exercise-18.scm b/sicp/tests/chapter-1/exercise-18.scm @@ -0,0 +1,13 @@ +(define-library (sicp tests chapter-1 exercise-18) + (import (scheme base) + (srfi :64) + (sicp solutions chapter-1 exercise-18)) + + (begin + (test-begin "chapter-1-exercise-18") + (test-equal (* 3 5) (fast-*-iterative 3 5)) + ;; 0 3 5 + ;; + (test-equal (* 5 7) (fast-*-iterative 5 7)) + (test-equal (* 7 11) (fast-*-iterative 7 11)) + (test-end "chapter-1-exercise-18")))