add SICP exercise solutions

7 files changed, 383 insertions, 0 deletions

diff --git a/SICP/c.c b/SICP/c.c
new file mode 100644
index 0000000..fae921b
--- /dev/null
+++ b/SICP/c.c
@@ -0,0 +1,8 @@
+#include <stdio.h>
+
+int main()
+{
+        printf("hello world\n");
+        return 0;
+
+}
diff --git a/SICP/ex2-4.scm b/SICP/ex2-4.scm
index 9078d99..3ad6d15 100644
--- a/SICP/ex2-4.scm
+++ b/SICP/ex2-4.scm
@@ -49,9 +49,17 @@
 ;Exercise 2.6
 
 (define zero (lambda (f) (lambda (x) x)))
+
 (define (add-1 n)
   (lambda (f) (lambda (x) (f ((n f) x)))))
+;; (add-1 zero)
+;; (lambda (f) (lambda (x) (f ((zero f) x))))
+;; (lambda (f) (lambda (x) (f (f x))))
 
+(define (add a b)
+  (lambda (f)
+    (lambda (x)
+      ((a f) ((b f) x)))))
 (define one (lambda(f) (lambda (x) (f x))))
 (define two (lambda(f) (lambda (x) (f (f x)))))
 (define three (lambda(f) (lambda (x) (f (f (f x))))))
@@ -74,3 +82,5 @@
 ((three square) 2)
 
 (((add two one) square) 2)
+
+
diff --git a/SICP/ex2_17.scm b/SICP/ex2_17.scm
new file mode 100644
index 0000000..ac8f0b2
--- /dev/null
+++ b/SICP/ex2_17.scm
@@ -0,0 +1,141 @@
+(cons 1
+      (cons 2
+            (cons 3
+                  (cons 4 nil))))
+
+(define one-through-four (list 1 2 3 4))
+
+one-through-four
+
+(car one-through-four)
+(cdr one-through-four)
+
+(define (list-ref items n)
+  (if (= n 0)
+    (car items)
+    (list-ref (cdr items)
+              (- n 1))))
+
+(list-ref one-through-four 3)
+
+(define (length items)
+  (if (null? items)
+    0
+    (+ 1 (length (cdr items)))))
+
+(define (length items)
+  (define (length-iter a count)
+    (if (null? a)
+      count
+      (length-iter (cdr a)
+                   (+ 1 count))))
+  (length-iter items 0))
+
+(define odds (list 1 3 5 7))
+(define squares (list 1 4 9 16 25))
+
+(define (append list1 list2)
+  (if (null? list1)
+    list2
+    (cons (car list1)
+          (append (cdr list1)
+                  list2))))
+
+(append odds squares)
+
+;; Exercise2.17
+(define (last-pair items)
+  (if (null? (cdr items))
+    (car items)
+    (last-pair (cdr items))))
+
+(last-pair (list 1 2 3 4 9 23))
+
+;; Exercise2.18
+(define (reverse items)
+  (if (null? (cdr items))
+    items
+    (append (reverse (cdr items))
+            (cons (car items) nil))))
+
+(list 4 3 2 1)
+(reverse (list 1 2 3 4))
+
+;; Exercise2.19 Counting change
+
+(define (count-change amount)
+  (cc amount 5))
+
+(define us-coins
+  (list 50 25 10 5 1))
+(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 (first-denomination coin-values)
+  (car coin-values))
+(define (no-more? coin-values)
+  (null? coin-values))
+(define (except-first-denomination coin-values)
+  (if (null? coin-values)
+    null?
+    (cdr coin-values)))
+
+(cc 100 us-coins)
+
+;; Exercise2.20
+
+(define (same-parity x . y)
+  (define (find-same-parity parity z)
+    (if (null? z)
+      nil
+      (if (= parity 1)
+        (if (odd? (car z))
+          (cons (car z) (find-same-parity 1 (cdr z)))
+          (find-same-parity 1 (cdr z)))
+        (if (even? (car z))
+          (cons (car z) (find-same-parity 2 (cdr z)))
+          (find-same-parity 2 (cdr z))))))
+  (if (odd? x)
+    (cons x (find-same-parity 1 y))
+    (cons x (find-same-parity 2 y))))
+
+(define (same-parity first . rest)
+  (define (same-parity-iter source dist remainder-val)
+    (if (null? source)
+      dist
+      (same-parity-iter (cdr source)
+                        (if (= (remainder (car source) 2) remainder-val)
+                          (append dist (list (car source)))
+                          dist)
+                        remainder-val)))
+  (same-parity-iter rest (list first) (remainder first 2)))
+(same-parity 1 2 3 4 5 6 7)
+(same-parity 2 3 4 5 6 7)
+
+;; Exercise2.21
+(define (map proc items)
+  (if (null? items)
+    nil
+    (cons (proc (car items))
+          (map proc (cdr items)))))
+
+(define (squares items)
+  (map (lambda (x) (* x x)) items))
+(squares (list 1 2 3 4))
diff --git a/SICP/ex2_7.scm b/SICP/ex2_7.scm
new file mode 100644
index 0000000..54e8b70
--- /dev/null
+++ b/SICP/ex2_7.scm
@@ -0,0 +1,90 @@
+;; 2.1.4 Extended Exercise:Interval Arithmetic
+
+(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))))
+
+;; Todo:ensure this is right
+(define (div-interval x y)
+  (if (>= 0 (* (lower-bound y) (upper-bound y)))
+    (error "error!" y)
+    (mul-interval x
+                  (make-interval
+                    (/ 1.0 (upper-bound y))
+                    (/ 1.0 (lower-bound y))))))
+
+(define (make-interval a b) (cons a b))
+
+;; Exercise:2.7
+
+;; My version
+;; (define (lower-bound interval) (car interval))
+;; (define (upper-bound interval) (cdr interval))
+
+(define (lower-bound interval) (min (car interval)
+                                    (cdr interval)))
+(define (upper-bound interval) (max (car interval)
+                                    (cdr interval)))
+
+;; ???
+;; Exercise:2.8 
+(define (sub-interval x y)
+  (make-interval (- (lower-bound x) (upper-bound y))
+                 (- (upper-bound x) (lower-bound y))))
+
+(define (display-interval i)
+  (newline)
+  (display "[")
+  (display (lower-bound i))
+  (display ",")
+  (display (upper-bound i))
+  (display "]"))
+
+(define i (make-interval 1 5))
+(define j (make-interval 1 4))
+
+(display-interval i)
+(display-interval (sub-interval i j))
+(display-interval (sub-interval j i))
+
+;; Exercise:2.9
+
+(define (interval-width i)
+  (/ (- (upper-bound i) (lower-bound i))
+     2))
+
+(interval-width (make-interval 2 8))
+
+;; Exercise:2.10
+
+(define (div-interval x y)
+  (if (>= 0 (* (lower-bound y) (upper-bound y)))
+    (error "error!" 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 span-0 (make-interval -1 2))
+
+(display-interval (div-interval i j))
+(display-interval (div-interval i span-0))
+
+;; Exercise:2.11
+
diff --git a/SICP/test.pl b/SICP/test.pl
new file mode 100644
index 0000000..2d52981
--- /dev/null
+++ b/SICP/test.pl
@@ -0,0 +1,64 @@
+
+#!/usr/bin/perl
+# Author: Todd Larason <jtl@molehill.org>
+# $XFree86: xc/programs/xterm/vttests/256colors2.pl,v 1.1 1999/07/11 08:49:54 dawes Exp $
+
+# use the resources for colors 0-15 - usually more-or-less a
+# reproduction of the standard ANSI colors, but possibly more
+# pleasing shades
+
+# colors 16-231 are a 6x6x6 color cube
+for ($red = 0; $red < 6; $red++) {
+    for ($green = 0; $green < 6; $green++) {
+        for ($blue = 0; $blue < 6; $blue++) {
+            printf("\x1b]4;%d;rgb:%2.2x/%2.2x/%2.2x\x1b\\",
+               16 + ($red * 36) + ($green * 6) + $blue,
+               int ($red * 42.5),
+               int ($green * 42.5),
+               int ($blue * 42.5));
+        }
+    }
+}
+
+# colors 232-255 are a grayscale ramp, intentionally leaving out
+# black and white
+for ($gray = 0; $gray < 24; $gray++) {
+    $level = ($gray * 10) + 8;
+    printf("\x1b]4;%d;rgb:%2.2x/%2.2x/%2.2x\x1b\\",
+       232 + $gray, $level, $level, $level);
+}
+
+
+# display the colors
+
+# first the system ones:
+print "System colors:\n";
+for ($color = 0; $color < 8; $color++) {
+    print "\x1b[48;5;${color}m  ";
+}
+print "\x1b[0m\n";
+for ($color = 8; $color < 16; $color++) {
+    print "\x1b[48;5;${color}m  ";
+}
+print "\x1b[0m\n\n";
+
+# now the color cube
+print "Color cube, 6x6x6:\n";
+for ($green = 0; $green < 6; $green++) {
+    for ($red = 0; $red < 6; $red++) {
+        for ($blue = 0; $blue < 6; $blue++) {
+            $color = 16 + ($red * 36) + ($green * 6) + $blue;
+            print "\x1b[48;5;${color}m  ";
+        }
+        print "\x1b[0m ";
+    }
+    print "\n";
+}
+
+
+# now the grayscale ramp
+print "Grayscale ramp:\n";
+for ($color = 232; $color < 256; $color++) {
+    print "\x1b[48;5;${color}m  ";
+}
+print "\x1b[0m\n";
diff --git a/SICP/test.scm b/SICP/test.scm
new file mode 100644
index 0000000..46f73ee
--- /dev/null
+++ b/SICP/test.scm
@@ -0,0 +1,4 @@
+(define (plus x y)
+  (+ x y))
+
+(plus 2 3)
diff --git a/SICP/tmp.scm b/SICP/tmp.scm
new file mode 100644
index 0000000..aed388f
--- /dev/null
+++ b/SICP/tmp.scm
@@ -0,0 +1,66 @@
+(define (gcd a b)
+  (if (= b 0)
+    a
+    (gcd b (remainder a b))))
+;(define (make-rat n d) (cons n d))
+(define (make-rat n d)
+  (let ((g (gcd n d)))
+    (cons (/ n g)
+          (/ d g))))
+
+(define (numer x) (car x))
+(define (denom x) (cdr x))
+
+(define (add-rat x y)
+  (
+   make-rat (+ (* (numer x) (denom y))
+              (* (numer y) (denom x)))
+   (* (denom x) (denom y))))
+
+(define (sub-rat x y)
+  (make-rat (- (* (numer x) (denom y))
+               (* (numer y) (denom x)))
+            (* (denom x) (denom y))))
+
+(define (mul-rat x y)
+  (make-rat (* (numer x) (numer y))
+            (* (denom x) (denom y))))
+
+(define (div-rat x y)
+  (make-rat (* (numer x) (denom y))
+            (* (denom x) (numer y))))
+
+(define (equal-rat? x y)
+  (= (* (numer x) (denom y))
+     (* (numer y) (denom x))))
+
+(define (print-rat x)
+  (newline)
+  (display (numer x))
+  (display "/")
+  (display (denom x)))
+
+(define one-half (make-rat 1 2))
+(print-rat one-half)
+
+(define one-third (make-rat 1 3))
+(print-rat one-third)
+
+(print-rat
+  (mul-rat one-half one-third))
+
+(print-rat
+  (add-rat one-third one-third))
+
+(print-rat
+  (make-rat -1 1))
+
+(define (print-point p)
+  (newline)
+  (display "(")
+  (display (x-point p))
+  (display ",")
+  (display (y-point p))
+  (display ")"))
+
+(define ())