4
\$\begingroup\$

The problem is:

Define a procedure that takes 3 number arguments and returns the sum of the squares of the 2 largest numbers.

I am a CS graduate and I am revising my university notes. This is my code so far:

(define (square n) (* n n))

(define (square_of_larger_numbs a b c)
  (cond ((and (> a b) (> a c))
         (cond ((> b c)
         (+ (square a) (square b)))
               (else (+ (square a) (square c))))
        )(else (cond ((> b c)
                      (+ (square b) (square c)))
                      (else (+ (square b) (square c))))
               )
         )
  )


(display (square_of_larger_numbs 4 3 3))

It seems to be working but the code looks terrible unreadable. Please note that I am not allowed to sort yet, as the book I am reading hasn't mentioned sorting yet, so I assumed that sorting is not welcomed as a part of the solution.

How can I make this more efficient/ readable?

\$\endgroup\$
  • \$\begingroup\$ You made a start by splitting out the square function. To improve this, you need to do more of that, so that each step is a clean function. It is much easier to create a tidy, robust and legible solution like that. Answer with examples attached. \$\endgroup\$ – itsbruce Feb 1 '15 at 20:29
-3
\$\begingroup\$

Edit: Also take a look at Sum of squares of two largest of three numbers and SICP Exercise 1.3 request for comments for more.

First of all the code isn't entirely correct, (s-o-l-n 2 3 1) returns 10 (choosing 3 and 1), where it should return 13.

Then a few points on the style:

  • Don't put the ending parens on their own line, that's not idiomatic and looks weird. You can (should) also choose an editor which will automatically balance parens to make your life much easier (and also keeps track of indentation).
  • Use dashes instead of underscores or camel-case - square_of_larger_numbs should be square-of-larger-numbers in line with usual Scheme names (few abbreviations).

For cond I would choose one style, either putting the clauses to the right of the cond, or below; in either case, the indentation for the else case should match the other cases. Since you only have two cases, using if would probably be preferred though, as there is no benefit to using cond with only one form in the clause body.

And you could switch the order of operations around, first calculating the squares and then comparing them, that way you get rid of a lot of square calls. Edit: If you have negative input that wouldn't work though as @benrudgers commented, the code is corrected accordingly.

In summary I would write the following instead:

(define (square n) (* n n))

(define (square-of-larger-numbers a b c)
  (let ((a2 (square a))
        (b2 (square b))
        (c2 (square c)))
    (cond
     ((and (>= a b) (>= a c))
      (cond
       ((> b c)
        (+ a2 b2))
       (else
        (+ a2 c2))))
     ((and (>= b a) (>= b c))
      (cond
       ((> a c)
        (+ b2 a2))
       (else
        (+ b2 c2))))
     (else
      (cond
       ((> a b)
        (+ c2 a2))
       (else
        (+ c2 b2)))))))

(display (square-of-larger-numbers 4 3 3))

That is not the most efficient though, albeit readable (one case for each maximum value). The following implements a limited sort instead, so the process is then sort the input (till where you want it to be sorted), then process the sorted values.

Edit: You noted that sorting wasn't yet mentioned, but at least the comparison you already had were implementing a sort-of sort already, so given that I think this is still applicable. The links above have some other suggestions that would also get rid of all sorting.

Take a look at Sorting networks for more information on that. In Lisp/Scheme it is also possible to abstract that kind of computation into a macro (cf. Let Over Lambda chapter 7.6 for an implementation of that), so assuming we had one already, something like (sorting-network 3) would then generate a function like sort-3 below.

Also note that the use of cond/set! here isn't the best, ideally a separate macro rotate! would be used to switch a number of variables in-place (i.e. (if (> c a) (rotate! a c))) and the return value would use (values a b c) instead to prevent additional memory allocation if applicable in the implementation.

(define (square n) (* n n))

(define (sort-3 a b c)
  (cond
   ((> c a)
    (let ((a* a))
      (set! a c)
      (set! c a*))))
  (cond
   ((> c b)
    (let ((b* b))
      (set! b c)
      (set! c b*))))
  (cond
   ((> b a)
    (let ((a* a))
      (set! b a)
      (set! a b*))))
  (list a b c))

(define (square-of-larger-numbers a b c)
  (let ((result (sort-3 a b c)))
    (+ (square (car result)) (square (cadr result)))))

(display (square-of-larger-numbers 4 3 3))
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Sorting the squares is contrary to the specification and leads to an incorrect implementation which does not account for negative numbers. In addition the suggested code is more complex than the original rather than less so. It does not utilize lexical scope to hide implementation details of square-of-larger-numbers. sort/3 does not use descriptive variable names, uses mutation, repeats code patterns, and does not follow the scheme naming convention of using -. \$\endgroup\$ – ben rudgers Feb 1 '15 at 17:20
  • 1
    \$\begingroup\$ It is also just terrible, non-functional code with duplication everywhere. \$\endgroup\$ – itsbruce Feb 1 '15 at 18:20
  • \$\begingroup\$ Thanks @benrudgers, I've changed it to account for negative numbers. Agreed, it's a bit longer, though the pattern is very regular, I don't think abbreviating it by macros is necessary, but I've mentioned how to do that regardless - the linked solutions are all shorter anyway. I've changed the / to a -. Could you explain what you mean by "does not utilize lexical scope to hide implementation details"? \$\endgroup\$ – ferada Feb 1 '15 at 19:09
  • \$\begingroup\$ sort-3 is implemented at the top level rather than within the lexical scope of square-of-larger-numbers. This means sort-3 can be called anywhere square-of-larger-numbers can be called. Other code may come to depend on it in ways that will break if it's implementation changes. Since the intent is only to use sort-3 within square-of-larger-numbers it would be better to use (let ((sort-3 (lambda (lst) ...)))...) to define it within the lexical scope of square-of-larger-numbers. \$\endgroup\$ – ben rudgers Feb 1 '15 at 20:25
0
\$\begingroup\$

Specification

It is helpful to specify the solution before writing code. The mathematics of sorting three values (a b c) means there are six (3!) permutations:

(define abc (a b c))
(define acb (a c b))
(define bac (b a c))
(define bca (b c a))
(define cab (c a b))
(define cba (c b a))

The code must cover all six possibilities.

There are three possible outputs:

(define output-ab (+ (* a a) (* b b)))
(define output-ac (+ (* a a) (* c c)))
(define output-bc (+ (* b b) (* c c)))

The code must map the six permutations to the three outputs.

abc || bac -> output-ab
acb || cab -> output-ac
bca || cba -> output-bc

Now the code can reflect the specification

   (cond 

     ((or (and (>= a b)
               (>= b c))
          (and (>= b a))
               (>= a c)))
      output-ab)

     ((or (and (>= a b)
               (>= c b))
          (and (>= a b))
               (>= c a)))
      output-ac)

     ((or (and (>= b a)
               (>= c a))
          (and (>= c b))
               (>= b a)))
      output-bc)

     (else (error "unhandled condition")))

Review

Style

Scheme has formatting conventions. The code does better with indentation than with parenthesis.

Logic

The lack of a specification and tests based upon it leads to an incorrect implementation and poorly organized code. There is a branch which returns the same value on both paths:

 (else (cond ((> b c)
                (+ (square b) (square c)))
              (else (+ (square b) (square c))))

Efficiency

Correct code is the first order objective. Writing clear code facilitates that because it makes debugging and testing and maintenance easier.

Speed of execution matters only when it matters. That is always after the code is correct and after there is an objective performance issue, not just a theoretical one. Getting a wrong answer fast may be worse than no answer at all if we mistakenly believe the wrong answer is correct.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This seems to give a correct answer but while better than ferada's answer is no tidier than the OP's code. All those conditionals and code duplication are not at all functional or clean. Messy and fragile. \$\endgroup\$ – itsbruce Feb 1 '15 at 19:23
  • \$\begingroup\$ Actually, this is not a correct answer. There should be no unhandled condition. If you are given the same number 3 times, you should take 2 out of those 3, square them and add the result. Failing is not the right thing to do. There is a very simple way to pick the two largest numbers out, even if two or three of the three numbers are the same. A chain of conditionals is messy and (as you have written it) wrong. \$\endgroup\$ – itsbruce Feb 1 '15 at 19:51
  • \$\begingroup\$ @itsbruce You're correct that there should not be an unhandled condition. That's what makes an unhandled condition an error. If the same number is passed in three times, the first condition is true and output-ab is returned. Note that >= is used in lieu of >. Because the specification was written in terms of states representing permutations rather than relations, this does not deviate from the specification. \$\endgroup\$ – ben rudgers Feb 1 '15 at 20:18
  • \$\begingroup\$ Specs are not always as clear as they might be, true. Still a fugly way of solving it. \$\endgroup\$ – itsbruce Feb 1 '15 at 20:28
  • \$\begingroup\$ @itsbruce The purposes of the review were: 1 Providing a link to a style resource. 2 Explaining why the author's code contained errors. 3 Illustrating a method that can be repeated to reduce the odds of making errors. Recently, I've been interested in the work of Margaret E. Hamilton. There are worse software engineers to consider exemplars of the craft. en.wikipedia.org/wiki/Margaret_Hamilton_%28scientist%29https://… \$\endgroup\$ – ben rudgers Feb 1 '15 at 20:43
0
\$\begingroup\$

Your code is full of conditionals and duplicated code. This makes it both fragile and hard to read (and, as a result, hard to verify visually).

This problem can best be addressed by splitting it cleanly into two functional parts.

  1. You want to find the largest two of three numbers.
  2. You want to add the squares of two numbers.

Step 2 is very simple and easy to write. So if you can create a function (or piece of code) which delivers the two largest numbers, it will be easy to do the second part.

If we call the function largest2 and assume it returns a list of two numbers, then the second part could like this:

  (apply + (map square (largest2 a b c)))

To explain

  (map square (... ))

Applies the function square to each member of the list, returning a list of the results.

  (apply + (... ))

Applies the sum function to the contents of a list. So my first line of code takes the list returned by largest2, squares each member of the list and returns the result.

Now, what you want to do is find the largest of two. Even if you don't think of a nice way to do this, your code would be cleaner if you just output the two largest and then give it to my first line of code above and it will be cleaner than what you have. But here is a simple way to find the biggest two of three.

Firstly, assume you have a function max which finds the largest in a list. It's actually part of the standard Scheme library but it is not hard to write if you want to write one yourself (or if your tutor wants you to write one yourself). Either way, this will give you the two highest of three numbers:

  (define (largest2 a b c) (list (max a b) (max (min a b) c)))

Think about it. Take any 3 numbers (even 3 the same) and run them through that function in any sequence you like. You will always find the two largest. So now we can put all this together:

  (define (square n) (* n n))
  (define (largest2 a b c) (list (max a b) (max (min a b) c)))
  (define (square_of_larger_numbs a b c)
    (apply + (map square (largest2 a b c)))
  )

This is the benefit of the functional approach. I have no code duplication at all. I just apply one function to the output of another, in sequence. This makes it

  • (relatively) easy to understand (particularly once you understand the functional style in general)
  • easy to modify or adapt. Each stage is separate from the others, so you can modify one, or add another step in between, without having to modify the code of the other parts.

The functional version is also only 5 lines long. If you really do not need those functions elsewhere, you can move them inside. Since they are only used once, you could even make one or both of them anonymous lambda functions.

  (define (square_of_larger_numbs a b c)
    (apply + (map (lambda (n) (* n n))
       (list (max a b) (max (min a b) c))))
  )

Both versions are more readable than your original. The latter is a little dense, though.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ (largest2 1 2 1) returns (2 2), depending on how the instructions are interpreted, shouldn't this rather return (2 1)? \$\endgroup\$ – ferada Feb 1 '15 at 19:53
  • \$\begingroup\$ Indeed, the better implementation of largest2 is (remv (min a b c) (list a b c)). \$\endgroup\$ – Chris Jester-Young Feb 1 '15 at 19:54
  • \$\begingroup\$ Correct. Error corrected. \$\endgroup\$ – itsbruce Feb 1 '15 at 19:55
  • \$\begingroup\$ @itsbruce Has it been corrected? I haven't seen the edit to your post yet. \$\endgroup\$ – Chris Jester-Young Feb 1 '15 at 19:58
  • \$\begingroup\$ Sorry, correcting. I have more to add to the post \$\endgroup\$ – itsbruce Feb 1 '15 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.