29 More really freaking awesome HOF: Tic-Tac-Toe and diff between dates. | (3 activities) |
The code from Appendix D in part 3 of the Difference Between Dates case study is available here.
Rewrite its preceding-month-lengths procedure to translate the sentence of month names to month numbers, then to shrink that to a sentence of relevant month numbers and translate that result to the desired sentence of month lengths. The code in the appendix uses the higher-order procedures every and keep. When you rewrite the procedure, you want to have it produce the same result by a different process, possibly using different higher-order procedures.
For example, evaluating
(preceding-months-lengths 'june)would be represented by the following data flow diagram in the rewritten code: |
Which version of preceding-months-lengths—the original, or the version you just coded—do you prefer, and why? It's OK to say you don't have any preference, but you have to say why. |
The next several steps involve a buggy version of the day-span program, available here.
The bug results from the modification of a single symbol in the program.
Paste the code into the Interpreter or stk to test it in order to find the bug.
Note that this code represents a date as a word rather than as a sentence.
A sample call to this version of day-span would thus be
(day-span 'january01 'december31)or (better) (day-span (new-date 'january 1) (new-date 'december 31)) |
Describe, as completely as possible, all inputs to the day-span procedure for which the buggy program returns the correct answer. |
Which symbol in the program was incorrect, and what did you change it to in order to fix the bug? |
Describe how you found the bug (what tests you tried, how you chose them, etc.). |
The precedes? procedure in the program you just debugged uses accumulate. Describe how precedes? figures out whether its first argument precedes its second argument. |
Modify the format of ttt's position argument.Currently, the Tic-Tac-Toe program uses an underbar to represent a blank square. This is inconvenient because (a) one needs to hit the shift key in order to type an underbar, and (b) it is sometimes difficult to tell how many underscores one has typed. Fix the program to allow any of underbar, hyphen, equal sign, or asterisk to represent a blank square. After your revision, you will then be able to represent the boardx | o | ---+---+--- | | ---+---+--- | | xin numerous ways, including xo-=**_*x, xo_-_-_-x, and xo******x. Put your revisions in a file named revised.ttt.scm. The code for the Tic-Tac-Toe program is available here. |
Figure out who is supposed to move.In your revised.ttt.scm file, redefine ttt to take a single argument, namely the game configuration, and to compute the me argument to ttt-choose. This will be the player whose turn it is to move. If the number of X's on the board is equal to the number of O's, it's X's turn to move; if the number of X's is one more than the number of O's, it's O's turn; otherwise ttt should return #f. Two examples of how the revised code should behave are shown below.
|
Rewrite the pivots procedure.The current pivots procedure analyzes each pair of triples to see if they produce a "pivot" move. Another way to find the pivots is to check each open square to see if it's a pivot. In your revised.ttt.scm file, reorganize the pivots procedure by completing the framework below, and by supplying any necessary helper procedures.(define (pivots triples me) (keep ___ '(1 2 3 4 5 6 7 8 9)) )Include tests of the new pivots procedure in the revised.ttt.scm file. |
Write a procedure called valid-position?, which takes one argument and returns #t if that argument is a legal tic-tac-toe position and #f if it is not. The argument can be anything, so make sure your program is careful. Assume that you are working with the original 3x3 board and that blank squares are only represented by _. Once you have posted your code, look for mistakes in programs other people have posted. If you find one, leave a comment that describes the problem. You should come back to this page later to see if anyone found a mistake in your code. |
Make the program use a slightly larger board.The book Winning Ways claims that it's possible to avoid a tie in Tic-Tac-Toe on any bigger board, even with just one extra square. Modify your revised.ttt.scm program so that the game is played on the following ten-square board. The new square should be square number 0.+---+ | | +---+---+---+ | | | | +---+---+---+ | | | | +---+---+---+ | | | | +---+---+---+Optional: Decide if either player has a winning strategy on the revised board. |
On page 165, Harvey and Wright comment on why they list the diagonals last in the triples list. Is this still necessary with the revised pivots procedure? Why or why not? |
|
You've been confronted by a number of challenging exercises involving higher-order procedures. Problems you encountered included
|
30 Second Survey | (1 activity) |
1.When I am writing scheme procedures, I often have trouble knowing how to get started: |
2.Once I've started writing a procedure, I often get stuck and have trouble knowing how to continue: |
3.When you give Scheme the exact same program over two different occasions, will Scheme do the same thing both times? |
4.Rate the amount of material and activities per lab section overall. |
5.Please list any particularly hard lab exercises that took you a long time to complete |
6.When reading online curriculum pages for this course, do you generally ... |
7.Some of the activities in this course involve "Brainstorming" questions, where you give an answer and then get to look at everyone else's answer to the question. Please check all that apply: |
8.When you get stuck while programming in this course, do you primarily: |
9.When you are reading online instructions or materials in this course, and you are confused or can't figure something out, do you primarily |
10.In this course, your instructor or lab assistant will sometimes interrupt the class to make an announcement about a confusion that many students are having. (Please note that we are not asking about normal course announcements that might happen at the beginning of the session). Please select the answer that best applies: |
11.In this course, your instructor or lab assistant may interrupt you or a small group you are working with in order to discuss a problem or confusion that you may be having. (Please note, we are not asking about instances where you request help from the instructor or lab assistant, only instances where they interrupt you unbidden). |
12.In a typical session of this course, how often would you like either the instructor or lab assistant to give you one-on-one help? (You might mention how many minutes, or how many interactions, you would want.) |
13.In a typical session of this course, how often does either the instructor or lab assistant give you one-on-one help? (You might mention how many minutes, or how many interactions, you typically have.) |
14.We are very interested in the ways that you try to get help in this course when you are stuck or confused, and what happens after you request it. If you have anything to add on this topic that the above questions did not capture, please include your thoughts below. |
15.Do you like programming? |
16.How much time do you spend outside of class on CS 3? |
17.What is the furthest behind you have fallen this semester, in terms of the lab work? |
18.How often have you been one or more labs behind in the course? |
19.What did you like most about the last midterm review? (FYI - Gilbert did a midterm review the two days before the midterm) |
20.How useful are the lectures for you? And, how can Colleen make them better? (Please be honest: this will be viewed anonymously, and won't affect your grade!). |
21.What can Gilbert do differently to make the midterm review more helpful? |
22.What is something the lab assistant Armen does that you find helpful? (write N/A if you haven't worked with this lab assistant) |
23.In what way could the lab assistant Hugh be more helpful? (write N/A if you haven't worked with this lab assistant) |
24.In what way could the lab assistant Andrew be more helpful? (write N/A if you haven't worked with this lab assistant) |
25.What is something the lab assistant Hugh does that you find helpful? (write N/A if you haven't worked with this lab assistant) |
26.What is something the lab assistant Andrew does that you find helpful? (write N/A if you haven't worked with this lab assistant) |
27.In what way could the lab assistant Justin be more helpful? (write N/A if you haven't worked with this lab assistant) |
28.What is something the lab assistant Justin does that you find helpful? (write N/A if you haven't worked with this lab assistant) |
29.In what way could the lab assistant Armen be more helpful? (write N/A if you haven't worked with this lab assistant) |
31 Miniproject 3: election processing | 2008-7-21 ~ 2008-7-23 | (1 activity) |
Miniproject 3BackgroundPresidential elections in the United States happen every four years. On November 2 of 2004, for instance, we chose between George Bush and John Kerry for president. The procedure for determining the winner of the election is somewhat complicated, and is described here; in short, the candidate who gets the most popular votes in a particular state earns that state's electoral votes, and whoever gets more than half of all the electoral votes wins the election.AssignmentWrite and test a program to process U.S. presidential election results. The program will include a procedure named winner, whose first argument is a sentence giving the number of electoral votes for each state and whose second is a sentence giving the percentage of popular votes for the Republican and Democratic candidates. (For this assignment, we ignore third-party candidates.) Winner returns either republican, democrat, or #f, depending on who wins the election. Each word in the electoral vote sentence has four characters. The first two are the state abbreviation; the last two are digits that together specify the number of electoral votes for the state. An example is ca55, which says that California has 55 electoral votes. Each word in the vote results sentence has six characters. The first two are the state abbreviation, as with the electoral votes sentence. The next two are the (rounded) percentage of popular votes earned by the Republican candidate; the last two are the percentage of popular votes earned by the Democrat candidate. Some examples from the 2000 election are
Miscellaneous requirementsPut your solution program into a file named winner.scm in your mp3 directory, and your tests (described below) into a file named winner-tests.scm in the same directory. Submit it as detailed below. None of your code may use recursion. Use the higher-order procedures every, keep, and accumulate instead. In general, restrict your use of Scheme to material covered in Simply Scheme chapters 1-10. Your program should include auxiliary procedures to be called from winner; none of your procedures should be a big mess. You will lose points for unnecessarily duplicated code; define procedures with extra placeholders (possibly procedures) to avoid this duplication. Provide names for your procedures and their parameters that clearly indicate their types and use. Also provide comments with your code. Your grade on this assignment will include evaluation of your comments. Each of your procedures must be accompanied with comments that describe each input—is it a sentence, a word, or a number? what kind?— along with the result returned.TestingInclude test expressions in a file named winner-tests.scm. Use the testing library discussed in the previous miniproject (a full writeup of its functionality is available here. There is an additional feature described there: in run-test-cases, you can provide an optional argument to run only some of you test cases. Test winner on races where each candidate wins and where neither candidate wins. Include at least one input where two candidates split all the electoral votes evenly, and another where neither candidate earns half the votes. Also test your auxiliary procedures individually, to provide additional evidence that they work correctly. Any procedure that involves a numeric comparison should be tested with values less than, equal to, and greater than the compared value. Any procedure that includes a keep should be tested at least with one input for which all the elements are kept, another for which nothing is kept, and a third for which some but not all of the elements are kept. (Note that these tests are not guaranteed to remove all your bugs.) |
We will be considering style more strictly than with previous miniprojects, and it will be reflected in your grade.
|
A solution to this project, involving the files winner.scm and winner-tests.scm, is due at 11:59pm on Thursday, July 24th.
To submit, put your files in a directory named mp3 and
submit them in the usual manner (i.e., by typing submit mp3 via unix).
You may, but need not, work in a partnership of two on this project; you and your partner should be in the same lab section. Both partners will receive the same score on the project.
If you work with a partner:
|
32 Quiz for last day of HOF | (1 activity) |
1.
Identify, as descriptively and accurately as possible, the type of value returned by the procedure below.
Possible types include but are not limited to a triple, a sentence of triples, a square number (1, 2, ..., 9), and a player (x or o). Assume that the argument for each procedure is a sentence of triples that could be produced by a call to find-triples.
What type of value is returned by
(define (proc1 triples) (keep (lambda (t) (not (number? t))) (every first triples) ) ) |
2.
What type of value is returned by
(define (proc2 triples) (first-if-any (pivots triples 'x)) ) |
3.Each of the following words represents a board that could be provided as input to the ttt procedure. Which of the boards contains a pivot square for player X? (The answer may be none, or all three.) |