000000.rkt, but replace 000000 with your generated random number. Submit this file on Pweb when you are finished with your exam.
Assigned: Friday, 10 April 2020
Prologue Due: Sunday, 12 April 2020 by 10:30pm
Exam Due: Thursday, 16 April 2020 by 10:30pm
Cover Sheet Due: Friday, 17 April 2020 by the start of class
Epilogue Due: Friday, 17 April 2020 by 10:30pm
Please read the exam procedures page for policies, turn-in procedures, and grading details. If you have any questions about the exam, check the frequently asked questions at the bottom of the page and Piazza. We will generally spend some time in class every day on questions and answers while the exam is in progress.
While the exam is out, please check Piazza periodically to see if any errata have been reported.
Complete the exam using the
exam3.rkt starter source
code. Please rename this file to 000000.rkt, but replace
000000 with your generated random number.
The prologue for this examination will be via Pweb.
For each problem, please include a short note about something that will help you solve the problem. Mostly, we want to see some evidence that you’ve thought about the problem. You might note some similar procedures you’ve written or problems you’ve solved in the past (e.g., in a lab or on a homework assignment). You might note procedures that you expect to use. You might sketch an algorithm. You might pose a question to yourself. (We won’t necessarily read this in a timely fashion, so if you have questions for your instructor, you should ask by email or in person.)
If, when looking at a problem, you think you already know the answer, you can feel free to write something short like “solved” or “trivial”.
Which of those six problems do you expect to be the most difficult for you to solve? Why?
Conclude by answering the question What is an approach that you expect will help you be successful on this exam? For example, you might suggest that you will work thirty minutes on the exam each day, or work on the exam at 7pm each day, when your brain is most able to process information.
The epilogue for this examination will also be via Pweb.
What was the most difficult part of the exam?
What made that part difficult?
What are two things you can do to be more successful on the next exam?
Topics: numeric recursion
Write and document (with 6P’s) a recursive procedure, (list-suffix lst n) that returns a list consisting of the last n elements from the list, lst, in their original order. Examples of how list-suffix should work are below.
> (list-suffix (list "a" "b" "c" "d" "e") 3)
("c" "d" "e")
> (list-suffix (list 23 5 7 9 11 13 17) 2)
(13 17)
> (list-suffix (list "here" "are" "some" "words") 0)
()
> (list-suffix (list null null) 2)
(() ())
While your procedure has much the same purpose as drop, you cannot use drop or take in your solution. Rather, the purpose is to implement the procedure recursively.
Topics: Higher-Order Procedure
Write and document (with 6P’s) a procedure (sum-upto-zero lst) that takes a list of integers as input and returns a list with one additional element which is the additive inverse of the sum of the original list so that all elements of the returned list add up to 0. Note that you are not allowed to drop/eliminate any existing item from the given list. If the sum of the input list, lst is already zero, the procedure will return lst as output. The procedure will only return a null list if the input is a null list.
> (sum-upto-zero null)
'()
> (sum-upto-zero '(-3 1 2))
'(-3 1 2)
> (sum-upto-zero '(-3 1 4 2))
'(-4 -3 1 4 2)
> (sum-upto-zero '(3 1 2))
'(-6 3 1 2)
Your procedure should not be recursive.
Topics: local bindings, recursion
Consider the problem of selecting numbers from a list. One possible solution using a helper procedure is below.
;;; Procedure
;;; select-numbers
;;; Parameters
;;; values, a list of Scheme Values
;;; Purpose
;;; Create a new list which consists of only the numbers
;;; in values
;;; Produces
;;; nums, a list of Scheme values
;;; Preconditions
;;; [No additional]
;;; Postconditions
;;; * number? Holds for every value in nums
;;; * Every element of values for which number? Holds appears in nums.
;;; * If a number appears multiple times in either list, it appears
;;; the same number of times in both lists.
;;; * The values retain their order
(define select-numbers
(lambda (values)
(select-numbers-helper null values)))
(define select-numbers-helper
(lambda (nums-so-far remaining)
(cond
[(null? remaining)
nums-so-far]
[(not (number? (car remaining)))
(select-numbers-helper nums-so-far (cdr remaining))]
[else
(select-numbers-helper (append nums-so-far (list (car remaining)))
(cdr remaining))])))
a. Rewrite select-numbers using letrec. Name this procedure select-numbers-letrec.
b. Rewrite select-numbers using a named let. Name this procedure select-numbers-named-let.
Since the documentation would be the same for these new procedures as in select-numbers, you do not need to provide documentation. Both of your new procedures should work exactly as select-numbers, and should not use helper procedures.
Topics: Vectors
As you know from your reading, the changes made by vector-set! can’t be undone.
But what if we wanted a special vector that did allow vector-set! changes to be
undone? We could do that by having each vector actually be a vector of lists
where each list holds the current and all previous values for a given location in the vector. We’ll
call such a vector a special vector in this problem. The first item in the list
will be considered the current value at that location.
Here is a procedure that turns a normal vector into a special vector:
(define special-vector!
(lambda (vec)
(let ([len (vector-length vec)])
(let kernel! ([pos 0])
(when (< pos len)
(vector-set! vec pos (list (vector-ref vec pos)))
(kernel! (+ 1 pos)))))))
Here is an example of that procedure in action:
> (define test (vector 1 2 3))
> test
'#(1 2 3)
> (special-vector! test)
> test
'#((1) (2) (3))
a. Write without documentation a procedure (special-vector-ref vec pos) that
takes a special vector and an index position and returns the current value at
that location, i.e. the first item in the list at that location.
b. Write without documentation a procedure (special-vector-set! vec pos val) that
takes a special vector, an index position, and a value, and adds that value
to the list at the specified location. Remember the first item of the list is
considered the current value.
c. Write without documentation a procedure (vector-undo-set! vec pos) that takes
a special vector and an index position and undoes the previous special-vector-set!
command.
Here are examples of each of these commands in action:
> (define test (vector 1 2 3))
> test
'#(1 2 3)
> (special-vector! test)
> test
'#((1) (2) (3))
> (special-vector-ref test 0)
1
> (special-vector-set! test 0 "hi")
> (special-vector-ref test 0)
"hi"
> test
'#(("hi" 1) (2) (3))
> (special-vector-ref test 1)
2
> (vector-undo-set! test 0)
> (special-vector-ref test 0)
1
> test
'#((1) (2) (3))
Topics: Recursion, Lists, Random
Write and document a recursive procedure (pokemon-battle hp1 hp2) that takes two integers representing the health points of two pokemon as input and outputs either the string “Pokemon 1 won!” or the string “Pokemon 2 won!” based on a random simulation of a battle. Your battle simulation should subtract a random number between 0 and 50 from Pokemon 1’s health points, subtract a different random number
between 0 and 50 from Pokemon 2’s health points, and once one Pokemon gets to 0 or fewer health points, the other Pokemon should be declared the winner. If they both get to 0 or fewer health points in the same round, either can be declared the winner. You need to include display statements to show the HP at the beginning of each round, as you can see in the examples.
Here are two examples executions of the procedure. Note that your code may produce a different outcome because we are dealing with random chance.
> (pokemon-battle 30 30)
Pokemon 1 has 30 HP and Pokemon 2 has 30 HP.
Pokemon 1 has 22 HP and Pokemon 2 has -10 HP.
"Pokemon 1 Won!"
> (pokemon-battle 30 30)
Pokemon 1 has 30 HP and Pokemon 2 has 30 HP.
Pokemon 1 has 3 HP and Pokemon 2 has 9 HP.
Pokemon 1 has -34 HP and Pokemon 2 has -23 HP.
"Pokemon 2 Won!"
Topics: File Handling, Recursion
Write and document (with 6P’s) a procedure (file-process input-file output-file) {:.signature} that takes two file names as input and reads the lines of expression from the input-file and writes the evaluated result of the corresponding expression to the output-file. The format of each expression in the file is simple: operator value1 value2 where the operator can be one from the {+, -, *, /} and the value1 and value2 are numbers.
;;; if the sample input file contains the following lines
+ 3 2
- 7 12
* 22 17
;;; sample output file should contain the following three lines
5
-5
374
Note:
read, read-line, read-line-of-chars useful.expressions.txt as a test input file.section?#| before the pasted material. Put
a |# after the pasted material.#| and |# or semicolons. You might also add a note or two as to
what you were trying to do.lambda that looks like (define (proc params) body). Can I use that?(random 1000000). If you end up with a number less than six digits, add zeros to the left side of the number until you have six digits.; STUB on some of the procedures. What does that mean?Some of the problems on this exam are based on—and at times copied from—problems on previous exams for the course. Those exams were written by Charlie Curtsinger, Janet Davis, Rhys Price Jones, Titus Klinge, Samuel A. Rebelsky, John David Stone, Henry Walker, and Jerod Weinman. Many were written collaboratively, or were themselves based upon prior examinations, so precise credit is difficult, if not impossible.
Some problems on this exam were inspired by conversations with our students and by correct and incorrect student solutions on a variety of problems. We thank our students for that inspiration. Usually, a combination of questions or discussions inspired a problem, so it is difficult and inappropriate to credit individual students.