T-Th 9:05
or
T-Th 11:15
in Olin 155

CS 1110: Introduction to Computing Using Python

Fall 2012

Assignment 4:
Turtles

Due to CMS by Tuesday, October 23rd at 11:59 pm

Computer graphics can be tricky, and you often need a lot of experience with programming before you can get started. However, for over forty years, the LOGO Turtle has allowed elementary-school students to draw cool and interesting shapes on their computer. And if they can do it, so can you.

The Turtle is a cursor on the screen that uses a Turtle for its icon. To draw a line, you push the Turtle forward. The screen draws a line of the same color as the Turtle (which can be changed at any time) along its path of movement. To draw more interesting shapes, you simply change the direction of the Turtle. With a few more commands you can even draw solid shapes.

While programming languages have come a long way since the early days of LOGO, the graphics Turtle lives on. Every major programming language, from C/C++ to Java to Python, has a version of the Turtle. For today's assignment you get to participate in this 40 year tradition, and hopefully have some fun in the process.

You only have a week and half to do this assignment, but you get two full weekends. In the past we have found this to be more than enough time for this assignment. Again, please remember to fill out the survey telling us how long you worked on this assignment.

Learning Objectives

This assignment serves several important roles.

  • It introduces you to the famous Turtle, which is a great way to learn a new language.
  • It gives you experience with writing simple for-loops.
  • It gives you experience with recursion.
  • It gives you experience with complex objects that have both attributes and methods.
  • It gives you experience with using helper functions to assert common preconditions.

Contents


Before You Get Started

Academic Integrity

This is a classic assignment that we are giving again because students really like it. That being said, to maximize your educational experience in working with this assignment, we require that you do not look at code from related assignments in previous runs of this course, or at other people's code from this semester. Also, do not share your code with others, in this semester or with students in future semesters. We prohibit this behavior because engaging in it so would help no one in the long run.

In this assignment, it is highly unlikely that your code for this assignment will look exactly like someone else's. We will be using Moss to check for instances of cheating and plagiarism. Anyone caught using files that are obviously identical to other students will be prosecuted, with the end result perhaps being to fail the course.

Collaboration Policy

You may do this assignment with one other person. If you are going to work together, then form your group on CMS as soon as possible. If you do this assignment with another person, you must work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping.

With the exception of your CMS-registered partner, you may not look at anyone else's code or show your code to anyone else, in any form whatsoever.

Assignment Scope

This is the first assignment that you do not need to create a unit testing module for. You will mostly be looking at visual output (graphics) to determine correctness.

To save you time, we have given complete specifications of most of the methods you are to write. Study them carefully. Note how precise and thorough they are. You should aim for this level of quality when you start to write your own specs.

Assignment Source Code

The first thing to do in this assignment is to download the zip archive A4.zip from this link. You should unzip it and put the contents in a new directory. As with the previous assignment, this directory will contain several files:

a4.py
This is the primary file that you will need to modify and the only file that you will submit for a grade.
colormodel.py
This is the colormodel module from the previous assignment. It is slightly different from that version; we have reimplemented str() and we have tweaked it a bit so the colors work with the Turtle.
cturtle.py
This is the module that provides the Turtle. You will need to create a Window to draw on first.
pencil.gif
This is an icon which we use when we draw with the Pen instead of the Turtle.

In addition to all of these files, we have provided you with some documentation on how to use the Window, Turtle, and Pen objects. You will find this useful in this assignment.

Getting Help

If you do not know where to start, if you do not understand loops or recursion, or if you are completely lost, please see someone immediately. This can be the course instructor, a TA, or a consultant. Do not wait until the last minute, particularly since this assignment is more complex than previous ones. A little in-person help can do wonders. See the staff page for more information.


Turtle Graphics

Python actually has a built-in Turtle provided by the Turtle module. However, we find this module a bit confusing to use, particularly for a beginner. Instead, we provide an alternative Turtle, which we call the Cornell Turtle. This Turtle is in the module cTurtle.py which should remain in the same folder as your assignment.

The module cTurtle actually provides three classes: Window, Turtle, and Pen. In this section, we talk about each one of these in turn. In addition, we have provided a quick documentation reference if you just want to quickly look at the methods and attributes of each of these classes.


Window

The Window class is very similar to the one that you played with in Lab 2. To create a window, you simply use the constructor Window() and assign the result to a variable. Try this command at the interactive prompt:

>>> import cTurtle
>>> w = cTurtle.Window()

This will display a window on your screen. The window object has several attributes that you can change.
Attribute Meaning Invariant
w.x x-coordinate of top left corner Must be an int
w.y y-coordinate of top left corner Must be an int
w.width Width of the window in pixels Must be an int
w.height Height of the window in pixels Must be an int
w.title Title at top of window Must be a string

In addition, there are two important methods:

w.clear()
This erases the contents of the Window. It removes all drawing, and detaches any Turtles so that they no longer work.
w.bye()
This closes the Window permanently.

Turtle

The Turtle class is used to draw on your Window. Each Turtle object t has the following important attributes:
Attribute Meaning Invariant
t.x x-coordinate of the Turtle Must be an int or float.
Cannot be altered directly
t.y y-coordinate of the Turtle Must be an int or float.
Cannot be altered directly
t.heading Turtle heading in degrees counter-clockwise from east. Must be an int or float.
t.color Current Turtle color Must be a string, an RGB object, or an HSV object.
t.speed The drawing speed of this Turtle. Must be an int 1 (slowest) to 10 (fastest), or 0 (instantaneous)
t.visible Whether the Turtle icon is visible. Must be a bool
t.drawmode Whether the Turtle should draw anything when it moves; if False, nothing is drawn. Must be a bool

To create a Turtle, you use the constructor Turtle() which takes a single argument: the Window that you want to draw on. Assuming that you made a Window object w in the previous section, try the following at the interactive prompt:

>>> t = cTurtle.Turtle(w)
You should now see a (red) Turtle on your Window!

The fact that Turtle and Window are separate allows you to have as many Turtles as you like so that you can draw different things with them. If at any time you have too many Turtles, use the method w.clear(). This removes all Turtles from the Window (which means that attempts to do anything with any old Turtles will fail), so you will need to add a brand new Turtle to start drawing again.

Position and Orientation

The position and heading of the Turtle are maintained using floating point numbers. This is needed for accuracy. If integers were used, errors would be introduced after only a few calculations. However, whenever a point is to be drawn in the window, its x- and y-coordinates are rounded to the nearest integer because the pixel coordinates are represented as integers.

The direction of the Turtle is called its heading. It is a number representing the angle in degrees counterclockwise from east (to the right). Thus east is 0 degrees, north is 90 degrees, west is 180 degrees, and south is 270 degrees. Negative angles and angles greater than 360 are allowed; the remainder modulo 360 is used.

While the heading attribute can be modified, the x and y attributes cannot. You can only control the Turtle's position via the methods listed below.

Important Methods

In addition to its attributes, a Turtle object t has several important methods:

t.forward(dist)
Moves the Turtle dist pixels in the direction of its current heading. If the drawmode is True, a line is drawn; otherwise, no line is drawn.
t.backward(dist)
Moves the Turtle dist pixels in the opposite direction of its current heading. If the drawmode is True, a line is drawn; otherwise, no line is drawn.
t.left(a)
Rotates the Turtle in place a degrees counterclockwise.
t.right(a)
Rotates the Turtle in place a degrees clockwise.
t.move(x,y)
Moves the Turtle t to pixel (x,y) without drawing anything.

Note that most of these methods are used to move the Turtle about the screen. This is why the attributes x and y cannot be altered directly (e.g. you cannot assign values to them). You should use these methods instead.

Colors

To change the Turtle color, you assign a new value to the color attribute. You can use the RGB and HSV objects from the last assignment; that is why we provided you with a new copy of colormodel.py. You cannot use a CMYK object; that color model is designed for printing, and not for displaying on your screen.

The Turtle also supports strings as colors. Just put the name of the color that you want in quotes; make sure the name is all lower case. For example, to make your Turtle blue, try

>>> t.color = 'blue'

Speed

The speed of the Turtle can be controlled. It is a number in the range 1 ≤ speed ≤ 10, with 1 slowest and 10 fastest. You can also set the speed to 0, which causes shapes to be drawn with no animation. However, even when the speed is set to 0, you will see the the Turtle draw each line individually, so sometimes shapes can take a while to draw (this is an unfortunate issue with the way the Turtle is implemented in Python).


Drawing with the Turtle

Throughout this assignment, you will be asked to draw shapes with a Turtle. There are three ways to do this. The first is to type Turtle commands directly in the Python interactive shell. You should do this right now to familiarize yourself with the Turtle class and its methods. For example, try these commands:

>>> from cTurtle import *
>>> w = Window()
>>> t = Turtle(w)
>>> t.color = 'green'
>>> t.forward(100)
>>> t.color = 'red'
>>> t.right(90)
>>> t.forward(150)

As you type the lines up to and including t = Turtle(w), you'll see a window appear with a Turtle at the center facing west. As you type the other commands, the Turtle will change color, move, and draw lines.

The second way is to add new procedures to the module a4.py and call them from the interactive prompt. If you look at the file, you will notice that it contains a procedure draw_two_lines. We gave you this procedure to show you how to write a graphics helper function. Note that it takes the Window object as an argument, so it does not create a new window. It also does not clear the Window, though we might want our other functions to do that. All it does is create a Turtle, and use that Turtle to draw two lines.

To try out this function, navigate to the directory containing the file a4.py and start up the interactive prompt. Then type:

>>> from cTurtle import *
>>> w = Window()
>>> import a4
>>> a4.draw_two_lines(w,2)
This will draw two lines in the window w, at speed 2. Study the body of draw_two_lines, as it will help you with all of the tasks in this assignment.

Finally, you will note that at the very end of the file a4.py there is some code

if __name__ == '__main__':
    main()
This means that you can run a4.py as an application. From the command shell (Terminal in OS X, Command Prompt in Windows), type
python a4.py
When you do this it will execute the main() function, which calls each of the procedures that you are supposed to implement. After it calls each procedure, it will pause until you hit return in the command shell. Of course, right now it does not do much. That is because you have not implemented any of these procedures yet.

For the remainder of this assignment, you will be writing procedures that draw shapes, much like draw_two_lines. As you write a procedure, refer constantly to the specification. Follow it carefully. If you have to call another procedure, look at its specification and make sure you follow it. A huge number of programming errors arise from not following specifications carefully.


Pen

Objects of type Pen are very similar to Turtle objects, except that they draw a bit differently. Creating a Pen is similar to creating a Turtle. At the interactive prompt try

>>> from cTurtle import *
>>> w = Window()
>>> p = Pen(w)
You should now see a pencil icon on your Window. If you do not, it is likely that you forgot to put the file
pencil.gif in this folder.

A Pen object has a lot of attributes in common with Turtle. However, it does not have a heading attribute. Instead, for a Pen object p, you draw with the following methods.

p.drawLine(dx,dy)
Draws a line starting from the current Pen position with distance dx pixels along the x-axis and dy pixels along the y-axis.
p.drawCircle(r)
Draws a circle of radius r (in pixels) centered at the current Pen position.
p.move(x,y)
Moves the Pen p to pixel (x,y) without drawing anything.

Solid Shapes

The Pen also does not have a drawmode attribute. The three methods listed above either always draw (drawLine, drawCircle) or never draw (move). Instead, the Pen has a fill attribute. When this attribute is True, the Pen will enter into a "fill mode". Anything that is drawn between now and when the attribute becomes False or when a call to move is made will result in a solid shape.

For example, to draw a solid square, try the following sequence of commands with your Pen.

>>> p.fillcolor = 'blue'
>>> p.fill = True
>>> p.drawLine(0,50)
>>> p.drawLine(50,0)
>>> p.drawLine(0,-50)
>>> p.drawLine(-50,0)
>>> p.fill = False
When you finish, the pen will fill the insides of the square with the color blue.

Because the pen can draw solid shapes, it actually has two color attributes: fillcolor and pencolor (there is no simple color attribute in Pen). The fillcolor is the color it uses inside a solid shape, and pencolor is the color for hollow shapes as well as the border of solid shapes.


Assignment Instructions

This assignment is broken up into four tasks. Each task corresponds to a procedure stub in a4.py. You will find this assignment to be a lot easier if you complete and fully test one task before moving on to the next. We do not require that you make a unit test this time. To test our your function, simply comment out or add commands to the body of the function main().

The function main() is what is executed when you run this module as an application. It is there to help you with your testing. Feel free to change it however you wish. We will not look a the body of this function in testing your solution.


Asserting Preconditions

As we saw in class, it is very helpful to assert your preconditions when you are using recursion or iteration. This keeps you from being caught in an (effectively) infinite loop.

Through out the code in a4.py, we have placed assert statements in the various function stubs. However, we do not guarantee that they are enough. When you complete a function, we expect that you fully check your precondition with assert statements. If the provided assert statements do not fully check your precondition, then you must add more.

To help you with this process, we have provided you with several helper functions at the very top of a4.py. All of these helper functions return a boolean value: True or False. These helper functions are to be used inside of an assert to check part of a precondition, as shown throughout the code. We guarantee that each function precondition can be fully checked by some combination of the provided helper functions.

This strategy of using helper functions to check preconditions is a common one in programming. Many of these functions have very similar preconditions. Furthermore, these preconditions can be quite complex (particularly the one shown in valid_color()). Instead of writing the same complex boolean expression over and over again, we write it once in the body of a helper function and call the helper function each time.


Task 1. Triangles

Complete the procedure draw_triangle(t,s,c). This procedure is given a Turtle as a parameter. You do not need to make a new Turtle, nor a new Window.

This procedure should draw an equilateral triangle of side length s and color c using Turtle t. It should draw the triangle using t's current position and orientation. The Turtle should end its drawing at the same position and orientation as when it started. Do not save the Turtle's position and orientation at the beginning and then restore them at the end. If you draw the triangle correctly, following the instructions in the procedure specification, then this should happen automatically.

To try out the procedure, type the following in the interactive prompt.

       
>>> from cTurtle import *
>>> from a4 import *
>>> w = Window()
>>> t = Turtle(w)
>>> draw_triangle(t,200,'green')


Task 2. Hexagons

Complete the procedure draw_hex(t,s). This method should draw six equilateral triangles using color 'orange' with side lengths s. This triangles should form a hexagon, as illustrated to the right. Follow the specification and hints carefully. In particular, be sure to use a helper function.

For both draw_triangle and draw_hex, it is very important that you follow the specifications. If you do not follow the specifications exactly, we will deduct points.


Task 3. Radial Shapes

Choose two (and only two!) from the following three activities: spirals, polygons, or radiating lines. Once you have done two of these, you are free (but not required) to do the remaining one. These are pretty fun assignments. If you decide to do all three, we will grade you on the best two.

Each of these tasks involves creating a helper procedure. In each case, the main procedure does not have a Turtle as parameter, but its helper procedure does. The main procedure clears the Window, creates a Turtle, calls the helper procedure to do the work, then hides the Turtle. Note that some of these procedures are very particular about which way that the newly created Turtle should start out facing. Remember that you can control the facing of your Turtle via the heading attribute.

When writing these procedures, write the main procedure first, then the helper, and finally test both by calling the first one in the interpreter.

If the main procedure is foo, its associated helper is called foo_helper. We have created stubs for these procedures in a4.py. Do not change the headers (either the names or the parameters), as our grading software will be calling them by those names. Just fill in the bodies.

Once again, it is very important that you follow the specifications for all of the three procedures below. If you do not follow the specifications exactly, we will deduct points.

Spirals

The first picture to the right is done by drawing 10 lines. The lines have length 10, 20, 30, ... . After each line, the Turtle turns left 90 degrees. The second diagram to the right shows a similar spiral but with the Turtle turning left 75 degrees after each line.

Complete the procedures draw_spiral and draw_spiral_helper. When you first test them, use 10 for the initial len. Try different angles, like 90 degrees, 92 degrees, 88 degrees, etc. Use sp = 1 to see the lines drawn slowly.

You will be amazed at what these procedures do. Find out by trying these calls (after creating window w):

draw_spiral(w, 8, 1, 90, 300)
draw_spiral(w, 8, 1, 135, 400)
draw_spiral(w, 9, 1, 60, 100)
draw_spiral(w, 9, 1, 121, 500)
draw_spiral(w, 10, 1, 89, 400)
draw_spiral(w, 10, 1, 150, 300)
draw_spiral(w, 10, 1, -144, 500)

Polygons

The first image to the right is a 9-sided polygon. The second image to the right is a series of 40 5-sided polygons of side length 35, the first started at angle 90, the second at an angle of 90 + 360.0/40, the third at an angle of 90 + 2*360.0/40, and so on. This demonstrates the kind of cool pictures you can draw just with polygons.

Complete the procedures multi_polygons and multi_polygons_helper so that your program can draw such designs. You should use the procedure draw_polygon, which we have provided, as a helper function. When finished, experiment to see what neat designs come out. For example, try the following (after creating window w):

multi_polygons(w, 10, 45, 3, 100)
multi_polygons(w, 10, 60, 30, 20)

Radiating Lines

The picture on the left consists of 15 lines of the same length radiating out from the initial Turtle position. The angle between the lines is the same. The second picture has 720 lines. If n lines are drawn, the angle between them is 360.0/n. Furthermore, the color of each line depends on the angle (i.e. the direction) of each line. A line drawn at angle ang is drawn with HSV color HSV(ang, 1.0, 1.0).

Up until now, we have been using strings for our color names. However, the Turtle color attribute will take an HSV object as well. Just assign the object to the attribute and start drawing. This should make this part of the assignment fairly straightforward. Remember the invariants for an HSV object.

Complete the procedures radiate and radiate_helper. When finished, test them with small values of n, like 4 or 8. After the procedures are completely tested, try them with 360 lines of length 200. Also, try 3000 lines and Turtle speed 0 (which still takes a while because of how the Turtle draws), and notice how much more filled in the disk becomes.


Task 4. Recursive Graphics

In this task, we ask you to use recursion to draw some interesting shapes. Choose two from the following three activities: the Sierpinski triangle, the Grisly snowflake, and the H-tree. Once you have done two of these, you are free (but not required) to do the remaining one. Again, if you do all three, we will grade the best two.

Throughout all three of these tasks, we ask that you use a Pen instead of a Turtle because (1) there is no need to maintain the direction and (2) Pen methods can draw solid shapes. See the overview of the Pen above for more information.

As with the radial shapes, for each of these recursive tasks, you should write two procedures, a main procedure and a helper. The main procedure clears the Window and creates a new Pen. It also calls the helper to do the drawing, then cleans up afterward. The main procedure does not have a Pen as a parameter (though it does have the Window as a parameter), while the helper does. Also, the helper is recursive because it calls itself, while the main procedure is not recursive.

Once again, it is very important that you follow the specifications for all of the three procedures below. If you do not follow the specifications exactly, we will deduct points.

Sierpinski Triangles

To the right you see three equal-size Sierpinski triangles of depth 0, 1, and 2, respectively. A Sierpinski triangle of size s and depth 0 is just an equilateral triangle of side length s. A Sierpinski triangle of size s and depth 1 consists of three Sierpinski triangles of size s/2.0 and depth 0 arranged in the orientation shown. A Sierpinski triangle of size s and depth 2 consists of three Sierpinski triangles of size s/2.0 and depth 1. In general, a Sierpinski triangle of size s and depth d > 0 consists of three Sierpinski triangles of size s/2.0 and depth d-1.

We have stubbed in the procedures sierpinski and sierpinski_helper for you to complete. We have provided a procedure fill_triangle, which you can use to draw a solid triangle. This procedure is needed only at depth 0.

The most difficult part may be to determine the placement of the three subtriangles in the recursive calls. You will need to know the height of an equilateral triangle with side length s. You can use the Pythagorean theorem to figure this out. Using h for the height, visualize a triangle that is 1/2 of the equilateral triangle, with side lengths s, s/2.0, and h. Then solve the formula s2 = (s/2)2 + h2 for h. Alternatively, if you know some trigonometry, there is a simple formula involving the sine function, using the fact that the interior angle of an equilateral triangle is 60o. The sqrt or sin functions from the Python math module will be useful here.

Grisly Snowflakes

To the right are three grisly snowflakes of depth 0, 1, and 2. A depth-0 snowflake is simply a filled-in hexagon. A depth-1 snowflake of side length s consists of seven depth-0 hexagons, each of side length s/3.0. In general, a grisly snowflake of side length s and depth d > 0 consists of seven grisly snowflakes, each of side length s/3.0 and depth d-1.

As with Sierpinski triangles, the difficulty with grisly snowflakes of depth d will be calculating the placement of the seven grisly snowflakes of depth d-1. Hint: the distance between the centers of the depth d-1 snowflakes on the same horizontal row is 2*s/3.0. Try to figure it out for yourself, but if you run into trouble, please get help from the course staff.

We have stubbed in the procedures grisly and grisly_helper for you to complete. The first does not have a Pen as a parameter; the second one does. We have also supplied the procedure fill_hex for you to use to draw a solid hexagon.

As a word of warning, a depth-3 Grisly snowflake appears to take up to 30 seconds to draw, even with animation speed set to the fastest possible. This is an unfortunate issue with the way Turtles and Pens works in Python, and we are not going to be able to fix this until a later semester (which we will do by reimplementing them from scratch).

H-Trees

H-trees are useful in designing microprocessor chips. The lines represent wires that connect circuit components in a tree of interconnections without wires crossing.

To the right are shown three H-trees of size s and depths 0, 1, and 2, respectively. To draw them, implement this set of instructions as given:

  1. Draw an H with all three lines of length s.
  2. If d > 0, draw four H-trees of size s/2.0 and depth d-1. The centers of the four H-trees are at the top and bottom of the two vertical lines drawn in the previous step.

We have stubbed in two procedures Htree and Htree_helper for you to complete. The first does not have a Pen as a parameter, the second one does. We have also stubbed in the helper procedure drawH, which you may complete and use if you like, although you are not required to. You should draw the lines by using the methods drawLine and move in your Pen object.


Finishing the Assignment

Once you have everything working you should go back and make sure that your program meets the class coding conventions. In particular, you should check that the following are all true:

  1. There are no tabs in the file, only spaces (recall, tabs look like arrows if whitespace is visible)
  2. Functions are each separated by two blank lines.
  3. Lines are short enough that horizontal scrolling is not necessary (about 80 chars is long enough).
  4. The specifications for all of the functions are complete.
  5. Specifications are immediately after the function header and indented.
  6. All preconditions in the newly defined functions are fully checked and asserted.

Furthermore, at the top of a4.py you should have three single line comments with (1) the module name, (2) your name(s) and netid(s), and (3) the date you finished the assignment.

We highly recommend that you look at your module one last time and make sure that you have followed all of the specifications exactly (e.g. is the Turtle or Pen hidden, or is it still visible); you don't want to lose points for not following the specifications.

Turning it In

Upload the file a4.py to CMS by the due date: Tuesday, October 23rd at 11:59 pm. Do not submit any files with the extension/suffix .pyc. It will help to set the preferences in your operating system so that extensions always appear.

Survey

In addition to turning in the assignment, we ask that you complete the survey posted in CMS. Once again, the surveys will ask about things such as how long you spent on the assignment, your impression of the difficulty, and what could be done to improve it. Please try to complete the survey within a day of turning in this assignment. Remember that participation in surveys comprise 1% of your final grade. Remember that individuals must complete the survey, even if done as a group.