This homework provides an introduction to a side of computer science you've probably never seen before. In part 1 you will work with a simple robot called Picobot. Picobot is patterned after the iRobot Roomba and its goal is much the same: to fully cover (vaccuum) its environment. Part 2 will introduce you to a language called Racket, which is a descendent of the language Scheme. Racket (and Scheme) is considered a very "clean" language, with a minimal syntax: few punctuation and formatting rules. In fact some might argue it's too minimal! As a result, Racket is one of the best examples of a language whose focus is supporting computation itself, as opposed to intricate data structuring. In this assignment you'll implement some useful and some silly but fun functions to familiarize yourself with Racket and to re-familiarize yourself with recursion.
Design and formatting account for roughly a quarter of the credit for
each function or program you complete.
Design, here, means algorithm design, that is, how you break a problem
down into smaller pieces and then compose those pieces into an overall
solution.
Large, convoluted functions are difficult to
understand (and debug!). Use
small, clear functions with lots of small helper functions, as
necessary.
Formatting includes coding style: clean and clear structure, meaningful
variable and function names, ample use of spacing, and indenting that
reflects code structure.
As for commenting,
in each problem we ask you to include
Important warning about function names! Be sure to name your functions as indicated in the problem statements below -- including capitalization and punctuation! This helps our graders, who can automate the running of many tests using those function names. Helper functions may have any name you like, but they should be descriptive and appropriate. When graders have to manually change your function names to match the ones in the homework problem descriptions, it angers them -- and a key guideline for CS 42 is not to anger the graders!
Computation in the form of software is useful to the extent that it works. But it only works to the extent that it has been tested! Testing your own software thoroughly is important -- we use test cases to check how well your functions work, and you will certainly want to do the same!
Some test cases are indicated for each of the problems. These can be copied from this assignment site into your code. When you use auxiliary functions, it is good practice (and will save time in the long run) to include tests for them as well. A small but non-trivial part of your grade each week may be based on how well you test your programs, so you should create at least one (more where appropriate) additional test for the primary functions, too!
The first two problems explore a simple "robot," named "picobot," whose
goal is
to completely traverse its environment.
Here
is a link to the Picobot page. (Works only in NON-IE Browsers)
Picobot starts at a random location in a room -- you don't have control over Picobot's initial location. The walls of the room are blue; picobot is green, and the empty area is white. Each time picobot takes a step, it leaves a grey trail behind it. When Picobot has completely explored its environment, it stops automatically.
Not surprisingly, picobot has limited sensing power. It can only sense its surroundings immediately to the north, east, west, and south of it. For example,
In the above image, Picobot sees a wall to the north and west and it sees nothing to the west or south. This set of surroundings would be represented as follows:
NxWx
The four squares surrounding picobot are always considered in NEWS order: an x represents empty space, the appropriate direction letter (N, E, W, and S) represents a wall blocking that direction. Here are all of the possible picobot surroundings:
Picobot's memory is also limited. In fact, it has only a single value from 0 to 99 available to it. This number is called picobot's state. In general, "state" refers to the relevant context in which computation takes place. Here, you might think of each "state" as one piece -- or behavior -- that the robot uses to achieve its overall goal.
Picobot always begins in state 0.
The state and the surroundings are all the information that picobot has available to make its decisions!
Picobot moves according to a set of rules of the form
StateNow Surroundings -> MoveDirection NewState
For example,
0 xxxS -> N 0
is a rule that says "if picobot starts in state 0
and sees the surroundings xxxS, it should move
North and stay in state 0."
The MoveDirection can be N, E, W, S, or X, representing the direction to move or, in the case of X, the choice not to move at all.
If this were picobot's only rule and if picobot began (in state 0) at the bottom of an empty room, it would move up (north) one square and stay in state 0. However, picobot would not move any further, because its surroundings would have changed to xxxx, which does not match the rule above.
The asterisk * can be used inside surroundings to mean "I don't care whether there is a wall or not in that position." For example, xE** means "there is no wall North, there is a wall to the East, and there may or may not be a wall to the West or South."
As an example, the rule
0 x*** -> N 0
is a rule that says "if picobot starts in state 0
and sees any surroundings without a wall to the North,
it should move
North and stay in state 0."
If this new version (with wildcard asterisks) were picobot's only rule and if picobot began (in state 0) at the bottom of an empty room, it would first see surroundings xxxS. These match the above rule, so picobot would move North and stay in state 0. Then, its surroundings would be xxxx. These also match the above rule, so picobot would again move North and stay in state 0. In fact, this process would continue until it hit the "top" of the room, when the surroundings Nxxx no longer match the above rule.
Anything after the pound sign (#) on a line is a comment (as in python). Comments are human-readable explanations of what is going on, but ignored by picobot. Blank lines are ignored as well.
Consider the following set of rules:
# state 0 goes N as far as possible
0 x*** -> N 0 # if there's nothing to the N, go N
0 N*** -> X 1 # if N is blocked, switch to state 1
# state 1 goes S as far as possible
1 ***x -> S 1 # if there's nothing to the S, go S
1 ***S -> X 0 # otherwise, switch to state 0
Recall that picobot always starts in state 0. Picobot now consults the rules from top to bottom until it finds the first rule that applies. It uses that rule to make its move and enter its next state. It then starts all over again, looking at the rules and finding the first one from the top that applies.
In this case, picobot will follow the first rule up to the "top" of its environment, moving north and staying in state 0 the whole time. Eventually, it encounters a wall to its north. At this point, the topmost rule no longer applies. However, the next rule "0 N*** -> X 1" does apply now! So, picobot uses this rule which causes it to stay put (due to the "X") and switch to state 1. Now that it is in state 1, neither of the first two rules will apply. Picobot follows state 1's rules, which guide it back to the "bottom" of its environment. And so it continues... .
For this part of the assignment, your task is to design two different sets of picobot rules:
IMPORTANT Note: There are many different maps included on the picobot site. For this assignment, you only need to deal with map 1 (the empty room) and map 2 (the maze). The map you are on will AUTOMATICALLY determine which problem you are submitting to, so make sure you submit the right rules with the right map.
The rest of the maps are purely for your fun, and you should not submit rules for these maps.
You might think about how efficient your solutions are -- both in terms of the number of states used and in terms of the number of rules. There are other ways to measure efficiency as well (e.g., speed).
For optional extra credit, try to create as efficient a solution as possible for both the empty room and the maze-solving set of rules. That is, strive to use as few rules as possible in creating your solution - so long as your solution will still succeed from any starting point in the environment! Up to +10% extra credit for each problem is available for solutions that match - or beat - 7 rules in the empty room and 8 rules for the maze-solver.'
If you just want to play around more, you can also try to write rules to cover the additional environments that you find on the picobot site. These aren't worth any credit, but they are worth a lot of fun! :)
Obtain access to the Dr. Racket programming environment, either by downloading it to your personal computer or by using the CS lab. On the lab Macs, Dr. Racket is located as follows:
; Provided tests
(test (erdos 3) 10)
(test (erdos 10) 5)
; Additional test
(test (erdos 4) 2)
For this problem define a function, named erdos,
with one argument, N. Thus, your definition will
begin as follows:
(define (erdos N)This function should compute the following:
(test (erdos 3) 10)Iterating this simple function leads to surprisingly difficult mathematical challenges, as this link (and the next function) suggests. The name erdos is from the mathematician Paul Erdos and is (very roughly) pronounced air-dish.
(test (erdos 10) 5)
Write erdosCount, a function of one postitive
integer argument:
(define (erdosCount N)where erdosCount should return the smallest number of times erdos must be iterated, when started with an input of N, in order to arrive at a value of 1. Let's use the symbol ==> to mean "evaluates to." Then, (erdosCount 3) ==> 7, because
(erdos (erdos (erdos (erdos (erdos (erdos (erdos 3))))))) ==> 1and there are 7 applications of erdos above. Here are two more tests:
(test (erdosCount 26) 10)Be sure to use recursion when writing erdosCount. As a starting point, consider how we wrote length in class.
(test (erdosCount 27) 111)
Aside It is an open question in mathematics whether or not (erdosCount N) halts for every positive integer N. It does halt for all of the values of N for which it has been tried; it is conjectured always to halt, but no one has proven it one way or the other. Paul Erdos famously quipped that "mathematics is not ready for such problems." The fact that a general-purpose "haltchecking" program would be powerful enough to answer this century-old conjecture hints at how strong a capability "haltchecking" actually is... . The state-of-the-art understanding of this 3x + 1 problem is available at this link.
In class, you saw how (remove e L) works: it
returns a list identical to L, except with the
first top-level instance of e removed. For this
problem, write (removeAll e L), which should
return a list identical to L, except that all
top-level instances of e have been removed. For
example,
(test (removeAll "i" '("a" "l" "i" "i" "i" "e" "n")) '("a" "l" "e" "n"))
(test (removeAll "i" '( ("a" "l" "i") "i" "i" "e" "n" )) '(("a" "l" "i") "e" "n"))
(test (removeAll 0 '(1 0 1 0 1 0)) '(1 1 1))
Write a function (find L M), taking in two lists L and M, such that find returns true (#t in Scheme) if L is a sublist of M. find should return false (#f) otherwise.
Note that the empty list is a valid sublist of any list at all. On the
other hand, no non-empty list is a sublist of the empty list.
Also, because find deals with sublists,
not subsequences, all of the top-level elements of L
must appear consecutively and contiguously at the top level of M
in order to yield #t. For example,
(test (find '(1 2 3) '(0 1 2 3 4)) #t)Here are a few other tests -- you should devise a few of your own, as well!
(test (find '(1 2 3) '(0 1 2 2 3 4)) #f) ;; they're not contiguous
(test (find '() '(1 2 3)) #t)Hint It may be helpful to use a second, helper function to handle the contiguous-element checking here... .
(test (find '(1) '()) #f)
(test (find '(1 2) '(2 1 1 1)) #f)
(test (find '(1 2) '(2 1 1 (1 2))) #f) ;; an element is not a sub-list
(test (find '(1 1 3) '(2 1 1 2 3 1)) #f)
Write a variant of reverse named (superreverse
L), whose input L will be a list that may
contain
lists as some of its elements. superreverse
should output a list identical to L, except that
all of its top-level
lists should be reversed. For example,
(test (superreverse '( (1 2 3) (4 5 6) 42 ("k" "o" "o" "l") ("a" "m") ))
'( (3 2 1) (6 5 4) 42 ("l" "o" "o" "k") ("m" "a") ) )
(test (superreverse '( (1 2 3) (4 5 6 (7 8) 9 ) ))
'( (3 2 1) (9 (7 8) 6 5 4) ) )
Next define (duperreverse L), which returns a
list whose structure is a complete reversal
of L's. For example,
(test (duperreverse '( (1 2 3) (4 5 6) 42 ("k" "o" "o" "l") ("a" "m") ))
'( ("m" "a") ("l" "o" "o" "k") 42 (6 5 4) (3 2 1) ) )
(test (duperreverse '( (1 2 3) (4 5 6 (7 8) 9 ) ))
'( (9 (8 7) 6 5 4) (3 2 1) ) )
Scheme's built-in function (list? x) returns #t
if and only if x is a list;
otherwise it returns #f.
For the purposes of this problem, consider any data type that is not a
list to be atomic, that is, it
can not be broken down to be reversed.
Association lists, or "a-lists" for short, are always lists of lists. For example, the above function, number-each outputs association lists. they are often used serve as data repositories, as this problem illustrates using the example of scrabble-letter scores.
The function (assoc e A) takes in an a-list A (remember that A contains lists of lists) and returns the element of A whose own first element is equal to e. For example:(assoc 3 '((1 jan) (2 feb) (3 mar) (4 apr))) ==> (3 mar)As the second example shows, assoc returns #f when e does not appear as a first element of any of A's sublists.
(assoc 5 '((1 jan) (2 feb) (3 mar) (4 apr))) ==> #f
In this problem we want to use an association-list to score
information about scrabble tiles. The following Scheme statement
defines an A-list that provides all of the letter scores. You should
copy this
code into your hw1part2.scm file:
;; scrabble-tile-bagThe notation #\a is Racket's way of representing single-character literals.
;;
;; letter tile scores and counts from the game of Scrabble
;; the counts aren't needed (but don't hurt)
;; obtained from http://en.wikipedia.org/wiki/Image:Scrabble_tiles_en.jpg
;;
(define scrabble-tile-bag
'((#\a 1 9) (#\b 3 2) (#\c 3 2) (#\d 2 4) (#\e 1 12)
(#\f 4 2) (#\g 2 3) (#\h 4 2) (#\i 1 9) (#\j 8 1)
(#\k 5 1) (#\l 1 4) (#\m 3 2) (#\n 1 6) (#\o 1 8)
(#\p 3 2) (#\q 10 1)(#\r 1 6) (#\s 1 4) (#\t 1 6)
(#\u 1 4) (#\v 4 2) (#\w 4 2) (#\x 8 1) (#\y 4 2)
(#\z 10 1) (#\_ 0 2)) ) ;; end define scrabble-tile-bag
;;
;; The underscore _ represents a blank tile.
;; The notation #\a is Scheme's unusual character notation
(test (score-letter #\w) 4)
(test (score-letter '#\z) 10)
(test (score-letter '_) 0)
Next, construct a function score-word
that determines the score for a string of letters. Note that strings in
Scheme are not the same as symbols, nor are characters the same as
strings (as in Python).
Strings are doubly quoted. The built-in functions string->list
and list->string,
which convert from strings to lists of characters and vice-versa, may
be of use. Here are examples of them in action:
(string->list "hi") ==> (#\h #\i)Here are three tests of score-word:
(list->string '(\#h \#i) ) ==> "hi"
(test (score-word "zzz") 30)
(test (score-word "fortytwo") 17)
(test (score-word "twelve") 12)
Define a function best-word as
follows:
(define (best-word rack wordList)best-word takes two inputs: a string of letters rack and a list of legal strings named wordList. Then, best-word should return a list of two elements: the return value's first element should be the highest-scoring word from wordList that can be made from the letters in rack. The return value's second element should be the score of that highest-scoring word. If there is a tie, any one of the strings in the wordList with maximal score may be returned. When we test your code, we will make sure that the highest-scoring word in each test case is unique.
(test (best-word 'academy '(ace ade cad cay day)) '(cay 8))Note that "paper" could not be made in the third example, because the rack had only a single #\p.
(test (best-word 'apple '(peal peel ape pape)) '(pape 8))
(test (best-word 'pale '(peal peel ape pape)) '(peal 6))
Hint: planning out your strategy for this problem before diving in to the coding is a good thing! In particular, you will want to define and use a number of helper-functions to keep your definition of best-word simple and elegant. You'll want to keep the helper-functions short, as well!