Solution to Efficiency

by Alex Vandiver, Reid Barton and John Danaher

; This scheme program is three interwoven threads of computation, with
; four shared variables. The code is intentionally written with race
; conditions and interdependencies between the threads. Untangling (or
; re-tangling, depending on your view) the code correctly causes it to
; print the answer, 10PLACEMENS2004OLYMPIC1500M, cluing the
; mostly-unknown runner from Ethiopia, MULUGETA WENDIMU.
; The version of the code below properly interleaves the threads to
; produce the correct output, and includes a somewhat-convincing argument
; of why things should be in this order. Each statement is assigned a
; number to track the ordering between threads, which are called X, Y, and Z.

(define (send x)
  (if (or (integer? x) (char? x))
      (display x)
      (send x))
(define (sendc x)
  (if (and (>= x 0) (< x 26))
      (send (integer->char (+ 65 x)))
      (sendc x)))

; Helpers to check that we unroll loops the correct number of times.
(define (expect-true x)
  (if (not x) (error "")))
(define (expect-false x)
  (if x (error "")))

(define a 2)
(define b '(11))
(define c 5)
(define d 30)
(define e 3)

; X1 requires a be a number then a list. a is set to a list only by Y1.
; Conceivably Z8 could come before Y1, but trying to do that would just
; get you trapped in the loop condition in Z5.
(let ((a-tmp a))
   (set! a (list c))                              ;Y1
   (set! a (* a-tmp (first a)))                          ;X1
; X2 must come before Y2, or else after Y13 or Z8, but we need
; the lambdas from X3-X4 to successfully get through Y4 and Z5.
   (send a)                                              ;X2
   (set! a (lambda (x) (if x (sendc x) x)))       ;Y2
; Before we get to Y3, we must assign a lambda to c: X3, X4, or Z2.
; Since all those lambdas require z to be numeric before they can be
; evaluated, do Z1 first.
   (set! b d)                              ;Z1
; The only lambda in a came from Y2, so (a b) can only be false if
; b is false. We can't get past Y6 until then. The only other way b can
; become false is Z5, so we need to get to Z5. That requires the
; conditions in Z4-Z6 to be true. And we can't progress on X past the
; two set-c-lambdas yet, since X5 requires d to be a list and nothing
; before the ends of the Y or Z loops can make it one.
;   To get Z4-Z6 all true, we need b to hit exactly 0. The only way to
; modify b is by evaluating the lambdas to subtract 4 or 11 from it,
; or divide it by 2. Once we subtract 11 we can't subtract 4 anymore
; and once we switch away from any operation we can't switch back. So:
; (30/2)-4-11 works. (30/2/2) gives a fraction. (30-4) is already a
; bad start, since it would call sendc on 26. (30-11) gives 19, from
; where you can't get anywhere: -4 is already gone, and -11 puts it
; at 8 which is too small. So (30/2)-4-11 it is.
   (set! c (lambda () (/ b 2)))            ;Z2
     (set! b (c))                                 ;Y3
     (expect-true (a b))                          ;Y4
         ;(loop)                                  ;Y5->Y3
   (set! c (lambda () (- b 4)))                          ;X3
     (set! b (c))                                 ;Y3
     (expect-true (a b))                          ;Y4
         ;(loop)                                  ;Y5->Y3
   (set! c (lambda () (- b 11)))                         ;X4
     (set! b (c))                                 ;Y3
     (expect-true (a b))                          ;Y4
         ;(loop)                                  ;Y5->Y3
; Now that b is 0, we get d down to 0:
     (set! d (- d 10))                     ;Z3
     (expect-false (and (= d 0)            ;Z4
                        (= b 0)
	                (< b 0)))
         ;(loop)))                         ;Z6->Z3
     (set! d (- d 10))                     ;Z3
     (expect-false (and (= d 0)            ;Z4
                        (= b 0)
	                (< b 0)))
         ;(loop)))                         ;Z6->Z3
     (set! d (- d 10))                     ;Z3
; And once d is exactly 0, this is our only opportunity to break out of
; this loop, so we need to interleave with another -11 to b. We can't
; evaluate (a b) again before we set b to something else, since otherwise
; it will try to sendc -11.
(let ((d-tmp d) (b-tmp b))
     (set! b (c))                                 ;Y3
     (expect-true (and (= d-tmp 0)         ;Z4
                       (= b-tmp 0)
	               (< b 0)))
         (set! b #f)                       ;Z5->Z7
     (expect-false (a b))                         ;Y4
         (set! d '(2 4 8 16 32))                  ;Y6
; And now d is a list, so X can proceed again. [We have 10PLA so far.]
; The next minipuzzle is that we need to get the assignments to c correct
; to get through X6 and X7. The only numbers ever assigned to c are from
; Y7, Y8, and Z7. All take from an element of d, and we can choose where
; to put X5, but still we only have (2 4 8) to work with.
; First we need an assignment to c in the middle of X6 such that c1 and c2
; are different, and c2-c1 is either 1, 2, or 4. So c2 is 4 and c1 is 2.
; To get c1 is 2, we need to take from d before we cdr it, and for
; maximum flexibility let's say we do it with Y7:
   (set! c (first d))                             ;Y7
; Now we need to get c to be 4. This could be either by taking (second d)
; or a cdr then first. But in X7, we'll need (c3 + (c4 * c5)) to be square.
; Since 2+2*2=6, 4+4*4=20, and 8+8*8=72 are all nonsquare, we need at
; least one interleaved assignment to c. That's the last assignment we
; have available, so we know there's none between c2 and c3 so c3=4.
; Now, (4 + (c4 * c5))... 4+4*2=12, 4+4*8=36 (ding!), 4+2*2=8, 4+8*8=68.
; The only answer is to interleave c=8 between c4 and c5, and the only
; way to do that is to take the second after the cdr here. That only
; leaves a first to assign to c2, so the cdr must come before that.
   (set! d (rest d))                                     ;X5
(let ((c1 c))
   (set! c (first d))                      ;Z7
   (sendc (/ 4 (+ (- c1) c)))                            ;X6
(let ((c3 c) (c4 c))
   (set! c (second d))                            ;Y8
   (set! a (sqrt (+ c3 (* c4 c))))                       ;X7
; [That gives 10PLAC]
; We need b to be a number before we can run X8 (it's #f). That can
; only happen in Y9. When we run Y9, we need it to give a positive
; result, which probably means a is positive since d won't contain 0.
; If we run Z8, a becomes 0, and there's no way to make it positive
; again until Z13. So either we run Z8-Z13 uninterrupted or we run
; Y9 now. But Z10 can't run since #f doesn't have a second. Y9 it is.
   (set! b (- a (sqrt (first d))))                ;Y9
; Now Z9 can't run until X9 makes b a list again. Nor can Y10. So
; we can maybe run Z8, but after that X8 would be the only option,
; and then X9. Since Z8 is independent of X8 and X9, arbitrarily
; say we do those first without figuring out where Z8 goes just yet.
   (sendc b)                                             ;X8
   (set! b '(((24 12 15 (2))) 1 (5 1) 3 2 8 10 (9 1 (3)) ((3) (1)) 5 14 10)) ;X9
; Now b and d are lists, while a is 6 and c is 8. We can't get to X11
; until c is a list, and only Z10 can do that. But we need a to be a
; list for X12, and only Y10 can do that, so Y10 must come after Z8
; sets a to 0.
   (set! a 0)                              ;Z8
; Z11 needs 12+(length d) to be square. If we run X10
; before Z11, we also need to get through a few loops in Y11-Y15 first
; so that b is again a list of length 4. But we can't run Y11 until
; b is a list whose first element is a number, unless we cheat out
; of Y12 by running X10 between Y11 and Y12. Assuming we don't do
; that cheat, Z9-Z10 must come before X10. And we need a to be
; a list of numbers, so Y10 must come before Z10.
   (set! a (list 14 (- (length b) 1) c))          ;Y10
   (sendc (length b))                      ;Z9
   (set! c (list (second b)))              ;Z10
   (sendc (sqrt (+ 12 (length d))))        ;Z11
; Now let's think about that cheat. We need a to be numeric when we
; get to Y13, so we need Z13 to run before Y13. But we need X13 to
; run before Z12. And we can't do a single honest loop through Y12-Y15
; before we do some X14-X16. So if we cheat it must be the very first iteration,
; between Y11 and X14, where we would slip in X10-X13 and then Z12-Z13. But
; in that case (first b) will still be a list, so Z13 will make a
; be a list, and Y13 will still not work. So the cheat doesn't work.
; Hooray!
;   Anyway, now we still can't run Y11 until after X14-X16 does its thing,
; and we can't run Z12 until after X13, so X10-X13 must come now.
   (set! d '())                                          ;X10
   (sendc (length (append c b)))                         ;X11
   (sendc (length (append a b c c c d)))                 ;X12
   (set! d 2)                                            ;X13
; This is the first place that Z12 can run, now that d is 2. And as
; it turns out, it's also the last, since it will produce a fraction
; if it runs once the map starts (by trial and error), and once the
; loop starts, d becomes a list again and never again becomes a
; number.
   (send (+ (/ (foldl * 26 a)              ;Z12
              (+ (length (append a b))
                  (* (length c) (length c))))
; Now we finally hit the loop in X14-X16. Each iteration stores (first b)
; into c and then c into b, so each iteration effectively cars down b.
(let ((a-map a))
   (set! c (first b))                                    ;X14
   (sendc (first a-map))                                 ;X15
   (set! b c)                                            ;X16->X14
(set! a-map (rest a-map))
   (set! c (first b))                                    ;X14
   (sendc (first a-map))                                 ;X15
   (set! b c)                                            ;X16->X14
; At this point, b is (24 12 15 (2)) so we've met the constraint for
; Y11: (first b) is a list. X14-X15 could still go forward on the
; last iteration of the map, but if they did so before b becomes ((2)) then
; either X16 will assign a number to b while Y is still looping, or else
; Y will try to print (first b) when b eventually becomes ((2)). Either way
; there will be an error.
;   Short version: X14 can't run again until b is ((2)).
;   And also, in the meantime, we ultimately need a to end up either 1
; or 2 less than a square, so that X17 can run either before or after Y13.
; All that's available for Z13 to choose from is what's in b now. Of those
; values, 24, 15, or 2 all work, but only 15 works for Z14 as well. (Even
; though 2+1+1=4 divides 204, the result is too large for sendc.)
   (set! d b)                                     ;Y11
     (expect-false (null? d))                     ;Y12
           (sendc (first d))                      ;Y14
           (set! b (rest d))                      ;Y15
           ;(loop))))                             ;Y16->Y11
   (set! d b)                                     ;Y11
     (expect-false (null? d))                     ;Y12
           (sendc (first d))                      ;Y14
           (set! b (rest d))                      ;Y15
           ;(loop))))                             ;Y16->Y11

; We're two cdrs in, so b is (15 (2)), giving us the 15 we wanted.
   (set! a (first b))                      ;Z13
   (set! d b)                                     ;Y11
     (expect-false (null? d))                     ;Y12
           (sendc (first d))                      ;Y14
           (set! b (rest d))                      ;Y15
           ;(loop))))                             ;Y16->Y11
; Time for the last iteration of the map, to get ((2)) to (2). 
(set! a-map (rest a-map))
   (set! c (first b))                                    ;X14
   (sendc (first a-map))                                 ;X15
   (set! b c)                                            ;X16->X14
(expect-true (null? (rest a-map))))
; Nothing stops X17 from running here, so let it run even though it really
; was meant to be farther down.
; And then the last couple iterations of the loop.
   (set! d b)                                     ;Y11
     (expect-false (null? d))                     ;Y12
           (sendc (first d))                      ;Y14
           (set! b (rest d))                      ;Y15
           ;(loop))))                             ;Y16->Y11
   (set! d b)                                     ;Y11
     (expect-true (null? d))                      ;Y12
         (set! a (+ a 1))                         ;Y13
 ; Now that a=16 it's finally possible to run X17.
   (send (* (+ 3 (first c)) 100 (- (sqrt a) 1)))         ;X17
   (set! a (+ a 1))                                      ;X18
; All that's left now is Z14, and it works now that a=17.
   (sendc (/ 204 a))                       ;Z14
; Well, all except the final decrements to e.
   (set! e (- e 1))                                      ;X19
   (set! e (- e 1))                               ;Y17
   (set! e (- e 1))                        ;Z15