[racket-dev] [racket] A puzzle

Anyone up for a dissertation? Multi-stepping debugging is, eh, pushing it. 




On Jan 19, 2011, at 2:43 PM, Doug Orleans wrote:

> The following program was a puzzle in the 2011 MIT Mystery Hunt held last weekend.  (I'm not linking directly to the site because they posted a solution and I don't want you to be tempted to look at the answer prematurely...)  I was disappointed that Dr Racket doesn't seem to have a multi-threaded stepping debugger, at least not in a form that could easily run this program-- correct me if I'm wrong.
> 
> I would be interested to hear what other ideas people have about solving this puzzle, either automatically or by hand (or some combination).  But, I haven't solved it myself yet, so I may be avoiding reading replies for a while...
> 
> --Doug
> 
> 
> 
> Efficiency
> The Prince is quite proud of his competitive Katamari-rolling time record, having mastered the art of multitasking.
> 
> All procedure calls are evaluated from left to right.
> 
> 
> 
> 
> 
> (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)))
> 
> 
> (define a 2)
> (define b '(11))
> (define c 5)
> (define d 30)
> (define e 3)
> 
> (thread
>  (lambda ()
>    (set! a (* a (first a)))
>    (send a)
>    (set! c (lambda () (- b 4)))
> 
> 
>    (set! c (lambda () (- b 11)))
> 
>    (set! d (rest d))
>    (sendc (/ 4 (+ (- c) c)))
>    (set! a (sqrt (+ c (* c c))))
>    (sendc b)
>    (set! b '(((24 12 15 (2))) 1 (5 1) 3 2 8 10 (9 1 (3)) ((3) (1)) 5 14 10))
> 
> 
>    (set! d '())
> 
>    (sendc (length (append c b)))
>    (sendc (length (append a b c c c d)))
>    (set! d 2)
>    (map (lambda (x)
>           (set! c (first b))
>           (sendc x)
>           (set! b c)) a)
> 
> 
>    (send (* (+ 3 (first c)) 100 (- (sqrt a) 1)))
> 
>    (set! a (+ a 1))
>    (set! e (- e 1))
>    ))
> 
> (thread
>  (lambda ()
>    (set! a (list c))
>    (set! a (lambda (x) (if x (sendc x) x)))
>    (let loop ()
> 
> 
>      (set! b (c))
> 
>      (if (a b)
>          (loop)
>          (set! d '(2 4 8 16 32))))
>    (set! c (first d))
>    (set! c (second d))
>    (set! b (- a (sqrt (first d))))
>    (set! a (list 14 (- (length b) 1) c))
> 
> 
>    (let loop ()
> 
>      (set! d b)
>      (if (null? d)
>          (set! a (+ a 1))
>          (begin
>            (sendc (first d))
>            (set! b (rest d))
>            (loop))))
>    (set! e (- e 1))
>    ))
> 
> 
> 
> 
> (thread
>  (lambda ()
>    (set! b d)
>    (set! c (lambda () (/ b 2)))
>    (let loop ()
>      (set! d (- d 10))
>      (if (and (= d 0)
>               (= b 0)
> 	      (< b 0))
>          (set! b #f)
> 
> 
>          (loop)))
> 
>    (set! c (first d))
>    (set! a 0)
>    (sendc (length b))
>    (set! c (list (second b)))
>    (sendc (sqrt (+ 12 (length d))))
>    (send (+ (/ (foldl * 26 a)
>                (+ (length (append a b))
> 
> 
> 		  (* (length c) (length c))))
> 
>             d))
>    (set! a (first b))
>    (sendc (/ 204 a))
>    (set! e (- e 1))
>    ))
> 
> (let loop ()
>   (if (> e 0)
>       (loop)
>       (newline)))
> 
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users