HW6 + Solutions

posted Oct 29, 2012, 9:23 AM by Samuel Konstantinovich   [ updated Nov 26, 2012, 5:57 AM ]
THE HW SERVER IS NOT RUNNING. DO NOT EMAIL THIS TO ME! 

This will be due on the homework server  MONDAY NOVEMBER 5th 11:59pm
You must submit it on time, and in an RKT or SCM file. If you submit anything else you will receive 0 points.  If you submit it late you will lose points. 

WARNING: (There is no slot on the homework server yet, because it seems to be down. Don't worry if you can't reach it for now.)

I will be traveling out of state the weekend that this is due, and will not be able to answer questions.
If you would like help, please work on this early. 

SAMPLE SOLUTIONS FOR THE WEEKEND HW:
;S1. Count the number of positive integers in a list (including it's sublists)
;    (countPositive '( (2 -3) -4 (3 (-1) 0 2) ) ) -> 3    
(define (countPositive L)
  (cond
    ((null? L) 0)
    ;This next part is new. Treat the car like you would treat the cdr, THEN join the two halves of the solution
    ((list? (car L)) (+(countPositive (car L))(countPositive (cdr L))))  
    ((> (car L)0) (+ 1 (countPositive (cdr L))))
    (else (countPositive(cdr L)))))
;Notice that this solution is like countPositive from before, except the extra case when the car is a list

;S2. Reverse a list, including sublists 
;   (myReverse '( a b c ) )   -> (c b a)
;   (myReverse '( 1 2 (3 4) (5 6))) -> ((6 5)(4 3) 2 1)
(define (MyReverse L)
  (cond
    ((null? L) L)
    ;Since the car is a list, you want it inside a set
    ;of parenthesis... so we use the list command before appending. 
    ((list? (car L)) (append (MyReverse (cdr L))(list(MyReverse (car L)))))
    (else (append (MyReverse(cdr L)) (list (car L))))))
;Notice that this solution is like my reverse from before, except the extra case when the car is a list


;Write the following functions
;6.1 
;Count the number of sublists inside a list including sublists.
;    (countLists '( (2 3) (3 (5) 2) )  -> 3    
;    Think how many open parentheis are in the list...
;
;6.2
; Remove the 0's from a list of integers which may have sublists.
; H
int, you need to know the different uses of cons vs append. 
;    (stripZeros '( 0 2 (3 0 (0 ) ) 5))   -> ( 2 ( 3 () ) 5)
;
;6.3
;Add 1 to each of the values in a list of integers which may have sublists.
;    (addOne '( 9 9 (4 3) (2 (1) ) ) )   -> (10 10  (5 4) (3 ( 2 ) ) ) 
;
;6.4
;(contains L x) : Contains is true when x is found inside of L
;L is a list of integers WITHOUT sublists, x is an integer 
;Examples:
;(contains '( 1 2 3) 4)  is #f
;(contains '( 1 2 3) 2)  is #t

;6.5  
;(containsSub L x) : Contains is true when x is found inside of L or any of its sublists.
;L is a list of integers that CAN have sublists, x is an integer or list of integers
;Hint DO NOT USE (= a b) use (equal? a b) to compare elements, because you need to use equal? when comparing lists. 
;You will need to use OR
;Examples:
;(containsSub '( 1 2 3) 4)  is #f
;(containsSub '( 1 2 3) 2)  is #t
;(containsSub '( 1 (2) 3) '(1) )  is #f 
;(containsSub '( 1 (2) 3)  2 )  is #t
;(containsSub '( 1 (2 3) (4 5) )  '(3 4) )  is #f
;(containsSub '( 1 (2 3) (4 5) )  '(2 3) )  is #t
;(containsSub '( 1 (2 3) (4 5 6) )  '(4 5) )  is #f




Solutions:

;6.1
(define (countLists L)
  (cond
    ((null? L) 0)
    ((list? (car L)) (+ 1 (countLists (car L))(countLists (cdr L))))
    (else (countLists (cdr L)))))

;6.2
(define (stripZeros L)
  (cond
    ((null? L) L)
    ((list? (car L)) (cons (stripZeros (car L))(stripZeros (cdr L))))
    ((= (car L) 0) (stripZeros (cdr L)))
    (else (cons (car L) (stripZeros (cdr L))))))

;6.3
(define (addOne L)
  (cond
    ((null? L) L)
    ((list? (car L)) (cons (addOne (car L))(addOne (cdr L))))
    (else (cons (+ 1 (car L)) (addOne (cdr L))))))

;6.4
(define (contains L x) 
  (cond
    ((null? L) #f)
    ((= (car L) x) #t)
    (else (contains (cdr L ) x))))

;6.5
(define (containsSub L x) 
  (cond
    ((null? L) #f)
;this is the tricky part... the car could match x, or the car could have x inside it, or the cdr could have x inside it:
    ((list? (car L)) (or (equal? (car L) x) (containsSub (car L ) x) (containsSub (cdr L) x)))
    ((equal? (car L) x) #t)
    (else (containsSub (cdr L ) x))))
     

Comments