CSC 160
Homework 7

Assigned 10 April, due 22 April

Links to textbooks

• HtDP Chapter 9
• HtDP Chapter 10

Problems on lists

• Develop a function named any-matches? that takes a string and a list of strings and returns whether that string appears in the list.
  Example:

  (any-matches? "hi" (cons "hey" (cons "ho" empty))) "should be" false
  (any-matches? "hi" (cons "hey" (cons "hi" empty))) "should be" true

• Develop a function count-matches that takes a string and a list of strings and returns the number of times that string occurs in the list.
  Example:

  (count-matches "hi" (cons "hey" (cons "hi" (cons "hello" (cons "hi" (cons "bye" (cons "hi" (cons "adios" empty))))))))
  "should be" 3

• Develop a function convert which takes in a list of digits, ones place first (this actually makes the problem easier), and returns the corresponding number. For example, (convert (cons 3 (cons 0 (cons 2 (cons 5 empty))))) should return the number 5203.

• Develop a function multiply-all which takes in a list of numbers, and produces the result of multiplying them all together.

  Hint: What is the "right answer" for the empty list? It may not be what you think!

• Develop a function general-bullseye which takes in a list of numbers, and produces an image with black rings at those radii.

  Hint: Use (circle 1 "solid" "white") as the answer for the empty case.

  Note: If you wish, you may assume that the numbers are in increasing order, e.g. (cons 3 (cons 7 (cons 12 (cons 15 (cons 29 empty))))). If this doesn't help, forget I said anything.

• Extra credit: Develop an animation based on Exercise 15.6.3, but every few seconds a dot is added to the screen (in addition to whatever is already there), and if you click on any one of the existing dots, the game ends. (The game will be really easy, since nothing ever disappears, and pretty soon the screen fills up with dots so it's difficult not to hit one.)

  Hint: Change your model from a posn to a list of posns.

Problems on returning lists

• Developa function stutter that takes in a list of objects and returns a list twice as long with each object appearing twice in a row. For example,

  (check-expect (stutter (cons 3 (cons 8 (cons -2 empty)))) 
      (cons 3 (cons 3 (cons 8 (cons 8 (cons -2 (cons -2 empty)))))))

• Develop a function remove-all that takes a string and a list of strings and returns the same list with all occurrences of the given string removed.
  Example:

  (check-expect
      (remove-all "bat" (list "doll" "bat" "bat" "nintendo" "bat" "ball"))
      (list "doll" "nintendo" "ball"))
  

• Develop a function replace that takes two strings (referred to as old and new) and a list of strings, and returns a list of strings with old replaced throughout by new.
  Example:

  (check-expect
      (replace "bat" "ball" (list "doll" "bat" "bat" "nintendo" "bat" "ball"))
      (list "doll" "ball" "ball" "nintendo" "ball" "ball"))
  

• Develop a function named add-vote-for which takes in a string (the name of a candidate) and a list of candidate structures, and returns a list of candidate structures in which that candidate has one more vote (and all the others are unchanged). You may assume that no name appears more than once in the list of candidate structures.
  Note: it's possible that the name doesn't appear in the list at all (e.g. it's a write-in vote, or something like that); if so, the resulting list should have 1 vote for that candidate.

• Develop a function named tally-votes which takes in a list of strings (Voter 1's favorite candidate, Voter 2's favorite candidate, etc.) and produces a list of candidate structures in which each candidate name appears once, with how many votes were cast for that candidate.

• Extra credit: develop a function named sort-candidates which takes in a list of candidate structs and produces a list of the same candidate structs, but with the candidates sorted in decreasing order of number of votes (so the one with the most votes is first in the list, and the one with the fewest votes is last).

• Extra credit: develop a function named permutations which takes in a list of things (strings, or symbols, or numbers, or characters... it doesn't matter) and produces a list of all the possible "scramblings" of that list. For example,

  (check-expect (permutations (list 'a 'b 'c))
    (list (list 'a 'b 'c) (list 'a 'c 'b) (list 'b 'a 'c) (list 'b 'c 'a) (list 'c 'a 'b) (list 'c 'b 'a)))
  

  (Your function may return the answers in a different order, as long as it returns a list of all the possible answers, once each.)

What to turn in and how

All of the problems are programming problems. There is one animation; deal with it as you did in the previous few assignments.

Also turn in a log of how many errors of different kinds you encountered in the assignment, with brief comments describing each one ("mismatched parentheses" is self-explanatory, but more complex errors might need more description). Note that "errors" means not only error messages from DrScheme, but also wrong answers. You may do this using the PSP forms, or simply by keeping track in a text file or on paper and turning it in.

Grading standards

Error log:       /30
(I'm not grading on how many or how few errors you encountered, only on whether you recorded them correctly.)

I sha'n't actually grade all the problems; consider the others "practice". For each function I grade, see the table below, which has columns for each step in the design recipe. You won't turn in a separate skeleton, inventory, and definition, but rather write a skeleton, then add an inventory, then add a body to turn it into a complete definition. However, if you don't get the definition working, comment it out and you'll still get partial credit for a correct skeleton and/or inventory.

General skills:

Total:         /???