Problem Set #3: More Repetitions

Objective

During this activity, students should be able to:

Write more Clojure functions that involve using repetition constructs.

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

Solve with your team the Clojure exercises described in this problem set. Make sure each function passes all the unit tests.

Create a namespace called more-repetitions. At the begining of the file add the following code in order to declare the namespace and import the required external functions:

(ns more-repetitions
  (:require [clojure.test :refer [deftest is run-tests]]))

and at the end add:

(run-tests)

All the code you write should go between these two instructions.

The function expand takes a sequence \(s\) as its input. It returns a list where the first element of \(s\) appears one time, the second elements appears two times, the third element appears three times, and so on.

Unit test:

(deftest test-expand
  (is (= () (expand ())))
  (is (= '(a) (expand '(a))))
  (is (= '(1 2 2 3 3 3 4 4 4 4) (expand '(1 2 3 4))))
  (is (= '(a b b c c c d d d d e e e e e)
         (expand '(a b c d e)))))

The function insert takes two inputs: a number \(n\) and a sequence of numbers \(s\) in ascending order. It returns a list with the same elements as \(s\) but inserting \(n\) in its corresponding place. Your solution should have a time complexity of \(O(N)\).

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 insertion-sort takes as input an unordered sequence of numbers and returns a list with the same elements but in ascending order. You must use the insert function defined for the previous problem to write insertion-sort. You must NOT use the predefined sort function.

Unit tests:

(deftest test-insertion-sort
  (is (= () (insertion-sort ())))
  (is (= '(0 1 3 3 4 6 7 8 9)
         (insertion-sort '(4 3 6 8 3 0 9 1 7))))
  (is (= '(1 2 3 4 5 6) (insertion-sort '(1 2 3 4 5 6))))
  (is (= '(1 5 5 5 5 5 5) (insertion-sort '(5 5 5 1 5 5 5)))))

The function rotate-left takes two inputs: an integer number \(n\) and a sequence \(s\). It returns a list that results from rotating \(s\) a total of \(n\) positions to the left. If \(n\) is negative, it rotates to the right.

Unit tests:

(deftest test-rotate-left
  (is (= () (rotate-left 5 ())))
  (is (= '(a b c d e f g) (rotate-left 0 '(a b c d e f g))))
  (is (= '(b c d e f g a) (rotate-left 1 '(a b c d e f g))))
  (is (= '(g a b c d e f) (rotate-left -1 '(a b c d e f g))))
  (is (= '(d e f g a b c) (rotate-left 3 '(a b c d e f g))))
  (is (= '(e f g a b c d) (rotate-left -3 '(a b c d e f g))))
  (is (= '(a b c d e f g) (rotate-left 7 '(a b c d e f g))))
  (is (= '(a b c d e f g) (rotate-left -7 '(a b c d e f g))))
  (is (= '(b c d e f g a) (rotate-left 8 '(a b c d e f g))))
  (is (= '(g a b c d e f) (rotate-left -8 '(a b c d e f g))))
  (is (= '(d e f g a b c) (rotate-left 45 '(a b c d e f g))))
  (is (= '(e f g a b c d) (rotate-left -45 '(a b c d e f g)))))

The function binary takes an integer \(n\) as input (\(n \ge 0\)). If \(n = 0\), it returns an empty list. If \(n > 0\), 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 (\(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 of \(n\) you obtain \(n\).

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 gcd takes two integers \(a\) and \(b\) as inputs (\(a > 0\) and \(b > 0\)). It returns the greatest common divisor (GCD) of \(a\) and \(b\). You must NOT use the predefined clojure.math.numeric-tower/gcd function.

NOTE: The GCD of two integers is the largest positive integer that divides both numbers exactly. For example, the GCD of 20 and 16 is 4.

Unit tests:
```
(deftest test-gcd
  (is (= 1 (gcd 13 7919)))
  (is (= 4 (gcd 20 16)))
  (is (= 6 (gcd 54 24)))
  (is (= 7 (gcd 6307 1995)))
  (is (= 12 (gcd 48 180)))
  (is (= 14 (gcd 42 56))))
```

The function insert-everywhere takes two inputs: an object \(x\) and a sequence \(s\). It returns a new list with all the possible ways in which \(x\) can be inserted into every position of \(s\).

Unit tests:

(deftest test-insert-everywhere
  (is (= '((1)) (insert-everywhere 1 ())))
  (is (= '((1 a) (a 1)) (insert-everywhere 1 '(a))))
  (is (= '((1 a b c) (a 1 b c) (a b 1 c) (a b c 1))
         (insert-everywhere 1 '(a b c))))
  (is (= '((1 a b c d e)
           (a 1 b c d e)
           (a b 1 c d e)
           (a b c 1 d e)
           (a b c d 1 e)
           (a b c d e 1))
         (insert-everywhere 1 '(a b c d e))))
  (is (= '((x 1 2 3 4 5 6 7 8 9 10)
           (1 x 2 3 4 5 6 7 8 9 10)
           (1 2 x 3 4 5 6 7 8 9 10)
           (1 2 3 x 4 5 6 7 8 9 10)
           (1 2 3 4 x 5 6 7 8 9 10)
           (1 2 3 4 5 x 6 7 8 9 10)
           (1 2 3 4 5 6 x 7 8 9 10)
           (1 2 3 4 5 6 7 x 8 9 10)
           (1 2 3 4 5 6 7 8 x 9 10)
           (1 2 3 4 5 6 7 8 9 x 10)
           (1 2 3 4 5 6 7 8 9 10 x))
         (insert-everywhere 'x '(1 2 3 4 5 6 7 8 9 10)))))

The function contains-all-digits? takes an integer number \(n\) as input and returns true if \(n\) contains each of the ten decimal digits from 0 to 9 at least once, or false otherwise.

Unit tests:

(deftest test-contains-all-digits?
  (is (contains-all-digits? 1023456789))
  (is (contains-all-digits? 5897230146))
  (is (contains-all-digits? 10123485679))
  (is (contains-all-digits?
       1223334444555566666677777778888888889999999990))
  (is (not (contains-all-digits? 1236)))
  (is (not (contains-all-digits? 1112223334455)))
  (is (not (contains-all-digits? -587230462413578)))
  (is (not (contains-all-digits?
            -122333444455556666667777777888888888999999999))))

The function pack takes a sequence \(s\) as its input. If \(s\) contains consecutive repeated elements they should be placed in separate sublists.

TIP: This problem can be easily solved using the partition-by predefined function.

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 compress takes a sequence \(s\) as its input. It returns a list with the same elements of \(s\) but repeated consecutive elements are replaced with a single instance. The order of the original elements should be preserved.

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 encode takes a sequence \(s\) as its input. It returns a list where consecutive repeated elements of \(s\) are encoded as vectors [\(n \; e\)], where \(n\) is the number of repetitions 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 sequence \(s\) as its input. It works the same as the previous problem, but if an element is single it is simply copied into the result list. Only elements with actual 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 input an encoded sequence \(s\) that has the same structure as the resulting list from the previous problem. It returns the decoded version of \(s\).

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

Deliverables

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

;----------------------------------------------------------
; Problem Set #3: More Repetitions
; Date: March 16, 2022.
; Authors:
;          A01770771 Sylvie Laufeydottir
;          A01777771 Loki Laufeyson
;----------------------------------------------------------

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

Instrucciones para subir archivo

Para entregar el archivo more_repetitions.clj, ingresa los siguientes datos:

Solicitar NIP

Only one team member needs to upload the file.

Due date is Wednesday, March 16.

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.