Need someone good expert in scheme programming
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 doublesix 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 doubletwo 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 doesnt matter. If your code prints the loops in a different order thats 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.05×1029 . Clearly you cant 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 doesnt 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 doesnt 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 isnt. Make sure your scheme program is workable in different PC. (Test it on your friends PC) 10 points deducted for the inexecutable program.
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 doesnt matter. If your code prints the loops in a different order
thats 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.05×1029. Clearly you cant 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 doesnt 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 doesnt 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 isnt.
Make sure your scheme program is workable in different PC. (Test it on your
friends PC) 10 points deducted for the inexecutable program.
