Below are exercises, often modified or extended, from Graham.
Warning: many of the exercises suggest terrible names for the functions
to define. Use the function names given in the exercise descriptions below.
These are the names used by the unit tests
defined in exercise-tests.lisp.
When inventing your own names, ignore Graham's examples and use the
principles of good naming.
Feel free to define subfunctions when they make the code clearer. In fact, you will be critiqued for not defining subfunctions when appropriate. Some students think the phrase "define a function" means "define just one function." That's not true in Lisp or anywhere else. That terminology is just how programmers describe the API (application program interface) for the public function that other code will call.
Quick jump to notes for Chapter 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Function names: greater, has-list-p, print-dots,
get-a-count, summit
Send the code for exercises 4, 7, 8, and 9 in one submission.
Even though the instructions say to use only what you've seen so far, use cond
rather than if, where appropriate.
Function names: stable-union,
stable-intersection, stable-set-difference
Names like new-xxx are always a bad idea. "New" says nothing
about what the function does. And how long can something stay "new?"
The term "stable" is used in computer science
to refer to sorting algorithms that don't mess up the order of elements any
more than they have to. Common Lisp provides two sorting functions: sort
and stable-sort to capture this difference.
Define stable versions of the three major
set functions: union, intersection, and difference.
These should work like the built-in versions (see Graham's glossary),
but items in the result
should have the same relative ordering they have in l1,
if any, or in l2, if any. Don't worry about handling
keyword arguments.
Avoid redundant code. Avoid needless CONSing or list scanning.
Function name: occurrences (yes, that is how you spell it)
It's very inefficient to do this by creating a new list of count pairs every
time you count a new element. Instead, keep a list of (item . count)
pairs, initially empty. For each element in the input list, update this list
of pairs, where updating means incrementing the counter in the appropriate pair,
if one exists, otherwise adding a new pair.
To increment the count, use (INCF (CDR pair)) which increments
the CDR of a pair.
NOTE: it's OK to get "a little too long" from the Lisp Critic on this, though there are many reasonably short solutions.
Function name: position+
In case you're not sure why the return value is (7 6 3 7): The first element is 7 (the first element of the original list) + 0 (the position of the first element, counting from 0), the second element is 5 (from the original list) plus position 1, the third element is 1 plus position 2, and the last element is 4 plus position 3.
Function names: show-dots, show-list.
Define show-dots as described in Graham. This is a simple function
and should have simple code. Look at the test cases in exercises-tests.lisp
for examples.
Define show-list to act like Lisp's PRINT, except that it should
print square brackets instead of parentheses. (Printing to a string and replacing
parentheses doesn't count.)
Both functions should be able to print any S-expression, including atoms.
Function name: longest-path
There are two problems with this exercise as given. First, Graham's phrase "the longest finite path" makes no sense if you allow cycles in the network, as he does and should. There are an infinite number of finite paths when the network has cycles.
We could say "find the longest path with no cycles," but consider asking for the longest path from node A to node A. This has a cycle, but it's asking a reasonable question: what is the longest round-trip tour from A?
So, define your function to find the longest path with no internal cycles, i.e., no node repeated except possibly the first and last nodes.
The second problem is that
looking for longest paths means that Graham's breadth-first
BFS function is not appropriate. Why? Because
breadth-first search has to build
a queue of alternatives, and such a queue is only worth doing
if it lets you stop before you've tried all possibilities.
There's no way to find the longest path without trying all possibilities. Therefore, there is no point to keeping a queue. Depth-first search would work just fine and is more efficient..
Define a recursive longest-path function that uses depth-first
search to explore all paths without internal cycles, one at a time.
That is, there will be a variable with the current
path, and perhaps another with the best path, but no list of all paths.
Function names: rotate-array, nrotate-array.
Define rotate-array to create a new array and copy the
elements from the old array into it. This can be done pretty simply
with a pair of nested dotimes and a formula that maps (x, y)
in the old array into a position in the new array.
In Lisp, for obscure historical reasons, destructive versions
of functions start with the letter "n" as in reverse /
nreverse and subst / nsubst. So nrotate-array
should be a version of
rotate-array that modifies and returns the original array. The
trick is to notice that every element participates in a 4-step
circular rotation. For example, in a 5x5 array, the element at (0, 0)
goes to (0, 4) which goes to (4, 4) which goes to (4, 0) which goes
to (0, 0). (In odd-sized arrays, the center element doesn't move.)
The formula for what goes where is not hard to figure out and similar
to the one needed for the easy version of this exercise.
Common Lisp has a very handy special form, rotatef, which
takes N "places" (variables, aref's, whatever), and "rotates" the
values in those places 1 position. (rotatef x y), for
example, swaps x and y.
Use rotatef to implement the 4-step rotations that
nrotate-array needs in a concise fashion. Don't rotate any
element more than once!
Function names: my-copy-list, my-reverse, hash-table->alist,
alist->hash-table
Send code for exercises 2 and 6 in one submission.
Structure name: 3tree
Function names: 3tree-clone, 3tree-member
Do as specified.
Function name: bst-elements
The specification "in order from greatest to least" is a bit confusing. Is this assuming a particular ordering predicate was used to build the tree?
In any case, define bst-elements to
return the elements of a binary search tree in the reverse order of
how they
appear in the tree. So bst-elements on
a tree with 1, 2 and 3 would return (3 2 1).
Your solution should only do N conses (not counting internal CONSes out of your control) to produce an N-element result. Hint: there's a BST function to make this fairly simple. The code code for Graham's binary search tree is in bst.lisp. Send only your code, not Graham's.
Function name: preceders
Do as specified. Put both versions in the same submission.
Function name: intersperse
Put both versions in the same submission.
NOTE: (intersperse '- '(a)) should return (a)
and (intersperse '- '()) should return ().
Avoid inefficiencies. There are two easy traps to fall into:
Function name: diff-by-one-p
Define four versions, all with the same name. The fourth should
use every. Put all four versions in the same submission.
return-from makes more sense than return in part
c.
Function name: max-min
Don't worry about using just one function, if more would make the code clearer or more efficient. Only one recursive function is needed though.
Don't use subseq to create subvectors. This is
expensive. Don't call length on every iteration either. This
is unnecessary. It also limits the generality of maxmin.
Instead, define max-min to take the keywords :start
and :end, just like the other sequence functions do. With:start
and :end, your code should be more efficient than code with subseq
and multiple calls to length, and more flexible at the same time.
Think about what other keyword arguments would provide similar efficiency and
flexibility.
Define both versions as specified. Put both versions in the same submission.
In addition, fix the code to handle cycles in the graph. Graham's code will find a path if one exists, no matter what, but will go into an infinite loop if no path exists and there are cycles in the graph.
Graham's finder function is not great Common Lisp. Run the Critic
on it and see.
Furthermore, it has a serious bug, as noted on the errata page at his web site.
Therefore, part of your job here is to reimplement the code to work correctly (pass the test cases) and be in good Common Lisp style.
Redefine bin-search so that
(bin-search object vector :key key-fn :start start :end end)
uses binary search to find an item in vector whose (funcall
key-fn item) value is equal to object. For example,
> (bin-search 8 #((1 a) (3 b) (5 c) (7 d) (8 e) (10 f))
:key #'car :start 3 :end 5)
(8 E)
The search should go from start (inclusive) to end (exclusive). All parameters should take their usual values. In particular, in Lisp, C++, Java and elsewhere, the end of a sequence is the first index past the last element. Graham uses the index of the last element, which makes his arithmetic more complicated. With the standard value you can test for the end case and calculate the midpoint without a range calculation.
Do not define a :test parameter. A :test parameter
makes little sense here, because the code takes a vector previously sorted using
<, and that implicitly defines an equality predicate.
You should not need a helper function, just a recursive bin-search.
Function names: my-remove-if, greatest-arg,
bigger-arg, memoize
Send code for exercises 5, 6, 7 and 8 in one submission.
The parameter to greatest-arg and bigger-arg should
be optional. If omitted, it should reset the internal data to its initial state.
Instead of frugal, define (memoize function).
(memoize function) should take one argument that is
itself a function of one argument, e.g., (memoize #'sqrt).
memoize should return a new function object, i.e., closure. The closure
should call function when it gets new argument values, and return
whatever function returns. When passed previously seen
equal values, the closure should return the previous answer without
calling function. If the closure is called with no arguments,
it should clear its internal table of argument values, and start over.
See the test cases in exercise-tests.lisp for examples.
Function names: map-file, map-stream
Exercise 7-1 is good practice for this exercise, but only send Exercise 7-2.
Instead of making a list of the expressions in a file, define
(map-stream function stream)
to apply function to every Lisp expression in stream. It
should return nil.
Define
(map-file function pathname)
to apply function to every Lisp expression in the file
named by pathname, and return nil. These functions
can be very useful for checking code files, collecting the names of
functions defined in a file, and so on.
There are test cases only for map-stream.
Do as specified. Currently, there are no test cases for this exercise.
Function name: stream-subst
To do this exercise, you need Graham's buffer and stream-subst code. The book version of the buffer code has an error. Use this version instead. Here's the stream-subst code, which you'll be changing.
Extend stream-subst as described for Exercise 7-5, but
the wildcard character should be specifiable with a :wildcard
keyword parameter, with the default +, e.g.,
Then extend stream-subst as described for Exercise 7-6.
Change the code so that the pattern old can be a sequence. (This
is a very easy change.)
Strings are sequences but so are lists and simple one-dimensional arrays.
By allowing non-string sequences, we can specify patterns with non-character
elements. In particular, you should change stream-subst
so that the elements :digit, :alpha,
:alphanumeric and :wild match
digits, alphabetics, alphanumerics, and any characters, respectively, e.g.,
#(:digit :alpha :digit) would match any subsequence
of a digit, letter, and digit.
To simplify writing tests, exercise-tests.lisp
defines string-subst to use strings as input
and output streams for stream-subst.
Do as specified. To test your package setup, use
(run-tests ring-package)
Henley is the random text generator in Figures 8.2 and 8.3.
I didn't understand what Graham meant, originally, but a student clarified it for me. The problem is to tell whether or not a given quote could have been produced by Henley. Hint: what tells Henley which words can follow which?
Along the way, change generate-text to be iterative.
In Scheme, you can count on tail-recursion optimization to get a
working text generator. In Common Lisp, this may happen, but
it depends on the platform. Making the code iterative
will also allow you to drop the optional
argument prev.
To test your code, initialize Henley on some corpus. You can get plain text versions of many books at Project Gutenberg. Paradise Lost for example is here. Be sure to remove the Project Gutenberg notice before feeding to Henley.
Then generate some texts with Henley, and feed the results to your predicate. It should always return true. Then feed it some texts from other sources. While some may return true, most should return false.
Do Exercise 8-5 first, because you need the predicate it defines to test your solution to this exercise.
It's not too difficult to use the existing hashtable to find a word that can precede a given word, and hence generate backwards from an initial word to the start of a sentence. But this is expensive and doesn't have the random generation statistical propertes of Henley.
A better approach is to create an equivalent hashtable for going backwards, using the data in the existing hashtable. Then generating in either direction is basically a matter of which hashtable you're using.
To test your code, feed the output of your generator into your Henley tester. It should always return true.
Function name: make-change
Define your function to take the number of cents and an optional list of the
available coins, largest to smallest, e.g., (make-change 72 '(25 10 1)).
The default list should be (25 10 5 1).
You can assume that the coins are such that the simple greedy algorithm will get the answer with the fewest coins. For a more challenging exercise that doesn't make this assumption, after you do this, try make-best-change.
Function name: solve
Graham says that max and min have opposite signs.
This makes no sense. It should say that (funcall f max) and (funcall
f min) have opposite signs.
Also, students frequently misunderstand the use of
epsilon. What Graham means (and what is usually intended) is
that you stop approximating when max and min are
within epsilon of each other.
Finally, my best solution requires two functions, one to check the initial values and handle some special cases that have no solution or an exact solution, and another to do the actual solving. The style critic calls the first a little too long, the latter somewhat too long.
Function name: horner
Do as specified.
See the challenge exercises for challenges based on exercises in this chapter.
Send code for exercises 3 and 5 in one submission.
Note that the test case Graham gives for nth-expr
rules out using a function. If you don't see why, try running
the example with this definition:
(defun nth-expr (n &rest l) (nth (1- n) l))
However, that one test case still allows for a macro that evaluates all expressions, catching any errors. We'll take the interpretation that
nth-expr n exp1 exp2 exp3 ...)
should evaluate only n and expN.
Here's a test case that your code has to handle correctly. Only one thing should print and it'll be clear if you're right.
(let ((n 3) (x "lose") (y "win"))
(nth-expr n
(format t "You ~S!" x)
(format t "You ~S!" x)
(format t "You ~S!" y)
(format t "You ~S!" x)
))Function name: preserve
This exercise requires you to understand how variable bindings work, but the answer is quite short. Your macro needs to work for both lexical and special variables.
Function name: doublef
Note the name change: Graham's name does not suggest the close connection
between this macro and incf.
Make sure doublef correctly handles generalized references.
Send code for exercises 1 and 5 in one submission.
Do as specified.
Function names: make-queue, empty-queue-p, copy-queue,
enqueue-front,
requeue-front
Send all the queue functions in one submission.
Queues in Lisp are easy and useful, but Graham left out one essential function,
and should have made make-queue more convenient. Define empty-queue-p
to return true if a queue is empty. Redefine (make-queue arg1 arg2
... to return a queue initialized with the items given, if any.
Function names: circular-member-p, cdr-circular-p
As far as I can tell, you need to do Exercise 7 first, before doing Exercise 6, so submit both as one submission.
For all the circular list exercises, make sure you set the global variable
*PRINT-CIRCLE*to true first! This tells Lisp to use a special printing algorithm that handles circular lists. Note that what Lisp prints can be typed in to make a circular list too. It's not just an output format.
As you might expect, by chapter 12, a simple question doesn't mean a simple answer. Graham should've said more.
First, for Exercise 7, something like
(eq l (cdr l))
won't work. This only catches a 1-element cdr-circular list, not lists like
(let ((l (list 1 2 3))) (nconc l l))
or
(let ((l (list 1 2 3))) (nconc l (cddr l)))
The obvious solution is to keep a list of every CDR and return true if you find the same list twice before hitting NIL. The problem with this solution is that it requires potentially large amounts of CONSing. If you assume a top-level circularity only in the final CDR, you can trade more pointer following to avoid CONSing.
Start a loop with two variables -- a "turtle" that CDR's down the list and a rabbit that CDDR's. That means the rabbit goes twice as fast as the turtle. If the list is CDR-circular, eventually the rabbit and turtle will bump into each other. If the list is not circular, the rabbit will hit NIL.
After you have CDR-circular lists working, then you can do Exercise 6. Careful! Make sure you test this thoroughly. It's easy to write a version that says false when it should say true.
Make sure your function works for regular lists too.
Function name: car-circular-p
Graham's definition of CAR-circular on page 209 says "the loop passes through the car of some cons." This is pretty open, so I'm defining this problem to be much more general than CDR-circular. In fact, it's comparable to what Lisp has to do when printing with *PRINT-CIRCLE* set to true. All the solutions I've seen keep a stack of sublists.
My exercise-tests.lisp include both CAR-circular and CDR-circular lists, and, in some cases, both. If you believe one of the tests is wrong, email me. Before doing so, draw the test case in box and arrow notation, as shown in the figures in Chapter 12. If there is a loop that goes through the CAR side of a box, then it's CAR-circular.
Comments? 
Send mail to Chris
Riesbeck.