Summary CPSC 110 - PSET 9 SOLUTIONS - 2022

;; 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-09-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 psets/pset-09);Do not edit or remove this tag

(@problem 1)

;;
;; THIS IS THE MOST CHALLENGING PROBLEM SET SO FAR THIS TERM. PLEASE BE
;; SURE YOU WORK THROUGH IT CAREFULLY THOUGH. 110 FINAL EXAMS OFTEN INCLUDE
;; PROBLEMS BASED ON PROBLEM SETS 9, 10, OR 11.
;;
;; ALSO NOTE THAT THE AUTOGRADER WILL ONLY GRADE ONE SUBMISSION PER HOUR FOR
;; THIS PROBLEM SET. SO START EARLY AND CAREFULLY TEST YOUR WORK ON YOUR OWN
;; EACH TIME BEFORE SUBMITTING TO THE AUTOGRADER.
;;
;; THERE WILL BE A SPECIAL PINNED THREAD ON PIAZZA IN WHICH WE WILL ANSWER
;; QUESTIONS ABOUT THIS PROBLEM SET.
;;
;; In this problem set you are going to work on one of the toughest problems
;; we face running 110 - scheduling of TAs. As you may know, we have about
;; 45 TAs, and we have to schedule them for many labs, 3 lectures, and office
;; hours. We solved this by writing a schedule solver, and that's what you
;; are going to do for this problem set.
;;
;; We are making it a little easier for you, in that all you will be having
;; to deal with is labs.
;;
;; We are giving you two key data definitions, as well as some examples of
;; that data. We are also giving you a wish list entry for the main solve
;; function you have to design. The function consumes a list of TAs and a
;; list of lab slots to fill. It produces a list of assignments. So, for
;; example, in the following very simple case, where there are two slots,
;; and two TAs, you get an assignment of the TAs to those slots.
;;
;; (solve (list (make-slot "A" 1) (make-slot "B" 1))
;; (list (make-ta "Ali" (list "B"))
;; (make-ta "Azi" (list "A")))) ==>
;;
;; (list (list "Ali" "B") (list "Azi" "A"))
;;
;; In this simple example there was only one possible assignment. But in
;; general there might be more than one assignment, or it might be impossible
;; to generate an assignment.

;; By now you know enough about search to know that the first thing you need
;; to do is figure out the search space. What does the tree look like? What
;; information do you have to represent at each node in the tree? Even though

, ;; The function ends up producing just a list of assignments, it need more than
;; just the assignments so far at each node in the tree? What other information
;; do you need to represent at each node?
;;
;; As you consider the search tree, note that a TA can work more than one slot,
;; but a slot is filled by one TA. So once you assign a TA to a slot that slot
;; is done.
;;
;; As usual, anything we give you you must use without changing. The autograder
;; will want to call solve with arguments as described below.

;; Constants:

(define MAX-SLOTS-PER-TA 3) ;this is the max number of labs a TA can work

;; Data definitions:

(@htdd Slot)
(define-struct slot (lab n))
;; Slot is (make-slot String Natural)
;; interp. the name of a lab - "A", "B", etc.
;; the lab's slot number - 1, 2, 3 etc.
;; CONSTRAINT:
;; a list of slots representing positions that need to be filled
;; should not contain duplicate slots (slots with same lab and n)
;;
(define SLOTS1
(list (make-slot "A" 1) (make-slot "A" 2) ;A needs 2 TAs
(make-slot "B" 1) ;B needs 1
(make-slot "C" 1) (make-slot "C" 2))) ;C needs 2

(@htdd TA)
(define-struct ta (name avail))
;; TA is (make-ta String (listof String))
;; interp. A TA with their name and the labs times they are free to work.
;; CONSTRAINT:
;; a list of TAs should not contain TAs with duplicate names

(define TAS1
(list (make-ta "Ali" (list "A" "B"))
(make-ta "Ari" (list "B" "C"))
(make-ta "Azi" (list "A" "C"))))



;;!!! below here is solution

(@htdf solve)
(@signature (listof Slot) (listof TA) -> (listof (listof String)) or false)
;; produce list of lab assignments of form: (list "ta name" "lab name")

(check-expect (solve empty empty) empty)
(check-expect (solve empty (list (make-ta "Ali" (list "A"))))
empty)
(check-expect (solve (list (make-slot "A" 1)) empty) false)
(check-expect (solve (list (make-slot "A" 1)
(make-slot "A" 2))
(list (make-ta "Ali" (list "A" "B"))))
false)