CSE 471/598 Spring 2004
Solutions to Lisp Assignment
1. Input/Ouput
Write a function unique that takes in two strings, 'infile' and
'outfile' as parameters. 'infile' is the name of a file containing a
sequence of words. The words are
separated by any combination of
whitespace characters (space, newline, tab). Your function should read
such a file, find the uniqe words in it and write it in a new file
named 'outfile'.
CONSTRAINTS: All the words are case insensitive
CAUTION: Be careful with the path separators while specifying the
filenames. For
windows use "\\" as separator and for unix/linux use "/" as separator.
unique.lisp
(defun unique(infile outfile)
(let (l)
(with-open-file (file infile :direction :input)
(setf l (do* ((result nil (cons next
result))
(next (read file nil 'eof) (read file nil 'eof)))
((equal next 'eof) result))))
(setf l (remove-duplicates l))
(with-open-file (file outfile :direction :output
:if-exists :overwrite)
(dolist (ele l)
(format file "~S~%" ele)))))
2. List Recursion
Write a recursive function revert which takes a list 'l' as parameter
and returns the reverse of the list. DO NOT use inbuilt function
'reverse'.
e.g., (revert '(a b c)) should return (C B A)
revert.lisp
(defun revert (l)
(if (null l)
nil
(append (revert (cdr l)) (list (car l)))))
3. Using Structures
a) create a structure to define a point in cartesian co-ordinate system
b) create a structure to define a line segment in cartesian co-ordinate
system
c) write function distance that take in two points as parameters and
returns the euclidean distance between the points.
Euclidean distance between points (x1, y1) and (x2,
y2) is defined as
dist =
sqrt((x1-x2)^2 + (y1-y2)^2)
d) write a function midpoint that take a line segment as parameter and
returns the midpoint (of point structure type) of the line segment.
Midpoint of a line segment connecting two
points (x1, y1) and (x2, y2)
is given by
(midx, midy) =
((x1+x2)/2, (y1+y2)/2)
structures.lisp
(defstruct point
x
y)
(defstruct segment
p1
p2)
(defun distance(p1 p2)
(sqrt (+ (expt (- (point-x p1) (point-x p2)) 2)
(expt
(- (point-y
p1) (point-y p2)) 2))))
(defun midpoint(l)
(make-point
:x (/ (+ (point-x (segment-p1 l)) (point-x (segment-p2
l))) 2)
:y (/ (+ (point-y (segment-p1 l)) (point-y (segment-p2
l))) 2)))
4. Power of 2
Write a recursive function power-of-two which takes an integer
parameter 'n' and returns 2^n. (This can be done in logarithmic time)
CONSTRAINTS: The parameter 'n' is non-negative
e.g., (power-of-two 10) should return 1024
power-of.two.lisp
(defun power-of-two (num)
(cond ((= num 0) 1)
((= num 1) 2)
((= (mod num 2) 0)
(let ((temp
(two-to-the (/ num 2))))
(* temp
temp)))
(t
(let ((temp
(two-to-the (/ (- num 1) 2))))
(* temp
temp 2)))))
5. Powerset
Write a function powerset that takes a list 'l' as input and
returns
the powerset of the list. Assume the input list as a set, and generate
the powerset. A powerset is defined as a set of all subsets of a set.
CONSTRAINTS: The elements of parameter 'l' will be distinct
e.g., (powerset '(1 2 3)) should return the following
(NIL (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))
HINT: powerset of {a, b, c, d,...} is equal to union of powerset of {b,
c, d,...} and 'a' appended to each element of powerset of {b, c, d,...}
PS: The ordering of the sets in the powerset is not important.
powerset.lisp
(defun powerset(l)
(if (null l)
'(nil)
(let ((ps (powerset (cdr l))))
(append ps (mapcar #'(lambda (x) (cons
(car l) x)) ps)))))