[SOLVED] parallel make-best-change

make-best-change
Function name:make-best-change
Number bundle
This is a variation on Grahams Exercise 9-2, which defines a functionmake-change. Do that exercise first, and make sure you have an approved clean solution, before doing this challenge.
make-changemay 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 doesnt 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.
Definemake-best-changeto take the same arguments asmake-change.make-best-changeshould return an answer that leaves the least amount of cents unaccounted for. If theres 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.

(defun make-change (total &optional (available-coins (25 10 5 1)))
(values-list (change total available-coins)))

(defun change (total available-coins)
(cond ((null available-coins) ())
(t (multiple-value-bind (already-have remaining)
(floor total (car available-coins))
(cons already-have (change remaining (cdr available-coins)))))))

Test cases
(define-test make-best-change
(assert-equal (values 2 1 1 2) (make-best-change 67))
(assert-equal (values 2 0 0 0) (make-best-change 50))
(assert-equal (values 0 0 0 4) (make-best-change 4))
(assert-equal (values 0 0 0 0) (make-best-change 0))
(assert-equal (values 0 3 0) (make-best-change 30 (25 10 1)))
(assert-equal (values 1 3) (make-best-change 32 (11 7)))
(assert-equal (values 1 5 0) (make-best-change 88 (23 13 5)))
(assert-equal (values 1 1) (make-best-change 11 (7 3)))
(assert-equal (values 2 0 1) (make-best-change 21 (10 5 1)))
)

intersect-segments
Function name:intersect-segments
Number bundle
9-4:
Define a function that takes 8 reals representing the endpoints of two segments in 2 space, and returns either nil if the segments do not intersect, or two values representing the x- and y- coordinates of intersection if they do.
This is Exercise 9-4 in Graham. It is a surprisingly knotty problem, given how simple it is to state. There are a number of special cases to handle:
Non-intersecting segments return nil.
Intersecting non-parallel segments return 2 numbers, the x and y of the intersection point.
Intersecting parallel segments return 4 numbers, the x and y of one end of the overlap, and the x and y of the other end of the overlap, even if those are the same point.
Zero-length segments, i.e., start point equals end point, are parallel to everything.
Use multiple values to return more than one number.
A major part of the challenge is organizing the code into short well-named modular subfunctions. There are a lot of special cases and a lot of repeated calculations.Subfunctions are a mustbut they should make sense. My personal solution uses about a dozen small functions!
You may find it useful to define structures or classes to represent points, lines, and segments. Good solutions exist with and without these.
Tests cases:
(defun segment-equals (results correct)
(or (equal results correct)
(and (= (length correct) 4)
(equal (first results) (third correct))
(equal (second results) (fourth correct))
(equal (third results) (first correct))
(equal (fourth results) (second correct)))))

(define-test intersect-segments
(assert-equality segment-equals
(2 2 3 3)
(multiple-value-list (intersect-segments 1 1 3 3 2 2 4 4)))
(assert-equality segment-equals
(2 2 3 3)
(multiple-value-list (intersect-segments 3 3 1 1 2 2 4 4)))
(assert-equality segment-equals
(2 2 3 3)
(multiple-value-list (intersect-segments 1 1 3 3 2 2 5 5)))
(assert-equal (nil)
(multiple-value-list (intersect-segments 1 1 2 2 3 3 4 4)))
(assert-equality segment-equals
(2 2 2 2)
(multiple-value-list (intersect-segments 1 1 2 2 2 2 3 3)))
(assert-equality segment-equals
(2 2)
(multiple-value-list (intersect-segments 1 1 3 3 3 1 1 3)))
(assert-equal (nil)
(multiple-value-list (intersect-segments 1 1 3 3 4 0 3 1)))
(assert-equality segment-equals
(0 0)
(multiple-value-list (intersect-segments -1 1 1 -1 0 0 1 1)))
(assert-equal (nil)
(multiple-value-list (intersect-segments -3 1 0 -2 -2 1 -1 0)))
(assert-equality segment-equals
(-2 1 -1 0)
(multiple-value-list (intersect-segments -3 2 1 -2 -2 1 -1 0)))
(assert-equality segment-equals
(2 2 2 2)
(multiple-value-list (intersect-segments 2 2 2 2 2 2 2 2)))
(assert-equality segment-equals
(2 3 2 4)
(multiple-value-list (intersect-segments 2 2 2 4 2 3 2 5)))
(assert-equal (nil)
(multiple-value-list (intersect-segments 2 2 2 2 3 3 3 3)))

(assert-equality segment-equals
(2 2 2 2)
(multiple-value-list (intersect-segments 2 2 2 2 1 1 3 3)))
(assert-equality segment-equals
(2 2 2 2)
(multiple-value-list (intersect-segments 0 0 2 2 2 2 2 2)))
(assert-equal (nil)
(multiple-value-list (intersect-segments 0 0 1 1 2 2 2 2)))
(assert-equal (nil)
(multiple-value-list (intersect-segments 0 0 1 0 2 0 3 0)))
(assert-equality segment-equals
(1 0 2 0)
(multiple-value-list (intersect-segments 0 0 2 0 1 0 3 0)))
)