Assignment 3. Sand

Due Monday, July 21 at 11:59 pm Pacific

  • Submissions received by due date receive a small on-time bonus.
  • All students are granted a pre-approved extension or "grace period" of 24 hours after the due date. Late submissions are accepted during the grace period with no penalty.
  • The grace period expires Tue, Jul 22 at 11:59 pm Pacific, after which we cannot accept further late submissions.
  • In this course, we express all date/times in Pacific time GMT -7. Our Paperless submission system also displays/records due dates and submission times in Pacific time.

Based on problems by Nick Parlante and Eric Roberts.

This assignment consists of a few different programs to give you practice with an assortment of topics we've seen recently in lecture: list of lists (2-dimensional lists), strings, and images in Python. We'll finish with a longer program called Sand, which uses lists of lists to form a grid through which grains of sand can fall. In order to download the starter code, please fill out the anonymous Mid-Quarter Class Survey. The starter code will be shown on the confirmation page after you submit the survey.

📦 Starter Code

Sandcastles

Zip Lists

In the file ziplists.py, implement the function

zip2lists(list1, list2)

This function is passed two lists of strings (list1 and list2), and you can assume that both lists have the same length (number of elements). The function should return a new list that "zips" together the two lists passed in. That is, the result should be a 2-dimensional list that contains lists that are pairs of elements, one from each of the original lists, in order. For example:

# calling this function:
zip2lists(["a", "b", "c"], ["d", "e", "f"])
# should return the following new list (of lists):
[["a", "d"], ["b", "e"], ["c", "f"]]

The original lists passed in should not be changed. If this function is passed two empty lists, it should just return an empty list, since there would be no lists (of pairs) in the result. In other words:

# calling this function:
zip2lists([],[])
# should return the following empty list:
[]

You can think of that as a list that contains no lists as elements.

Doctests are provided in the starter code for you to test your zip2lists function. You can run them by right-clicking on the doctests and then clicking "Run Doctest …" as we saw in class, or by running python3 -m doctest ziplists.py -v in the terminal (replacing python3 with py or python on Windows computers). Feel free to write additional doctests if you would like to test your code more thoroughly.

Expand Encoded Strings

One way of compressing text with many repeated characters is to use something known as run-length encoding. The idea is that rather than representing every character in a string explicitly, we instead have each character immediately followed by a digit which denotes how many times that character should be repeated.

For example, the string "B4" would be the encoding for the string "BBBB" as the character B is to be repeated 4 times. Similarly, the string "m1e2t1" would represent "meet". Thus, the general format for run-length encoded strings is a series of pairs, where each pair contains a single character followed immediately by a single digit (1 through 9 only, and the digit will never be 0). The digit denotes the number of consecutive occurrences of the character immediately before it in the encoded string.

In the file encoded_string.py, implement the function

expand_encoded_string(encoded)

that takes as a parameter encoded, which is a string representing the run-length encoded text, and returns a string which is the expanded version of the text.

# calling this function:
expand_encoded_string("B1o2k2e2p1e1r1!3")
# should return the following string:
"Bookkeeper!!!"

We've included doctests in the starter code for you to test your expand_encoded_string function. You can run them by right-clicking on the doctests and then clicking "Run Doctest …", or by running python3 -m doctest encoded_string.py -v in the terminal (replacing python3 with py or python on Windows computers). Feel free to write additional doctests if you would like to test your code more thoroughly.

Finding Forest Fires

⚠️ Before you get started on this part of the assignment, make sure that you have followed the Pillow installation instructions, which can be found on the Image Reference handout. If you cannot get Pillow installed successfully, please come to LaIR or post on the Ed forum for help.

We're going to write a function called highlight_fires in the file forestfire.py that highlights the areas where a forest fire is active. You're given a satellite image of the 2018 "Camp Fire" wildfire in California (credit: NASA), and your job is to detect all of the "sufficiently red" pixels in the image, which are indicative of where fires are burning.

We consider a pixel "sufficiently red" if its red value is greater than or equal to the average of the pixel's three RGB values times some intensity threshold. In this case, we have provided you with an appropriate intensity threshold of 1.35 via a constant named INTENSITY_THRESHOLD in the file forestfire.py.

When you detect a "sufficiently red" pixel in the original image, set its red value to 255 and its green and blue values to 0. This will highlight the pixel by making it entirely red. For all other pixels (i.e., those that are not "sufficiently red"), you should convert them to their grayscale equivalent, so that we can more easily see where the fire is burning. You can grayscale a pixel by summing together its red, green, and blue values and dividing by three (finding the average), and then setting the pixel's red, green, and blue values to all have this same "average" value. Once you highlight the areas that are on fire in the image (and grayscale all the remaining pixels), you should see an image like the one shown below on the right.

Original Image With Fires Detected

You can run your code by entering python3 forestfire.py in the terminal (replacing python3 with py or python on Windows computers).

For a helpful reminder about the SimpleImage library and tips on working with images, you can use the Image Reference handout.

Sand

For the final part of this assignment, you will write a program in sand.py, that uses 2-dimensional lists to to implement a kind of 2-dimensional (grid) world of sand. When the program is working, it's pretty fun to play around with.

This is a longer program, and we want the advantage of using decomposition to solve this problem in bite-sized chunks. So, we will build the program up as a series of decomposed functions. We can leverage doctests, testing each function in isolation before moving on to the larger functions.

The Sand world is represented using a 2-dimensional list (i.e., list of lists or grid) that keeps track of the elements in the Sand world. Each element (which you can think of as a square) in the Sand world holds one (and only one) of three things:

  • Sand, represented by the string 's'
  • Rock, represented by the string 'r'
  • Empty, represented by None (this is Python's None, not a string)

Here is a visual representation of a 3x2 grid (i.e., list of lists) with some rocks and one sand. The sand 's' is in the 0th row, 1st column (equivalently, x = 1, y = 0). Recall that y represents the row number and x is the column number. The 0th row (y = 0) is the top row.

Note that the strings here are shown with a single quotation mark, when in lecture we've seen strings with double quotation marks. Either are fine in Python!

This grid can be represented by a list of lists, as follows:

[['r', 's', 'r'], ['r', None, 'r']]

If we move the sand ('s') down from row 0, column 1 (x = 1, y = 0) to row 1, column 1 (x = 1, y = 1) the grid would looks like this:

This grid can be represented by a list of lists, as follows:

[['r', None, 'r'], ['r', 's', 'r']]

Moving sand down by one square like this is the central operation of this game, and moving down each piece of sand one square at a time creates the effect of falling sand you saw in the demo.

You should write your code in the following five stages, which accord with helper functions that you'll want to implement.

Moving Elements in the Grid

Function: do_move(grid, x1, y1, x2, y2)

Write the code for the do_move function. This function is passed a grid (list of lists, representing the Sand world, as described above) and two coordinate pairs: x1, y1 and x2, y2. The function should update the grid by moving the contents of the grid at location x1, y1 into the grid at location x2, y2. That means you should also update the element at position x1, y1 to reflect that this cell in the grid is now empty (None). You can assume that your function is only called with parameters for "legal" moves, that is, you can assume that all coordinates given to you are in the bounds of the grid and that the element at position x2, y2 starts empty. Your function should return the updated grid.

You may be wondering why your function needs to return the updated grid if changes you make to the grid parameter will persist after this function is done. The reason is that we provide doctests for your function and these tests work by examining what is returned by the function. So, for the doctests to work, your function needs to return the updated grid. You should use these doctests to test that your implementation works before you move on.

The code for do_move is short, but it is a good example of using doctests to try out test cases. Two doctests are provided. Feel free to add others to more thoroughly test your code. Doctest pro-tip: you can run a doctest by right-clicking on the doctest text and selecting the "Run Doctest …" option from the menu that pops up. Running a doctest again and again is common as you debug each function.

The first doctest we've provided looks just like the diagrams we explored above:

>>> grid = [['r', 's', 'r'], ['r', None, 'r']]
>>> do_move(grid, 1, 0, 1, 1) 
[['r', None, 'r'], ['r', 's', 'r']]

  1. [['r', 's', 'r'], ['r', None, 'r']] - This sets up a grid variable for the next 2 lines. The grid is tiny: width is 3 and height is 2, just enough to write a little test.

  2. do_move(grid, 1, 0, 1, 1) - This line calls your do_move function, moving the 's' at location (1,0) to location (1,1). The function returns the changed grid.

  3. [['r', None, 'r'], ['r', 's', 'r']] - This shows what the grid should look like post-move. The doctest machinery verifies that the result returned by the do_move function matches this expected output. Notice that the expected return is the only line that doesn't begin with >>>.

IMPORTANT NOTE: Recall that when you access elements of a list of lists, the first index represents the row, which is the y-coordinate. The second index represents the column, which is the x-coordinate. That's in reverse order of what we usually think of when dealing with (x, y) coordinates. To be more explicit, to access the element at location (x = 1, y = 0), you would do grid[0][1]. It's important to keep this point clear while you are developing your code for this assignment.

Function: check_move(grid, x1, y1, x2, y2)

Write the code for the check_move function. This function is given a starting (x1, y1) location and destination (x2, y2)location for a potential move, and returns True if the move is okay, or False otherwise. The grid is not changed by this operation.

We'll call location (x1, y1) the "start" of the move, and (x2, y2) the "destination" of the move. In the Sand world, there are five possible moves relative to the starting location: left, right, down, down-left, and down-right. Here are the rules for a legal move:

  • The destination must be in bounds.

Three doctests for this rule are provided. These tests build a 3 column by 2 row grid, checking that a few out-of-bounds moves return False.

>>> grid = [[None, 's', 'r'], [None, None, None]]
>>> check_move(grid, 0, 0, -1, 0) # x2 = -1 is out of bounds
False
>>> check_move(grid, 0, 0, 0, 4)  # y2 = 4 is out of bounds
False
>>> check_move(grid, 0, 0, 3, 1)  # x2 = 3 is out of bounds
False
  • The destination square in the grid must be empty (that is, it should contain None).

Here are some doctests we've provided to confirm that your function returns True or False depending on whether the destination square is empty.

>>> grid = [[None, 's', 'r'], [None, None, None]]
>>> # check of left move from (1,0)
>>> check_move(grid, 1, 0, 0, 0)  # left ok
True
>>> # check of right move from (1,0)
>>> check_move(grid, 1, 0, 2, 0)  # right blocked
False
>>> # check of down move from (1,0)
>>> check_move(grid, 1, 0, 1, 1)  # down, ok
True
  • For a diagonal down-left or down-right move, the "corner" must be empty (it should contain None).

Consider the down-left and down-right diagonal moves of a piece of sand at location (x=1, y=0) in a 3 column, 2 row grid:

The "corner rule" states that for a down-left or down-right move, the square above the destination must also be empty. So, in the picture above, the down-left is okay since location (0, 0) is empty, but down-right is bad due to the 'r' (rock) at location (2, 0). Sand ('s') at the same location (2, 0) would also block the move.

Note that the "corner rule" isn't referring to the four corners of the grid; any diagonal move within the grid has a "corner" (the square above the destination), even if it isn't in the corner of the grid.

We've provided two doctests for the corner rule, which match the diagram shown above:

>>> grid = [[None, 's', 'r'], [None, None, None]]
>>> # check of down-left move from (1,0)
>>> check_move(grid, 1, 0, 0, 1)  # down-left ok, corner rule
True
>>> # check of down-right move from (1,0)
>>> check_move(grid, 1, 0, 2, 1)  # down-right blocked, corner rule
False

All three of these conditions must be met for the move to be valid. There are many reasonable ways to structure your code for the check_move function. Our solution has a single return True at the bottom of the function, and many if ... : return False statements detecting the various cases where the move is bad. Use the doctests as you work out the code - you'll want these passing before you move on to the next section!

Note that it's fine to use == and != in comparisons like this:

if x != None:

Disregard warnings PyCharm gives you about the line above. The warnings, in this case, are misguided. PyCharm is pretty good, but it's not perfect.

Implementing Gravity

Function: do_gravity(grid, x, y)

Write the code for the do_gravity function. This function simulates the effect of gravity on a single piece of sand in the Sand world. Here's the basic set-up. Consider an (x,y) location in the grid (these are passed in as parameters to do_gravity). This function does one "gravity" move if there is sand at that (x,y) location as described below. In the gravity algorithm, the moves should be attempted in a specific order:

  1. If there is not a sand 's' at location (x,y), do nothing, the move is over.

  2. If the sand can move down, do it, this ends the move.

  3. Otherwise, if the sand can move down-left, do it, this ends the move.

  4. Otherwise, if the sand can move down-right, do it, this ends the move.

Note that these cases are mutually exclusive, meaning that only one move, if any, should occur. In all cases, return the grid when the function is done. As we talked about earlier in this assignment, you need to return the grid here so that the doctests for this function work appropriately.

Use the helper functions you wrote in the previous steps to do the heavy lifting of this function - that is the key to this function. How do you know if it's okay for sand to move from one location to another? You've got a helper function for that! We provide a set of doctests for this function, but you are always free to add more doctests if you like.

Looping Through the Whole Grid

Function: do_whole_grid(grid, brownian)

The next step is to write the code for the do_whole_grid function. For the moment, ignore the brownian parameter, which is handled in a later step.

To create the effect of falling sand, call do_gravity once for every (x,y) location in grid. The function should return the grid when it is done (again, the reason for this is to have some result returned from the function for doctests to compare against).

⚠️ Important note on looping through the grid: The standard y/x nested for loops to loop through the coordinates of a grid from the top row downward are usually fine for working with grids. However, in this case, it is important to reverse the y-direction to have the loop go bottom-up. That is, you should visit the bottom row (which is at y = height - 1) first and the top row (which is at y = 0) last. In this situation, it will be helpful to use the reversed function. The reversedfunction can be applied to a range to generate the elements of that range in reverse order. Here is an example of using the reversed function with range in a for loop:

for i in reversed(range(3)):
    print(i)

The code above would produce the following output:

2
1
0

What's wrong with the regular top-down order of going through rows? Suppose the loops went top-down, and at the top row (y=0), a sand moved from row 0 to row 1 by gravity. Then, when the loop got to y=1, that same sand would get to move again. Since behind the scenes, we're animating our Sand graphics using a similar technique to the animation loop we've seen before, we wouldn't want a single piece of sand to move more than once in a single timestep! Going bottom-up avoids this problem.

The do_whole_grid function just does one pass over the whole grid in the Sand world, calling do_gravity (and later, after you implement the next step, do_brownian) once for each square. The provided graphics code calls your do_whole_grid function again and again to run the whole simulation.

Milestone: Run sand.py!

With your functions tested, you can try running the whole program by entering python3 sand.py (replace python3 with py or python on Windows computers) into your terminal. Gravity should work, but "Brownian" is not done yet. Normally when a program runs the first time, there are many problems. But here we have leaned on decomposition and testing of the pieces as they were built, so there is a chance your code will work perfectly the first time. If your program works the first time, try to remember the moment. More typically, new code is not so well tested and so exhibits some bugs when run the first time.

When the Sand window comes up, you can click (and hold the mouse) anywhere in the window to start generating "sand" in the simulation. The radio-buttons for "Sand", "Rock", "Erase", and "Big Erase" allow you to generate different effects when you select them and the click in the window (allowing you to create rocks and also erase existing sand/rocks). You can turn on/off Gravity and Brownian motion using the respective checkboxes. Right now, Brownian should appear to do nothing.

Create Brownian Motion

Function: do_brownian(grid, x, y, brownian)

You're nearly there! Brownian motion is a real physical process, documented first by Robert Brown, who observed tiny pollen grains jiggling around on his microscope slide.

We'll say that doing a "Brownian" move for an (x,y) location means that there is a probability that sand at that location will randomly move just a little bit — one square left or right. The brownian parameter is an integer in the range 0 to 100 inclusive: 0 means never do a Brownian move, 100 means always do a Brownian move. This value is taken in real-time from the little slider at the top of the Sand application window. This function does not have tests (randomness and tests are an awkward combination).

Here are the steps for implementing Brownian motion in the Sand world:

  • Check if the square is sand. Proceed to the next steps only if it is sand. If it is not sand, the square cannot have Brownian motion.

  • Create a random number in the range 0 to 99. Note that the Python function random.randrange(n) (from the random library) returns a random number uniformly distributed in the range from 0 to n - 1, inclusive. So, you could use the following call:

num = random.randrange(100)

Proceed to step #3 below only if num < brownian (recall that brownian is a parameter to this function). In this way, for example, if brownian is 50, we'll do Brownian motion about 50% of the time.

  • To decide whether to move left or right, "flip a coin" by randomly generating a 0 or 1 like this:
coin = random.randrange(2)
  • If coin is 0, try to move the sand at the current (x,y) location one square to the left. If coin is 1, try to move the sand at the current (x,y) location one square right. Use your helper functions to check if the move is possible and then move the sand if so. Don't try both directions; if you flip a 0 and find that you cannot move left, do not try moving right.

After you have implemented the do_brownian function, you should edit the loop body in do_whole_grid so that after calling do_gravity for an (x,y) location, it also calls do_brownian for that (x,y) location.

Now, try running the Sand program from the terminal as you did before, and make sure the Brownian checkbox in the application is switched on. Hopefully, you'll see a lively, less artificial look. Play around with the slider (next to the Brownian checkbox) to create different levels of Brownian motion.

Wrapping Up

Give yourself a pat on the back - you've learned a ton over the course of this assignment! Check out these sections to learn some more about your wonderful new Sand program.

Running with Different Sizes

You can provide two command line arguments (numbers) to specify the number of squares wide and high that the grid should be in the Sand simulation. The following line would run the Sand simulation using a grid that is 100 by 50 squares:

python3 sand.py 100 50

An optional third command line argument specifies how many pixels wide each square should be. For example, the following line would run the Sand simulation with a 100 by 50 square grid, where each square was just 4 pixels:

python3 sand.py 100 50 4

Lots of Computation!

The Sand program may be pretty demanding on your computer - it's a lot of computation run continuously. You may notice the fans on your laptop spinning up. At the upper right of the window is a little gray number, which is the frames-per-second (fps) the program is achieving in the sand animation at that moment. The animation has a nice, fluid look when the fps is higher.

The more grid squares there are, and the more grains of sand there are, the slower the program runs. For each gravity round, your code needs to at least glance at every square and every grain of sand, and we want to do that 40 times per second. Play around with different grid and pixel sizes to try out the different aesthetics.

Extensions

Once you've completed all the required parts of the assignment, you might want to consider adding an optional extension. Remember not to modify your completed assignment files, but instead put the extension in a new file like extension.py.

While we aren't providing any guidelines for extensions, some ideas you might try out are:

  • Write a program that does the opposite of encoded_string.py - that is, it turns regular text into its run-length encoding.
  • Create a different image manipulation program.
  • Create a version of Sand with different physical properties.

Submitting Your Code

All assignments are submitted electronically through the Paperless website. Since this timestamp is based on the time that the server that receives the assignment, we recommend submitting with at least a few minutes to spare, particularly if you discover that your computer's clock is running slow.

Click on the link to Paperless above. Select the assignment you wish to submit (in this case, Assignment 3: Sand). You should upload all of the appropriate files for the chosen assignment. Please do not rename the files when you download them. Here are the files to submit for this assignment:

  • ziplists.py
  • encoded_string.py
  • forestfire.py
  • sand.py

If you did an optional extension on the assignment, be sure to submit that file too.

Once they have been uploaded and you have verified that you've included all of the files outlined in the assignment handout, hit the "Submit Assignment" button. You should always check the contents of your submission to make sure the code files are up-to-date and correct. To inspect the submission, click on the specific assignment and use the dropdown to view each file's contents.

Woohoo, you've finished assignment 3! 🎉 You can submit each assignment as many times as you would like by following the instructions outlined in this document. However, your section leader will grade only the most recent submission.