Programming Assignment 2 (Toothpick Sequence)

Write a Python program that draws the "toothpick" pattern (Wikipedia page) on a canvas of size 1000x1000 pixels. The program should take as command line input the number of iterations to draw. Besides displaying the pattern on the canvas in a separate window, the program should print the number of toothpicks added in each iteration as well as the cumulative number of toothpicks after each iteration. A sample run is shown below along with the canvas.

mirage:toothpicks raj$ python3 Sketch.py 12
Iteration #0: #Toothpicks added in this iteration: 1, Total #toothpicks: 1
Iteration #1: #Toothpicks added in this iteration: 2 Total #toothpicks: 3
Iteration #2: #Toothpicks added in this iteration: 4 Total #toothpicks: 7
Iteration #3: #Toothpicks added in this iteration: 4 Total #toothpicks: 11
Iteration #4: #Toothpicks added in this iteration: 4 Total #toothpicks: 15
Iteration #5: #Toothpicks added in this iteration: 8 Total #toothpicks: 23
Iteration #6: #Toothpicks added in this iteration: 12 Total #toothpicks: 35
Iteration #7: #Toothpicks added in this iteration: 8 Total #toothpicks: 43
Iteration #8: #Toothpicks added in this iteration: 4 Total #toothpicks: 47
Iteration #9: #Toothpicks added in this iteration: 8 Total #toothpicks: 55
Iteration #10: #Toothpicks added in this iteration: 12 Total #toothpicks: 67
Iteration #11: #Toothpicks added in this iteration: 12 Total #toothpicks: 79
Iteration #12: #Toothpicks added in this iteration: 16 Total #toothpicks: 95
mirage:toothpicks raj$

To draw the toothpick pattern, you will use the graphics.py package. The documentation for this package is available at John Zelle Python Book.

Toothpick Pattern Rules

1. A toothpick is depicted in the canvas as a line segment (say 63 pixels in width).
2. We start at iteration 0 with a toothpick in the horizontal direction in the middle of the canvas. When we place the toothpick, we can use the center of the toothpick as the reference point, i.e. if we are placing it horizontally, the left end can be placed 31 pixels to the left of the center point and the right end can be placed 31 pixels to the right of the center point.
3. In general, given a configuration of toothpicks in the canvas, at the next iteration we add as many toothpicks as possible, subject to certain conditions:
   • Each new toothpick must lie in the horizontal or vertical directions.
   • Two toothpicks may never cross.
   • Each new toothpick must have its midpoint touching the endpoint of exactly one existing toothpick.
   • The toothpick sequence (#toothpicks after each iteration) is the following (until a certain number of iterations):

     0, 1, 3, 7, 11, 15, 23, 35, 43, 47, 55, 67, 79, 95, 
     123, 155, 171, 175, 183, 195, 207, 223, 251, 283, 
     303, 319, 347, 383, 423, 483, 571, 651, 683, 687, 
     695, 707, 719, 735, 763, 795, 815, 831, 859, 895, 
     935, 995, 1083, 1163, 1199, 1215, 1243, 1279, 1319, 1379
     

Tips

1. It will be convenient to design a Toothpick class that encapsulates all information about the toothpick, such as the direction (vertical or horizontal) and the location (x,y) coordinate on the canvas. This class can have the following methods:
   • show() to display the itself on the canvas.
   • toothpickToAddA() returns a new Toothpick object that can be added at one of it's ends; if the end is blocked then return None.
   • toothpickToAddB() returns a new Toothpick object that can be added at the other end; if the end is blocked then return None.
   Note: you will need to decide the parameters for these methods.
2. So that you do not draw the same toothpick object more than once, you may choose to use an instance variable to indicate if the toothpick is a new toothpick in the current iteration or is one from a past iteration. This will speed up the drawing.
3. You should write the main code in a file called Sketch.py. This should initialize the canvas and set up a for-loop to go through the iterations. The Toothpick class can be imported in this file.

What to submit?

1. Toothpick.py
2. Sketch.py