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))
(flush-output)
#t)
(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))))
d))
; 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