The Grid

In Project 1, the Grid type was represented using a list of lists to represent the cells. This representation makes testing the neighbors of a cell for infection expensive, since list-ref is not a constant-time operation. For Project 2, we are going to change the representation of grids to use immutable vectors to represent the cells.

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).

;; A (Coord r c) is the index of a cell in row r, column c
;;
(define-struct Coord
  ([r : Integer]
   [c : Integer]))

;; A (Grid nr nc cells) represents a grid with nr rows of nc columns
;; each.  The cells component is a flat vector of cells in row-major
;; order, where the cell at (Coord r c) has index (+ (* r ncols) c).
;;
(define-struct (Grid A)
  ([nrows : Natural]
   [ncols : Natural]
   [cells : (Vectorof A)]))

You will notice that we replace the list-of-lists representation of the grid from Project 1 with a flat vector of cells. This flat representation is essentially a concatenation of the rows. Before starting the project, you should review the discussion about vectors in the Notes on Typed Racket that is available from the class Canvas page. Also note that we are using immutable vectors; your code should not use operations like vector-set! that destructively modify the vectors.

Neighbors

The supplied code includes an implementation of the neighbors function that you implemented for Project 1. If you wish, you may replace our implementation with your own.

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. The grid operations for Project 2 are basically the same as for Project 1, although their implementations will be different.

Conversion Between Indices and Coordinates

With the flat-vector representation of the grid, we need some helper functions for mapping back and forth between the index of a cell in the cells vector and its coordinate in the two-dimensional view of the grid. The formula for converting from a Coord value to an index was given above; to convert from an index to a Coord, one divides (using the quotient function) the index by the number of columns to get the row and take the remainder (using either remainder or modulo) to determine the column.

You should define the following two helper functions (note that these functions are not exported from the grid.rkt module):

(: index->coord : Integer -> Integer -> Coord)
;; given the number of columns in the grid,
;; convert an index in the cells vector to a Coord

(: coord->index : Integer -> Coord -> Integer)
;; given the number of columns in the grid,
;; convert a Coord to a vector index

These functions are curried, which means that the can be partially applied to the number of columns in the grid to get a function for doing the conversion.

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-cells

The grid-cells function returns the cells of the grid as a list of lists (i.e., a list of rows, where each row is a list of cells). The primarly purpose of this function is to aid writing check-expect tests for the later modules in the project, so we provide an implementation.

(: grid-cells : (All (A) (Grid A) -> (Listof (Listof A))))
;; return the cells of the grid in list-of-list format
(define (grid-cells grid)
  (match grid
    [(Grid nr nc cells)
     (local
       {(: cell : Integer Integer -> A)
        ;; get the contents of the cell at row r, column c
        (define (cell r c) (vector-ref cells (+ (* r nc) c)))
        (: gather-rows : Integer (Listof (Listof A)) -> (Listof (Listof A)))
        ;; gather the rows by traversing the grid from bottom to top
        (define (gather-rows r rows)
          (if (< r 0)
              rows
              (local
                {(: gather-cells : Integer (Listof A) -> (Listof A))
                 ;; gather the cells of row r from right to left
                 (define (gather-cells c cells)
                   (if (< c 0)
                       cells
                       (gather-cells (- c 1) (cons (cell r c) cells))))}
                (gather-rows (- r 1) (cons (gather-cells (- nc 1) '()) rows)))))}
       (gather-rows (- nr 1) '()))]))

(check-expect
 (grid-cells (Grid 2 3 (vector 'A 'B 'C 'X 'Y 'Z)))
 (list
  (list 'A 'B 'C)
  (list 'X 'Y 'Z)))

Notice that we iterate right-to-left (and bottom-to-top); we use this order because we are using cons to build the result.

Important

This function should not be used to implement the higher-order functions described below. Instead, your implementations should work directly on the vector representation of the grid.

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))

Note that this function should be constant time, since the underlying representation provides constant-time random access.

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-set : (All (A) (Grid A) Coord A -> (Grid A)))

Note that this function take time proportional to the number of cells in the grid, so it should not be used in the implementation of the higher-order grid functions below.

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 (we need the inst because the vector construct can produce either mutable or immutable vectors and, thus, the type checker gets confused):

(define test-grid : (Grid Boolean)
  ((inst Grid Boolean) 4 6
        (vector #f #f #f #t #f #f
                #f #t #t #f #f #f
                #f #f #f #f #t #f
                #f #f #f #f #f #f)))

Then, the expression

((draw-grid draw-bool-cell 20) test-grid)

should yield

draw example

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.

Tip

For the draw-grid function, you need to process the contents of a row in a separate iteration from processing the rows. You may find the implementation of grid-cells as useful template when thinking about the design of your function.

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])
         grid-cells
         grid-ref
         grid-set
         grid-map
         grid-map-with-coord
         grid-andmap
         grid-fold
         grid-fold-with-coord
         draw-grid)

These exports specify the public interface to the module. You should not extend these exports in any way.