The Grid
The main data structure in this project is the Grid, which is a
rectangular array of cells. Unlike a normal rectangular grid, however,
we offset every-other row so that each cell has six neighbors.
Furthermore, we wrap the coordinate system of the grid so that cells
on the border have six neighbors. The following figure illustrates
the grid’s coordinate system:
Here we label each cell with its row and column index; the blue dashed circles represent the virtual neighbors of the border cells. For example, the cell at row 0, column 1 has the six neighbors with coordinates: \((3, 0)\), \((3, 1)\), \((0, 0)\), \((0, 2)\), \((1, 0)\), and \((1, 1)\).
The supplied grid.rkt file contains definitions for the
Coord struct type, which is used to represent coordinates
in the grid, and the Grid type constructor, which is used
to represent a grid of cells, where the cell type is left
unspecified (i.e., we use a type variable for it).
Neighbors
The Coord struct type is used to represent coordinates in a grid.
It is a pair of integers representing the row and column of a cell.
The main operation on coordinates is getting the six neighbors of
a cell. Because of the way that the coordinate system wraps at the
border of the grid, this operation necessarily involves a specific
grid. We use the following curried type for this operation:
(: neighbors : (All (A) (Grid A) -> Coord -> (Listof Coord)))In other words, if we apply this function to a grid, we get back
a function for computing the neighbors of a cell. To implement
coordinate wrapping, we use Racket’s modulo function; this function
is similar to the remainder function, but it always returns a
positive value.
The other complication in computing neighbors is that the coordinate offsets of the neighbors depends on whether the cell in question is on an odd or even row of the grid. The following figure shows the offsets for the two cases:
The neighbors should be returned in top-down left-to-right order.
For example, the neighbors of the cell at (Coord 0 1) in the
\(4 \times 6\) grid above is the list
(list (Coord 3 0) (Coord 3 1)
(Coord 0 0) (Coord 0 2)
(Coord 1 0) (Coord 1 1))Operations on Grids
The Grid type is abstract outside the grid.rkt module,
so all manipulation of grids will be done using the operations
defined in the module.
In particular, you should implement the following operations on grids:
build-grid
The first function to implement is used for generating grids. It takes the number of rows, the number of columns, and a function for generating cells, and creates a grid.
(: build-grid : (All (A) Natural Natural (Coord -> A) -> (Grid A)))A grid with no rows or columns is allowed, although such a grid is not very useful.
grid-ref
The grid-ref function returns the specified cell of the grid.
We assume that the coordinates are in range for the grid.
(: grid-ref : (All (A) (Grid A) Coord -> A))grid-set
The grid-set function replaces a single cell in a grid with a new
value. This operation is provided to make it easier to initialize
grids. As with the grid-ref function, we assume that the
coordinates are in range for the grid.
An implementation of this function is included in the seed code.
(: grid-ref : (All (A) (Grid A) Coord A -> (Grid A)))grid-map
The grid-map function computes a new grid by mapping a function
over a grid.
(: grid-map : (All (A B) (A -> B) (Grid A) -> (Grid B)))grid-map-with-coord
The grid-map-with-coord function is like the grid-map function,
but it also supplies the cell coordinate to the function being mapped
over the grid.
(: grid-map-with-coord : (All (A B) (Coord A -> B) (Grid A) -> (Grid B)))grid-andmap
The grid-andmap function tests a predicate across the cells of the
grid. If the predicate returns #t for all of the cells, then the
call to grid-andmap returns #t; otherwise it returns #f.
(: grid-andmap : (All (A) (A -> Boolean) (Grid A) -> Boolean))grid-fold
The grid-fold function folds an operation over the cells of the
grid in top-down, left-to-right order.
(: grid-fold : (All (A B) (A B -> B) B (Grid A) -> B))grid-fold-with-coord
The grid-fold-with-coord function is like the grid-fold function,
but it also supplies the cell coordinate to the function.
(: grid-fold-with-coord : (All (A B) (Coord A B -> B) B (Grid A) -> B))draw-grid
Lastly, we define an operation for drawing a grid. Since the actual type
of a grid’s cells is unspecified, the draw-grid function is polymorphic
in the cell type.
(: draw-grid : (All (A) (Coord A -> Image) Integer -> (Grid A) -> Image))The first argument to draw-grid is the function for drawing cells (these
will typically be circles shaded to illustrate their state). The second
argument is the radius of the circles, which is used to compute the
indentation width of the odd rows. The draw-grid function then returns
a function for drawing grids.
For example, assume we have a grid where the cells are Boolean values and we want to shade the true cells with gray. First we could define a cell drawing function:
(: draw-bool-cell : Coord Boolean -> Image)
;; draw a Boolean-valued cell with true cells shaded gray
(define (draw-bool-cell coord val)
(if val
(overlay (circle 20 "outline" "black")
(circle 20 "solid" "gray"))
(circle 20 "outline" "black")))Here we have hardwired a radius of 20. If we had the following Grid
value:
(define test-grid : (Grid Boolean)
(Grid 4 6
(list (list #f #f #f #t #f #f)
(list #f #t #t #f #f #f)
(list #f #f #f #f #t #f)
(list #f #f #f #f #f #f))))Then, the expression
((draw-grid draw-bool-cell 20) test-grid)should yield
Drawing a row of the grid can be done using Racket’s beside function
to build up the row image from the individual cell images.
Combining rows is a bit more complicated, since the odd rows are offset
to the right by the cell radius. You can implement that by putting
a white rectangle of the appropriate size at the left end of odd
rows and then using above/align to compose the rows into the final
image.
Hints
A number of these operations can be implemented by nested uses
of the list combinators (i.e., an outer iteration over
the rows of the grid and an inner iteration over the cells of
a row). You may also find it useful to implement helper functions
that are indexed versions of the list combinators. For example, a
version of map with the type
(: map-with-index : (All (A B) (Integer A -> B) (Listof A) -> (Listof B)))where the index of the list elements is passed into the function being mapped.
Exports
You will notice that at the end of the file there are already exports
for the Coord and Grid types.
Once you have written and tested the functions described above, you
should add the following export declarations following the type exports.
(provide neighbors
build-grid
(rename-out [Grid-nrows grid-nrows])
(rename-out [Grid-ncols grid-ncols])
(rename-out [Grid-cells grid-cells])
grid-ref
grid-set
grid-map
grid-map-with-coord
grid-andmap
grid-fold
grid-fold-with-coord
draw-grid)Notice that we make the selector functions for the Grid struct type
visible, but with slightly different names.
These exports specify the public interface to the module. You should not extend these exports in any way.