Com S 227 --- Introduction to Computer Programming HOMEWORK 6: Interactive Programming (File $Date: 1993/11/04 15:45:34 $) Due: (((1-6 8-10) (Oct. 29)) ((14 16 21) (Nov 3)) (24-25 (Nov 5))) The homework for this chapter involves some larger problems. Don't start the work at the last minute! All the directions from homework 2 apply to this homework. In particular, remember to hand in labeled printouts for procedures, and transcripts showing your testing. SECTION 6.2, STRINGS 1. (5 points; basic) Do exercise 6.1. 2. (0 points; suggested practice) To edit strings, you often have to know where some target string is in the string. Define a procedure string-index that takes two strings, ``short'' and ``long'' and returns the first index in ``long'' at which ``short'' occurs as a substring. If ``short'' does not occur as a substring in ``long'', return -1. For example, (string-index "bush" "Trees and bushes") ==> 10 (string-index "Tr" "Trees and bushes") ==> 0 (string-index "xyzzy" "Trees and bushes") ==> -1 (string-index "xyzzy" "xyzzy") ==> 0 (string-index "xyzzy" "x") ==> -1 (string-index "z" "xyzzy") ==> 2 3. (0 points; suggested practice) What does the procedure substring-ref in exercise 6.2 do? Do exercise 6.2 and check your answer on the computer. 4. (0 points; suggested practice) Do exercise 6.3. Note that the empty string is a palindrome. 5. (15 points) A common function of computer programs is to recognize some pattern in the input. This is used heavily in ``lexical analysis'' which precedes parsing in a compiler. The lexical analysis phase breaks the input string up into tokens, like words in natural language. One often needs to look for sequences of zero or more characters from some class of characters. Define a procedure ``zero-or-more?'' that takes a string ``char-set'' and a string ``str'' and returns #t if ``str'' is composed of 0 or more occurrences of characters from ``char-set'' and #f otherwise. For example, (zero-or-more? "" "") ==> #t (zero-or-more? "" "a b c") ==> #f (zero-or-more? "0123456789" "227") ==> #t (zero-or-more? "0123456789" "a fine day") ==> #f (zero-or-more? "abcdefghijklmnopqrstuvwxyz" "humhum") ==> #t (zero-or-more? "abcdefghijklmnopqrstuvwxyz" "Some Caps") ==> #f (zero-or-more? "" "a b c") ==> #f (zero-or-more? "0123456789" "227") ==> #t (zero-or-more? "0123456789" "a fine day") ==> #f (zero-or-more? "abcdefghijklmnopqrstuvwxyz" "humhum") ==> #t (zero-or-more? "abcdefghijklmnopqrstuvwxyz" "Some Caps") ==> #f 6. (10 points) Define a procedure ``one-of-these?'' that takes a list of strings ``los'', a string ``str'' and returns #t if one of the strings in ``los'' is found in ``str'' and #f otherwise. For example, (one-of-these? (list "a" "b" "c") "a fine day") ==> #t (one-of-these? (list "1" "one" "uno") "once in a while") ==> #f (one-of-these? (list "1" "one" "uno") "how can one be uno?") ==> #t (one-of-these? (list "294" "1580") "555-1212, (555)292-1580") ==> #t (one-of-these? (list "good") "is it bad?") ==> #f (one-of-these? '() "x") ==> #f 7. (8 points; extra credit) For humans, output in lists separated by some character, such as a comma, is desirable. Define a procedure ``sep-by'' that takes a list of strings ``los'', a string ``sep'' and returns a string containing the elements of ``los'' separated by ``sep''. For example, (sep-by (list "a" "b" "c") ", ") ==> "a, b, c" (sep-by (list "a" "b" "c") ".") ==> "a.b.c" (sep-by (list "294" "1580") "-") ==> "294-1580" (sep-by '() "x") ==> "" SECTION 6.3, IMPLICIT BEGIN 8. (0 points; suggested practice) 9. (5 points) Do exercise 6.4. The code for this exercise is in /home/cs227/lib/ch6.ss. 10. (10 points) This is an intentionally tricky problem, so watch out! a. Give the output of the following code. Circle the printed output, and show what is returned by underlining it. (let ((x 3) (y 4)) (letrec ((s (lambda (n) (if (zero? n) 0 (+ x (s (sub1 n))))))) (let ((x (begin (writeln "x is " x) (+ y 2))) (y (begin (writeln "y is " y) x))) (writeln "the result of (s y) is " (s y))) (writeln "the result of (s y) is " (s y))) (* x y)) b. Explain why you get the printing that happens and why the value returned is returned. 11. (5 points; extra credit only) How could you improve the code in problem 10 to make it clear instead of tricky? 12. (15 points; extra credit only) At OOPSLA '93, Gary saw an idea for a computer that has a human face to give better feedback. Can you write a procedure that takes a boolean, and prints a happy face that is appropriate for yes (#t), and a frowning face that is appropriate for no (#f)? Just use normal characters, display, newline, and writeln; you needn't use X window system graphics or anything fancy like that. SECTION 6.3, INPUT AND OUTPUT There are more examples of interactive programming in the files grading.ss, type-check.ss, and car-cdr-game.ss in the directory /home/cs227/lib on Vincent. 13. (0 points; suggested practice) Do exercise 6.5. Check your work on the computer. 14. (10 points; basic) In this problem you will write an interactive procedure, ``telephone-directory'', that takes a list of 2-item lists containing names and phone-numbers as arguments, and which prompts for a name, prints the corresponding phone number or an error message. It continues prompting and printing until ``stop'' (without the quotes) is entered, and then prints ``Bye.'' and exits. For example, consider the following transcript. > (telephone-directory '((sam 2928400) (information 5551212) (sally 1111111))) Name please? sam The number is: 2928400 Name please? information The number is: 5551212 Name please? sam The number is: 2928400 Name please? sally The number is: 1111111 Name please? ada Sorry, there is no listing for ada Name please? fred Sorry, there is no listing for fred Name please? stop Bye. > (telephone-directory '((dean-of-students 2941020) (dept-of-public-safety 2944428) (emergency 911) (access 2322303))) Name please? emergency The number is: 911 Name please? access The number is: 2322303 Name please? stop Bye. 15. (10 points; extra credit) How would you modify the program in the previous problem so that it allows people's names to be capitalized, and prints phone numbers in the style 294-1580. You can change the inputs to the program too. 16. (20 points) When Gary went to France, he found it hard to think in French and also make deal with French money. (Being absent-minded doesn't help either.) On Gary's next trip to France, he wants to make sure he isn't cheated when buying goods in French shops, and so has decided to have you write a program to tell him how much change he should get. The program should prompt for the amount of a purchase, the amount paid, and then should describe how to give change using the minimum number of coins and bills. The French currency is called the ``Franc'', which is composed of 100 ``centimes'' (cents). There are coins with values of 5, 10, 20, and 50 centimes, and also 1, 2, 5, 10, 20 Franc coins. There are bills with values of 50, 100, 200, 500, 1000, and 10000 Francs. (A Franc is worth about 16 cents US.) The change should give the minimum number of things back, that is using the largest bills and coins if possible. The following is a sample transcript. > (french-changer) price? 12.95 Amount paid? 1000 Your change is 987.05 Francs, which should be given as: 1 500 Franc bill 2 200 Franc bills 1 50 Franc bill 1 20 Franc coin 1 10 Franc coin 1 5 Franc coin 1 2 Franc coin 1 5 centimes coin price? 13 Amount paid? 20 Your change is 7 Francs, which should be given as: 1 5 Franc coin 1 2 Franc coin price? done Ok Note that getting the plurals right (bills vs. bill) is important for this program. 17. (0 points; suggested practice) Do exercise 6.7. (Note that, according to the errata, if you have the first printing of the textbook, you should change ``C'' to ``E'' in the last two lines of page 177, and change ``D'' to ``F'', and on top of page 178, change step 5 to read: ``Set R equal to F modulo 7''.) 18. (20 points; extra credit only) Write an interactive program histogram that prompts for a list of integers, and prints a histogram (as shown below). (Another name for this is a bar-graph.) It continues prompting and printing until an empty list is entered. The histogram uses asterisks to show occurrences. For example, consider the following transcript. > (histogram) Enter a list of integers (no quote) or () to stop: (3 4 3 20 0 20 8 8) 20: ** 19: 18: 17: 16: 15: 14: 13: 12: 10: 9: 8: ** 7: 6: 5: 4: * 3: ** 2: 1: 0: * Enter a list of integers (no quote) or () to stop: (3 4 5 3 3 4) 5: * 4: ** 3: *** Enter a list of integers (no quote) or () to stop: (-3 -4 2 2 2 2 0) 2: **** 1: 0: * -1: -2: -3: * -4: * Enter a list of integers (no quote) or () to stop: () You will only lose 1 point if you don't get the numbers to line up as in the above examples; if you don't line them up that way, use a tab to line up the asterisks. A string consisting of a single tab character can be written by writing the tab character into the string or by using the string returned by the ``magic'' expression: (string (integer->char 9)) (Hint: if you can't figure out where to start, think of a similar but easier problem and solve that first.) 19. (10 points; extra credit only) Add the ability to ``bin'' data in the histogram. That is, prompt the user for intervals in which to lump together points of data. Allow real numbers to be input as well as integers. 20. (20 points; extra credit only) Print the histogram horizontally instead of vertically. For example, consider the following histogram. > (horizontal-histogram) Enter a list of integers (no quote) or () to stop: (3 4 5 3 3 4) * * * * * * 3 4 5 Enter a list of integers (no quote) or () to stop: () SECTION 6.5, TWO FAMOUS PROBLEMS 21. (20 points) Write a procedure, print-hanoi-states, that takes a number n and prints 3-element lists of numbers; these 3-element lists show how many disks are on each post as the moves are made by the priests for n disks, in order You may assume that n is at least 1. For example, consider the following transcript. > (print-hanoi-states 3) (3 0 0) (2 0 1) (1 1 1) (1 2 0) (0 2 1) (1 1 1) (1 0 2) (0 0 3) > (print-hanoi-states 2) (2 0 0) (1 1 0) (0 1 1) (0 0 2) 22. (10 points; extra credit only) Do exercise 6.8. 23. (35 points; extra credit only) Do exercise 6.9. This is hard! 24. (10 points) Do exercise 6.10. 25. (25 points) Do exercise 6.11. Be sure to read the exercise's description in the book! The following is intended to clarify the book's description. In this problem, ``n'' is the length of the sequence, not a number that can appear in the sequence. Each good sequence can only contain the integers 1, 2, and 3. For example, (good-sequences 0) ==> () (good-sequences 1) ==> ((3) (2) (1)) (good-sequences 2) ==> ((2 3) (1 3) (3 2) (1 2) (3 1) (2 1)) (good-sequences 3) ==> ((3 2 3) (1 2 3) (3 1 3) (2 1 3) (2 3 2) (1 3 2) (3 1 2) (2 1 2) (2 3 1) (1 3 1) (3 2 1) (1 2 1)) (good-sequences 5) ==> ((3 1 3 2 3) (2 1 3 2 3) (2 3 1 2 3) (1 3 1 2 3) (3 2 1 2 3) (3 2 3 1 3) (1 2 3 1 3) (2 3 2 1 3) (1 3 2 1 3) (3 1 2 1 3) (3 1 2 3 2) (2 1 2 3 2) (2 3 1 3 2) (3 2 1 3 2) (1 2 1 3 2) (3 2 3 1 2) (1 2 3 1 2) (2 1 3 1 2) (2 3 2 1 2) (1 3 2 1 2) (1 3 2 3 1) (3 1 2 3 1) (2 1 2 3 1) (3 2 1 3 1) (1 2 1 3 1) (1 2 3 2 1) (3 1 3 2 1) (2 1 3 2 1) (2 3 1 2 1) (1 3 1 2 1)) Note that the order of the top-level items in the output of a call to good-sequences does not matter. For example, your procedure may give the result for 2 as follows, (good-sequences 2) ==> ((2 1) (3 1) (1 2) (3 2) (1 3) (2 3)) or any other order with the same top-level items. 26. (0 points; suggested practice only) Do exercise 6.12. This may help you visualize the backtracking process. 27. (0 points; suggested practice only) Do exercise 6.13. 28. (10 points; extra credit only) Do exercise 6.14. 29. (7 points; extra credit only) Do exercise 6.15. 30. (0 points; suggested practice only) Do exercise 6.16. EXTRA CREDIT EXPLORATIONS Note that there are several different kinds of problems below. They are in no particular order, so don't feel that you can't do a later one because you didn't do an earlier one. 31. (20 points; extra credit) If you have PC Scheme or access to a PC, read chapter 7 of Programming in Scheme by Eisenberg (on reserve at the library) and do exercises 1 and 5 on pages 76 and 77. (You can do just one of these for 10 points each.) These exercises show how to draw pictures using graphics-mode in PC Scheme. Note that in Scheme (define (foo x y) ; ... ) is equivalent to (define foo (lambda (x y) ; ... )) If you are using the PC Scheme/Geneva interpreter, you should use the file /home/cs227/PCScheme/bgicompa.s to make the graphics primitives match Esienberg's book. 32. (30 points; extra credit) If you don't have access to a PC, you can't do the previous problem. But you can still do some graphics. Imagine that a terminal screen is a 24x80 (24 lines, 80 columns) array of ascii characters. Establish a coordinate system for these characters. Design and write procedures ``plot,'' ``draw-line,'' and ``draw-rectangle'' that can put given characters at individual points, draw a line of a given character, and draw a rectangle. Note that part of this problem consists in deciding what exactly the problem is to solve. That is, these procedures are intentionally underspecified, and it's your job to specify them precisely. If you find the problem too hard, you may make it easier on yourself by changing the problem! 33. (30 points; extra credit only) Write up a problem description, which is for an interactive game, and program it using Scheme. The points you get will depend on how good your problem description is, and how well you solve it. Don't make it too hard on yourself; you can adapt your problem description if what you originally tried to do seems to difficult. But the problem description and the program should match in what you hand in. 34. (5 points; extra credit only) This problem is about doing Unix programming in Scheme. The Unix shell has a feature to invoke an interpreter like Scheme The simplest way to make a Unix command call a Scheme program is by using the Unix Shell programming language. A simple version of this is your file ~/bin/scheme. Here is another one... #!/bin/sh # fact -- factorial function exec scheme fact.ss < 24 > To get rid of the prompts and the 227 specific loading messages, we can make a slight change as follows to the file fact #!/bin/sh # fact -- factorial function /home/scheme/bin/dec/scheme /home/cs227/lib/call-from-shell.ss fact.ss < prompts. The use of /home/scheme/bin/dec/scheme bypasses your ~/bin/scheme program, and thus suppresses the loading of the Com S 227 file springer-friedman.ss. So you can get the following. vincent% fact Chez Scheme Version 4.1 Copyright (c) 1991 Cadence Research Systems 24 The use of call-from-shell.ss is not necessary for interactive Scheme programs that have no command line arguments. They can exit by putting a call to exit in the program itself. For example, if the interactive French change making program is in french-changer.ss, then the following shell script will run the code. #!/bin/sh /home/scheme/bin/dec/scheme /home/cs227/lib/writeln.ss french-changer.ss You have to put this in a file, and make it executable as described above. Convert your French change making program to run as a Unix program as described above. Test the program. Describe any problems you encounter. Hand in this description and a printout of your Unix shell script. 38. (10 points; extra credit only) Some students (certainly not at ISU) drink a lot of beer and sing songs about it. A classic drinking song is ``N bottles of beer on the wall''. Even though this song is repetitive, some find that they need prompting to sing it in their drunken state. Can you help them by writing a program that prints the lyrics to the song. That is write an interactive program ``bottles-of-beer'' that takes a non-negative number, ``N'' and prints out the song. For example, consider the following transcript. > (bottles-of-beer 0) > (bottles-of-beer 3) 3 bottles of beer on the wall, 3 bottles of beer! If one of the bottles should happen to fall, 2 bottles of beer on the wall. 2 bottles of beer on the wall, 2 bottles of beer! If one of the bottles should happen to fall, 1 bottles of beer on the wall. 1 bottles of beer on the wall, 1 bottles of beer! If one of the bottles should happen to fall, 0 bottles of beer on the wall. 39. (15 points; extra credit) Some songs are recursive. For example ``the 12 days of Christmas''. Write a program that prints out all the lyrics for this song, or some other similar song (such as ``old McDonald''). If you don't know one of these songs, ask me or someone who does. 40. (10 points; extra credit only) Write an ``A'', ``C'' and an ``F'' version of problem 16 above. That is produce a program that is as good as possible, one that is mediocre, and one that is as bad as possible. 41. (5 points, extra credit only) Improve the code for print-poly in /home/cs227/lib/print-poly.ss so that instead of printing -5.3 x^{41} + -3.2 x^2 + 5.0 it prints this as -5.3 x^{41} - 3.2 x^2 + 5.0. The idea is that it uses a minus sign instead of a plus sign when the next coeffient is negative. You should test for special cases thoroughly. 42. (15 points, extra credit only) Improve the code for print-poly in /home/cs227/lib/print-poly.ss so that instead of printing -5.3 x^{41} + 3.2 x^2 + 5.0 41 2 it prints this as -5.3 x + 3.2 x + 5.0. The idea is that it uses two lines and prints exponents as superscripts.