CMSC 15100: Lab 4

This lab uses the language, "Beginning Student with List Abbreviations". Also load the "matrix.ss" teachpack.

In this lab, you will create a program for a word-search puzzle (like Boggle), which involves searching for words in a grid of characters. If you are not familiar with the concept, look at this for a few minutes. You are given a grid and a dictionary. A word is correctly spotted if (1) the word's path through the grid is contiguous and does not repeat cells, and (2) the word is in the dictionary. You will write a set of functions culminating in a method that takes a path through the grid and returns a score for the word traced by the path.

1. Setup

Copy and paste the code below into your definitions window. This defines the character grid and the dictionary.

(define grid (make-matrix 4 4 (list "A" "D" "E" "P" "E" "O" "P" "A" "K" "Z" "I" "F" "F" "T" "H" "I"))) grid (define dictionary (list "ADD" "ADO" "APE" "APED" "APP" "DEAF" "DOE" "DOZE" "FAITH" "FIT" "HIP" "HIT" "HOP" "HOPE" "ODE" "PAP" "PEA" "PED" "PEP" "PIT" "PITH" "POD" "POKE" "POKED" "TIP" "TOP" "ZED" "ZIP" "ZIT"))

Running the program will bring up a visualization of the character grid, which should look like this:

Now define a datatype, cell which denotes a position on the character grid. The type should have two number fields, row and col. Numbering on the grid starts from zero. To indicate the cell on the row 1, column 2 (in this case, corresponding to the letter "P"), I would type (make-cell 1 2).

2. Validity of a path

The user's input is a path, which is a list of cells. Assume the input is the list (list (make-cell i₁ j₁) (make-cell i₂ j₂) ... (make-cell i_n j_n)). The "contiguity" check must first be performed; that is, for all k<n, '(i_k j_k) should be adjacent to '(i_k+1 j_k+1).The second condition is that a path must not contain loops; in other words, it must not contain repeated cells. Implement these checks by following these three steps --

2.1. Adjacency

Define a function adjacent?: cell cell -> boolean, which takes two cells, representing (row, column) positions, and returns true if one of them is horizontally, vertically, or diagonally adjacent to the other, in any direction. For example, (adjacent? (make-cell 0 1) (make-cell 1 2)) is true, but (adjacent? (make-cell 0 1) (make-cell 2 3)) is false.

2.2 Contiguity

Define a function contiguous?: list -> boolean, which takes a path -- represented by a list of cells -- and returns true if it is contiguous path, and false if not. A contiguous path is one which moves through adjacent cells at every step. Make use of recursion and adjacent? in your definition. Sample test cases:

(contiguous? (list (make-cell 1 3) (make-cell 1 2) (make-cell 0 2))) evaluates to true.
(contiguous? (list (make-cell 3 1) (make-cell 1 1) (make-cell 1 2))) evaluates to false.

2.3. Looplessness

Define a function hasnoloops? that takes a path and makes sure it does not contain repeated cells. You may use the built-in member function to check if a cell is in a list of cells.

For example:

(hasnoloops? (list (make-cell 1 3) (make-cell 1 2) (make-cell 0 2))) evaluates to true.
(hasnoloops? (list (make-cell 1 3) (make-cell 1 2) (make-cell 1 3))) evaluates to false.

3. Validity of a word

3.1. Converting a path to a word

The word corresponding to a path (list (make-cell i₁ j₁) (make-cell i₂ j₂) ... (make-cell i_n j_n)) is the string formed by concatenating the characters in the grid at each cell in order. Write a function path2word: list -> string which takes a path and returns the corresponding word. (You may assume that the path entered does not contain any positions outside the grid -- that is, all i, j are between 0 and 3.) You will need to make use of these two built-in methods:

matrix-ref. Calling (matrix-ref grid i j) retrieves the character in position (i, j) of the grid. For example, (matrix-ref grid 2 1) is "Z".
string-append. Calling (string-append s1 s2 ... sn) builds a word by concatenating the strings s1, s2, ... sn. For example, (string-append "F" "IT") gives "FIT".

Test that

(path2word (list (make-cell 1 3) (make-cell 1 2) (make-cell 0 2))) evaluates to "APE".
(path2word (list (make-cell 2 3) (make-cell 2 2) (make-cell 3 1))) evaluates to "FIT".
(path2word (list (make-cell 3 1) (make-cell 1 1) (make-cell 1 2))) evaluates to "TOP".

etc.

3.2. Checking if a word is in the dictionary

Write a function indict?: string list -> boolean which checks if an input word is in the dictionary. Use the operation equal? to check whether two strings are equal.

Test cases:

(indict? "APE" dictionary) evaluates to true
(indict? "AEK" dictionary) evaluates to false.
(indict? "ZIT" dictionary) evaluates to true.

3.3. Checking that a path constitutes a valid word

Now write a function evalpath: list -> string which takes a path as input. If the path is contiguous without repeated cells, and the word corresponding to the path is in the dictionary, return the word. If any of these conditions are false, return the empty string "". For example,

> (evalpath (list (make-cell 1 3) (make-cell 1 2) (make-cell 0 2))) "APE" > (evalpath (list (make-cell 0 0) (make-cell 0 1) (make-cell 0 2))) "" > (evalpath (list (make-cell 0 1) (make-cell 1 1) (make-cell 2 1) (make-cell 0 2))) "" > (evalpath (list (make-cell 0 0) (make-cell 0 1) (make-cell 0 1))) ""

You will need to make use of contiguous?, hasnoloops?, path2word and indict? in your definiton.

4. Scoring

Now that we have a mechanism to validate the path and check whether a word is correctly found, the next step is to add a scoring function.

4.1. Character scores

Copy and paste this into your definitions window:

(define letterscores (list (list #\A 1) (list #\D 1) (list #\E 1) (list #\F 2) (list #\H 2) (list #\I 1) (list #\K 3) (list #\O 2) (list #\P 1) (list #\T 1) (list #\Z 3)))

letterscores is a list that assigns a score to each character of the alphabet. Write a function getscore: list character -> number which takes as input a list (in particular, letterscores) and a character, and returns the score of the character according to the list. The function should return 0 if the character is not present in the list. Use the operation char=? to compare two characters.

Test cases:
(getscore letterscores #\K) gives 3.
(getscore letterscores #\Y) gives 0.

4.2. Word scores

We will define the score of a word to be the sum of the scores given to its constituent characters.

Write a function charlistscore: list -> number which takes a list of characters and returns the sum of their scores. If the list is empty, return 0. For example, (charlistscore (list #\F #\I #\T)) gives 4.

4.3. Putting it all together: path scores

Finally, write a function pathscore: list -> number. This function takes a path and finds the score of the corresponding word. Make use of your previous function evalpath. You will also need the built-in function string->list, which breaks up a word into a list of its characters -- for example, (string->list "APE") evaluates to (list #\A #\P #\E). The definition of pathscore should be very short. Some test cases:

(pathscore (list (make-cell 1 3) (make-cell 1 2) (make-cell 0 2) (make-cell 0 1))) gives 4.
(pathscore (list (make-cell 0 0) (make-cell 1 2) (make-cell 0 2))) gives 0.
(pathscore (list (make-cell 2 0) (make-cell 1 1) (make-cell 2 1))) gives 0.
(pathscore (list (make-cell 0 1) (make-cell 1 1) (make-cell 2 1) (make-cell 1 0))) gives 7.

5. Optional, for extra credit: creating an image representation of the puzzle

This section guides you in creating an image of the character grid with the path marked and the score displayed, like this:

Complete as much as you can...

Submit

Make sure you have written the contract, purpose and tests for all the functions that you write. If you do the extra credit section, write the code in the same file as the main lab. Include your name and userid as a comment at the top. Optionally, also include your feedback on the lab, and comments/suggestions. Use the handin button to submit your work.