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.
Programming Praxis 
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;; 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
In Python.
Scala:
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 == positiveMy 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 == nEX1.
#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]);
}
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
#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