This assignment has two parts. The first part is practice working with backtracking. The second part is the first part of the MiniScheme interpreter project.
Your implementations will be in several files. The start of each file should be
#lang racket
; Your name(s) here.
Preliminaries
Click on the assignment link. If you’re working with a partner, one partner should create a new team. The second partner should click the link and choose the appropriate team. (Please don’t choose the wrong team, there’s a maximum of two people and if you join the wrong one, you’ll prevent the correct person from joining.)
Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instruction and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style from the first homework.
Be sure to ask any questions on Piazza.
Submission
To submit your homework, you must commit and push to GitHub before the deadline.
Your repository should contain the following files
hw5.rkttests.rktenv.rktenv-tests.rkt
It may also a .gitignore file which tells Git to ignore files matching patterns in your working directory.
Any additional files you have added to your repository should be removed from the main branch. (You’re free to make other branches, if you desire, but make sure main contains the version of the code you want graded.)
Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.
Part 1. Backtracking
Your implementations of the following functions in this part should all be placed in a single Racket file named hw5.rkt. For this part, tests have been provided for you in the tests.rkt file.
You may use the solution to any exercise as a helper function in subsequent exercises and you may also write stand-alone helper functions.
For each function, write the function.
- (25 points) Write a solution to the subset sum problem. This means you should write a procedure
(subset-sum n nums) where n is an integer and nums is a list of integers that returns a subset of the integers in the list nums whose values sum to n. If no subset of nums does this, the function should return #f. (subset-sum 23 '(2 10 5 7 3 8 6)) returns '(10 5 8) or '(2 10 3 8) or any other subset of '(2 10 5 7 3 8 6) that sums to 23.(subset-sum 23 '(2 10 5 7)) returns #f.
Hint 1: subset-sum’s feasible check is particularly simple: any number is feasible. For example, suppose n is 4, nums is '(5 2 -1). 5 is feasible even though it’s greater than 4 because '(5 -1) is a valid solution.
Hint 2: The structure of the subset sum problem is also simpler than the others we’ve looked at. If n is 0, then empty is a valid solution. Otherwise, if nums is empty, then there is no solution. Otherwise, nums starts with some value x and we can ask the questions:
- Is there a subset of the rest of
nums that sums to n - x? - Is there a subset of the rest of
nums that sums to n?
Hint 3: Because of the implications of hints 1 and 2 e don’t actually need to build the partial solution sofar. It’s enough to answer one or both of the questions in hint 2 and if the answer to either is yes, return the appropriate result list by consing x onto the result in one case and not doing so in the other.
(25 points) A “no-repeat” sequence is a sequence containing only the digits 1, 2, and 3 that does not contain two identical adjacent subsequences. For example '(2 1 3 1 2 1) is a no-repeat sequence, but '(1 2 3 3 2 1) is not (because 3 is a repeated subsequence of length 1), and '(1 2 3 2 3 1) is not (because the subsequence '(2 3) is repeated in adjacent spots.
Write a procedure (no-repeat n) that returns a no-repeat sequence of length n.
Hint: This is very similar to the n-queens problem. The backtracking is actually straightforward; the more difficult part is writing a function (feasible sofar curr) that says that if sofar is a no-repeat sequence, then (cons curr sofar) is also one. Since we know sofar is a no-repeat sequence, we only need to check subsequences starting with curr. Suppose sofar is the sequence (list x1 x2 ... xn). You need to check if (list curr) is a prefix of (list x1 x2 ... xn) and then if (list curr x1) is a prefix of (list x2 x3 ... xn) and then if (list curr x1 x2) is a prefix of (list x3 x4 ... xn) and so forth. You may want to use the list-prefix? standard library function.
Hint 2: If we change feasible to take two lists rather than a list sofar and a number curr, we can simplify the implementation of feasible since it then becomes a check if one list is a prefix of the other list and if not, recursing appropriately. This means you’ll want to call (feasible sofar (list curr)) as part of your backtracking procedure.
Part 2. Interpreter environment
For this part, read parts 1, 2, and 3 of the MiniScheme project. Your task is to implement the procedure described in part 3. You should implement that in env.rkt (35 points) and the tests in env-tests.rkt (15 points).
In future homeworks, you will use your env.rkt and env-tests.rkt.