Challenges are typically two or three times longer and/or more difficult than average exercises. They involve the application of multiple skills and the ability to keep complex long code readable and maintainable. Students who come to this course with no prior Lisp or Scheme experience should do at least a few challenges. More experienced programmers should focus on challenges over simpler exercises.

make-best-change

Function name: make-best-change

This is a variation on Graham's Exercise 9-2, which defines a function make-change. Do that exercise first, and make sure you have an approved clean solution, before doing this challenge.

make-change may fail to find the best answer for certain sets of coins, where best means "uses the fewest coins." For example, if there are no nickels, then (make-change 30 '(25 10 1)) will return 1 quarter and 5 pennies, which is 6 coins, but 3 dimes would be better.

Also, if the set of coins doesn't include pennies, then there may not be an exact answer. The best answer would be the one that comes closest, without going over the total amount.

Define make-best-change to take the same arguments as make-change. make-best-change should return an answer that leaves the least amount of cents unaccounted for. If there's more than such answer, it should return a solution that uses the fewest coins.

Avoid excessive CONSing. In particular, your code should not generate a new list for each possible combination it tries, only for those that actually work.

intersect-segments

Function name: intersect-segments

This is Exercise 9-4 in Graham. It is a surprisingly tough problem, given how simple it is to state. The solution will have a number of different cases to check. A major part of the challenge is organizing the code into short well-named modular subfunctions.

First, we need to clarify what intersect-segments should do for several special cases:

• If the segments do not intersect, it should return nil.
• If the segments are not parallel and intersect at one point, it should return 2 numbers, the x and y of the intersection point.
• If the segments are parallel and overlap, then it should return 4 numbers, the x and y of one endpoint of the overlap, and the x and y of the other endpoint of the overlap.

Parallel segments that meet at just an end point should return 4 numbers, x1, y1, x1, y1, to distinguish that situation from the non-parallel case.

The other hard part of this problem is making the code maintainable. There are a lot of special cases and a lot of repeated calculations. Subfunctions are a must. My personal solution uses about a dozen functions!