Summary CPSC 110 PSET 10 SOLUTION

;; The first three lines of this file were inserted by DrRacket. They record
metadata
;; about the language level of this file in a form that our tools can easily
process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname pset-10-solution)
(read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-
decimal #f #t none #f () #t)))
;; DO NOT PUT ANYTHING PERSONALLY IDENTIFYING BEYOND YOUR CWL IN THIS FILE.
;; YOUR CWLs WILL BE SUFFICIENT TO IDENTIFY YOU AND, IF YOU HAVE ONE, YOUR
;; PARTNER.
;;
(require spd/tags)

(@assignment pset-10); Do not edit or remove this tag



(@problem 1)

(@htdf max-num-repeats)
(@signature (listof String) -> Natural)
;; produce maximum number of times same string appears consecutively in los0
(check-expect (max-num-repeats empty) 0)
(check-expect (max-num-repeats (list "cat")) 1)
(check-expect (max-num-repeats (list "cat" "bird" "dog")) 1)
(check-expect (max-num-repeats (list "cat" "cat" "bird" "dog")) 2)
(check-expect (max-num-repeats (list "cat" "cat" "bird" "dog" "dog" "dog"))
3)
(check-expect (max-num-repeats (list "cat" "cat" "cat"
"bird"
"boy" "boy" "boy"
"toy" "toy" "toy" "toy" "toy"
"trick"
"zebra" "zebra" "zebra" "zebra"))
5)

(@template (listof String) accumulator)

(define (max-num-repeats los0)
;; prev is String: the previous first string in list
;; curr is Natural: number of times prev has been seen so far
;; rsf is Natural: maximum number of times a string has been seen so far
(local [(define (fn-for-los los prev curr rsf)
(cond [(empty? los) (max curr rsf)]
[else
(if (string=? (first los) prev)
(fn-for-los (rest los) (first los) (add1 curr) rsf)
(fn-for-los (rest los) (first los) 1 (max curr rsf)))]))]
(if (empty? los0)
0
(fn-for-los (rest los0) (first los0) 1 0))))

(@problem 2)

(@htdf list-range)
(@signature (listof Integer) -> Natural)
;; produce the difference between the max and min integer in the list
;; CONSTRAINT: loi0 has at least one element
(check-expect (list-range (list 100)) 0)

, (check-expect (list-range (list 2 -5 -10 50 80)) 90)
(check-expect (list-range (list 5000 -5 -100 50 0)) 5100)
(check-expect (list-range (list 3 8 1 2 9 4 2 3 -5)) 14)
(check-expect (list-range (list -5000 3 2 2 4 5000 4 2 3)) 10000)
(check-expect (list-range (list 400 500 500 400)) 100)

(@template (listof Integer) accumulator)

(define (list-range loi)
;; max-rsf is Integer: maximum integer seen so far
;; min-rsf is Integer: minimum integer seen so far
(local [(define (fn-for-loi loi max-rsf min-rsf)
(cond [(empty? loi) (- max-rsf min-rsf)]
[else
(fn-for-loi (rest loi)
(max (first loi) max-rsf)
(min (first loi) min-rsf))]))]
(fn-for-loi (rest loi) (first loi) (first loi))))



(@problem 3)

(@htdf in-alphabetical-order?)
(@signature (listof String) -> Boolean)
;; produce true if list is sorted in order according to string-ci<=?
(check-expect (in-alphabetical-order? empty) true)
(check-expect (in-alphabetical-order? (list "a")) true)
(check-expect (in-alphabetical-order? (list "All" "bees" "Feel" "HAPPY")) true)
(check-expect (in-alphabetical-order? (list "aaaaa" "bb" "dd" "ccc")) false)

(@template (listof String) accumulator)

(define (in-alphabetical-order? los0)
;; prev is String: previous string in los
(local [(define (fn-for-los los prev)
(cond [(empty? los) true]
[else
(if (string-ci<=? prev (first los))
(fn-for-los (rest los) (first los))
false)]))]
(if (empty? los0)
true
(fn-for-los (rest los0) (first los0)))))



;;
;; Please read through the data definition introduced in Problem Set 6
;; for a Course.
;;

(@htdd Course)
(define-struct course (number credits dependents))
;; Course is (make-course Natural Natural ListOfCourse)
;; interp. a course with a course number,
;; the number of credits the course is worth,
;; a list of courses that have this course as a pre-requisite