Homework 5b

MUST BE DONE WITH YOUR PARTNER

MUST USE CHECKED-SIGNATURES!

Due Date Thurs at 9:00pm (Week 5)

Purpose Continue working on course project

Exercises

Recall the game, Shannon, that you started working on in HW2A.

In this game, players use gates from Boolean logic (AND, OR, NOT) and to solve puzzles on space-constrained grids.

The puzzles have the following form: a grid has a fixed number of input & output wires, and a Boolean function that is the goal of the game. To play the game, players add gates & connective plates in order to implement the goal function. Given infinite space (and in 3D), this would be relatively easy, but the space and planar constraints can make it possible to create somewhat tricky puzzles.

For example, a simple example grid might be:

Where the black letters are input wires, the red are output. If the function was:

(define (f x y)

(not x))

Then the puzzle could be solved by connecting the input to output with conductive plates (which allow boolean values to flow across them in any non-diagonal direction) and a single NOT gate that is oriented down, e.g., as follows:

Exercise 1 In HW2a, you designed data to represent a single "Cell" in the above board (please copy that definition into your file). In the game, you may want to represent a multi-set of Cells. One way of doing so is with a List, but lists are ordered, whereas multi-sets are not. A multi-set, for review, is an unordered collection of elements that may include duplicates (whereas a set is an unordered collection with no duplicates). In this exercise, you should design a function "cell-set-equal?" that compares two lists of "Cell"s, but using (multi-)set equality; i.e., the order of the "Cell"s should not matter.

Exercise 2 Next, we want you to design data to represent a "Grid" of "Cells". The grid should be two-dimensional, which means that every "Cell" can be addressed with a "Posn" (for its X and Y coordinate). You should re-use your prior definition for "Cell". There are multiple ways of designing this data, but whatever you do will impact the next several functions.

Exercise 3 Now, design a function, "grid->image", that turns a "Grid" into an image, suitable for displaying to a player of the game. You should re-use the "cell->image" function you designed previously.

Exercise 4 Implement "get-cell", which takes a "Grid" and a "Posn" and returns the "Cell" at that position. If the "Posn" is not in the "Grid", return "#f".

Exercise 5 Implement "set-cell", which takes a "Grid", a "Posn" (i.e., a "(make-posn Number Number)"), and a new "Cell", and returns a new "Grid" where the given "Posn" has been replaced with the new "Cell". If the "Posn" is not in the "Grid", return "#f".

Exercise 6 In a "Grid", each "Cell" has up to four cardinal neighbors: i.e., "Cell"s that are immediately to the north, east, west, or south (so _not_ including diagonally to the north-east, etc). "Cell"s along the edge or corners may have fewer than four. Implement "get-neighbors", which takes a "Grid" and a "Posn" and returns a list of the cardinal neighbors of the "Cell" at the given "Posn". If the "Posn" is not in the "Grid", return "#f".