►Fundamentals 1
▼Homeworks
6.6
    ← prev  up  next → 

Homework 10

home work!

Programming Language ISL+

Due Date: Monday March 30, 9pm

Purpose: To practice mutually recursive data; Project Phase I

The first assignment practices designing mutually recursive functions. Then we move on to Part I of the Project.

Exercise 1 Revisit the File System data definitions from Lecture 28 (Monday, March 23) and copy them into your homework file. You need the definitions of File, Dir, and Entry. You should also copy the examples (you may reuse them).

  • In class we already designed a function that simulates one of the UNIX OS utilities: du. Here is another one: Design a function find that takes a Dir and a predicate on files (i.e., a function taking a File and returning a Boolean). The function finds all occurrences of files satisfying the given predicate under that directory and returns the result as a list of Strings. Each String should be the path to the file in the directory, with sub-directories separated by "/".

    For instance, consider directory D-H and the file with name "2500-grades.xls". Wouldn’t it be nice to find that file? Given the D-H directory and a suitable predicate (that checks whether a file’s name is "2500-grades.xls"), your find function should return

    (list "Home/Wahl/Course/2500-grades.xls")

    indicating that there is exactly one file named "2500-grades.xls" in D-H, and it can be found by following the path your function returned.

    Create some tests that find files by name, tests that find executable files, and tests that find writeable files. Make sure to include tests where no file is found, and where more than one file is found.

  • Realizing that, most of the time, we want to find files by name, quickly write an instance of find called find-by-name that takes a Dir and a String and finds files by that name. This is very short!

We are now switching to the Project, which is to implement a (pretty complete) version of the Mine Sweeper (MS) game. If necessary, you can read details about it at https://en.wikipedia.org/wiki/Minesweeper_(video_game), but here are the basics:

Input to the game are two natural numbers n and m such that m <= n2. MS is played on an n x n board of cells, each of which may be mined, i.e. occupied by a mine; there is a total of m mines on the board. Cells are also either hidden, visible, or flagged. Initially all cells are hidden. The goal of the game is to unhide all mine-free cells, and to flag all mined cells with a special symbol. Once all mine-free cells are visible and all mined cells are flagged (no hidden cells remain), you win. If you ever unhide a mined cell, you lose.

So far this is just a guessing game. To make it more interesting, mine-free cells contain a number in the range 0..8, namely the number of mines in neighboring cells (N, NE, E, SE, S, SW, W, NW). For instance, for a cell containing 0, we know that all neighboring cells are also mine-free. This number is, however, only visible if the cell is visible, i.e. once you unhide it. Also note that cells near an edge of the board have fewer than 8 neighbors (there is no "wrap-around").

There are many online sites for playing the game, e.g. http://minesweeperonline.com.

We split the implementation of the MS game into three parts. In Part I (today), we design the appropriate data representation, and set up the World that let’s us play this game.

Exercise 2 Design data Content for storing the content of a cell, which is either a natural number (representing the number of surrounding mines), or a representation of a mine. Then design data Cell for a cell of the board. A cell is essentially the content just defined, but a cell is also either hidden, visible, or flagged. Think carefully about how to represent this information.

Make sure to follow the data design recipe for these (and all following) definitions. In particular, good examples are crucial for this (fairly complex) programming assignment.

Exercise 3 Design data Board to represent the MS board. There are several ways of doing this. We recommend that you represent the board as a list of rows, where each row is a list of cells; but thinking about alternatives never hurts.

Exercise 4 Finally, design data Game to represent the whole game. A game is essentially a board, but also has one additional bit of data. To explain this, we need to digress:

We will later use the mouse to play the game. The left mouse button is typically (e.g. when you play online) used to unhide a cell, the right mouse button to flag it (suspecting a mine underneath). But some mice come with only one button, and DrRacket in fact cannot distinguish left from right mouse buttons. Bummer!

We solve this problem by adding a Boolean-valued reveal? to Board, where value #t is interpreted to mean that mouse clicks unhide (normally done using a left-click), while #f is interpreted to mean that mouse clicks flag (normally done using a right-click). To simulate left and right mouse clicks, the player needs to first toggle the state of this Boolean, if necessary, and then click.

So a game has two parts, a board and a reveal?. Design it, and don’t forget to define some good examples of game states. For instance, make up a 3x3 board, plant some number of mines (3, say), and correctly fill out the remaining cells with numbers, as defined above.

Exercise 5 Now let’s set up the World program. The state of the world is a Game. We first discuss the initial state.

The eventual goal is to initialize the game with a board with m randomly placed mines, and appropriately filled-in number values for mine-free cells. Such a program with a random initial state has one big disadvantage during the development phase: it makes testing very hard, since errors, if any occur, will be impossible to reproduce. A general software design principle is to add a "development version" to such functions that starts from a given, rather than randomly generated, board.

To follow this principle, we will design two functions to launch the game. The first, called mine-sweeper-from, takes in a Game to start from (any dimension and any [legal] number of mines). The second, called mine-sweeper, instead takes in n and m and creates a "random" board. It then simply calls mine-sweeper-from, passing to it the game with the randomly generated board. We will implement the random board generation later; for now, simply call a function that builds a game with some fixed (non-random) n x n board with m mines. Note that inputs such that m > n2 should be rejected using an (informative!) error message.

The benefit of this strategy is that we need to set up big-bang only once: for the mine-sweeper-from function. Here is our wishlist: we need a to-draw function, and we need clauses to respond to mouse clicks (for unhiding and flagging), key presses (for toggling the mouse button interpretation), and to detect the end of the game. Set these up, and put in stubs for the drawing and mouse button handler functions, since we will not design them in this homework (the others are designed in the exercises below). A stub is a function with the same signature as the function we eventually want in its place, but does nothing. For instance, the mouse button handler stub simply returns the world unchanged. A lambda expression is a good way to write compact stubs that do nothing.

Exercise 6 Design the on-key handler function process-key. Remember that key presses are used to toggle the interpretation of the mouse button between "left" (used to unhide cells) and "right" (used to flag suspected mines). This information is stored in the reveal? Boolean variable of a Game; it should be toggled when the player presses the space key. All other keys should be ignored (to avoid accidental toggling), and no other parts of the Game should change.

Exercise 7 Design the stop-when handler function game-over?. The game is over when the winning condition holds, or the losing condition holds. The winning condition is that all mine-free cells are visible, and that all visible cells are mine-free. Whether you require that all mined cells are flagged (or whether they may remain hidden) is up to you (although it seems safer to require mined cells to be explicitly flagged). The losing condition is that the game board contains a visible mine, which means the player clicked on a mined cell.

    ← prev  up  next →