1. Here's a solution to exercise 1.
% cat divides
#!/bin/csh
set nums = ( $argv )
set i = 1
while ( $i <= $#nums )
@ remainder = $nums[$i] % $nums[1]
if ( $remainder == 0 ) echo $nums[$i]
@ i ++
end
% divides 3 5 9 17 21
3
9
21
2. Here's a solution to exercise 2.
#!/bin/csh
set directory = $argv[1]
chdir $directory
if ( ! -e images ) mkdir images
foreach file ( `ls *.gif *.jpg` )
cp $file images/$file
end
3. Here's a solution to exercise 3 that uses a 'while' loop as
specified in the instructions. This solution uses a couple of
temporary files to store the intermediate results. Shell scripts
often use temporary files in this way. Here I chose to use the system
/tmp/ directory though I could have just as easily used the current
working directory in which the script is being executed.
What are the advantages of using the /tmp/ directory? You avoid the
possibility of inadvertently writing over any existing files in the
current working directory that just happen to have the same name as
the temporary files being used by the script. You won't be allowed to
write over someone else's files in the /tmp/ directory (if you try the
script will probably terminate with an error) but you might write over
your own files. An alternative solution would be to generate a file
name that is guaranteed not to exist in the directory you want to
store the file. How would you do this?
Here's the solution using the /tmp/ directory:
#!/bin/csh
set file = $argv[1]
set fix = `cat $argv[2]`
set one = /tmp/$file.one
set two = /tmp/$file.two
cat $file > $one
set i = 1
while ( $i < $#fix )
@ j = $i + 1
eval "cat $one | sed 's/$fix[$i]/$fix[$j]/g'" > $two
mv -f $two $one
@ i = $i + 2
end
cat $one
rm -f $one $two
Here's a solution that relies entirely on the 'sed' utility by making
use of the ability that 'sed' has to execute a sequence of 'sed'
instructions in a separate file. This solution does, however, rely on
rewriting the file of spelling corrections as a sequence of 'sed'
instructions; this can be done with a simple 'awk' script. The 'awk'
utility is particularly good for separating lines into fields and then
stitching them back together using print statements:
% cat mspl.txt | awk '{print "s/" $1 "/" $2 "/g"}' > mspl.sed
% cat mspl.sed
s/tey/the/g
s/teh/the/g
s/arguement/argument/g
s/lawer/lawyer/g
s/plaintif/plaintiff/g
With the commands in mspl.sed it is now easy to complete the exercise:
% cat msg.txt
teh lawyer's arguement was pretty weak
but tey plaintif still got a big settlement
% cat msg.txt | sed -f mspl.sed
the lawyer's argument was pretty weak
but the plaintiff still got a big settlement
You can use the above technique to strip out HTML tags from a
web page or remove uninteresting material from a mail message.
Think about how you might use it as a SPAM filter.
1. Here's a solution to exercise 1.
#!/bin/csh
set divisor = $argv[1]
foreach num ( $argv )
@ remainder = $num % $divisor
if ( $remainder == 0 ) echo $num
end
And the 'powers' command using a nested loop
#!/bin/csh
set d = $argv[1]
foreach i ( $argv )
set n = $i
while ( $n > 1 )
@ r = $n % $d
if ( $r != 0 ) break
@ n = $n / $d
end
if ( $n == 1 ) echo $i
end
and the 'primes' commands also using a nested loop
#!/bin/csh
foreach n ( $argv )
@ d = $n / 2
while ( $d > 1 )
@ r = $n % $d
if ( $r == 0 ) break
@ d --
end
if ( $d == 1 ) echo $n
end
2. A solution to exercise 2
#!/bin/csh
set one = ( `cat $argv[1]` )
set two = ( `cat $argv[2]` )
if ( $#one != $#two ) then
echo "The two columns of numbers must be of equal length"
exit
endif
set i = 1
while ( $i <= $#one )
@ sum = $one[$i] + $two[$i]
echo $sum
@ i ++
end
1. Compare the running time of these two solutions to Exercise 1:
% cat sorthat
#!/bin/csh
rm -f nums alphs bets
touch nums alphs bets
foreach word ( `cat $argv | tr "A-Z" "a-z" | tr -dc "a-z0-9 \n"` )
printf "."
if ( `echo $word a | awk '{ print ( $1 < $2 ) }'` ) then
echo $word >> nums
else if ( `echo $word m | awk '{ print ( $1 < $2 ) }'` ) then
echo $word >> alphs
else
echo $word >> bets
endif
end
% cat stringlessthan
#!/bin/csh
echo $1 $2 | awk '{ print ( $1 < $2 ) }'
% cat sorthat
#!/bin/csh
rm -f nums alphs bets
touch nums alphs bets
foreach word ( `cat $argv | tr "A-Z" "a-z" | tr -dc "a-z0-9 \n"` )
printf "."
if ( `stringlessthan $word 'a'` ) then
echo $word >> nums
else if ( `stringlessthan $word 'm'` ) then
echo $word >> alphs
else
echo $word >> bets
endif
end
2. A solution to Exercise 2:
% cat diagonal
#!/bin/csh
set n = $argv[1]
set i = 0
while ( $i < $n )
set j = 0
while ( $j < $n )
if ( $i == $j ) then
printf "1 "
else
printf "0 "
endif
@ j ++
end
printf "\n"
@ i ++
end
3. Solution to Exercise 3:
% cat isprime
#!/bin/csh
set n = $argv
@ d = $n / 2
while ( $d > 1 )
@ r = $n % $d
if ( $r == 0 ) then
echo 0
exit
endif
@ d --
end
echo 1
4. Solution to Exercise 4:
% cat isprime
#!/bin/csh
set n = $argv
@ d = $n / 2
while ( $d > 1 )
@ r = $n % $d
if ( $r == 0 ) exit 1
@ d --
end
exit 0
I. First things first - write down a solution to the problem in plain
English prose. It helps to provide a little structure in the form
of indentation. This middle ground between English prose and
working code is often called 'pseudo code' and writing your program
first in pseudo code is the best approach to working through the
conceptual part of your design.
set the display width to be 72
set the cursor position to be zero
for each word in the file
if the current word is <p> then
print a newline and then two spaces and
set the cursor position to be 2
else if the current word is </p> then
print a newline
else
if the cursor position plus the number of characters
in the current word is greater than the display width then
print a newline, two spaces, the word and then another space and
set the cursor position to be the number of characters in
the word plus 3 = 2 (for the two spaces of indentation) plus
1 (for the space following the word)
else
print the word and a space and
set the cursor position to be the cursor position plus the
number of characters in the word plus 1 (for the space
following the word)
II. Next figure out the basic structure (skeleton) of the code.
#!/bin/csh
set cursor_position = 2
set display_width = 72
foreach word ( `cat $argv` )
if ( "$word" == "<p>" ) then
...
...
else if ( "$word" == "</p>" ) then
...
...
else
@ cursor_position += `echo $word | wc -m`
if ( $cursor_position > $display_width ) then
...
...
else
...
...
endif
endif
end
III. Work through each line of your code interacting with the shell.
Interpreting and debugging each line doesn't guarantee that it
will work when you put them all together but it eliminates the
lion's share of syntax errors and conceptual problems.
% set word = "<p>"
% if ( "$word" == "<p>" ) echo yes
yes
% set word = "word"
% printf "$word " | wc -m
5
% @ cursor_position = 2 + `printf "$word " | wc -m`
% echo $cursor_position
7
% set word = "</p>"
% if ( "$word" == "</p>" ) echo yes
yes
... and so on ...
IV. Finally, when you're confident of the pieces, put them all together.
#!/bin/csh
set display_width = 72
set cursor_position = 2
foreach word ( `cat $argv` )
if ( "$word" == "<p>" ) then
printf "\n"
@ cursor_position = 2
else if ( "$word" == "</p>" ) then
printf "\n"
else
@ cursor_position += `printf "$word " | wc -m`
if ( $cursor_position > $display_width ) then
printf "\n$word"
@ cursor_position = 2 + `echo $word | wc -m`
else
printf "$word "
endif
endif
end
V. Your code probably won't work the first time and in that case
you should use the debugging strategies that we've suggested in
the past and are summarized in ../../../doc/debug.txt, e.g.,
% csh -xv format paragraphs.html
set display_width = 72
set display_width = 72
set cursor_position = 2
set cursor_position = 2
foreach word ( `cat $argv` )
foreach word ( `cat $argv` )
cat paragraphs.html
if ( "$word" == "<p>" ) then
if ( <p> == <p> ) then
printf "\n"
printf \n
@ cursor_position = 2
@ cursor_position = 2
else if ( "$word" == "</p>" ) then
else if ( <p> == </p> ) then
end
end
if ( "$word" == "<p>" ) then
if ( The == <p> ) then
if ( "$word" == "</p>" ) then
if ( The == </p> ) then
@ cursor_position += `printf "$word " | wc -m`
@ cursor_position += `printf "$word " | wc -m`
printf The
wc -m
if ( $cursor_position > $display_width ) then
if ( 6 > 72 ) then
...
2. Solution for Exercise 2:
#!/bin/csh
# This script reads from the standard input the result of
# an SQL query and produces as output an HTML document that
# features an HTML table displaying the query. The result
# of the SQL query is assumed to have one record per line
# with the record fields delimited by semicolons.
# begin the HTML document
echo "<html>"
# begin the body of the document
echo "<body>"
# begin the table used to display the data
echo '<table align="center" border="1">'
# read from the standard input record by record
set line = $<
while ( $line != "" )
# begin a new row and the first field in that row
printf "<tr>\n<td>"
# pad the semicolon with spaces to form a distinct word
foreach word ( `echo $line | sed 's/;/ ; /g'` )
# if you encounter a field separator
if ( $word == ";" ) then
# end the current field and start a new one
printf "</td>\n<td>"
else
# otherwise print each word in the current field
printf "$word "
endif
end
# end the last field in the current row and the current row
printf "</td>\n</tr>\n"
# read another record from the standard input
set line = $<
end
# end the table
echo "</table>"
# end the body of the document
echo "</body>"
# end the HTML document
echo "</html>"
3-5. A combined solution to Exercises 3-5. This solution doesn't
work for delimiters corresponding to white space but otherwise
works fine for single-character delimiters that aren't meta
characters in the 'sed' utility's regular expression language.
% cat file | table.options -c "Table Caption" -a -t "Document Title" -d ";"
...
...
% cat table.options
#!/bin/csh -b
# table command - table [-d delimiter] [-a] [-t title] [-c caption]
# This script reads from the standard input the result of an SQL query
# and produces as output an HTML document that features an HTML table
# displaying the query. The script also accepts several options that
# can appear in any order on the command line. The input is assumed
# to have one record per line with fields separated by a
# single-character delimiter. The first line of the file is assumed
# to contain the names of the fields. The '-a' signals that the
# second line in the input specifies a sequence of alignment
# directives ('left', 'right' or 'center') for displaying the
# corresponding fields. The '-c' option signals a string intended for
# use as the caption of the HTML table. The default delimiter is the
# space character. The '-d' option is used to specify an alternative
# to the default delimiter. The '-t' option signals a string intended
# for use as the title of the HTML document.
# process the command-line options
while ( $#argv > 0 )
switch ( $argv[1] )
case "-a":
shift argv
set alignment
breaksw
case "-c":
shift argv
set caption = ( $argv[1] )
shift argv
breaksw
case "-d":
shift argv
set delimiter = $argv[1]
shift argv
breaksw
case "-t":
shift argv
set title = ( $argv[1] )
shift argv
breaksw
default:
shift argv
endsw
end
# if the '-d' option is not present then set the default delimiter
if ( ! $?delimiter ) then
# the default is semicolon; can't deal with white space delimiters
set delimiter = ";"
endif
# the first line of input is assumed to consist of column headers
set headers = ( `echo $< | sed 's/'$delimiter'/ '$delimiter' /g'` )
# if the '-a' option is present on the command line then the
# second line of the input consists of alignment directives
if ( $?alignment ) then
# we exploit fact that alignment directives are single words
set alignment = ( `echo $< | sed 's/'$delimiter'/ /g'` )
else
# if '-a' option is not present all fields are center aligned
# the number of fields is half of one plus length of $headers
@ n = ( $#headers + 1 ) / 2
# we use a trick to create a list of alignments of this length
set alignment = ( `repeat $n echo center` )
endif
# begin the HTML document
echo "<html>"
# insert the title if present
if ( $?title ) then
printf "<head>\n<title>"
foreach word ( $title )
printf "$word "
end
printf "</title>\n</head>\n"
endif
# begin the body of the document
echo "<body>"
# begin the table used to display the data
echo '<table align="center" border="1">'
# insert the caption if present
if ( $?caption ) then
printf "<caption>"
foreach word ( $caption )
printf "$word "
end
printf "</caption>\n"
endif
# begin the top row of headers
printf "<tr>\n<th>"
# insert the name of each field
foreach word ( $headers )
if ( $word == "$delimiter" ) then
printf "</th>\n<th>"
else
printf "$word "
endif
end
# end the header and the top row
printf "</th>\n</tr>\n"
# read from the standard input record by record
set line = $<
while ( $line != "" )
# initialize the counter used to insert alignments
set rcrd = 1
# begin a new row and the first field in that row
printf '<tr>\n<td align="'$alignment[$rcrd]'">'
# pad the semicolon with spaces to form distinct words
foreach word ( `echo $line | sed 's/'$delimiter'/ '$delimiter' /g'` )
if ( $word == "$delimiter" ) then
# increment the counter used to insert alignments
@ rcrd ++
# end the current field and start a new one
printf '</td>\n<td align="'$alignment[$rcrd]'">'
else
# print each word of the current field in turn
printf "$word "
endif
end
# end last field in current row and then end the row
printf "</td>\n</tr>\n"
# read another record from the standard input
set line = $<
end
# end the table
echo "</table>"
# end the body of the document
echo "</body>"
# end the HTML document
echo "</html>"
1. Write a command that returns the maximum of two numbers:
(define (max_two a b)
(if (> a b) a b))
> (max_two 1 2)
2
2. Using the 'factorial' function as a model, write a function
that takes a list of numbers and returns the largest number.
(define (factorial n)
(if (= n 1)
1
(* n
(factorial (- n 1)))))
(- n 1) => (null? (rest lst))
1 => (first lst)
* => max_two
n => (first lst)
factorial => my_max
(- n 1) => (rest lst)
(define (my_max lst)
(if (null? (rest lst))
(first lst)
(max_two (first lst)
(my_max (rest lst)))))
> (my_max '(1 2 3))
3
> (my_max '(4 7 3 9 2 11 4))
11
2. Solution to Exercise 2:
> (first (rest '(1 2 (3 4) 5 6)))
2
> (first (rest (rest '(1 2 (3 4) 5 6))))
(3 4)
> (first (rest (rest (rest '(1 2 (3 4) 5 6)))))
5
> (first (rest (first (rest (rest '(1 2 (3 4) 5 6))))))
4
3. A solution to Exercise 3 with in-line comments:
(define (special-list-type? arg)
(and ;; is it a list
(list? arg)
;; is there at least one element in the list
(not (null? arg))
;; is the first element a number
(number? (first arg))
;; are there at least two elements in the list
(not (null? (rest arg)))
;; is the second element of the list a number
(number? (first (rest arg)))
;; are there at least three elements in the list
(not (null? (rest (rest arg))))
;; is the third element of the list a list
(list? (first (rest (rest arg))))
;; is the third element a list with at least one element
(not (null? (first (rest (rest arg)))))
;; is the third element a list with exactly one element
(null? (rest (first (rest (rest arg)))))
;; is the third element a list whose first argument is a string
(string? (first (first (rest (rest arg)))))
;; are there at least four elements in the list
(not (null? (rest (rest (rest arg)))))
;; is the fourth element in the list a symbol
(symbol? (first (rest (rest (rest arg)))))
;; are there exactly four elements in the list
(null? (rest (rest (rest (rest arg)))))))
4. Solution to Exercise 4:
(define (special-list-type-cond? arg)
(cond ((not (list? arg)) (printf "Expecing a list: ~a~%" arg))
((null? arg) (printf "Expecting a non-empty list: ~a~%" arg))
((not (number? (first arg)))
(printf "Expecting the first element to be a number: ~a~%" arg))
((null? (rest arg))
(printf "Expecting a list of length > 1: ~a~%" arg))
((not (number? (first (rest arg))))
(printf "Expecting the second element to be a number: ~a~%" arg))
((null? (rest (rest arg)))
(printf "Expecting a list of length > 2: ~a~%" arg))
((not (list? (first (rest (rest arg)))))
(printf "Expecting the third element to be a list: ~a~%" arg))
((null? (first (rest (rest arg))))
(printf "Expecting third element to be a non-null list: ~a~%" arg))
((not (null? (rest (first (rest (rest arg))))))
(printf "Expecting the third element to be list with one item: ~a~%" arg))
((not (string? (first (first (rest (rest arg))))))
(printf "The only item in the third element should be a string: ~a~%" arg))
((null? (rest (rest (rest arg))))
(printf "Expecting a list of length 4: ~a~%" arg))
((not (symbol? (first (rest (rest (rest arg))))))
(printf "Expecting the fourth element to be symbol: ~a~%" arg))
(else (printf "Just what I was expecting: ~a~%" arg))))
> (special-list-type-cond? '(1 2 ("foo") a))
Just what I was expecting: (1 2 (foo) a)
> (special-list-type-cond? (list 1 "" (list "foo") 'a))
Expecting the second element to be a number: (1 (foo) a)
> (special-list-type-cond? (list 1 7 '("foo" "bar") 'a))
Expecting the third element to be list with one item: (1 7 (foo bar) a)
2. Create the list structure (1 2 (3 (4) 5) 6) using 'cons':
> (cons 6 ())
(6)
> (cons 4 ())
(4)
> (cons 5 ())
(5)
> (cons (cons 4 ()) (cons 5 ()))
((4) 5)
> (cons 3 (cons (cons 4 ()) (cons 5 ())))
(3 (4) 5)
> (cons (cons 3 (cons (cons 4 ()) (cons 5 ()))) (cons 6 ()))
((3 (4) 5) 6)
> (cons 2 (cons (cons 3 (cons (cons 4 ()) (cons 5 ()))) (cons 6 ())))
(2 (3 (4) 5) 6)
> (cons 1 (cons 2 (cons (cons 3 (cons (cons 4 ()) (cons 5 ()))) (cons 6 ()))))
(1 2 (3 (4) 5) 6)
4. Produce a list of the numbers 1 through n.
> (define (numbers n)
(if (= n 1)
(list n)
(cons n (numbers (- n 1)))))
> (numbers 3)
(3 2 1)
> (define (numbers n)
(if (= n 1)
(list n)
(append (numbers (- n 1))
(list n))))
> (numbers 4)
(1 2 3 4)
5. Reverse written using 'append'
(define (reverse lst)
(if (null? lst)
lst
(append (reverse (cdr lst))
(list (car lst)))))
6. Reverse written using 'cons' and a second 'output' parameter.
(define (reverse input output)
(if (null? input)
output
(reverse (cdr input)
(cons (car input) output))))
7. Implement a version of 'assoc'.
(define (my_assoc key alist)
(cond ((null? alist) #f)
((equal? key (car (car alist))) (car alist))
(else (my_assoc key (cdr alist)))))
1. Solution to Exercise 1:
(define (total_cost prices shipping taxes)
(map (lambda (p s t) (+ p s (* p t))) prices shipping taxes)
2. Selected linear algebra functions defined on vectors:
(define (inner u v)
(apply + (map * u v)))
(define (magnitude v)
(sqrt (apply + (map (lambda (v_i) (* v_i v_i)) v))))
(define (cos-angle u v)
(/ (inner u v) (* (magnitude u) (magnitude v))))
4. Solution to Exercise 9: the 'repeat' macro
(define-syntax repeat
(syntax-rules ()
((repeat n expr ... )
(do ((_i_ n (- _i_ 1)))
((= _i_ 0))
expr ... ))))
1. Solutions to Exercise 1
;; Define the Cartesian 'point' data structure.
(define-struct point (x-coord y-coord))
;; Create a bunch of points for testing.
(define pt1 (make-point 0 0))
(define pt2 (make-point 0 1))
(define pt3 (make-point 1 1))
(define pt4 (make-point 1 0))
;; Define some mnemonic aliases.
(define first car)
(define rest cdr)
(define second cadr)
;; The 'square' function will come in handy.
(define (square x) (* x x))
;; Compute the Euclidean distance between two points.
(define (distance pt1 pt2)
(sqrt ( + (square (- (point-x-coord pt2)
(point-x-coord pt1)))
(square (- (point-y-coord pt2)
(point-y-coord pt1))))))
;; Technically speaking a tour is defined as a path in a graph
;; that starts and ends at the same node. This is slightly
;; different from what was asked for in the exercise. You can
;; take a list of points and turn it into a tour by appending
;; the list consisting of the first point to the end of the
;; original list of points.
(define (points->tour points)
(append points (list (car points))))
;; Here's a recursive solution to Exercise 1. Note that we
;; define the empty list of points to have a length of zero.
(define (tour-recur points)
(if (null? points)
0
(aux-tour (points->tour points))))
;; The auxiliary recursive function does all the work.
(define (aux-tour points)
(if (null? (rest points))
0
(+ (distance (first points)
(second points))
(aux-tour (rest points)))))
;; Here's a solution using the 'do' iteration operator.
(define (tour-iter points)
(if (null? points)
0
(do ((pts (points->tour points) (rest pts))
(len 0 (+ len (distance (first pts) (second pts)))))
((< (length pts) 2) len))))
;; This solution uses functional programming techniques. Note
;; that the 'shift' operator aligns the argument pairs to the
;; distance function so that they refer to consecutive pairs
;; of points as required to compute the tour distance.
(define (tour-map points)
(apply + (map distance points (shift points))))
;; This just shifts the elements of a list to the right in a
;; round-robin fashion so that the first element becomes last.
(define (shift lst)
(append (cdr lst) (list (car lst))))
;; Let's try out the three solutions:
(tour-recur (list pt1 pt2 pt3 pt4))
(tour-iter (list pt1 pt2 pt3 pt4))
(tour-map (list pt1 pt2 pt3 pt4))
1. Solution to Exercise 1
(define (one input)
(set! input (+ 1 input))
(printf "1 -> ~a~%" input)
input)
(define (two input)
(set! input (+ 1 input))
(printf "2 -> ~a~%" input)
input)
2. Solution to Exercise 2
(do ((input 0))
(#f)
(if (even? input)
(set! input (one input))
(set! input (two input))))
3. Solution to Exercise 3.
(define (one input)
(set! input (+ 1 input))
(printf "1 -> ~a~%" input)
(two input))
5. Solution to Exercise 5.
((I think you are ?x)
(I think you are ?x too)
(I certainly am not ?x)
(Why do you think I am ?x)
6. Solution to Exercise 6.
(((?* ?x) I want to (?* ?y))
(That would be nice to be able to ?y)
(I too would like to ?y))
8. Solution to Exercise 8.
(define (mean-match pattern input bindings var)
(if (not (member (car input) '(sad depressed melancholy)))
fail
(begin (printf "~%BAD ALBERT - ")
(map (lambda (word) (printf "~a " word))
(append '(Oh\, boo hoo\! Who cares if you\'re)
(list (car input))))
(printf "~%GOOD ALBERT - ")
(pattern-match (cons var (cdr pattern)) input bindings))))
> (pattern-match '((?* ?x) I feel (special mean-match ?y) (?* ?z))
'(Ever since my I turned eighty I feel depressed))
BAD ALBERT - Oh, boo hoo! Who cares if you're depressed
GOOD ALBERT -
((?z) (?y . depressed) (?x Ever since my I turned eighty))
> (let ((input '(Ever since my I turned eighty I feel depressed))
(rules '((((?* ?x) I feel (special mean-match ?y) (?* ?z))
(Do you feel ?y often?)
(That's interesting that you feel ?y)))))
(printf "~%ELIZA - ")
(map (lambda (word) (printf "~a " word)) input)
(printf "~%ALBERT - ")
(map (lambda (word) (printf "~a " word))
(apply-rules rules input))
(printf "~%ELIZA - ...~%") (void))
ELIZA - Ever since my I turned eighty I feel depressed
ALBERT -
BAD ALBERT - Oh, boo hoo! Who cares if you're depressed
GOOD ALBERT - Do you feel depressed often?
ELIZA - ...