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.

Advertisements

Pages: 1 2

3 Responses to “Nuts And Bolts”

  1. John Cowan said

    The correct answer is obviously “There can be no such program”.

  2. 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)))
    
  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: