Problem Set: Recursive Functions II

Objectives

During this activity, students should be able to:

Write recursive functions of medium complexity using the Clojure programming language.

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.

Activity Description

This activity can be developed individually or in pairs.

Solve the following programming problem set using Clojure. Place all your functions and unit tests in a file called recursion2.clj. All problems should be solved using explicit recursion or the recur and loop special forms.

The function 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))))

The function 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])))))

The function 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)))))

The function 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)))))

The function 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)))))

The function 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))))))
```

The function 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)))))

The function 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)))))
```
The function 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))))
```
The function 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))))
```

The function 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)))))

The function 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)))))

The function 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)))))

The function 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)))))

The function 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

Deliverables

The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

;----------------------------------------------------------
; Activity: Problem Set: Recursive Functions II
; Date: August 31, 2017.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Also, each function should include a documentation string (docstring) with a brief description of its behavior. For example:

(defn max2
  "Returns the largest of the two numbers x and y."
  [x y]
  (if (> x y) x y))

Upload Instructions

To deliver the recursion2.clj file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Thursday, August 31.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
-30	A docstring is missing in one or more functions.
10	The program contains syntax errors.
1	The program was plagiarized in whole or in part.
10-100	Depending on the amount of exercises that were solved correctly.