Need someone good expert in scheme programming

Assignment 5

Copying answers directly from the textbook gets 0 points. Answer the question in

your own words and hand-in your assignment before 12/22 23:59:59.

Domino Loops in 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 (𝑁 + 1)(𝑁 + 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.

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 can implement a more efficient solution for extra credit. Note that the

number of permutations of a double-N domino set is ((𝑁 + 1)(𝑁 + 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.

Requirements

You must begin with the code shown above. These three sub-functions will be tested

individually, giving partial credit for the ones that work correctly:

1. (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). Order doesn’t matter.

(dominoes 2) ==> ((2 . 2) (2 . 1) (2 . 0) (1 . 1) (1 . 0) (0 . 0))

2. (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.

3. (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.

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.

⚫ Output function may not be needed. Returning the result list is sufficient.

⚫ Defining any helper function(list) is allowed, but modifying the interface of three

functions isn’t.

⚫ Make sure your scheme program is workable in different PC. (Test it on your

friend’s PC) 10 points deducted for the inexecutable program.