29 More really freaking awesome HOF: Tic-Tac-Toe and diff between dates.
(3 activities)
29.1 Work with versions of the day-span program that use higher-order procedures.(7 steps)
29.1.1 (Display page) Rewrite "preceding-months-lengths".
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:
29.1.2 (Brainstorm) Which version of "preceding-months-lengths" do you prefer?
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.
29.1.3 (Display page) Analyze another version of the "day-span" program.
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))
29.1.4 (Brainstorm) For what dates does the buggy code produce the correct answers?
Describe, as completely as possible, all inputs to the day-span procedure for which the buggy program returns the correct answer.
29.1.5 (Brainstorm) What is the bug?
Which symbol in the program was incorrect, and what did you change it to in order to fix the bug?
29.1.6 (Brainstorm) How did you find it?
Describe how you found the bug (what tests you tried, how you chose them, etc.).
29.1.7 (Brainstorm) Explain how the "precedes?" procedure works.
The precedes? procedure in the program you just debugged uses accumulate. Describe how precedes? figures out whether its first argument precedes its second argument.
29.2 Modify the Tic-tac-toe program.(6 steps)
29.2.1 (Display page) Modify the format of ttt's "position" 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 board
 x | o | 
---+---+---
   |   |
---+---+---
   |   | x
in 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.
29.2.2 (Display page) Figure out who is supposed to move.

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.
a call in the original program an equivalent call in the revised program
(ttt '____x____ 'o) (ttt '____x____ )
(ttt 'o__xxo___ 'x) (ttt 'o__xxo___ )
29.2.3 (Display page) Rewrite the "pivots" procedure.

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.
29.2.4 (Discussion Forum) Make sure the position is valid
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.
29.2.5 (Display page) Make the program use a slightly larger board.

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.
29.2.6 (Brainstorm) Must diagonal triples still follow row/column triples?
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?
29.3 Homework(2 steps)
29.3.1 (Display page) Homework
  1. Go back to the discussion in the last homework and make two comments on other people's posts for the discussion.
  2. Then make an initial entry into the discussion below: "Reflect on your experience with higher order procedures".
Soon we'll cover Tree Recursion. Be sure to read the last case study: Change Making it is really important! Check the schedule for when you should have finished reading it. Also, be sure to take the second survey by next lab session.
29.3.2 (Discussion Forum) Reflect on your experience with higher-order procedures.
You've been confronted by a number of challenging exercises involving higher-order procedures. Problems you encountered included
  • confusing keep and every;
  • using the wrong kind of procedure with keep, every, or accumulate;
  • using the wrong sentence or word argument with keep, every, or accumulate;
  • figuring out what processing to put in the procedure argument and what processing to put in the sentence or word argument;
  • keeping nested lambda expressions straight.
Describe which of these was hardest for you, and what you learned from earlier exercises that helped you with the later ones. Then respond to two of your classmates' posts with tips you have for managing uses of higher-order procedures.
30 Second Survey
(1 activity)
30.1 Second Survey(1 step)
30.1.1 (Student Assessment) The Questions
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)
31.1 Write a program to help process the election totals.(3 steps)
31.1.1 (Display page) Here are the project details.

Miniproject 3

Background

Presidential 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.

Assignment

Write 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
ca4254 George Bush earned 42% and Albert Gore earned 54% of the California votes.
dc0986 Bush earned 9% and Gore earned 86% of the District of Columbia votes.
id6928 Bush earned 69% and Gore earned 28% of the Idaho votes.
fl4949 Bush and Gore both earned 49% of the Florida votes.
A framework file that provides the electoral votes for each state and the 2000 election returns is available here. You should use smaller test arguments. You should not make any assumptions about the order of words in the argument sentences, nor make assumptions about what the states are or how many of them are in the argument sentences. If both candidates get an equal percentage of votes in a state, neither candidate should get that state's electoral votes. Otherwise, every state is winner-take-all. That means there are two ways for winner to return #f. One is the situation where each candidate gets exactly half the total electoral votes. The other is where one candidate receives more votes than the other, but because of a tie in one or more states, the candidate with more votes doesn't get more than half the total.

Miscellaneous requirements

Put 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.

Testing

Include 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.)
31.1.2 (Display page) Your programming style matters!
We will be considering style more strictly than with previous miniprojects, and it will be reflected in your grade.
  • Keep procedures small. Procedures should tackle small, coherent tasks. They should probably only be a handful of lines of code (not including comments). If you find a procedure doing too many things, think about the subtasks and separate those into sub-procedures. Another benefit of many smaller procedures is that it makes for easy testing.
  • Choose good names for procedures and parameters. They must be meaningful!
  • Include adequate comments. In many cases, you need to put meaningful comments both for the procedure as a whole as for parts of the procedure itself.
  • Avoid nesting conditional statements. In general, nested conditional statements make code harder to read. There are situations when, especially with sufficient comments, that a little bit of nesting will help separate the cases logically, so we don't want to enforce a blanket ban on the practice.
  • Don't return #t and #f in an if statement! This one bugs a lot of experienced Scheme programmers for good reason: it makes it harder for them to read the program. For example, rather than:
    (if (funny? sent)
       #t
       #f)
    
    simply do this:
    (funny? sent)
    
    And, don't forget to use the not statement if you find yourself needing to reverse the order of the #t and #f statements. (E.g., in the example above, if you're testing if something is not funny).
  • Use proper indenting. Making sure your indenting follows the program flow can make the difference between a readable program and an unreadable one. Emacs, and other scheme editors, can automatically re-indent a range of source code for you. Use this feature!
None of this should be new to you! Be sure to discuss anything you are unsure about with your TA. Your reader contains a document titled Coding Conventions (also available here) which discusses some of these issues in more detail.
31.1.3 (Display page) Miniproject 3 submission details
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:
  • Make sure only one partner submit the files.
  • Put both your names in a comment at the top of winner.scm.
  • Include description inside the file winner.README that describes how each partner contributed to the project. Put the file inside the mp3 directory, and submit it with your other files.
32 Quiz for last day of HOF
(1 activity)
32.1 Quiz(1 step)
32.1.1 (Student Assessment) Here's the quiz.
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.)