summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorbnewbold <bnewbold@eta.mit.edu>2009-03-29 16:57:47 -0400
committerbnewbold <bnewbold@eta.mit.edu>2009-03-29 16:57:47 -0400
commitab0abf13b69d0911cde46bdafedcef4d485f63f3 (patch)
tree5de541545c18c649b7ba0b75b3c0b75715ffc3e9
parent101810266cb649d530827a49cb1dc907d4c9da93 (diff)
download6.945-ab0abf13b69d0911cde46bdafedcef4d485f63f3.tar.gz
6.945-ab0abf13b69d0911cde46bdafedcef4d485f63f3.zip
done...
-rw-r--r--ps07_amb/bnewbold_ps07.txt56
-rw-r--r--ps07_amb/bnewbold_ps07_work.scm219
2 files changed, 270 insertions, 5 deletions
diff --git a/ps07_amb/bnewbold_ps07.txt b/ps07_amb/bnewbold_ps07.txt
index 27bc791..aa91f6a 100644
--- a/ps07_amb/bnewbold_ps07.txt
+++ b/ps07_amb/bnewbold_ps07.txt
@@ -13,7 +13,61 @@ the who-owns-what-yacht pairings by hand because it only takes one elimination.
[see code in bnewbold_ps07_work.scm]
-Problem 7.2:
+Problem 7.2: Continuation Returning
+---------------------------------------
+At the return of every branch I printed the result; if a #t result thunked up
+through the return structure normally, there would be a series of statements
+printed, instead there's just the #t.
+
+[see code in bnewbold_ps07_work.scm]
+
+Problem 7.3: Depth vs. Breadth
+--------------------------------
+The breadth-first essentially trys all combinations by incrementing the final
+element of the triple while the depth first increments the first digit; the
+first-digit incrementing comes to (12 16 20) with fewer steps. I checked this
+by pp-ing every tested triple.
+
+The extra fail calls are coming from the require in integer-between; eg when
+i=10, j increments up to j=20 at which point the selection of k fails.
+
+The depth-first method would try to first enumerate all possible first-digits
+then proceed to the second digits; with a-pythagorean-triple-from, the number
+of possible first-digits is infinite, so evaluation would never proceed beyond
+that point.
+
+[see code in bnewbold_ps07_work.scm]
+
+Problem 7.4: No Such Problem?
+-----------------------------------------------
+
+Problem 7.5: Alternative Alternation Orders
+-----------------------------------------------
+I wrote an itinerary generator based on budget; you wouldn't want to go through
+the itineraries with a regular left-to-right type schedule or really any order,
+you would want a randomly different itinerary (fitting the constraints and
+not something you've done before) every time.
+
+In the end though, the list comes out fairly ordered, I guess the only way to
+really get a totally random list would be to build an entire search schedule
+without evaluating the last step of each, then randomize the entire schedule
+and go through evaluating.
+
+[see code in bnewbold_ps07_work.scm]
+
+Problem 7.6:
--------------------------------
+This doesn't seem too mysterious to me, maybe I don't fully understand the
+question. When each variable {x,y,z} is assigned an amb value withing a let,
+that value (within the let environment) is stored in following continuations.
+When using set! the variable values are not stored in later continuations, or
+more technically, the set! alters the value of the variables in all
+continuations (globally). So when a continuation gets called, the value of
+{x,y,z} is not the value from when that continuation was stored, but global
+value, aka the last value set!.
+When going depth-first, the continuations reach back far enough that the
+variables get reset properly. Another way of stating this is that the order of
+evaluation procedes in just the right order so that the globaly set! value
+is the appropriate one for each individual alternative continuation.
diff --git a/ps07_amb/bnewbold_ps07_work.scm b/ps07_amb/bnewbold_ps07_work.scm
index 9419ac8..f134fa7 100644
--- a/ps07_amb/bnewbold_ps07_work.scm
+++ b/ps07_amb/bnewbold_ps07_work.scm
@@ -2,7 +2,7 @@
;;; 03/28/2009
;;; Bryan Newbold <bnewbold@mit.edu>
-;(load "load")
+(load "load")
;;;------------------------------------------------------------------------
;;; Problem 7.1: Warmup
@@ -50,8 +50,9 @@
(newline)
(amb))))
-(with-depth-first-schedule find-daughters)
+
#|
+(with-depth-first-schedule find-daughters)
((ann hall) (gabrielle moore) (lorna parker) (rosaline downing) (melissa hood))
((ann moore) (gabrielle hall) (lorna downing) (rosaline parker) (melissa hood))
;Value: #f
@@ -65,7 +66,7 @@
(lambda (return)
(letrec ((hunt (lambda (s)
(cond ((null? s) #f)
- ((list? (car s)) (or (hunt (car s))
+ ((pair? (car s)) (or (hunt (car s))
(hunt (cdr s))))
((eq? (car s) 'snark) (return #t))
(else (hunt (cdr s)))))))
@@ -74,6 +75,216 @@
#|
(snark-hunt '(a (1 2 3) v w))
; #f
-(snark-hunt '(a (1 2 'snark 3) v w))
+(snark-hunt '(a (1 2 snark 3) v w))
+; #t
+(snark-hunt '(((a b c) d (e f)) g (((snark . "oops") h) (i . j))))
; #t
+|#
+
+(define (snark-hunt/instrumented l)
+ (call-with-current-continuation
+ (lambda (return)
+ (letrec ((hunt (lambda (s)
+ (cond ((null? s) #f)
+ ((pair? (car s))
+ (let ((result (or (hunt (car s))
+ (hunt (cdr s)))))
+ (display ";Found: ")
+ (display result)
+ (newline)
+ result))
+ ((eq? (car s) 'snark) (return #t))
+ (else (hunt (cdr s)))))))
+ (hunt l)))))
+
+
+#|
+(snark-hunt/instrumented '(a (1 2 3) v w))
+;Found: #f
+;Value: #f
+
+(snark-hunt/instrumented '(a (1 2 snark 3) v w))
+;Value: #t
+
+(snark-hunt/instrumented '(((a b c) d (e f)) g (((snark . "oops") h) (i . j))))
+;Found: #f
+;Found: #f
+;Value: #t
+
+|#
+
+
+;;;------------------------------------------------------------------------
+;;; Problem 7.3
+
+(define (a-pythagorean-triple-between/verbose low high)
+ (let ((i (an-integer-between low high)))
+ (let ((j (an-integer-between i high)))
+ (let ((k (an-integer-between j high)))
+ (set! count (+ count 1))
+ (pp (list i j k))
+ (require (= (+ (* i i) (* j j)) (* k k)))
+ (list i j k)))))
+
+(define count 0)
+
+#|
+(begin
+ (init-amb)
+ (set! count 0)
+ (with-breadth-first-schedule
+ (lambda () (pp (a-pythagorean-triple-between/verbose 10 20)))))
+
+(begin
+ (init-amb)
+ (set! count 0)
+ (with-depth-first-schedule
+ (lambda () (pp (a-pythagorean-triple-between/verbose 10 20)))))
+|#
+
+;;;------------------------------------------------------------------------
+;;; Problem 7.4
+
+(define (a-nice-itinerary budget)
+ (let ((city (amb '(boston 0)
+ '(san-fransisco 250)
+ '(nyc 30)
+ '(paris 500)
+ '(london 500)
+ '(auckland 1500)))
+ (meal (amb '(steak 30)
+ '(falafel 8)
+ '(foi-gras 100)
+ '(dumpster-dive 0)))
+ (hotel (amb '(ritz 800)
+ '(hostel 20)
+ '(couch 0)))
+ (drinks (amb '(0 0)
+ '(1 5)
+ '(2 10)
+ '(3 15)
+ '(4 20)
+ '(5 25)
+ '(6 30)))
+ (activity (amb '(museum 15)
+ '(concert 20)
+ '(opera 100)
+ '(park 0))))
+ ; stay on budget:
+ (require (>= budget
+ (fold + 0 (map cadr (list city meal hotel drinks activity)))))
+ ; mad cow:
+ (require (not (and (equal? meal 'steak) (equal? city 'london))))
+ ; get lost:
+ (require (not (and (equal? city 'nyc) (> (car drinks) 3))))
+ (pp (map car (list city meal hotel drinks activity)))
+ (amb)))
+
+; (a-nice-itinerary 40)
+
+(define (randomize l)
+ (if (null? l)
+ '()
+ (let ((e (list-ref l (random (length l)))))
+ (cons e (randomize (list-difference l (list e)))))))
+
+#|
+(randomize '(1 2 3 4 5))
+;Value: (3 5 2 1 4)
+;Value: (1 5 4 3 2)
+;Value: (3 4 5 1 2)
+;Value: (5 4 1 2 3)
+;Value: (5 1 3 4 2)
+;Value: (2 5 4 1 3)
+;Value: (1 3 2 5 4)
+;Value: (3 2 1 4 5)
+|#
+
+(define (add-left-to-right alternatives)
+ (for-each (lambda (alternative)
+ (push! *search-schedule* alternative))
+ (reverse alternatives)))
+
+(define (add-right-to-left alternatives)
+ (for-each (lambda (alternative)
+ (push! *search-schedule* alternative))
+ alternatives))
+
+(define (add-randomly alternatives)
+ (for-each (lambda (alternative)
+ (push! *search-schedule* alternative))
+ (randomize alternatives)))
+
+(define (with-left-to-right-alternation thunk)
+ (call-with-current-continuation
+ (lambda (k)
+ (fluid-let ((add-to-search-schedule
+ add-left-to-right)
+ (*search-schedule* (empty-search-schedule))
+ (*top-level* k))
+ (thunk)))))
+
+(define (with-right-to-left-alternation thunk)
+ (call-with-current-continuation
+ (lambda (k)
+ (fluid-let ((add-to-search-schedule
+ add-right-to-left)
+ (*search-schedule* (empty-search-schedule))
+ (*top-level* k))
+ (thunk)))))
+
+(define (with-random-alternation thunk)
+ (call-with-current-continuation
+ (lambda (k)
+ (fluid-let ((add-to-search-schedule
+ add-randomly)
+ (*search-schedule* (empty-search-schedule))
+ (*top-level* k))
+ (thunk)))))
+
+#|
+(begin
+ (init-amb)
+ (with-left-to-right-alternation
+ (lambda ()
+ (pp (a-pythagorean-triple-between/verbose 10 20)))))
+
+(10 10 10)
+(10 10 12)
+(10 10 13)
+(10 10 14)
+(10 10 15)
+(10 10 16)
+(10 10 17)
+(etc)
+
+(begin
+ (init-amb)
+ (with-right-to-left-alternation
+ (lambda ()
+ (pp (a-pythagorean-triple-between/verbose 10 20)))))
+
+(20 20 20)
+(19 20 20)
+(19 19 20)
+(19 19 19)
+(18 20 20)
+(18 19 20)
+(etc)
+
+
+(begin
+ (init-amb)
+ (with-random-alternation
+ (lambda ()
+ (pp (a-pythagorean-triple-between/verbose 10 20)))))
+
+(10 13 13)
+(10 13 15)
+(10 13 16)
+(10 13 18)
+(10 13 19)
+(10 13 20)
+(etc)
+
|# \ No newline at end of file