Exercise 162: Here is the function 'search'...

Exercise 162: Here is the function search:

; Number List-of-numbers -> Boolean

(define (search n alon)

(cond

[(empty? alon) false]

[else (or (= (first alon) n) (search n (rest alon)))]))

It determines whether some number occurs in a list of numbers. The function may have to traverse the entire list to find out that the number of interest isn’t contained in the list.
Develop the function search-sorted, which determines whether a number occurs in a sorted list of numbers. The function must take advantage of the fact that the list is sorted.

The function we are developing here is quite similar to the last two questions. The only real difference is that we are starting to look at trying to optimise list traversal. This is simple enough to do as the list is already sorted and we can easily check where we are in the list and return as soon as we know the number can't be in the list (as we have gone past the place where the number would have to be).

Firstly we need (or desire) to include racket/base. This will give us access to fprintf - a function that can print out some diagnostic information so that we prove that we are taking advantage of the fact that the list is sorted. This is absolutely not required for the question.


(require racket/base)


; this testlist is just for ease of testing.
(define TESTLIST (list 100 80 45 23 22 20 3 1))


; tests are pretty straight forward - either the number in the list is there or it is not.
(check-expect (search-sorted 100 TESTLIST) true)
(check-expect (search-sorted 1 TESTLIST) true)
(check-expect (search-sorted 50 TESTLIST) false)




This is the search-sorted function. This is fairly straight forward. First I display some information as to what the current state of the list is and where we are at, then I recurse further down the list. If the first item on the list is larger than where we are at, then the list can't contain the n we are searching for and we immediately return false.


; Number List-of-numbers -> Boolean
(define (search-sorted n alon)
  (fprintf (current-output-port) 
           "searching for ~a First of alon: ~a. Alon is ~a \n" n (first alon) alon)
  (cond
    [(or (empty? alon)
         (> n (first alon))) false]
    [else (or (= (first alon) n) (search-sorted n (rest alon)))]))

This is the output from running out test cases on the above function. As you can see the first test case (where the n is not present in the list) iterates thru the entire list. For the second test case, as soon as we find the head of the list is less than 50, we stop recursing and return false.

Test Case 1

searching for 100 First of alon is 100.     Alon is (100 80 45 23 22 20 3 1) 
searching for 1 First of alon is 100.     Alon is (100 80 45 23 22 20 3 1) 
searching for 1 First of alon is 80.     Alon is (80 45 23 22 20 3 1) 
searching for 1 First of alon is 45.     Alon is (45 23 22 20 3 1) 
searching for 1 First of alon is 23.     Alon is (23 22 20 3 1) 
searching for 1 First of alon is 22.     Alon is (22 20 3 1) 
searching for 1 First of alon is 20.     Alon is (20 3 1) 
searching for 1 First of alon is 3.     Alon is (3 1) 
searching for 1 First of alon is 1.     Alon is (1) 

Test Case 2

searching for 50 First of alon is 100.     Alon is (100 80 45 23 22 20 3 1) 
searching for 50 First of alon is 80.     Alon is (80 45 23 22 20 3 1) 
searching for 50 First of alon is 45.     Alon is (45 23 22 20 3 1) 

Exercise 161: Design a programe that sorts lists of game players by score.

Exercise 161: Design a program that sorts lists of game players by score:

(define-struct gp (name score))

; A GamePlayer is a structure:

; – (make-gp String Number)

; interp. (make-gp p s) represents player p who scored

; a maximum of s points

This question (and solution) is again fairly similar to exercises 160 and 159. It's almost as though they wanted to drive home how similar these sorts of problems are.


Accordingly my answer is similar to the last, but we will still play along and create the solution from scratch...


; this struct is supplied by the question.
(define-struct gp (name score))


; start by creating a number of structs for easy testing etc
(define FIRST (make-gp "dave"  0 ))
(define SECOND (make-gp "bob" 10))
(define THIRD (make-gp "frank" 20))
(define FOURTH (make-gp "tom" 30))






; some tests to make sure we are doing things right.
(check-expect (sort-> empty) empty)
(check-expect (sort-> (list THIRD FOURTH FIRST)) 
              (list FOURTH THIRD FIRST))
(check-expect (sort-> (list THIRD SECOND FIRST)) 
              (list THIRD SECOND FIRST))
(check-expect (sort-> (list FIRST SECOND THIRD)) 
              (list THIRD SECOND FIRST))






This is the basic sort function - as you can see it is more or less identical to the last solution.



; List-of-gps -> List-of-gps
; produces a version of a gps (game player score), sorted by score in 
; descending order

(define (sort-> gps)
  (cond
    [(empty? gps) empty]
    [else (insert (first gps) (sort-> (rest gps)))]))


; Gps, List-of-Gps -> List-of-Gps 
; a helper function to do the actual insert
; insert n into the sorted list of gps's
(define (insert n alogps)
  (cond [(empty? alogps) (cons n empty)]
        [else (cond [(higher-score? n (first alogps)) (cons n alogps)]
                    [else (cons (first alogps) 
                                (insert n (rest alogps)))])]))


; utility function to determine which of two games had the higher score
; we could do this inline, but this lends itself to more clarity i think
(define (higher-score? game-1 game-2)
  (>= (gp-score game-1) (gp-score game-2)))

Exercise 160: Design a program that sorts lists of mail messages by date:

(define-struct mail (from date message))

; A Mail Message is a structure:

; – (make-mail String Number String)

; interp. (make-mail f d m) represents text m sent by

; f, d seconds after the beginning of time

Also develop a program that sorts lists of mail messages by name. To compare two strings alphabetically, use the string<? primitive.

***

This exercise was pretty easy - the answer to most of this was given more or less directly in the previous example of sorting a list of numbers. To make this more challenging I tried to do this without referring back to the previous example.

First I defined a series of structs that contain some predefined emails. This is just to make to check-expects easier to code and to read.




; Number List-of-numbers -> List-of-numbers

(define-struct mail (from date message))

(define FIRST (make-mail "dave"  0 "hello"))

(define SECOND (make-mail "john" 10 "hello"))

(define THIRD (make-mail "andrew" 20 "hello"))

(define FOURTH (make-mail "andrew" 40 "hello"))

These check-expects are pretty similar to the previous example - I've just changed them to look at mails instead.

; List-of-mails -> List-of-mails

; produces a version of alom, sorted by date in descending order

(check-expect (sort-date-> empty) empty)

(check-expect (sort-date-> (list THIRD FOURTH FIRST)) 

              (list FOURTH THIRD FIRST))

(check-expect (sort-date-> (list THIRD SECOND FIRST)) 

              (list THIRD SECOND FIRST))

(check-expect (sort-date-> (list FIRST SECOND THIRD)) 

              (list THIRD SECOND FIRST))

Sort-date is again almost identical to the standard previous example. The only difference is that we are sorting by date and inserting by date.

(define (sort-date-> alom)

  (cond

    [(empty? alom) empty]

    [else (insert-date (first alom) (sort-date-> (rest alom)))]))

Here we insert our date in to the already sorted list. To simplify this I have made a helper function more-recent? which will compare the dates on two emails and let us know which is more recent.

; insert n into the sorted list of date alon

(define (insert-date n alon)

  (cond [(empty? alon) (cons n empty)]

        [else (cond [(more-recent? n (first alon)) (cons n alon)]

                    [else (cons (first alon) 

                                (insert-date n (rest alon)))])]))

This is the helper function to determine which of two emails is more recent. We could do this inline in the insert-date method, but this lends itself to more clarity. 

(define (more-recent? email-1 email-2)

  (>= (mail-date email-1) (mail-date email-2)))

The sort order is not specified, so I will assume we are sorting from most recent -> least recent                                

(check-expect (insert-date FIRST empty) (list FIRST))

(check-expect (insert-date FIRST (list SECOND )) 

              (list SECOND FIRST))

(check-expect (insert-date SECOND (list FIRST)) 

              (list SECOND FIRST))

(check-expect (insert-date SECOND (list THIRD FIRST)) 

              (list THIRD SECOND FIRST));;;

; For the second part of the question we need to sort by name. The easiest way to do this would be to pass the insert and comparison methods into our sort function so that the same function could sort both names and dates. However we haven't been told how to do this in the text yet, so I assume they don't want us to do this.


As this is so similar to sorting by date I won't document what I am doing in as much detail.


I have created some more structs for this - I could have rigged the original ones so that they were both alphabetically and date sorted, but creating new ones seems to be more honest.

(define NFIRST (make-mail "andrew"  20 "hello"))

(define NSECOND (make-mail "bob" 410 "hello"))

(define NTHIRD (make-mail "charlie" 20 "hello"))

(define NFOURTH (make-mail "dave" 4 "hello"))

; List-of-mails -> List-of-mails

; produces a version of alom, sorted by name in descending order

(check-expect (sort-name-> empty) empty)

(check-expect (sort-name-> (list NTHIRD NFOURTH NFIRST)) 

              (list NFOURTH NTHIRD NFIRST))

(check-expect (sort-name-> (list NTHIRD NSECOND NFIRST)) 

              (list NTHIRD NSECOND NFIRST))

(check-expect (sort-name-> (list NFIRST NSECOND NTHIRD)) 

              (list NTHIRD NSECOND NFIRST))

(define (sort-name-> alom)

  (cond

    [(empty? alom) empty]

    [else (insert-by-name (first alom) (sort-name-> (rest alom)) )]))

; insert n into the sorted list of mails alom

(define (insert-by-name n alom)

  (cond [(empty? alom) (cons n empty)]

        [else (cond [(alphabetically-earlier? n (first alom)) 

                     (cons n alom)]

                    [else (cons (first alom) 

                                (insert-by-name n (rest alom)))])]))

; sort order not specified, so will assume sort from most recent -> least recent                                

(check-expect (insert-by-name NFIRST empty) (list NFIRST))

(check-expect (insert-by-name NFIRST (list NSECOND ))

              (list NSECOaND NFIRST))

(check-expect (insert-by-name NSECOND (list NFIRST)) 

              (list NSECOND NFIRST))

(check-expect (insert-by-name NSECOND (list NTHIRD NFIRST))

              (list NTHIRD NSECOND NFIRST))

; utility function to determine which of two emails is more recent

(define (alphabetically-earlier? email-1 email-2)

  (string>? (mail-from email-1) (mail-from email-2)))

Exercise 159: You know about first and rest from BSL, but BSL+ comes with even more selectors than that....

Exercise 159: You know about first and rest from BSL, but BSL+ comes with even more selectors than that. Determine the values of the following expressions:

1. (first (list 1 2 3))
2. (rest (list 1 2 3))
3. (second (list 1 2 3))

Find out from the documentation whether third, fourth, and fifth exist.



This is a very straight forward exercise. As always with exercises of this type the hardest thing is making yourself do the exercise rather than just pasting the expressions into racket and seeing what they evaluate to.

I did not do as well as I expected - I got the first and third questions wrong. I was expecting them to return a list instead of the element.

A quick look at the documentation shows that not only do third, fourth and fifth exist, but so do sixth, seventh, eighth, nineth and tenth.

;(first (list 1 2 3))
(check-expect (first (list 1 2 3))
              1)


;(rest (list 1 2 3))
(check-expect (rest (list 1 2 3))
              (list 2 3))


;(second (list 1 2 3))
(check-expect (second (list 1 2 3))
              2)
     

Exercise 158: Determine the values of the following expressions...

Exercise 158: Determine the values of the following expressions:

1. (list (string=? "a" "b") (string=? "c" "c") false)
2. (list (+ 10 20) (* 10 20) (/ 10 20))
3. (list "dana" "jane" "mary" "laura")

This is a pretty straight forward exercise. The hardest part here is to avoid the temptation to paste these directly in to the racket interpreter. I got 2/3 correct on my first pass though.


;1) (list (string=? "a" "b") (string=? "c" "c") false)
(check-expect (list (string=? "a" "b") (string=? "c" "c") false)
              (list false true false))
              
;2) (list (+ 10 20) (* 10 20) (/ 10 20))
(check-expect (list (+ 10 20) (* 10 20) (/ 10 20))
              (list 30 200 0.5))


;3) (list "dana" "jane" "mary" "laura")
(check-expect (list "dana" "jane" "mary" "laura")
              (list "dana" "jane" "mary" "laura"))

Exercise 157b: On some occasions lists are formed with cons and list. Reformulate the following lists using list exclusively

Exercise 157: On some occasions lists are formed with cons and list. Reformulate the following lists using list exclusively:;


;(cons "a" (list 0 false))
;
;(list (cons 1 (cons 13 empty)))
;
;(cons (list 1 (list 13 empty)) empty)
;
;(list empty empty (cons 1 empty))
;
;(cons "a" (cons (list 1) (list false empty)))

Whoops! Completely missed that second part about doing this also exclusively using list. Luckily this is a lot easier than doing them using cons exclusively. The tricky part about this exercise was doing it all in your head before pasting the source expression into racket - as soon as you do that, racket gives the answer formatted using list. Doh!



;1 Reformulate: (cons "a" (list 0 false))
(check-expect (cons "a" (list 0 false))
              (list "a" 0 false))


  
;2 Reformulate (list (cons 1 (cons 13 empty)))
(check-expect (list (cons 1 (cons 13 empty)))  
              (list (list 1 13) ))
              
;3 Reformulate (cons (list 1 (list 13 empty)) empty)
(check-expect (cons (list 1 (list 13 empty)) empty)
              (list (list 1 (list 13 empty))))


;4 Reformulate
;(list empty empty (cons 1 empty))
(check-expect (list empty empty (cons 1 empty))
              (list empty empty (list 1)))




;5 Reformulate (cons "a" (cons (list 1) (list false empty)))
(check-expect (cons "a" (cons (list 1) (list false empty)))
              (list "a" (list 1) false empty))

Exercise 157: On some occasions lists are formed with cons and list. Reformulate the following lists using cons and empty exclusively

Exercise 157: On some occasions lists are formed with cons and list. Reformulate the following lists using cons and empty exclusively



;(cons "a" (list 0 false))
;
;(list (cons 1 (cons 13 empty)))
;
;(cons (list 1 (list 13 empty)) empty)
;
;(list empty empty (cons 1 empty))
;
;(cons "a" (cons (list 1) (list false empty)))


This exercise was pretty straight forward. I just built up the lists from scratch only using cons.

;1 Reformulate: (cons "a" (list 0 false))
(check-expect (cons "a" (cons 0 (cons false empty)))
              (cons "a" (list 0 false)))




;2 Reformulate: (list (cons 1 (cons 13 empty)))
(check-expect (list (cons 1 (cons 13 empty)))  
              (cons (cons 1 (cons 13 empty)) empty) )
    
          
;3 Reformulate (cons (list 1 (list 13 empty)) empty)
;  this one is a little more interesting - we are making 
;  a list of empty lists - easy enough to do though with 
;  a (cons empty empty)
(check-expect (cons (list 1 (list 13 empty)) empty)
              (cons (cons 1 (cons (cons 13 
                            (cons empty empty)) empty)) empty))


;4 Reformulate: (list empty empty (cons 1 empty))
(check-expect (list empty empty (cons 1 empty))
              (cons empty (cons empty (cons 
                                      (cons 1 empty) empty))))




;5 Reformulate: (cons "a" (cons (list 1) (list false empty)))
(check-expect (cons "a" (cons (list 1) (list false empty)))
              (list "a" (list 1) false empty))