Three More Homework Problems

September 22, 2015

I can tell from my statistics that people like the homework problem exercises, I suppose because they are short and provide simple drill. I can also tell, from reading some of the beginning-programmer message boards, that students seem to be quicker that they used to be to post their homework problems on-line rather than figuring out the solutions themselves, either because they are lazy or because their teachers aren’t providing sufficient help. So today we have three more homework problems:

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

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

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.

Your task is to write programs that solve the three homework problems. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: