Good Things Come in Small Packages

Breaking Down More Complex Problems

Consider the following specification:

Write a procedure to sum the values of the two largest different items in a list of integers.

Considering inputs and outputs, we could start by writing the following header:

PROCEDURE SumTwoLargest(list : ListPtr) : INTEGER

This problem is more difficult than those we have met so far. It will not be simple to write it out straight away. Instead we need to try and simplify it into more manageable components, using several procedures rather than just one.

Firstly, let us be sure that the specification is complete. What if the list is empty? We could return zero as a reasonable answer in this case. What if there is only one unique value in the list? It would probably be reasonable to use zero as the value of the missing second item. What are the elements of the solution? We have to be able to identify maximum values. Would it help to sort the list and then find the two largest? We already have a way to find one maximum (see Largest, above) could we make use of that procedure - is finding the second largest more difficult?

These are the kinds of thinking processes that we have to go through when trying to find solutions to new problems. Here is one possible design that breaks down the original problem, and makes use of some of the earlier solutions:

Sum the two largest:
  IF the list is empty THEN
    RETURN 0
    Find the largest element;
    Make a copy of the list with the largest element removed;
    IF the new list is not empty THEN
      Find the largest element in the new list;
      RETURN the sum of the two values;
      RETURN the largest element;

The only part of this for which we do not already have a solution is that of removing the largest element. This will be a procedure that takes a list and the value of the elements to be removed as inputs and returns a new list as its output:

PROCEDURE CopyAndRemoveItem(list : ListPtr;
		item : INTEGER) : ListPtr

Once again, we can use our earlier models to solve this. If the list is empty, then it returns an empty list. If the item occurs at the head of the list then it does not make a copy of that item but recursively calls itself on the tail of the list. If the item does not occur at the head of the list, it makes a copy of the head and prepends it onto a copy of the list remaining after the recursive call.

PROCEDURE CopyAndRemoveItem(list : ListPtr;
		item : INTEGER) : ListPtr =
  IF ListIsEmpty(list) THEN
  ELSIF ListHead(list) = item THEN
    RETURN CopyAndRemoveItem(ListTail(list),item);
    RETURN ListPrepend(ListHead(list),
END CopyAndRemoveItem;

So we can write the remainder of the solution as follows:

PROCEDURE SumTwoLargest(list : ListPtr) : INTEGER =
  copyList : ListPtr;
  largest, secondLargest : INTEGER;
  IF ListIsEmpty(list) THEN
    RETURN 0;
     largest := Largest(list);
     copyList := CopyAndRemoveItem(list,largest);
     IF ListIsEmpty(copyList) THEN
       RETURN largest;
       secondLargest := Largest(copyList);
       RETURN largest+secondLargest;
END SumTwoLargest;

Previous Page

To Overview

To Next Page