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.
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.)
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.)
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 () (use-modules (ice-9 readline)) (activate-readline)) (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.)
Create a fast version of domino-loops
that executes in
time proportional to the number of loops, not the number of
permutations.
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.
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.
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)
.
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).
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.
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)
.
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.