Harvey Mudd College
Computer Science 60
Assignment 3, Due Monday, September 21, by 11:59pm

Graphical programming

Although CS 60 will introduce graphics in the coming weeks, this week's "graphical" programming refers to mathematical graphs, i.e., connection networks of nodes and edges that might represent human relationships, physical links, or hierarchical structures.

This week's three (out four options) problems are fewer than previous assignments, but each of these has a component of open-ended algorithm design, as well as reinforcement of this week's themes. Feel free to seek out help in discussions with other students, the CS 60 tutors, or to chat with me any time about any of these problems... . Good luck!

Submitting your work

For this assignment, you should type (and test!) your programs in a files named


You should submit your file in the usual way at the CS 60 submissions site. Keep in mind that you may submit multple times -- only the final submission before the deadline will be graded.

Design, commenting, and formatting

As with the previous two assignments, design and formatting will account for roughly a quarter of the credit for each function or program you complete. The commenting and code-formating guidelines carry over from homework #2. Here, however, there will also be consideration for algorithm design and modularity:

The graders will keep an eye out for your overall design with these guidelines in mind.

Testing

A few tests are provided below, but as these problems become larger, it becomes increasingly important to create and use additional tests of your own -- not only for top-level functions, but for helper functions, as well.  For problems 2-4 you should include these additional tests in your submitted file (you'll be graded on them).  Be sure to test problem 1 too!

The Problems

Part 1: Complete problems 1 and 2 individually in your hw3part1.scm file

Problem 1:    twenty-questions


20 Questions!
This problem asks you to implement the game of 20 questions.

First, to give you a sense of the game of 20 questions, here is an example of a run in Scheme. The user's input is in blue 
> (twenty-questions)

Is it bigger than a breadbox? (y/n) y
Is it a computer scientist? (y/n) n
What was it? a chemist
What's a question distinguishing a computer scientist and a chemist? Do you titrate?
And what's the answer for a chemist? (y/n) y
Play again? (y/n) y
Is it bigger than a breadbox? (y/n) y
Does you titrate? (y/n) y
Is it a chemist? (y/n) n
What was it? Wally Wart
What's a question distinguishing a chemist and Wally Wart? Is it concrete?
And what's the answer for Wally Wart? (y/n) y
Play again? (y/n) y
Is it bigger than a breadbox? (y/n) y
Do you titrate? (y/n) y
Is it concrete? (y/n) y
Is it Wally Wart? (y/n) y
I got it!
Play again? (y/n) n

Features

Your twenty questions should allow users to

Many of the questions can be yes/no questions. You are welcome to use the askyn function below to handle those. In particular, your game should always allow y to represent a "yes" answer. Also, n should always be allowed to represent a "no" answer. This will make the submissions simpler for the graders to try out!

Representation

For consistency, your game should always start with the question Is it bigger than a breadbox? and should have the objects spam and a computer scientists available as guesses if the user answers the initial question with a n or a y, respectively.

You are welcome to represent the game's data however you like. However as a guide to one possible representation (the one used for the example program demoed in class), you might consider a tree in which internal nodes are questions and leaf nodes are objects, e.g., 

(define initialTree '("Is it bigger than a breadbox?" "spam" "a computer scientist"))
Strings are likely the simplest data structure for questions and objects. The function string-append, along with the other string functions noted on the Scheme reference card may be of use.

Possible decomposition

As with the data structure, the choice here is yours. As one possible suggestion to get you started (if you'd like), consider the decomposition of the demo version, which included

  1. A function named (tq-once tree) that plays the game of 20 questions, as described above, and then returns the augmented tree after one complete round of the game. If the computer guesses the object correctly, it would simply return the same tree it was originally passed.
  2. A function named (tq-continuer tree) that calls tq-once in order to run one round of the game. When finished, this function should ask if the user wants to play again and take the appropriate action.
  3. A function named (twenty-questions) that calls tq-container using the default tree named initialTree.

Input:

Here are two functions demonstrating how to use (read-line) to grab a line of user input. The first tests the resulting value (which will be a string). The second is a more general-purpose question-asking function: 

(define (askyn Q) ;; asks a yes/no question Q and returns #t or #f
 (begin
 (display Q)
 (display " (y/n) ")
 (if (equal? "y" (read-line))
 #t
 #f)
 ))


(define (ask Q)
 (begin
 (display Q)
 (read-line)))

Hints:    (feel free to disregard!)

The binary tree used in this game is slightly different than the numeric ones used in last week's HW. In this case, the leaves are not empty, but contain possible objects; internal nodes contain questions. After the first round in the example above, the tree's structure would be 

("Is it bigger than a breadbox?" "spam" ("Do you titrate?" "a computer scientist" "a chemist"))
Note that, by our convention, "no" traverses to the left and "yes" to the right.

A crucial facet of the game is that (tq-once tree) must return a valid twenty-questions tree from all of the different conditional branches it handles. That returned tree will be augmented by an additional question and an additional object if the previous run did not guess the object correctly. If it did guess the object correctly, the original tree will be returned.

The tq-continuer function will want to give a name to the value of that new tree (using let is one way to do this). It will then ask the user whether they would like to continue and use that new tree as appropriate.

As with any large functional program, the key is to break up the tasks into manageable chunks, write functions that handle those pieces, and then compose them into a solution. Write a number of helper functions that will keep your code succinct and straightforward.


Problem 2:    make-change

This problem follows in the footsteps of the current president's ubiquitous calls for change! Here, your task is to write the computational engine required of the kinds of change-making devices found at supermarkets (or vending machines, for that matter):

The idea is this: (make-change amt CoinList) takes in a positive integer amt and a list of positive integers CoinList. The function should then return a list of all the ways that the change amt can be made using coin-value combinations from CoinList. Your function should return each coin-value combination in sorted order. In addition, the function should not return identical coin-value combinations more than once. You're welcome to use the uniquify function that we wrote in class to help with this, perhaps in tandem with other functions. The "weirdo" approach is a friend in this case!

Another hint, entirely optional of course, is that you might consider using pset, the powerset function we wrote in class. In a sense, it provides a general-purpose "weirdo" approach to problems... .

Below are some example runs. We will test your outputs against the expected values by using the testPrep function and its supporting cast (also below): 

(test (testPrep (make-change 15 '(1 10 1 2 4 6 6))) '((1 4 10) (1 2 6 6)) )
(test (testPrep (make-change 16 '(1 10 1 2 4 6 6))) '((6 10) (2 4 10) (4 6 6) (1 1 4 10) (1 1 2 6 6)) )


Here are testPrep and the other helper functions we will use to test your make-change function: 
(define (listLess L1 L2)
 (cond
 [ (and (null? L1) (null? L2)) #f ]
 [ (< (length L1) (length L2)) #t ]
 [ (> (length L1) (length L2)) #f ]
 [ (< (first L1) (first L2)) #t ]
 [ (< (first L2) (first L1)) #f ]
 [ else (listLess (rest L1) (rest L2))]
 ))

(define (sortL LoL) (sort LoL listLess))

(define (uniquify L)
 (cond
 [ (null? L) L ]
 [ (member (first L) (rest L)) (uniquify (rest L)) ]
 [ else (cons (first L) (uniquify (rest L))) ]
 ))

(define (testPrep makeChangeList)
 (sortL (uniquify (map (lambda (L) (sort L <)) makeChangeList))))

Part 2: Complete EITHER problem 3 OR problem 4, individually or with a partner, in your hw3part1.scm file.  

Completing both problems is worth up to +20% extra credit.

Problem 3:    min-dist and min-path

Write a function (min-dist a b G), which takes in two nodes a and b and a directed, positively-weighted graph G. Graph G will be represented as a list of edges: (src dst weight). See Gt, below, for an example.

Your min-dist should return the smallest distance that is required to travel from a to b through graph G. Every node should be considered 0.0 away from itself. However, if there is no path from a to b in G, your function should return the valid Scheme value +inf.0, which represents positive, floating point infinity. For example, 

(define Gt '((e b 100) (a b 25) (e a 42) (a c 7) (a d 13) (a e 15)
 (b c 10) (b d 5) (d e 2) (b e 100) (c d 1) (c e 7)) )

(test (min-dist 'a 'e Gt) 10.0)
(test (min-dist 'e 'b Gt) 67.0)
(test (min-dist 'd 'd Gt) 0.0)
(test (min-dist 'f 'a Gt) +inf.0)

To help sanity-check your tests, here is a picture of Gt:

Feel free, also, to use a subgraph (as these algorithms can be very slow!)

Hints: Consider using weirdo analysis for this problem in a manner similar to the reachable example we considered in class. That file is linked here and from the top-level assignment page. In fact, you might start with that reach code and consider how to change the return values appropriately from booleans to numeric quantities... !

Follow up your min-dist function with another function, (min-path a b G), whose inputs are the same as min-dist's. Your min-path function, on the other hand, should return a list whose first element is the minimum distance from a to b in G and whose remaining elements list the nodes, in order, on the minimum path from a to b. The minimum path from a to itself is simply a. If no minimum path exists, omit the nodes. If more than one equal-cost minimum path exists, your function may return any one of them. (We will only test your code on goals and graphs offering a single minimum path.) As examples: 

(test (min-path 'a 'e Gt) '(10.0 a c d e))
(test (min-path 'e 'b Gt) '(67.0 e a b))
(test (min-path 'd 'd Gt) '(0.0 d))
(test (min-path 'a 'z Gt) '(+inf.0)) ;; z's not there!
in which Gt is the same graph used in testing min-dist.

Problem 4:    min-road-cut

Preventing spam wars!

The mayors of a number of neighboring cities have been noticing some conflicts brewing between their cities over the rumor of an upcoming Spam shortage. Cities with small Spam reserves have been making plans to raid the stores of those with larger reserves, should it come to that.

The mayors, wishing to avoid all conflicts over canned meat products, have decided that if two cities are about to go to war, the mayors will cut off all access from one city to another by destroying all roads that would allow travel between the two towns (perhaps by way of other towns). They want to do the minimal damage to their infrastructure, so they have contacted Napquest, a popular map-information company, to help them determine the minimum number of roads that must be destroyed in order to fully separate the two cities. Napquest has hired you to help with this problem.

Thus, for this problem you should write a function (min-road-cut a b G), whose inputs are identical to those of min-dist and min-path from problem 2, except that G does not include path costs (you can imagine all paths having a cost of 1). In addition, the edges in G should be interpreted as undirected: a road from a to b will also allow travel from b to a. Order does not matter.

Your min-road-cut should return the value of the smallest number of roads that must be destroyed to successfully separate the two cities. Remember that roads are undirected and that it is not sufficient simply to cut the road between a and b (if one exists in the first place) because there might be another way to get there, e.g., going through c, for example.

The solution to this problem is not long, but your efforts will benefit from prior planning, so make sure you sit down and map out an algorithm before you start coding! This planning is extremely important to avoid confusion and frustration. Weirdo analysis is a good way to approach this problem, but you will need to deal with a number of subproblems (e.g., determining when you are done).

The program need not be fast, but it must compute the right answer. For full credit, keep your code concise.

Hints: since this problem uses reach, but it interprets its graphs as undirected, it will be helpful to write - and use - an undirected version of reachable, e.g., (ureach a b G).

Another hint, similar to problem #2, is that you might consider using pset, the powerset function we wrote in class. In a sense, it provides a general-purpose "weirdo" approach to problems... .

Here are some example runs: 

(define Gx '( (a b) (b c) (a c) (a d) (b d) ) )
(define Gy '( (a b) (b c) (a c) (a d) (c d) ) )

(test (min-road-cut 'a 'b Gx) 3)
(test (min-road-cut 'a 'b Gy) 2)