11:59PM Monday, March 3, 2008.

You may want to reuse the functions developed for Assignment 1. If so, be sure to cut-paste or copy them into the file, a2.scm, that you submit with this assignment.

After completing this assignment you will know how to:

You are to implement in Scheme a boolean function that determines if two shapes are distinct free polyominoes. Two free polyominoes are distinct as long as none is a translation, rotation, or reflection of another.

Although not authoritative, you may find the Wikipedia article, http://en.wikipedia.org/wiki/Polyomino, useful as a starting point for further study about polyominoes.

As with the last assignment, you will also need to define a student-name function. The function should be modeled like this:

(define (student-name) "Joe Student")

So that when you evaluate it behaves like this:

> (student-name)
"Joe Student"
> 

Of course, use you own name.

We will represent a polyomino as a set of coordinate pairs indicating the positions of the polyomino's squares. Each square of the polyomino is a 1x1 unit square, and it's convenient to think of each centered on an integral valued coordinate position. We represent a polyomino using a set of (x y) coordinate pairs, As in Assignment 1, a coordinate is represented using a list with exactly two elements. To represent a polyomino, we use a list of lists with the meaning of a set of coordinate pairs.

Here is an example of a "T" tetromino,

((1 1) (1 2) (1 3) (2 2))

Note that the list represents an unordered set of pairs, so this set of coordinates would be equivalent,

((2 2) (1 2) (1 1) (1 3))

This set of coordinates is different, but the polyomino shape is still a "T" translated by 10 along the x-axis.

((10 1) (10 2) (10 3) (11 2))

Implement the function, distinct-free? to accept two arguments, each of which is a polyomino represented by a list of coordinates as described above. Your function will return a boolean #t or #f indicating whether the two shapes are distinct free polyominoes.

Your program should handle any order polyomino including 0-ominoes, 1-ominoes, dominoes, triominoes, etc. There is only one 0-omino, represented by the empty list. There are infinitely many representations of 1-ominoes. Here are a few,

((-5 4))
((0 0))
((1 1))

Since they are equivalent under translation, there is only one distinct-free monomino. Dominoes also have infinitely many representations, but there is only one distinct-free domino. In addition to translation we also must consider rotation for dominoes.

Things start to get interesting with triominoes. There are two distinct-free triominoes, an "L" shape and an "I" shape. Starting with tetrominoes, reflection becomes important, too. There are five distinct-free tetrominoes.

Here is a example mzscheme session showing how you program might run.

$ mzscheme
Welcome to MzScheme v370 [3m], Copyright (c) 2004-2007 PLT Scheme Inc.
> (load "a1.scm")
> (distinct-free? '((10 1) (10 2) (10 3) (11 2)) '((2 2) (1 2) (1 1) (1 3)))
#f
> (distinct-free? '((1 1) (1 2) (1 3) (1 4)) '((2 2) (1 2) (1 1) (1 3)))
#t
> (distinct-free? '((1 1)) '((4 4)))
#f
> (distinct-free? '() '())
#f
> (distinct-free? '((1 1) (1 2) (2 2) (2 3)) '((2 1) (1 2) (2 2) (1 3)))
#f
> (distinct-free? '((1 1) (1 2)) '((1 2) (2 2) (1 3)))
#t

Note that the first call compares two "T" tetrominoes. Since they only differ by translation they are not distinct, thus the function returns #f. The second call compares an "I" shape with a "T" shape and returns #t because they are distinct free polyominoes. The third call compares monominoes, which are trivially not distinct. The fourth call handles the boundary case for 0-ominoes, which are not distinct. The fifth call demonstrates equivalence under reflection. The sixth call compares a domino to a triomino and shows that your program should treat different order polyominoes as distinct-free.

Do not use any of Scheme's I/O functions. Neither distinct-free? nor student-name should generate output.

In developing your first Scheme program, you will want to save the entire program source in a single file, "a2.scm", that you can load. See the description of the driver program, below. This file must contain the definition of your scheme function and a definition of the student-name function. You will likely make use of helper functions, too. All function definitions should be contained in this single file.

Try entering these expressions at the Scheme prompt.

(distinct-free? '() '())
(distinct-free? '((1 1)) '((2 2)))
(distinct-free? '((1 1) (1 2) (1 3) (1 4)) '((1 1) (2 1) (3 1) (4 1)))
(distinct-free? '((1 1) (1 2) (2 2) (3 2)) '((2 1) (1 2) (2 2) (3 1)))

Be sure to name you function with a question mark. This,

distinct-free?

Not this,

distinct-free

Don't forget your student-name.

Submit via e-mail using a mime-encoded, zipped attachment. (Note, most e-mail client programs do mime-encoding automatically for you, but to create the zip file attachment, you will need to use zip utility. The zipped attachment must be named, a2.zip, which contains one file, a2.scm in the current directory (i.e., the top-level rooted directory of the zip archive).

To: martin@cs.sjsu.edu
Subject: A2