Find the sequence of cars and cdrs that return x when applied to the following expressions:
(a b x d)
(car (cdr (cdr '(a b x d))))
(a (b (x d)))
(car (car (cdr (car (cdr '(a (b (x d))))))))
What is the difference between the following s-expressions:
(car (setq '(a b c)))
Attempts to use '(a b c)
as the name of a value to assign to and fails.
(car '(setq '(a b c)))
Returns setq
as the front of a list consisting of the string setq
and the quoted list '(a b c)
.
Suppose you executed the following set of commands:
(car (setq x '(a b c))) x (1) (setq x nil) (car '(setq x '(a b c))) x (2)
What value of x would appear on the screen after:
(1)?
(a b c)
(2)?
nil
Assign to the symbol x the list '(a b c). Use this to create the list '(a b c a b c).
(setq x '(a b c)) (append x x)
Write a function that replaces the first element of a list, i.e., (replace-first x y), replaces the first element of list y with the value of x.
(defun replace-first (x y) (append (list x) (cdr y)))
Write a recursive function power-of-two that computes the nth power of 2; e.g. (power-of-two 8) returns 256.
(defun power-of-two (n) (cond ((= n 0) 1) ((> n 0) (* 2 (power-of-two (1- n)))) ((< n 0) (/ 1.0 (power-of-two (- n))))))
Write a non-recursive form of the same function, i.e., one that uses iterative constructs instead of recursion.
(defun power-of-two (n) (do ((x 1 (+ x 1)) (sum 1)) ((> x (abs n)) (cond ((< n 0) (/ 1.0 sum)) (t sum))) (setq sum (* 2 sum))))
Write a recursive function count-atoms that counts the number of atoms that appear at all levels of an s-expression. For example:
(defun count-atoms (list) (let ((count 0)) (cond ((listp list) (dolist (x list) (setq count (+ count (count-atoms x))))) (t (setq count 1))) count))
Given a map represented as a property list, write functions that, given a start-node and a goal-node, implement:
depth-first search
(defun depth-first-search (start-node goal-node) (let ((searched-nodes ())) (defun dfs-impl (current-node) ;(print (format "searching for ~S~ from ~S~ (~D~)" goal-node current-node (length searched-nodes))) (cond ((eq current-node goal-node) (list current-node)) (t (setq searched-nodes (cons current-node searched-nodes)) (let ((path nil)) (dolist (node (get current-node 'adjdst)) (cond ((not (member node searched-nodes)) (block recurse (setq path (dfs-impl node)) (if (not (eq path nil)) (return (cons current-node path))))))))))) (dfs-impl start-node)))
breadth-first search
(defun breadth-first-search (start-node goal-node) (let ((searched-nodes ()) (node-queue (list start-node))) (loop (when (or (endp node-queue) (eq goal-node (car node-queue))) (return)) (let ((current-node (car node-queue)) (children (get (car node-queue) 'adjdst))) (let ((new-children (set-difference children (append searched-nodes node-queue)))) (dolist (node new-children) (setf (get node 'parent) current-node)) (setq searched-nodes (append searched-nodes (list current-node))) (setq node-queue (append (cdr node-queue) new-children)) ;(format t " Searching for ~S from ~S (~D) ~S~%" goal-node current-node (length searched-nodes) node-queue) ))) (defun getpath (node) (cond ((null node) nil) (t (append (getpath (get node 'parent)) (list node))))) (cond ((endp node-queue) nil) (t (getpath (car node-queue))))))