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.
Why Work with Us
Top Quality and Well-Researched Papers
We always make sure that writers follow all your instructions precisely. You can choose your academic level: high school, college/university or professional, and we will assign a writer who has a respective degree.
Professional and Experienced Academic Writers
We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.
Free Unlimited Revisions
If you think we missed something, send your order for a free revision. You have 10 days to submit the order for review after you have received the final document. You can do this yourself after logging into your personal account or by contacting our support.
Prompt Delivery and 100% Money-Back-Guarantee
All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension. In case you cannot provide us with more time, a 100% refund is guaranteed.
Original & Confidential
We use several writing tools checks to ensure that all documents you receive are free from plagiarism. Our editors carefully review all quotations in the text. We also promise maximum confidentiality in all of our services.
24/7 Customer Support
Our support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.
Try it now!
How it works?
Follow these simple steps to get your paper done
Place your order
Fill in the order form and provide all details of your assignment.
Proceed with the payment
Choose the payment system that suits you most.
Receive the final file
Once your paper is ready, we will email it to you.
No need to work on your paper at night. Sleep tight, we will cover your back. We offer all kinds of writing services.
No matter what kind of academic paper you need and how urgent you need it, you are welcome to choose your academic level and the type of your paper at an affordable price. We take care of all your paper needs and give a 24/7 customer care support system.
Admission Essays & Business Writing Help
An admission essay is an essay or other written statement by a candidate, often a potential student enrolling in a college, university, or graduate school. You can be rest assurred that through our service we will write the best admission essay for you.
Our academic writers and editors make the necessary changes to your paper so that it is polished. We also format your document by correctly quoting the sources and creating reference lists in the formats APA, Harvard, MLA, Chicago / Turabian.
If you think your paper could be improved, you can request a review. In this case, your paper will be checked by the writer or assigned to an editor. You can use this option as many times as you see fit. This is free because we want you to be completely satisfied with the service offered.