Nuts And Bolts
July 14, 2017
We begin by noting the problem is ill-specified. If three bolts are sizes 1, 2, and 3, and the only nut is size 5, there is no way to compare the bolts and determine which is larger; a similar problem occurs if there are three bolts of size 7, 8, 9 and only one nut of size 5. Thus, we must assume there is one and only one bolt larger than the largest nut. Given that restriction, the program is simple:
(define (biggest bolts nuts)
; assume there exists exactly one bolt bitter than all nuts
(if (null? bolts) #f
(let loop ((bolts (cdr bolts)) (nuts nuts) (biggest (car bolts)))
(cond ((null? nuts) biggest)
((<= (car nuts) biggest)
(loop bolts (cdr nuts) biggest))
((null? bolts) #f)
(else (loop (cdr bolts) nuts (car bolts)))))))
And here are some examples:
> (biggest '() '()) #f > (biggest '() '(4)) #f > (biggest '(4) '()) 4 > (biggest '(1 4 2) '(3)) 4 > (biggest '(7 8 9) '(5)) 7 > (biggest '(1 2 3) '(5)) #f
Note that 7 is the wrong answer for the fifth exercise, but there is more than one bolt bigger than the biggest nut, and there is no way to distinguish the largest, so the program simply returns the first.
You can run the program at http://ideone.com/8ToE3R.
The correct answer is obviously “There can be no such program”.
Of course, there can be such a program. But sometimes, there may be several biggest nuts:
(defun find-biggest-nut (nuts bolts) (loop :while (and (cdr nuts) bolts) :do (let ((bolt (pop bolts)) (bigger-nuts '()) (smaller-nuts '())) (dolist (nut nuts) (if (<= nut bolt) (push nut smaller-nuts) (push nut bigger-nuts))) (setf nuts (or bigger-nuts smaller-nuts))) :finally (return nuts))) (defun set-equalp (a b) (and (subsetp a b) (subsetp b a))) (assert (set-equalp (find-biggest-nut '(1 2 3 4 5) '(1 2 3 4)) '(5))) (assert (set-equalp (find-biggest-nut '(1 2 3 4 5 6) '(1 2 3 4)) '(5 6))) (assert (set-equalp (find-biggest-nut '(1 2 3 4 5 6) '(1 2 3 4 7)) '(5 6)))Consider the case where the bag of nuts contains one nut, which is bigger than all of the bolts. Nothing in the task description rules this out. In this case it is impossible to discriminate between the bolts. John Cowan is right.