## Project V

Due Date: Friday December 5th, noon

In this project you will write small programs in Scheme and in Prolog to familiarize you with the functional and logic programming paradigms.

Please note that this project has two parts.

## Scheme

Dominoes are small rectangular game tiles with dots embossed at both ends. They are used to play a variety of games involving patterns on a tabletop. A standard “double-six” domino set has 28 tiles: one for each possible pair of values from (0.0) to (6.6). In general, a “double-N” domino set would consist of (N+1)(N+2)/2 tiles.

One possible pattern to make with dominos is a loop, in which the tiles are laid in a circle, end-to-end, with identical numbers of spots on all adjacent ends. In a double-two domino set, with six tiles, `((0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2) (2 . 0))` is a domino loop.

You are to write a program in Scheme that prints all domino loops in a double-N domino set. Specifically, you are to flesh out the following program:

```    (define domino-loops (lambda (n)
(filter loop? (permutations (dominoes n)))))

(define filter (lambda (f L)
; return list of those elements in L which pass through filter f
(if (null? L) L
(let ((N (f (car L))))
(if (null? N) (filter f (cdr L))
(cons N (filter f (cdr L))))))))
```
The expression `(domino-loops 2)` would evaluate to
```(((2 . 2) (2 . 1) (1 . 1) (1 . 0) (0 . 0) (0 . 2))
((2 . 2) (2 . 0) (0 . 0) (0 . 1) (1 . 1) (1 . 2))
((2 . 1) (1 . 1) (1 . 0) (0 . 0) (0 . 2) (2 . 2))
((2 . 0) (0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2))
((1 . 2) (2 . 2) (2 . 0) (0 . 0) (0 . 1) (1 . 1))
((1 . 1) (1 . 2) (2 . 2) (2 . 0) (0 . 0) (0 . 1))
((1 . 1) (1 . 0) (0 . 0) (0 . 2) (2 . 2) (2 . 1))
((1 . 0) (0 . 0) (0 . 2) (2 . 2) (2 . 1) (1 . 1))
((0 . 2) (2 . 2) (2 . 1) (1 . 1) (1 . 0) (0 . 0))
((0 . 1) (1 . 1) (1 . 2) (2 . 2) (2 . 0) (0 . 0))
((0 . 0) (0 . 2) (2 . 2) (2 . 1) (1 . 1) (1 . 0))
((0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2) (2 . 0)))
```
(NB: order in this list doesn't matter. If your code prints the loops in a different order that's fine.) For larger values of N, where N is even, the number of loops grows exponentially. Note, however, that there are no domino loops when N is odd. (Proof left as an extra-credit exercise.)

There are many possible ways to write your program. Perhaps the simplest (but not the fastest) is to generate all permutations of a list of the tiles in the domino set, and check to see which are loops. You are required to adopt this approach, as described in more detail below. You are encouraged, for extra credit, to find a more efficient solution. Note that the number of permutations of a double-N domino set is ((N+1)(N+2)/2)!. For N=6 (the standard number), this is about 3.05x1029. Clearly you can't afford to construct a data structure of that size. My own (slow) solution to the assignment generates the double-2 loops quite quickly. It takes a couple minutes to determine that there are no double-3 loops. When asked for double-4 loops it thrashes. (For what it's worth, my version of `dominoes` is 10 lines long; `permutations` is 17 lines long; `loop?` is 16 lines long. More elegant versions may be possible. Your mileage may also vary depending on algorithm and on coding and indentation style.)

### Required (slow) solution

You must begin with the code shown above. We will test the three sub-functions individually, giving partial credit for the ones that work correctly:

• `(dominoes N)` — returns a list containing the (N+1)(N+2)/2 tiles in a double-N domino set, with each tile represented as a dotted pair (an improper list).
```    (dominoes 2) ==> ((2 . 2) (2 . 1) (2 . 0) (1 . 1) (1 . 0) (0 . 0))
```
(Order doesn't matter.)
• `(permutations L)` — given a list L as argument, generates all permutations of the elements of the list, and returns these as a list of lists.
```    (permutations '(a b c)) ==>
((a b c) (b a c) (b c a) (a c b) (c a b) (c b a))
```
(Again, order doesn't matter, though obviously all permutations must be present.) Hint: if you know all the permutations of a list of (N-1) items, you can create a permutation of N items by inserting the additional item somewhere into one of the shorter permutations: at the beginning, at the end, or in-between two other elements.
• `(loop? L)` — given a list L as argument, where the elements of L are dotted pairs, returns L if it is a domino loop; else returns the empty list. Note that the first and last dominoes in the list must match, just like the ones in the middle of the list. Also note that a straightforward implementation of your `permutations` function will give you lists that should be considered loops, but in which you need to “flip” certain dominoes in order to make all the ends match up. For example, in a double-2 domino set, ```((0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2) (0 . 2))``` should be considered a domino loop, even though the last tile needs to be flipped. In the example output above, dominoes have been flipped where appropriate to make the loops self-evident. You are not required to do the flips, but you can do them for extra credit. For the basic assignment, output such as ```((0 . 0) (0 . 1) (1 . 1) (1 . 2) (2 . 2) (0 . 2))``` is acceptable.

Important: you are required to use only the functional features of Scheme; functions with an exclamation point in their names (e.g. `set!`) and input/output mechanisms other than `load` and the regular read-eval-print loop are not allowed. (You may find imperative features useful for debugging. That's ok, but get them out of your code before you hand anything in.)

### Tools

We will be using the GNU Scheme interpreter, `guile`. When it starts up, it simply prints a prompt:

```    guile>
```
You can then enter expressions to be evaluated. You will want to keep your code in a file. If you name it `dominoes.sc`, you can then type
```    guile> (load "dominoes.sc")
```
`Guile` will respond with `()`, indicating that `load` returned an empty list, after which you'll be able to use functions defined in file ``dominoes.sc'' just as if you had defined them from the command line.

Note that `guile` prints the `guile>` prompt at the beginning of each line; you just type the parenthesized expression. Also note that you can re-load a modified file as often as you like; you don't have to quit `guile` and re-start it every time you fix a bug. To exit the interpreter, type control-D at the prompt.

if you type something into `guile` and it responds with an elipsis (`...`), that means the expression you entered is incomplete (though correct so far), and `guile` is waiting for you to enter the rest of it.

If `guile` falls into an infinite loop, or if you accidentally ask it to do something that's going to take exponential time, you can interrupt it with control-C.

`Guile` supports command completion and command-line editing, much as you may be used to in the shell. To enable this feature, put the following code in a file named `.guile` in your home directory:

```    ;; -*- scheme -*-
(cond
((equal? (getenv "TERM") "dumb")
;;; emacs
)
(#t
(catch
'misc-error
(lambda ()
(lambda (key . args)
#t))))
```
Don't worry if you don't understand how this works; just include it verbatim.

`Guile` can also be used inside `emacs`. To enable this, put the following code in the `.emacs` file in your home directory:

```    (setq scheme-program-name "guile")
(setq xscheme-process-command-line scheme-program-name)
```
Then type “M-x run-scheme RET” in `emacs`. For further information see the on-line documentation for Scheme mode in `emacs`.

For questions on Scheme itself, refer to the Fourth Revised Report on the Programming Language Scheme. Scheme has been standardized at version 5 (see ACM SIGPLAN Notices, Sept. 1998), but our version of `guile` is still R4.

Extensive resources, including a `guile` reference manual (which among other things documents the built-in debugger) is available at the `guile` home page. (Note: the navigation buttons for the reference manual are a little confusing. If clicking on an item doesn't get you what you expect, try the “next” button.)

### Extra Credit

Create a fast version of `domino-loops` that executes in time proportional to the number of loops, not the number of permutations.

## Prolog

There is a famous proven conjecture in graph theory that any map divided into countries can be colored with 4 colors such that no two adjacent countries have the same color. We'll call this the "no same colors share a border" rule. We are going to write a Prolog program that produces all such colorings using red, yellow, blue, and green., for the Atlantic Coast (NJ, NY, PA, VA, MD, DE, SC, NC, GA, FL), and New England (MA, NH, VT, ME, RI, CT) regions of the United States.

### Generate and Test

A standard paradigm for Prolog programs is called generate and test. This means that we write a Prolog program (i.e., a set of rules) that searches a space of possible solutions, generates a candidate solution, and then tests that this candidate has the right properties to be an acceptable solution of our problem (as we saw in the naive sorting example used in class). The backtracking execution of Prolog allows us to do this in a very simple, but not always efficient, fashion.

### Required (slow) solution

You should begin by encoding the adjacency relation among the US states mentioned above. Note that adjacency is a symmetric relation, which means if NJ is adjacent to NY, then NY is adjacent to NJ. You do not need two Prolog facts for each adjacency and should avoid this.

Write a coloring program, which if given a list of states, will return a valid coloring. A coloring is a list of state/color pairs. Use the naive approach of generating a coloring for an entire list of states and then checking that this coloring is valid for all adjacencies. Call this predicate `valid_coloring(Statelist, Coloring)`.

### Hints

You may find the use of `not` and the use of `member` useful. Our solution has a total of 9 rules (and uses `not` and `member`) in addition to the facts. Chapter 11 of the class text should provide a sufficient introduction to the language.

You will want to use the `consult` and `reconsult` primitives. Put your program in one file. Read the program into the interpreter using `consult`. If you change your program, read it again using `reconsult` (this will over-ride the earlier definitions of your rules).

### Sample Session

Here is a prolog session from a solution to the problem. Your solution should behave similarly.

` ?- valid_coloring([nj,ny,pa,md],C).`

`C = [(nj,red),(ny,yellow),(pa,blue),(md,red)];`

`C = [(nj,red),(ny,yellow),(pa,blue),(md,yellow)];`

If you continue to hit ; you will see more colorings. Note that due to the inefficiency of the naive algorithm, it make take a very long time to return a valid coloring for all the states encoded. A smart solution, however, should be able to return a valid coloring in reasonable time.

### Extra Credit

Write a smarter map coloring program that is more efficient than the naive approach. Here you should only color a state with a color, if you can show none of its neighbors has this color. Call this predicate `smart_coloring(Statelist, Coloring)`.

## DUE DATE:

Friday December 5th, noon.

As with the compiler assignments, use the TURN_IN script. Put your write-up in a `README.txt` or `README.pdf` file in the directory in which you run the script. Be sure to include a description of any features of your code that the TA might not immediately notice.