During this activity, students should be able to:
This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.
Individually, solve the following set of programming
exercises using Clojure. Place all your functions in a name space called
recursion2. All problems should be solved using explicit recursion or the recur and loop special forms.
my-repeat takes a number n and any data x as its arguments. It returns a list that contains n copies of x. Do not use the predefined repeat function. Unit tests:
(deftest test-my-repeat (is (= () (my-repeat 0 'x))) (is (= '(6 6 6) (my-repeat 3 6))) (is (= '((ha ha) (ha ha) (ha ha)) (my-repeat 3 '(ha ha)))) (is (= '(true true true true true) (my-repeat 5 true))))
invert-pairs takes as an argument a list of vectors containing two elements each. It returns a new list with every vector pair inverted. Unit tests:
(deftest test-invert-pairs
(is (= () (invert-pairs ())))
(is (= '([1 a][2 a][1 b][2 b]))(invert-pairs '([a 1][a 2][b 1][b 2])))
(is (= '([1 January][2 February][3 March])
(invert-pairs '([January 1][February 2][March 3])))))
enlist surrounds in a list every upper-level element of the list it takes as input. Unit tests:
(deftest test-enlist (is (= () (enlist '()))) (is (= '((a) (b) (c)) (enlist '(a b c)))) (is (= '(((1 2 3)) (4) ((5)) (7) (8)) (enlist '((1 2 3) 4 (5) 7 8)))))
my-interleave takes two arguments: the lists a and b. It returns a list containing the first element of a, followed by the first element of b, followed by the second element of a, followed by the second element of b, and so on. The lists a and b don't have to be of the same size. The interleaving of the elements stops when either a or b is exhausted. Do not use the predefined interleave function. Unit tests:
(deftest test-my-interleave (is (= () (my-interleave () ()))) (is (= () (my-interleave '(a) ()))) (is (= () (my-interleave () '(1)))) (is (= '(a 1 b 2 c 3 d 4 e 5) (my-interleave '(a b c d e) '(1 2 3 4 5)))) (is (= '(a 1 b 2 c 3 d 4) (my-interleave '(a b c d e) '(1 2 3 4)))) (is (= '(a 1 b 2 c 3 d 4) (my-interleave '(a b c d) '(1 2 3 4 5)))) (is (= '(a 1) (my-interleave '(a) '(1 2 3 4 5)))) (is (= '(a 1) (my-interleave '(a b c d e) '(1)))))
my-flatten removes all the interior parenthesis of the list it takes as input. Do not use the predefined flatten function. Unit tests:
(deftest test-my-flatten
(is (= () (my-flatten ())))
(is (= '(a b c d e) (my-flatten '((a b) ((c) d (e))))))
(is (= '(one two three four)
(my-flatten '(((one) ((two))) () (three (())) four)))))
exchange takes three arguments: two non-list values x1 and x2, and a list lst. It returns a list with the same elements as lst, except that all occurrences of x1 are replaced by x2 and vice versa, including any occurrences inside nested lists. Unit tests:
(deftest test-exchange
(is (= () (exchange 'x 'y ())))
(is (= '(d b c a) (exchange 'a 'd '(a b c d))))
(is (= '((42) true ((cool (true)) (42))))
(exchange true 42 '((true) 42 ((cool (42)) (true))))))
insert takes two arguments: a number n and a list of numbers lst in ascending order. It returns a new list with the same elements as lst but inserting n in its corresponding place. Unit tests:
(deftest test-insert (is (= '(14) (insert 14 ()))) (is (= '(4 5 6 7 8) (insert 4 '(5 6 7 8)))) (is (= '(1 3 5 6 7 9 16) (insert 5 '(1 3 6 7 9 16)))) (is (= '(1 5 6 10) (insert 10 '(1 5 6)))))
my-sort takes an unordered list of numbers as an argument, and returns a new list with the same elements but in ascending order. You must use the insert function defined in the previous exercise to write the my-sort. Do not use the predefined sort function. Unit tests:
(deftest test-my-sort (is (= () (my-sort ()))) (is (= '(0 1 3 3 4 6 7 8 9) (my-sort '(4 3 6 8 3 0 9 1 7)))) (is (= '(1 2 3 4 5 6) (my-sort '(1 2 3 4 5 6)))) (is (= '(1 5 5 5 5 5 5) (my-sort '(5 5 5 1 5 5 5)))))
binary takes an integer n as input (assume that n ≥ 0). If n is equal to zero, it returns an empty list. If n is greater than zero, it returns a list with a sequence of ones and zeros equivalent to the binary representation of n. Unit tests:
(deftest test-binary (is (= () (binary 0))) (is (= '(1 1 1 1 0) (binary 30))) (is (= '(1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1) (binary 45123))))
prime-factors takes an integer n as input (assume that n > 0), and returns a list containing the prime factors of n in ascending order. The prime factors are the prime numbers that divide a number exactly. If you multiply all the prime factors you get the original number. Unit tests:
(deftest test-prime-factors (is (= () (prime-factors 1))) (is (= '(2 3) (prime-factors 6))) (is (= '(2 2 2 2 2 3) (prime-factors 96))) (is (= '(97) (prime-factors 97))) (is (= '(2 3 3 37) (prime-factors 666))))
compress takes a list lst as its argument. If lst contains consecutive repeated elements, they should be replaced with a single copy of the element. The order of the elements should not be changed. Unit tests:
(deftest test-compress (is (= () (compress ()))) (is (= '(a b c d) (compress '(a b c d)))) (is (= '(a b c a d e) (compress '(a a a a b c c a a d e e e e)))) (is (= '(a) (compress '(a a a a a a a a a a)))))
pack takes a list lst as its argument. If lst contains consecutive repeated elements they should be placed in separate sublists. Unit tests:
(deftest test-pack
(is (= () (pack ())))
(is (= '((a a a a) (b) (c c) (a a) (d) (e e e e))
(pack '(a a a a b c c a a d e e e e))))
(is (= '((1) (2) (3) (4) (5)) (pack '(1 2 3 4 5))))
(is (= '((9 9 9 9 9 9 9 9 9)) (pack '(9 9 9 9 9 9 9 9 9)))))
encode takes a list lst as its argument. Consecutive duplicates of elements in lst are encoded as vectors [n e], where n is the number of duplicates of the element e. Unit tests:
(deftest test-encode
(is (= () (encode ())))
(is (= '([4 a] [1 b] [2 c] [2 a] [1 d] [4 e])
(encode '(a a a a b c c a a d e e e e))))
(is (= '([1 1] [1 2] [1 3] [1 4] [1 5]) (encode '(1 2 3 4 5))))
(is (= '([9 9]) (encode '(9 9 9 9 9 9 9 9 9)))))
encode-modified takes a list lst as its argument. It works the same as the previous problem, but if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are converted to [n e] vectors. Unit tests:
(deftest test-encode-modified
(is (= () (encode-modified ())))
(is (= '([4 a] b [2 c] [2 a] d [4 e])
(encode-modified '(a a a a b c c a a d e e e e))))
(is (= '(1 2 3 4 5) (encode-modified '(1 2 3 4 5))))
(is (= '([9 9]) (encode-modified '(9 9 9 9 9 9 9 9 9)))))
decode takes as its argument an encoded list lst that has the same structure as the resulting list from the previous problem. It returns the decoded version of lst. Unit tests:
(deftest test-decode
(is (= () (decode ())))
(is (= '(a a a a b c c a a d e e e e)
(decode '([4 a] b [2 c] [2 a] d [4 e]))))
(is (= '(1 2 3 4 5) (decode '(1 2 3 4 5))))
(is (= '(9 9 9 9 9 9 9 9 9) (decode '([9 9])))))
Source of many of these problems: Ninety-Nine Lisp Problems
Using the Online
Assignment Delivery System (SETA), deliver a single file called
recursion2.clj containing your solutions and the unit
tests. No assignments will be accepted through e-mail or any other
means.
IMPORTANT: The program source file must include at the top the author's personal information (name and student id) within comments. For example:
;;; ITESM CEM, August 31, 2012.
;;; Clojure Source File
;;; Activity: Recursive Functions, Part II
;;; Author: Steve Rogers, 1166611
.
. (The rest of the program goes here)
.
Due date: Friday, August 31.
This activity will be evaluated using the following criteria:
| -10 | The program doesn't contain within comments the author's personal information. |
|---|---|
| 10 | The program contains syntax errors. |
| DA | The program was plagiarized. |
| 10-100 | Depending on the amount of exercises that were solved correctly. |