Homework 11
Due Date: Monday April 6, 9pm (AOE).
Purpose: To do exercises with Graphs; to continue the project discussed in Homework 10.
Important: Unlike homeworks 1–9, we cannot accept late submissions from Homework 10 onward (not with penalty, and not without penalty). The reason is that we need to publish the solutions soon after the due date, so the project can go on. Thus you must submit by 9pm AOE (which is already several hours after the previous 9pm EDT deadline). Do not miss this deadline!!
This assignment is to be completed with your homework partner. As before, it suffices for one partner to submit the homework via the handin server (whatever is submitted last counts for the pair).
You must submit a single .rkt file containing your responses to all exercises via the Handin Server. We do not accept email submissions.
You must use the programming language specified at the top of this page.
Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses, so revisit it before submitting each assignment.
Unless otherwise stated, for all programming problems you must provide (i) a signature, (ii) a purpose statement, (iii) sufficiently many check-expects (not for big-bang programs), and (iv) the code, in the language specified at the top of this page.
Be sure to look at the feedback for previous assignments before submitting, as we will be grading you more strictly on things we have pointed out before.
Exercise 1 Recently we have looked at several functions that return a list of data where we don’t care about the order or duplicity. For instance, the broken-links function is simply supposed to return the broken links (presumably so that someone can fix them). We don’t care whether a broken link is mentioned once or more than once, and we don’t care about the order they are reported. This causes trouble with our check-expects: they may fail simply because the expected and the actual answer differ in duplicity or order.
One way to fix this is to compare the expected and actual answer for equality up to duplicity and order. Mathematically speaking, this means to treat the two given lists as sets, and compare the sets for equality.
Design a function set=? that takes two [List-of X] and an equality predicate and returns true iff the two lists are equal up to duplicity and order. Create at least 5 meaningful check-expects.
Show how this function can be used to make the tests for the broken-links function designed in Lecture 31 (03/30) robust, as follows: Fill in the ... in the code below such that the first check-expect fails and the second passes:
(define TEST-WIKI (list ...)) ; ... is a [List-of Page] (define TEST-RESULT (list ...)) ; ... is a [List-of String] (check-expect (broken-links TEST-WIKI) TEST-RESULT) (check-expect ... (broken-links TEST-WIKI) ... TEST-RESULT ...) Use the constants PAGE-0 ... PAGE-4 and the page names ("Khoury", etc.) from the lecture (do not define new pages). Make the text that you fill in as small as possible. Check your results against the code presented in Lecture 31, but do not include this code in your submission. Instead, include only the above four lines, and put them in comments.
Exercise 2 Consider again the data designs of Page and Wiki from Lectures 30/31. Copy these designs into your homework file.
Design the function find-path that takes two strings t1 and t2 representing page names in a wiki, and a wiki. If there is a path (following links) from t1 to t2 in the wiki, your function should return such a path as a list of strings, representing the pages visited along the path. Note that the first string in the output must be t1, and the last string must be t2.
If there is no such path, your function should return the empty list.
The length of the list your function returns should equal the number of links followed along the path PLUS 1. For example, if t1 and t2 are equal, then (list t1) is one valid answer (the number of links followed is 0; the list has length 1).
Hint: You will need a helper function that finds a path from one of t1’s links to t2. This function and find-path will call each other mutually recursively. Also, you will likely need the eliminate function and perhaps other helper functions from Lectures 30/31.
We now return to the Minesweeper project. Recall, from Homework 10, our description of the game. As a reminder, you can play the game for free online here.
Last time we developed our data definitions and worked on the design of a few handler functions.
Exercise 3 Review the solution to HW 10 (posted on Piazza after the homework deadline) and compare it to your submission. If you have questions about the way we approached the assignment, speak to a staff member. Having a firm grasp of the code from the previous solution will be essential when completing this assignment. You may continue the project based on your own solution to HW 10, or based on the posted solution. We will grade HW 11 based on whatever we receive.
There is no credit for Exercise 3.
Exercise 4 Design the on-mouse handler. First, let’s identify all the actions that DO NOT have an effect on the game. These are the actions in the following list. Note that your program should still be able to "handle" these actions (that is, the game does not crash when you perform them).
The user performs a MouseEvent other than "button-down" (e.g. "drag").
The user clicks anywhere that is not on the grid.
The user clicks on a cell that is already visible on the grid.
The mouse is in reveal mode and the user clicks on a flagged cell on the grid.
Now let’s identify the actions that do have an effect on the game.
If the mouse is in reveal mode and the user clicks on a hidden cell, it should become a visible cell. If the cell is blank (the contents are zero), all the surrounding cells should become visible as well. Note that this has a flooding effect: if a neighboring cell is also blank then all of its neighboring cells should be visible, and so on.
If the mouse is in flag mode and the user clicks on a hidden cell, it should become a flagged cell.
If the mouse is in flag mode and the user clicks on a flagged cell, it should become a hidden cell (i.e., the flag is removed).
Note that we do not need to check if the cell is a mine before we reveal it. Our stop-when handler will take care of ending the game if a mined cell is revealed.
At this point, two components are missing to complete the game: placing random mines on the board, and of course the visualization (to-draw). For your testing at this stage, you can circumvent the first problem by using the mine-sweeper-from function, which takes in a fixed board. You could have one homework partner design a toy board (hidden from view for the other partner), and have the other partner play the game on this board.
To work around the missing visualization, you can call the on-mouse functions that you just defined "manually", i.e. from the interaction window, much like the check-expects you wrote for this function. The board after each change will be returned in its textual data representation. This work-around is painful, but better than nothing to try to run at least a small game instance. We will do the visualization in HW 12 as the final step, but we don’t want to postpone testing the whole game entirely to the end.
Exercise 5 Design a function generate-mine-board which takes as input two natural numbers n and m representing the side length of the board and the number of mines to place, resp. The function should output a board of size n x n with m mines placed randomly on it.
Hint: Use the random function to choose a position where to place a mine. If the board already has a mine at that position, then do not place a second mine in the same cell! There is an easy and elegant solution to this problem.