; First, possible mobile and branch abstractions: (define make-mobile cons) (define left-branch car) (define right-branch cdr) (define make-branch cons) (define len car) (define struct cdr) (define weight? number?) (define mobile? pair?) ; Here is a test mobile so we can have a sample input to the ; programs, below. Note that we must adhere to the abstractions. (define m (make-mobile (make-branch 6 (make-mobile (make-branch 1 8) (make-branch 4 2))) (make-branch 5 12))) ; OK, now check out the elegance of the program. (This is the ; part that really appeals to the mathematician in me. Yeah, ; so that may seem weird, but you should be used to me by now.) ; ; The torque of a branch is its length times its total weight. ; To get the total weight of a branch, it's either going to be ; a single weight or the total weight of the mobile hanging off ; that branch... (define (branch-weight branch) (let ((thing (struct branch))) ; to minimize computation (cond ((weight? thing) thing) ; the thing is a weight (else (mobile-weight thing))))) ; thing is a mobile ; And we have a great case for mutual recursion because the ; weight of a mobile is simply the sum of the weights of its ; branches. And we already have a function that figures out ; the weight of a branch, above. (define (mobile-weight mobile) (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile)))) ; And now the beautiful algorithm. First, torque, which is ; the length of a branch times its weight... (define (torque branch) (* (len branch) (branch-weight branch))) ; And now balanced? The base case is essentially a weight. ; If a weight is reached, it's balanced. If a mobile is ; reached, then if its left side torque equals its right ; side torque AND any sub-mobiles of the mobile are also ; balanced, this predicate should return #t. Otherwise, it ; should return #f. (define (balanced? mobile) (or (weight? mobile) (and (= (torque (left-branch mobile)) (torque (right-branch mobile))) (balanced? (struct (left-branch mobile))) (balanced? (struct (right-branch mobile)))))) ; Eh? ; ; Certainly, this could have been written with an if or a cond, ; but it turns out there is no need. ; ; If the mobile is a weight, the first part of the or will be #t ; and Scheme's or is a special form, using normal-order evaluation. ; ; Note that it makes sense to consider the possibility of a mobile ; simply being a weight. A weight isn't going to tilt left or ; right. It will simply sit there. That's as balanced as it gets. ; ; If the mobile is not a weight, then the and will be computed. ; The and will not bother to compute either of the balanced? predicates ; if the torques are not equal due to normal-order evaluation. ; ; There are other ways to approach this problem, but this is as ; close as I can come to translating a problem description in ; English into code in any programming language.