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
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
permutationsfunction 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.
you are required to use only the functional features of Scheme;
functions with an exclamation point in their names
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,
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")
Guilewill respond with
(), indicating that
loadreturned 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.
guile prints the
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
if you type something into
guile and it responds with an
...), that means the expression you entered is
incomplete (though correct so far), and
guile is waiting
for you to enter the rest of it.
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
;; -*- 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
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
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
(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
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
notand the use of
memberuseful. Our solution has a total of 9 rules (and uses
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
primitives. Put your program in one file.
Read the program into the interpreter using
If you change your program, read it
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.
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
As with the compiler assignments, use the TURN_IN script. Put your
write-up in a
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.