Lab 09 - Functional Programming

Due by 11:59pm on 2023-07-13.

In this lab, you're to look at some functional programming concepts using the Grid class you've been developing and random numbers.

Starter Files

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab.

Random numbers

Remember from lecture, we can use random numbers in our program by importing from the random library. Some of the useful functions from this library include:

  • seed(n) – sets the initial seed value. If no argument given or n=None, uses the system time
  • randrange(stop) – generate a random number from 0 to stop-1
  • randrange(start,stop) – generate a random number from start to stop-1
  • randint(a,b) – generate a random number from a to b (inclusive)
  • random() – generate a floating-point number between 0.0 and 1.0
  • uniform(a, b) – generate a floating-point number between a and b
  • choice(seq) – randomly select an item from the sequence seq

Q0: Printing the Grid

In your lab09.py file, there is a print_grid() function that takes as input a Grid object and prints it out row by row. Take a look at this function and discuss the following with your lab group:

  1. There is a conditional statement in the print() statement in the innermost for loop.
grid.get(x,y) if grid.get(x,y) is not None else 0

Do you understand what it is doing?

  1. Is this function a pure or non-pure function? Why?

Q1: Random Rocks and Bubbles

Write a function random_rocks which takes a Grid object and chance_of_rock where chance_of_rock is floating point number between 0 and 1 that represents the probability that a rock should be placed in any given location. The function will return a Grid object with rocks placed in it.

def random_rocks(grid, chance_of_rock):
    '''Take a grid, loop over it and add rocks randomly 
    then return the new grid. If there is something already
    in a grid position, don't add anything in that position.'''
    "*** YOUR CODE HERE ***"

This lab is about functional programming and one of the ideas in that programming paradigm is to try to make our functions as "pure" as possible. And that means that the function should have no side effects or in other words, not change any of the object passed to it.

By default when we pass in our Grid object, any set() operation we perform on it will change the original Grid that we pass in. So if we want this to be a pure function, we need to start by making a complete copy of the Grid. As part of Homework 3, you'll be adding a copy() method to the Grid class that will do this. For now, we'll just take advantage of Python's deepcopy() function. You invoke it like this:

from copy import deepcopy

my_copy = deepcopy(original_object)

Start by making a deep copy of the input grid. Then loop over the grid copy and if there is nothing there, randomly choose to add a rock, represented by 'r', based on chance_of_rock. Since chance_of_rock is a number between 0 and 1, generate a random number in that range and add a rock if that number is less than or equal to chance_of_rock.

Note: You shouldn't call random.seed anywhere in your code, as the autograder will be calling it so that your modified grid matches the key. Additionally, to this end, you should iterate over the input grid row by row from top to bottom, left to right.

Once you're done, return the updated copy of the grid. You should test that you're not changing the original grid in your function. Create a small grid, call your random_rocks() function and assign the return value to a new name, then call print_grid() to print the original and new grid. Are they the same? You might want to pass in a fairly large value for chance_of_rock to make sure some rocks are created.

Similarly write a function random_bubbles which takes a Grid. Loop over grid and if there is nothing there, randomly choose to add a bubble 'b' based on the chance_of_bubbles parameter.

def random_bubbles(grid, chance_of_bubbles):
    '''Take a grid, loop over it and add bubbles 'b' randomly 
    then return the new grid. If there is something already
    in a grid position, don't add anything in that position.'''
    "*** YOUR CODE HERE ***"

Take a minute and think about the two functions you just wrote. Discuss the following with your lab group and TA:

  • Are these pure functions?
    • Do they return a value of some sort?
    • Do they have side effects?
    • Are they affected by external state beyond the parameters passed in?
  • If they are not pure functions, can you think of any way to make them so?
  • Is there any penalty for writing these as pure functions? If so, what is it?

Q2: General grid modifications

Since these functions act almost the same, we can create a higher-order function that generalizes the behavior. Finish the modify_grid which can take in a Grid (grid), a function (func), and a probability (prob).

It should loop through the grid like the previous functions. If the same conditions are true call func to modify the grid then return it. Modify random_rock and random_bubbles to call this new function.

def modify_grid(grid, func, prob):
    """Write a function which can take in a grid, a function
    and a probablily as parameters and updates the grid using
    the function passed in."""
    "*** YOUR CODE HERE ***"

Notes:

  • func should take in two variables representing the (x, y) coordinates in the grid to update
  • modify_grid() may not be a pure function. This is because variables in the expression part of lambda functions are bound in the frame where the lambda is defined. Thus if I call modify_grid() from random_rocks() and the lambda function I pass in operates on a variable named grid it will look up the name grid in random_rocks()—not modify_grid()—even though the function is being executed in modify_grid().

Q3: Bubble Up

Write a function bubble_up which takes in a grid, x and y coordinate. The x and y coordinate should give you a bubble and moves the bubble one row up, replacing its former position with None. Then it returns the modified grid. (Remember to use the deepcopy function)

Note: You can assume the given x, y coordinate contains a bubble. Also, make sure you're not modifying the original grid.

def bubble_up(grid,x,y):
    """
    Write a function that takes a bubble that is known 
    to be able to bubble up and moves it up one row.
    """
    "*** YOUR CODE HERE ***"

Q4: Move Bubbles

Write a function move_bubbles that finds all the bubbles in a Grid object and checks if each bubble can move up. If it can, the function moves it up. After checking all the bubbles, the function returns the grid. Bubbles can only move up if the space above them is empty. Also, they cannot move out of the grid. (Remember to use the deepcopy function)

def move_bubbles(grid):
    """
    Write a function that loops over the grid, finds
    bubbles, checks if the bubble can move upward, moves
    the bubble up.
    """

Before you start implementing this, think about the code you've already written. Can you leverage any of those methods to simplify your work in this one?

Once this is done, you can call the animate_grid() function provided in lab09.py to see an animation of the bubbles floating up in your grid. You need to run this in the terminal to get the best effect.

Submit

If you are not in lab today, submit your lab09.py file along with your Grid.py file to Gradescope to receive credit. Submissions will be in Canvas.

Otherwise, thanks for coming to lab! You don't have to submit anything.

© 2023 Brigham Young University, All Rights Reserved