Out: Monday, 30 October 2017
Due: Monday, 6 November 2017 at 6pm local time

This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.

The main purpose of this problem set is to give you practice designing functions with general recursion and halting measures.

You must use Racket's Intermediate Student Language + Lambda for this problem set.

For these problems, download a copy of extras.rkt and put it in the directory with your solutions. Then import rackunit and this library by including the lines

      (require rackunit)
      (require "extras.rkt")

at the top of your file. Then, for each problem, put in lines that say

      (provide function)

for each deliverable function, as you have done on previous problem sets. This will allow our testing framework to import your file and do automated testing on it. You can use check-location to double-check that your solutions are in the right place.

Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.

Be sure to fill out a work session report at the end of each work session. Be sure to report only the hours spent in that work session; do not report the cumulative time. Tell git to add your work session report to the files you will commit, and then commit and push (sync) that report in addition to committing and pushing your entire set06set08 directory. Do this at the end of every work session.

Remember to include a copy of extras.rkt racket in your set08 directory along with your q1.rkt and q2.rkt files.

For both parts, you should require rackunit and "extras.rkt" but nothing else.

---

This problem set deals with the problem of ranking individuals or teams in a sport such as chess whose contests result in a win or tie (draw).

Unlike most ranking systems, the ranking system you will implement treats a tie as a win for both competitors and also as a loss for both competitors. (This problem set may help to explain why most ranking systems don't do that.)

We will use strings to name competitors:

      ;;; A Competitor is represented as a String (any string will do).

1. (Outranking)
   

   For this first part of Problem Set 08, you will design data types named Tie and Defeat. A Tie represents a tie (draw) between two competitors. A Defeat represents the outcome of a contest in which one competitor wins and the other loses. The outcome of a contest is either a Tie or a Defeat:

             ;;; An Outcome is one of
             ;;;     -- a Tie
             ;;;     -- a Defeat
             ;;;
             ;;; OBSERVER TEMPLATE:
             ;;; outcome-fn : Outcome -> ??
             #;
             (define (outcome-fn o)
               (cond ((tie? o) ...)
                     ((defeat? o) ...)))
   

   The ranking system specified below uses this definition:

   Given a list of outcomes, a competitor A outranks a competitor B if any of the following are true:

   • One of the outcomes shows that A has defeated B.
   • One of the outcomes shows that A and B have tied.
   • There is a competitor C that outranks B according to the list of outcomes, and there is an outcome that shows A has defeated or tied C.

   You are to deliver a file named q1.rkt that

   • defines the Competitor, Tie, Defeat, and Outcome types; the Competitor and Outcome types must be defined as shown above
   • defines and provides all 5 of the functions specified below
   • gives halting measures for all functions that may call themselves directly or indirectly

   The 5 functions you must define and provide are:

             ;;; tie : Competitor Competitor -> Tie
             ;;; GIVEN: the names of two competitors
             ;;; RETURNS: an indication that the two competitors have
             ;;;     engaged in a contest, and the outcome was a tie
             ;;; EXAMPLE: (see the examples given below for defeated?,
             ;;;     which shows the desired combined behavior of tie
             ;;;     and defeated?)
             ;;;
             ;;; defeated : Competitor Competitor -> Defeat
             ;;; GIVEN: the names of two competitors
             ;;; RETURNS: an indication that the two competitors have
             ;;;     engaged in a contest, with the first competitor
             ;;;     defeating the second
             ;;; EXAMPLE: (see the examples given below for defeated?,
             ;;;     which shows the desired combined behavior of defeated
             ;;;     and defeated?)
             ;;;
             ;;; defeated? : Competitor Competitor OutcomeList -> Boolean
             ;;; GIVEN: the names of two competitors and a list of outcomes
             ;;; RETURNS: true if and only if one or more of the outcomes indicates
             ;;;     the first competitor has defeated or tied the second
             ;;; EXAMPLES:
             ;;;     (defeated? "A" "B" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => true
             ;;;
             ;;;     (defeated? "A" "C" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => false
             ;;;
             ;;;     (defeated? "B" "A" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => false
             ;;;
             ;;;     (defeated? "B" "C" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => true
             ;;;
             ;;;     (defeated? "C" "B" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => true
             ;;;
             ;;; outranks : Competitor OutcomeList -> CompetitorList
             ;;; GIVEN: the name of a competitor and a list of outcomes
             ;;; RETURNS: a list of the competitors outranked by the given
             ;;;     competitor, in alphabetical order
             ;;; NOTE: it is possible for a competitor to outrank itself
             ;;; EXAMPLES:
             ;;;     (outranks "A" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => (list "B" "C")
             ;;;
             ;;;     (outranks "B" (list (defeated "A" "B") (defeated "B" "A")))
             ;;;  => (list "A" "B")
             ;;;
             ;;;     (outranks "C" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => (list "B" "C")
             ;;;
             ;;; outranked-by : Competitor OutcomeList -> CompetitorList
             ;;; GIVEN: the name of a competitor and a list of outcomes
             ;;; RETURNS: a list of the competitors that outrank the given
             ;;;     competitor, in alphabetical order
             ;;; NOTE: it is possible for a competitor to outrank itself
             ;;; EXAMPLES:
             ;;;     (outranked-by "A" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => (list)
             ;;;
             ;;;     (outranked-by "B" (list (defeated "A" "B") (defeated "B" "A")))
             ;;;  => (list "A" "B")
             ;;;
             ;;;     (outranked-by "C" (list (defeated "A" "B") (tie "B" "C")))
             ;;;  => (list "A" "B" "C")
   

   We will be doing automated testing of your solution, so be sure your solution is in the right place (set08/q1.rkt in your private cs5010f17/pdp-YOURUSERNAME repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after your require declarations:

             (check-location "08" "q1.rkt")
   

2. (Power Ranking)
   

   For this second problem, your job is to implement a power-ranking system based on the types and functions you defined in part 1.

   Given a list of outcomes, the non-losing percentage of a competitor A is the number of outcomes in which A defeats or ties another competitor divided by the number of outcomes that mention A.

   The power-ranking system you will implement has the following characteristics:

   1. If competitor A is outranked by fewer competitors than competitor B, then the power-ranking of A is higher than the power-ranking of B.
   2. If competitor A is outranked by the same number of competitors as competitor B, but competitor A outranks more competitors than competitor B, then the power-ranking of A is higher than the power-ranking of B.
   3. If competitor A is outranked by the same number of competitors as competitor B, and competitor A also outranks the same number of competitors as competitor B, and competitor A has a higher non-losing percentage than competitor B, then the power-ranking of A is higher than the power-ranking of B.
   4. If competitor A is outranked by the same number of competitors as competitor B, and competitor A also outranks the same number of competitors as competitor B, and competitor A has the same non-losing percentage as competitor B, and Racket's string<? function considers the name of competitor A to be less than the name of competitor B, then the power-ranking of A is higher than the power-ranking of B.

   You are to deliver a file named q2.rkt that defines all of the data types from part 1, defines and provides all 5 of the functions specified in part 1 above, and also defines and provides the power-ranking function specified below (so you will provide 6 functions in all). As in part 1, you are to give halting measures for all functions that may call themselves directly or indirectly.

             ;;; power-ranking : OutcomeList -> CompetitorList
             ;;; GIVEN: a list of outcomes
             ;;; RETURNS: a list of all competitors mentioned by one or more
             ;;;     of the outcomes, without repetitions, with competitor A
             ;;;     coming before competitor B in the list if and only if
             ;;;     the power-ranking of A is higher than the power ranking
             ;;;     of B.
             ;;; EXAMPLE:
             ;;;     (power-ranking
             ;;;      (list (defeated "A" "D")
             ;;;            (defeated "A" "E")
             ;;;            (defeated "C" "B")
             ;;;            (defeated "C" "F")
             ;;;            (tie "D" "B")
             ;;;            (defeated "F" "E")))
             ;;;  => (list "C"   ; outranked by 0, outranks 4
             ;;;           "A"   ; outranked by 0, outranks 3
             ;;;           "F"   ; outranked by 1
             ;;;           "E"   ; outranked by 3
             ;;;           "B"   ; outranked by 4, outranks 12, 50%
             ;;;           "D")  ; outranked by 4, outranks 12, 50%
   

   Instead of copying most of your q1.rkt file into q2.rkt, we suggest you have your q2.rkt file require your q1.rkt file. Remember, however, that your q2.rkt file must still provide all 6 functions.

   Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (set08/q2.rkt in your private cs5010f17/pdp-YOURUSERNAME repository), and that it provides all of the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after your require declarations:

             (check-location "08" "q2.rkt")