Problem Set 0

due by 11:59 p.m. on Sunday, January 28, 2018

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs111-staff@cs.bu.edu.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

Problems

Problem 0: Reading and response

5 points; individual-only

Each week, problem 0 will involve reading a short article and writing a brief response. The readings may not relate directly to the technical topics that you will be learning in class, but our hope is that they will allow you to explore some of the many real-world aspects of computer science.

This week’s reading is an excerpt from a New York Times article about two fundamental facets of CS: language and thought. It also relates the wonderful story of the Picobot-like human language Guugu Yimithirr!

The excerpt is available here. If you are interested in more about this topic, you can read the full article.

After you have read the above excerpt (or the whole article), write a response that addresses one or both of the following prompts. (Important: Put your response in a file named ps0pr0.txt. The file that you submit must be a plain-text file. More information about what this means is available here. Please read the information on that page carefully before you proceed.)

1. Have there been moments in which you felt that your language or another language “got in the way” of something you wanted to accomplish? That is, have you “bumped into a language’s boundaries,” in the manner suggested by the article? Elaborate briefly.

2. To what extent do artificial languages (such as Python or Picobot) have the ability to shape human thought, if at all? Or are such languages fundamentally different from human ones, such as Guugu Yimithirr or English?

You only need to write a few sentences. The important thing is that your response shows you have thought about the article and added your own experience or insights to its ideas.

Problem 1: Picobot in an empty room

12 points; pair-optional

This is the first of two Picobot problems of the assignment, both of which you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Develop a set of rules that cause Picobot to completely cover an empty square room, regardless of where it starts within the room.

You may find it helpful to review the material on Picobot in Chapter 1 of the textbook and in the lecture notes.

Open the Picobot simulator, and modify/replace the existing rules with your own rules until you can get it to work. Whenever you modify the rules, be sure to click the Enter rules for Picobot button before you click Go.

As discussed in lecture, you should avoid repeat rules – two or more rules that would both be triggered by a given combination of state and surroundings.

When you are satisfied with your rules, copy them into a plain-text file called ps0pr1.txt. We encourage you to include comments that describe your rules. These comments should be preceded by a # symbol. For example:

# The following rule tells Picobot to ...

Hints:

• One possible approach is to begin with the four rules that are present in Picobot when you first load it in your browser. Try those rules on several different starting positions by repeatedly clicking the Reset button and then the Go button.

  Ask yourself: What portion of the overall task do these initial rules accomplish? What remains to be done? Then try to add rules that will cause the robot to move in ways that will complete the overall task of covering/vacuuming the entire room. You will also need to revise the second rule so that it doesn’t cause the robot to crash when it has a wall to its west.

• It’s worth noting that it’s perfectly okay if your new rules cause the robot to revisit portions of the room that it has already covered. More generally, your rules do not need to be efficient!

Optional extra challenge

for personal gratification only!

At the heart of computer science are questions of complexity and efficiency: questions about how simple, fast, etc. the solution to a problem can be. For an optional challenge, see if you can create a solution for problem 1 that uses only 6 rules! If you are able to do so, copy them into a plain-text file called ps0pr1extra.txt.

Note: Because reducing the number of rules to 6 is a completely optional challenge, we will not be answering questions about how to do so!

Problem 2: Picobot in a maze

13 points; pair-optional

This is the second of the two Picobot problems of the assignment, and you may complete it with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Develop a set of rules that enable Picobot to completely navigate a connected maze with corridors one square wide, regardless of its starting point. You can obtain an example of such a maze by opening the Picobot simulator and clicking on the right-arrow (-->) button below the lower right-hand corner of the room, which will show you this maze:

Modify/replace the existing rules with your own rules until you can get it to work. Whenever you modify the rules, be sure to click the Enter rules for Picobot button before you click Go.

As discussed in lecture, you should avoid repeat rules – two or more rules that would both be triggered by a given combination of state and surroundings.

When you are satisfied with your rules, copy them into a plain-text file called ps0pr2.txt. We encourage you to include comments that describe your rules. These comments should be preceded by a # symbol, as described in the earlier problem.

Hint: We strongly recommend that you take the approach outlined in lecture:

• using the right-hand rule
• having four states – one for each direction in which the robot could be facing
• starting with at least three rules for each state: one for when the wall is on your right and you are able to move, one for when you “lose the wall,” and one or two rules for hitting a dead end – i.e., for when you can no longer make progress in the current direction because there’s a wall in front of you.

Optional extra challenge

for personal gratification only!

See you if you can create a solution for problem 2 that uses only 8 rules. This is extremely challenging, and we don’t recommend starting with only 8 rules! Rather, begin by having at least 3 rules for each state as discussed in lecture, and then see if you combine rules in some way. If you are able to come up with a set of 8 rules that works, copy them into a plain-text file called ps0pr2extra.txt.

Note: Because reducing the number of rules to 8 is a completely optional challenge, we will not be answering questions about how to do so!

Problem 3: The four fours challenge

20 points; individual-only

The material needed for this problem will be discussed during the second week of lecture. You can find more information in the pre-lecture readings and videos for the first lecture on Python.

To begin, right-click on the following link, and then choose Download File As or Save Link As in order to download the file:
ps0pr3.py

Next, start up the program called IDLE that is part of the Python 3 distribution that you installed in Lab 0. Open ps0pr3.py in IDLE using the File->Open menu option.

In this problem you will write a simple Python program that computes the integers 0 through 4 using expressions involving exactly four fours and no other numbers. For example:

zero = 4 + 4 - 4 - 4
print('zero =', zero)

Your expressions may use any of the following operators: +, -, *, // (integer division), ** (power), and parentheses. Note that you should use the integer division operator (//) instead of the regular division operator (/), because the / operator will cause your results to include a decimal. For example, 4//4 will give you 1, but 4/4 will give you 1.0.

In ps0pr3.py, we have given you the two lines above for computing 0. You should add in the code needed to compute the integers 1 through 4 using four fours. For each integer, you should (i) assign the result of the computation to an appropriately named variable, and (ii) use a print statement to produce the appropriate output, following the model given for 0.

To test your code, use the Run->Run Module menu option in IDLE (or – even easier – press the F5 key!). Doing so will take you to a separate window for the Python Shell, where the output of your program will be displayed. The output should appear in a blue font, and it should look like this:

zero = 0
one = 1
two = 2
three = 3
four = 4

Notes:

• There are multiple ways to compute a given integer. For example, here is an alternative approach for 0:

  zero = 4//4 - 4//4

• We encourage you to try to come up with each of the expressions on your own. However, the real point of this problem is getting comfortable with Python, so if you have trouble coming up with an expression for a given number, feel free to ask a classmate or one of the course staff members, or to consult information about the four fours challenge that is available online. However, please do not post your expressions on Piazza for everyone to see.

Submitting Your Work

You should use Apollo to submit the following files:

• your ps0pr0.txt file containing your response to the reading for Problem 0

• your ps0pr1.txt file containing your solution for Problem 1; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner

• optional: your ps0pr1extra.txt file containing your solution to the optional extra challenge for Problem 1

• your ps0pr2.txt file containing your solution for Problem 2; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner

• optional: your ps0pr2extra.txt file containing your solution to the optional extra challenge for Problem 2

• your modified ps0pr3.py file containing your program for Problem 3

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate problem set section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.