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 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.05×1029 . 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.
