Three More Homework Problems

September 22, 2015

For the first problem, adjoin each element of the list to a set to eliminate duplicates from the list. This is easy in languages that provides sets as a native data type and not much harder in languages that don’t. We’ll represent the list as a set. Adjoin adds x to the list xs if it is not already present, and the loop adjoins each element in turn:

(define (adjoin x xs)
  (if (member x xs) xs (cons x xs)))

(define (problem1 xs)
  (let loop ((xs xs) (zs (list)))
    (if (null? xs) zs
      (loop (cdr xs) (adjoin (car xs) zs)))))

> (problem1 '(3 2 4 2 7 3 5 1 3))
(1 5 7 4 2 3)

The second problem is easy because the two lists are sorted; all we have to do is iterate through the list, advancing whichever list has the lesser head, and outputting any integers common to both:

(define (problem2 xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((or (null? xs) (null? ys))
            (reverse zs))
          ((< (car xs) (car ys))
            (loop (cdr xs) ys zs))
          ((< (car ys) (car xs))
            (loop xs (cdr ys) zs))
          (else (loop (cdr xs) (cdr ys)
                      (cons (car xs) zs))))))

> (problem2 '(2 3 5 5 6 7 8 9) '(1 2 4 5 5 7))
(2 5 5 7)

The third problem uses Newton’s method to compute the largest integer with cube not exceeding the input, then cubes it to see if it equals the input. We have an iroot function from a previous exercise, which we repeat below:

(define (iroot k n)
  (let ((k-1 (- k 1)))
    (let loop ((u n) (s (+ n 1)))
      (if (<= s u) s
        (loop (quotient (+ (* k-1 u) (quotient n (expt u k-1))) k) u)))))

(define (problem3 n)
  (let ((n3 (iroot 3 n)))
    (= (* n3 n3 n3) n)))

> (problem3 125)
#t
> (problem3 121)
#f

You can run the program at http://ideone.com/wG5Dt5.

Advertisements

Pages: 1 2

9 Responses to “Three More Homework Problems”

  1. klettier said

    Ex1 :

    let data = [ 3; 2; 4; 2; 7; 3; 5; 1; 3 ]
    
    let rec distinct arr res = 
        let rec isAlreadyIn a arr = 
            match arr with
            | [] -> false
            | b :: tail when b = a -> true
            | b :: tail -> isAlreadyIn a tail
        match arr with
        | [] -> res
        | a :: tail when (isAlreadyIn a res) -> distinct tail res
        | a :: tail -> distinct tail (a :: res)
    
    distinct data [] // [1; 5; 7; 4; 2; 3]
    

    Ex2:

    let d2 = [2; 3; 5; 5; 6; 7; 8; 9]
    let d3 = [1; 2; 4; 5; 5; 7] 
    
    let rec commonIntegers arr1 arr2 (prev : int option) (arr3 : List<int>) = 
        match arr1, arr2  with
        | [], [] -> arr3
        | [], arr -> arr3
        | arr, [] -> arr3
        | (a1 :: tail1), (a2 :: tail2) when prev.IsNone -> 
            if a1 = a2 then 
                arr3.Add(a1)
                commonIntegers tail1 tail2 None arr3
            elif a1 < a2 then commonIntegers tail1 tail2 (Some a2) arr3
            else commonIntegers tail1 tail2 (Some a1) arr3
        | ((a1 :: tail1) as arr1), ((a2 :: tail2) as arr2) -> 
            if prev.Value = a1 then 
                arr3.Add(a1)
                commonIntegers tail1 tail2 (Some a2) arr3
            elif prev.Value = a2 then 
                arr3.Add(a2)
                commonIntegers tail1 tail2 (Some a1) arr3
            else commonIntegers arr1 arr2 None arr3
    
    commonIntegers d2 d3 None (List<int>()) // [2; 5; 5; 7]
    

    Ex3 :

    let cube x = x *x *x
    
    let getCubes = seq{ for i in 1..Int32.MaxValue do yield cube i}
    
    let isPerfectCube x = 
        seq{for i in getCubes do
                if i = x then yield true
                elif i > x then yield false} |> Seq.head
    
    isPerfectCube 125 // True
    isPerfectCube 121 // False
    
  2. Informatimago said

    ;; 1) Given a list of integers, return a list in which all the duplicates
    ;; have been removed. For instance, given the input list [3, 2, 4, 2,
    ;; 7, 3, 5, 1, 3] return the output list [3, 2, 4, 7, 5, 1].

    This exercise is a good example of what is wrong with specifications,
    when you have one. The specification is to return a list with the
    duplicates removed, but it doesn’t specify in what order the remaining
    elements shall be placed in the resulting list, and which duplicates
    shall be removed (the first occurence? the last? any?). Such a weak
    specification can be a good thing, because it allows the programmer to
    implement usually very simple and efficient programs. For example, we
    could just write in Common Lisp:

    (defun remove-duplicate-integers/badass1 (list-of-integers)
    (remove-duplicates list-of-integers ))

    Unfortunately, the example given along with the specification, are
    often to be understood as part of the specification, and as such, over
    specify greatly. In this case, the example implies an order of the
    elements in the result list (same as the original list), and the
    duplicates that must be deleted (the last ones). Are those
    constraints really needed? And in TDD, those “examples” will often be
    used in tests, thus, hardwiring possibly an overspecification.

    Happily, Common Lisp expected those requirements, and there’s an
    option to the REMOVE-DUPLICATES function to process the duplicates
    from the end and therefore returning what the example expects:

    (defun remove-duplicate-integers/badass (list-of-integers)
    (remove-duplicates list-of-integers :from-end t))

    Of course, as a student exercise, such a solution might be rejected
    (again, the problem statement lacks in formality, and probably relies
    on a lot of assumptions). So as indicated, you might want to write a
    simple recursive solution such as:

    (defun remove-duplicate-integers/On^2/out-of-specs (list-of-integers)
    (cond ((null list-of-integers)
    ‘())
    ((member (first list-of-integers) (rest list-of-integers))
    (remove-duplicate-integers/On^2 (rest list-of-integers)))
    (t (cons (first list-of-integers)
    (remove-duplicate-integers/On^2 (rest list-of-integers))))))

    Unfortunately this simple solution fails on three counts:
    – it keeps the last duplicate instead of the first one,
    – using member on the rest of the list, it is O(n²) in time;
    – using a non-tail recursive call, it uses O(n) stack space.

    To transform the recursivity into a tail recursion, we can instead use
    an accumulator, an additionnal parameter that will collect the
    result. When using an accumulator to process a list, we obtain the
    resulting list in the reverse order, and since the specification seems
    to be unfortunately that the result must be in the same order as the
    original list, we have to reverse the result. Happily, this is only
    O(n), so it won’t be catastrophic. On the other hand, we still use
    member on the accumulated unique values, so this is still O(n²) in
    time, even if the constants are less than previously, since we search
    only the list of unique elements.

    (defun remove-duplicate-integers/On^2 (list-of-integers)
    (labels ((remdup (uniques list)
    (cond ((null list)
    (nreverse uniques))
    ((member (first list) uniques)
    (remdup uniques (rest list)))
    (t
    (remdup (cons (first list) uniques) (rest list))))))
    (remdup ‘() list-of-integers)))

    Finally, here is a solution that is O(n), uses O(1) stack space, and
    O(n) temporary space, and returns the exact results specified by the
    example: we use a hash-table to remember the unique elements.

    (defun remove-duplicate-integers/On (list-of-integers)
    (let ((uniques (make-hash-table)))
    (dolist (element list-of-integers)
    (setf (gethash element uniques) 1))
    (mapcan (lambda (element)
    (unless (minusp (decf (gethash element uniques)))
    (list element)))
    list-of-integers)))

    (mapc (lambda (rem) (assert (equal (funcall rem ‘(3 2 4 2 7 3 5 1 3))
    ‘(3 2 4 7 5 1))))
    ‘(remove-duplicate-integers/badass
    remove-duplicate-integers/On^2
    remove-duplicate-integers/On))

    A O(n) remove duplicates that wouldn’t have to keep the order of the
    original list or select a precise duplicate to keep would be:

    (defun remove-duplicate-integers/On/relaxed (list-of-integers)
    (let ((uniques (make-hash-table)))
    (dolist (element list-of-integers)
    (setf (gethash element uniques) 1))
    (let ((results ‘()))
    (maphash (lambda (element present)
    (declare (ignore present))
    (push element results))
    uniques)
    results)))

    (remove-duplicate-integers/On/relaxed ‘(3 2 4 2 7 3 5 1 3))
    ;; –> (7 2 1 3 5 4)

    ;; 2) Given two lists of integers, each sorted in ascending order, return
    ;; a list of the integers common to the two lists; the output list
    ;; must also be in ascending order. For instance, give the input lists
    ;; [2, 3, 5, 5, 6, 7, 8, 9] and [1, 2, 4, 5, 5, 7] return the output
    ;; list [2, 5, 5, 7].

    (defun common-integers (lista listb)
    (loop
    :for a := (first lista)
    :for b := (first listb)
    :while (and lista listb)
    :when (< a b)
    :do (pop lista)
    :when (> a b)
    :do (pop listb)
    :when (= a b)
    :collect (progn (pop lista) (pop listb))))

    (common-integers ‘(2 3 5 5 6 7 8 9) ‘(1 2 4 5 5 7))
    ;; –> (2 5 5 7)

    ;; 3) Given a positive integer, determine if it is a perfect cube. For
    ;; instance, the integer 125 is a perfect cube, 5*5*5, but the integer
    ;; 121 is not.

    (defun perfect-cube-p (n)
    (assert (plusp n))
    (= n (expt (truncate (expt n 1/3)) 3)))

    (perfect-cube-p 125) ; –> t
    (perfect-cube-p 121) ; –> nil

  3. Rutger said

    In Python.

    def exercise_1(lst):
    	return list(set(lst)) # no constraints w.r.t. retaining order
    
    # by definition of the exercise I believe example is wrong (result should only be one 5), hence this solution.
    def exercise_2(lst_1, lst_2):
    	return list(set(lst_1).intersection(set(lst_2)))   
    
    def exercise_3(n):
    	return n**(1.0/3) == int(n**(1.0/3))
    
    print exercise_1([3, 2, 4, 2, 7, 3, 5, 1, 3])
    print exercise_2([2, 3, 5, 5, 6, 7, 8, 9], [1, 2, 4, 5, 5, 7])
    print exercise_3(125)
    
  4. FA said

    Scala:

      // https://programmingpraxis.com/2015/09/22/three-more-homework-problems/
    
      // 1)
      List(3, 2, 4, 2, 7, 3, 5, 1, 3).distinct        //> res15: List[Int] = List(3, 2, 4, 7, 5, 1)
    
      // 2)
      def common(l1: List[Int], l2: List[Int]): List[Int] = l1.filter(l2.contains(_))
    
      common(List(2, 3, 5, 5, 6, 7, 8, 9), List(1, 2, 4, 5, 5, 7)) //> res16: List[Int] = List(2, 5, 5, 7)
    
      // 3) 
      def isPerfectCube(n: Long, c: Long = 1): Boolean = c * c * c == n || (c * c * c < n && isPerfectCube(n, c + 1))
      isPerfectCube(125)  //> res17: Boolean = true
      isPerfectCube(121)  //> res18: Boolean = false
    
  5. Paul said

    In Python.

    from collections import Counter
    
    def exercise1(seq):
        res, seen = [], set()
        for e in seq:
            if e not in seen:
                res.append(e)
            seen.add(e)
        return res
    
    def exercise2(seq1,  seq2):
        common = Counter(seq1) & Counter(seq2)
        return sorted(common.elements())
        
    def iroot3(n):
        'works also for big numbers'
        s = 2 ** ((n.bit_length() + 1)//3 + 1)
        u = s - 1
        while u < s:
            s = u
            u = (2*s + n//s**2) // 3
        return s
    
    def exercise3(positive):
        return iroot3(positive)**3 == positive
    
  6. Mike said

    My Python 3.4 solutions. (Your teacher would probably be suspicious if you turned these in for an intro level class.)

    The OrderedDict and OrderedCounter classes remember the order the keys are first encountered.

    The ‘&’ on the OrderedCounter class returns an OrderedCounter in which the count for each key is the minimum of the two operands.

    iscube() first finds ‘lo’, a power of 2 that is less than or equal to the cube root of n. Bisect_left(), from the standard library, then performs a binary search of Cube() to find where abs(n) would go between list indices lo and 2*lo. The Cube class provides a __getitem__() method, so an instance looks like a list (i.e., duck-typing) in which each element in the list is the cube of its index. It works for n up to about 5e55; above that, bisect_left fails, complaining that n won’t fit in the data-type (ssize_t) used for a list index.

    from bisect import bisect_left
    from collections import Counter, OrderedDict
    
    # problem 1
    def dedup(seq):
        return OrderedDict(zip(seq,seq)).keys()
    
    # problem 2
    class OrderedCounter(Counter, OrderedDict):
        pass
    
    def common(seq1, seq2):
        return (OrderedCounter(seq1) & OrderedCounter(seq2)).elements()
    
    # problem 3
    class Cube:
        def __getitem__(self, key):
            return key**3
    
    def iscube(n):
        lo = 2 ** ((n.bit_length() - 1)//3)
        index = bisect_left(Cube(), abs(n), lo, 2*lo)
        return index**3 == n
    
  7. Mayur Lokare said

    EX1.
    #include
    int main()
    {
    int n,arr[20],i,j,l=0;
    printf(“Enter the Number of elements\n”);
    scanf(“%d\n”,&n);
    for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
    for(i=0;i<n;i++)
    {
    for(j=0;j<i;j++)
    if(arr[i]==arr[j])
    break;
    if(j==i)
    arr[l++] = arr[i];
    }
    printf("new numbers\n");
    for(i=0;i<l;i++)
    printf("%d\n",arr[i]);
    }

  8. Mayur Lokare said

    EX2.
    #include
    int main()
    {
    int i,j,n,num1,num2,arr1[10],arr2[10],l1=0,l2=0,arr3[10],l3=0;
    printf(“Enter num1 and num2\n”);
    scanf(“%d%d”,&num1,&num2);
    printf(“Array 1\n”);
    for(i=0;i<num1;i++)
    scanf("%d",&arr1[i]);
    printf("Array 2\n");
    for(i=0;i<num2;i++)
    scanf("%d",&arr2[i]);

    for(i=0;i<num1;i++)
    {
    for(j=0;j<i;j++)
    if(arr1[i]==arr1[j])
    break;
    if(j==i)
    arr1[l1++] = arr1[i];
    }

    for(i=0;i<num2;i++)
    {
    for(j=0;j<i;j++)
    if(arr2[i]==arr2[j])
    break;
    if(j==i)
    arr2[l2++] = arr2[i];
    }

    for(i=0;i<l1;i++)
    {
    for(j=0;j<l2;j++)
    if(arr1[i]==arr2[j])
    arr3[l3++]=arr1[i];
    }
    printf("Result\n");
    for(i=0;i<l3;i++)
    printf("%d\n",arr3[i]);

    }
    1,1 Top

  9. Mayur Lokare said

    #include
    int main()
    {
    int num,i=1,j=0;
    printf(“Enter the number\n”);
    scanf(“%d”,&num);
    while(j<num)
    {
    j=i*i*i;
    i++;
    }
    if(j==num)
    printf("%d is perfect Cube\n",num);
    else
    printf("%d Not a perfect Cube\n",num);
    }

    O/P:
    Enter the number
    123
    123 Not a perfect Cube
    mayur@Embedded:~/Desktop/C/Logic$ ./a.out
    Enter the number
    1000
    1000 is perfect Cube

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: