โ“ ENGR131: Practice Final: Introduction to Programming for Engineers

Contents 

# You must make sure to run all cells in sequence using shift + enter or you might encounter errors
from pykubegrader.initialize import initialize_assignment

responses = initialize_assignment("1_practicefinal_q", "week_10", "practicefinal", assignment_points = 460.0, assignment_tag = 'week10-practicefinal')

# Initialize Otter
import otter
grader = otter.Notebook("1_practicefinal_q.ipynb")

โ“ ENGR131: Practice Final: Introduction to Programming for Engineers#

Practice Final#

The practice final is designed to help you prepare for the actual final exam. It is designed to be similar in format and difficulty to the actual exam. The practice final is graded and counts as 2% bonus points towards your final course grade.

Time Limit#

You will have 2 hours to complete the Final Exam. The actual final exam will be similar in format, difficulty, and scope as this practice final.

# Run this block of code by pressing Shift + Enter to display the question
from questions._1_practicefinal_q import Question1
Question1().show()

# Run this block of code by pressing Shift + Enter to display the question
from questions._1_practicefinal_q import Question2
Question2().show()

Question 3 (Points: 110.0): Introduction to Shape Analysis#

Shape analysis is a critical component in various fields such as manufacturing, engineering, and design. It involves examining the geometric properties of objects to understand their structure, function, and performance.In this problem, we will develop a package that can analyze different shapes, providing insights that can be used to optimize designs, improve manufacturing processes, and ensure quality control.

Question 3-Part 1 (Points: 3.0): Importing Functions#

Before you start, you need to import the necessary functions.

You need to import the following functions:

  • numpy

  • matplotlib.pyplot as plt

  • mpl_toolkits.mplot3d as Axes3D

...

grader.check("importing-functions")

Question 3-Part 2 (Points: 9.0): Building a Modular Function to Compute the Perimeter of a Shape#

We now want to build a modular function to compute the perimeter of a shape.The function should take a 2D array of shape (n, 2) as input, where n is the number of edge points of the shape. The function should return the perimeter of the shape as a float.

# define the function compute_perimeter
...
    """
    Compute the perimeter or total edge length of the shape.

    Parameters:
    edge_points (numpy.ndarray): A 2D array of shape (n, 2) representing the coordinates of the edge points of the shape.

    Returns:
    float: The perimeter or total edge length of the shape.

    The function calculates the differences between consecutive edge points, computes the Euclidean distance for each segment,
    and then sums these distances to obtain the total perimeter.
    """
    
    # use the np.diff function to calculate the differences between consecutive edge points, set the optional parameter axis to 0
    ...
    
    # use the np.linalg.norm function to calculate the Euclidean distance for each segment, and set the optional parameter axis to 1
    ...
    
    # return the sum of the segment lengths
    ...

grader.check("compute_perimeter-function")

Question 3-Part 3 (Points: 11.0): Building a Modular Function to Compute the Area of a Shape#

We now want to build a modular function to compute the area of a shape.

The function should take a 2D array of shape (n, 2) as input, where n is the number of edge points of the shape.

The function should return the area of the shape as a float.

\[ \text{Area} = 0.5 \times \left| \sum_{i=0}^{n-1} (x_i \cdot y_{i+1} - y_i \cdot x_{i+1}) \right| \]
# define the compute_area_2d function
...
    """
    Compute the area enclosed by a 2D shape using the Shoelace theorem.

    Parameters:
    edge_points (numpy.ndarray): A 2D array of shape (n, 2) representing the coordinates of the edge points of the shape.
                                 The first and last points must be the same to ensure the shape is closed.

    Returns:
    float: The area of the shape. If the shape is not closed, returns 0.0.

    The Shoelace theorem (or Gauss's area formula) is used to compute the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane.
    The formula is given by:
    
    Area = 0.5 * |ฮฃ (x_i * y_(i+1) - y_i * x_(i+1))| for i = 0 to n-1

    where (x_i, y_i) are the coordinates of the vertices of the polygon, and (x_(n+1), y_(n+1)) is the same as (x_0, y_0) to close the polygon.
    """
    # Check if the first and last points of the edge_points array are the same
    # This ensures that the shape is closed
    # if the shape is not closed, return an area of 0.0
    ...
    
    # Calculate the area using the Shoelace theorem
    # extract the x and y coordinates from the edge_points array, the first column is the x coordinates and the second column is the y coordinates
    ...
    
    # calculate the area using the Shoelace theorem
    # use the np.roll function to shift the x, y coordinates by one position to the left, this is how you get x_(i+1) and y_(i+1)
    # use the np.dot function to calculate the dot product of the x and y coordinates, this avoids the need to explicitly loop through the coordinates, or call the np.sum function
    # use the np.abs function to take the absolute value of the result
    # use the 0.5 * function to multiply the result by 0.5
    # store the result in the `shoelace_formula` variable
    ...
    
    # return the result
    ...

grader.check("compute-area-2d-function")

Question 3-Part 4 (Points: 12.0): Computing the Centroid of a Shape#

The centroid of a shape is the average of all the points in the shape.

The function should take a 2D array of shape (n, 2) as input, where n is the number of edge points of the shape.

The function should return the centroid of the shape as a numpy array of shape (2,).

\[ C_x = \frac{1}{6A} \sum_{i=0}^{n} \left( (x + x_{i+1}) \cdot (x \cdot y_{i+1} - x_{i+1} \cdot y) \right) \]
\[ C_y = \frac{1}{6A} \sum_{i=0}^{n} \left( (y + y_{i+1}) \cdot (x \cdot y_{i+1} - x_{i+1} \cdot y) \right) \]

Hint: make sure to notice the difference in the n value for the summation, and consider its influence on the rolling of the coordinates.

# define the compute_centroid function
...
    """
    Compute the centroid of a closed polygon considering the enclosed area, works in both 2D and 3D.

    Parameters:
    edge_points (array-like): A 2D array of shape (n, d) representing the coordinates of the polygon's vertices,
                            where d is 2 or 3 for 2D or 3D points respectively.
                            The first and last points must be the same to ensure the polygon is closed.

    Returns:
    numpy.ndarray: A 1D array of shape (d,) representing the coordinates of the centroid.

    Raises:
    ValueError: If the polygon is not closed (i.e., the first and last points are not the same).
               If the input points are not 2D or 3D.

    Notes:
    - The function uses different formulas for 2D and 3D centroids
    - If the area/volume is close to zero, the function falls back to computing the simple mean of the points.
    """
    
    # ensure the edge_points is a numpy array
    ...
    
    # Check dimensionality
    # ensure the edge_points is a 2D or 3D array, if not raise a ValueError
    ...
        
    # check if the edge_points is a closed polygon, if not raise a ValueError
    # a closed polygon is when the first and last points are the same
    ...
    
    # If points are 2D, use the 2D method
    ...
    
        # extract coordinates
        ...
        
        # compute area using shoelace theorem
        ...
        
        # if area is close to zero, return mean of points, setting the axis to 0 ensures that the mean is computed along the first dimension
        ...
            
        # compute 2D centroid
        # use the np.roll function to shift the x, y coordinates by one position to the left, this is how you get x_(i-1) and y_(i-1)
        # use the np.dot function to calculate the dot product of the x and y coordinates, this avoids the need to explicitly loop through the coordinates, or call the np.sum function
        # use the 1 / (6 * A) * function to multiply the result by 1 / (6 * A)
        # store the result in the `Cx` and `Cy` variables
        ...
        
        # return the result as a numpy array, the first element is the x coordinate and the second element is the y coordinate
        ...
        
    # For 3D points
    else:
        # For 3D points, compute centroid without duplicate points
        # Get unique points by removing duplicates use the np.unique function, the axis=0 argument ensures that the unique points are along the first dimension
        ...
        
        # compute the centroid of the unique points
        # use the np.mean function to compute the mean of the unique points, this is the centroid
        # make sure to set the axis to 0 to ensure that the mean is computed along the first dimension
        ...
        
        # return the result
        ...
        

grader.check("compute-centroid-2d-function")

Question 3-Part 5 (Points: 16.0): Compute the bounding box of a 2D shape.#

The bounding box of a 2D shape is the smallest rectangle that can contain the shape. The function should take a 2D array of shape (n, 2) as input, where n is the number of edge points of the shape. This is commonly used in machine learning tasks to identify the extent of the shape, and mark a detected object.

# define the compute_bounding_box function
...
    """Compute the bounding box of the shape."""
    # compute the bounding box of the shape and return the minimum and maximum values of the x and y coordinates
    # the return should be a tuple of two numpy arrays, the first array should contain the minimum values and the second array should contain the maximum values
    ...

grader.check("compute-bounding-box-function")

Question 3-Part 6 (Points: 14.0): Compute the curvature of a 2D shape at each edge point.#

It is helpful to compute the curvature of a 2D shape at each edge point, as this can be used to identify sharp corners and other features for subsequent machine learning tasks.

The curvature of a 2D shape at each edge point can be computed using the following formula:

\[ dx = \frac{d}{dx}x \]
\[ dy = \frac{d}{dy}y \]
\[ ddx = \frac{d}{dx}dx \]
\[ ddy = \frac{d}{dy}dy \]
\[ \kappa = \frac{\left| \frac{d^2 x}{dx^2} \cdot \frac{dy}{dx} - \frac{d^2 y}{dx^2} \cdot \frac{dx}{dx} \right|} {\left( \left(\frac{dx}{dx}\right)^2 + \left(\frac{dy}{dx}\right)^2 \right)^{\frac{3}{2}}} \]

This equation represents the curvature \(( \kappa )\) of a 2D parametric curve \((x(t), y(t))\), where:

  • \(( \frac{dx}{dx} )\) and \(( \frac{dy}{dx} )\) are the first derivatives (approximated using np.gradient).

  • \(( \frac{d^2 x}{dx^2} )\) and \(( \frac{d^2 y}{dy^2} )\) are the second derivatives.

  • The denominator normalizes the curvature by the squared first derivatives raised to ( 3/2 ).

# Write the compute_curvature_2d function
...
    """
    Approximate the curvature of a 2D shape at each edge point.

    Parameters
    ----------
    edge_points : numpy.ndarray
        A 2D array of shape (n, 2) representing edge points (x, y).
        
    Returns
    -------
    numpy.ndarray
        A 1D array of length n containing the curvature values at each edge point.

    Notes
    -----
    - The curvature is computed using:
      ฮบ = |x'' y' - y'' x'| / ((x'^2 + y'^2)^(3/2) + ฮต)
    - np.gradient() is used to approximate first and second derivatives.
    - A small epsilon (ฮต) is added to avoid division errors when the denominator is small.
    """


    # if the length of the edge points is less than 3, return an array of zeros, it is not possible to compute curvature
    # because there are not enough points to compute the derivatives
    ...

    # Extract x and y coordinates
    ...

    # Compute first derivatives
    # use the np.gradient function to compute the first derivatives
    ...

    # Compute second derivatives
    ...

    # Compute curvature based on the formula provided
    # add a small epsilon to the denominator to prevent division by zero this value should be 1e-8
    ...

    # return the curvature
    ...

grader.check("compute-curvature-function-2d")

Question 3-Part 7 (Points: 9.0): Compute key properties of a shape given its edge points.#

The shape properties are computed using the following functions:

  • compute_perimeter

  • compute_centroid

  • compute_bounding_box

# Write the compute_shape_properties function
...

    # compute the properties of the shape and store them in the `properties` dictionary
    # the keys for the base properties are "perimeter", "centroid", and "bounding_box", these are computed for all shapes
    ...
    
    # if the shape is 2D, compute the area and curvature
    ...
        # compute the area and curvature
        # store the results in the properties dictionary, with the keys "area" and "curvature"
        ...

    # return the properties dictionary
    ...

grader.check("compute-shape-properties-function")

Question 3-Part 8 (Points: 16.0): Plot a 2D shape and its centroid#

With any calculation, it is important to plot the results to check if they are correct. Plotting the results can provide you with a visual representation of the data, and help you identify any errors in the calculation.

In this question, you will write a function that plots a 2D shape and its centroid. The function should take a 2D array of shape (n, 2) as input, where n is the number of edge points of the shape. The function should also take an optional title argument, which is a string that will be used as the title of the plot.

The function should return the figure and axis object, which can be used to display the plot.

# Define a function plot_2d_shape_with_centroid that takes points and title as arguments
...
    """
    Plot a 2D shape and its centroid.

    Parameters:
    points (array-like): An array of shape (n, 2) representing the coordinates of the points that form the 2D shape.
    title (str): The title of the plot. Default is "2D Shape with Centroid".

    Returns:
    fig (matplotlib.figure.Figure): The figure object containing the plot.
    ax (matplotlib.axes._subplots.AxesSubplot): The axes object containing the plot.

    The function converts the input points to a NumPy array, computes the centroid of the shape,
    and then plots the shape and its centroid using Matplotlib. The centroid is marked with a red dot.
    The plot includes labels for the X and Y axes, a legend, a grid, and an equal aspect ratio.
    """
    
    # make sure the points are a numpy array
    ...
    
    # compute the centroid of the shape, using the compute_centroid function
    ...
    
    # plot the shape and its centroid
    # build a figure and axis object `fig` and `ax`, using the subplots module in matplotlib
    # make the figuresize (5, 5)
    ...
    
    # plot the shape and its centroid on the axis object `ax`, 
    # recall the shape of the points is (n, 2), where n is the number of points, and the first column is the x-coordinates and the second column is the y-coordinates
    # use the `plot` method to plot the shape, with 'o-' markers, with a marker size of 5, and a label of "Edge"
    # The `scatter` method to plot the centroid, with a marker size of 100, a label of "Centroid", and a zorder of 3 (zorder is the order of the elements in the plot, the higher the zorder, the closer to the front), and a color of 'red'
    # make sure to use the `*` operator to unpack the centroid coordinates
    ...
    
    # add a title to the plot from the optional title argument
    ...
    
    # add labels to the x and y axes, the labels should be "X" and "Y"
    ...
    
    # add a grid to the plot, using the `grid` method of the axis object `ax`
    ...
    
    # set the aspect ratio of the plot to be equal, using the `axis` method of the axis object `ax`
    ...
    
    # return the figure and axis object
    ...

grader.check("plotting-2d-shape-with-centroid")

Question 3-Part 9 (Points: 20.0): Plot a 3D shape#

Since we are not confined to 2D, we also need to be able to plot 3D shapes. In this question, you will write a function that plots a 3D shape. The function should take a 3D array of shape (n, 3) as input, where n is the number of edge points of the shape. The function should also take an optional title argument, which is a string that will be used as the title of the plot.

The function should return the figure and axis object, which can be used to display the plot.

# Define a function plot_3d_shape that takes points and title as arguments
...
    """Plot a 3D shape given its edge points.
    
    This function creates a 3D visualization of a shape by plotting its edges and centroid.
    The edges are connected in order of the provided points, so the points should form
    a continuous path that defines the shape's edges.
    
    Args:
        points (array-like): Array of shape (n, 3) containing the x, y, z coordinates 
            of n points that define the edges of the 3D shape. Points should be ordered
            to form continuous edges when connected sequentially.
        title (str, optional): Title for the plot. Defaults to "3D Edge Shape".
            
    Returns:
        tuple: A tuple containing:
            - fig (matplotlib.figure.Figure): The figure object containing the plot
            - ax (matplotlib.axes.Axes): The 3D axes object containing the plotted shape
            
    The plot includes:
        - Blue lines and markers connecting the edge points
        - A red marker showing the centroid
        - Axis labels for X, Y, and Z dimensions
        - A legend identifying the edges and centroid
        - The specified title
    """
    
    # Create 3D plot
    
    # create a figure and axis object, using the subplots module in matplotlib
    # use the subplot_kw argument to set the projection to 3d, this is done by passing a dictionary to the subplots function
    # set the figure size to 6 inches by 6 inches
    ...
    
    # Convert points to numpy array if not already
    ...
    
    # Plot the edges
    # use the plot method of the axis object `ax` to plot the edges of the shape, you need to pass the x, y, z coordinates to the plot method
    # use the `o-` marker to plot the edges, this is a blue line with blue markers at the vertices
    # use the `markersize` argument to set the size of the markers to 5
    # use the `label` argument to label the edges as "Edge"
    ...
        
    # Calculate and plot centroid
    # use the compute_centroid function to compute the centroid of the shape
    # use the scatter method of the axis object `ax` to plot the centroid, use the `color` argument to set the color of the centroid to red
    # use the `s` argument to set the size of the centroid to 100
    # use the `label` argument to label the centroid as "Centroid"
    # use the `zorder` argument to set the zorder of the centroid to 3
    # make sure to unpack the centroid tuple using the `*` operator so that you can plot multiple centroids if needed
    ...
    
    # Set labels and title
    # use the set_title method of the axis object `ax` to set the title of the plot
    # use the set_xlabel method of the axis object `ax` to set the label of the x axis to "X"
    # use the set_ylabel method of the axis object `ax` to set the label of the y axis to "Y"
    # use the set_zlabel method of the axis object `ax` to set the label of the z axis to "Z"
    ...
    
    # Only show one legend entry for edges
    # use the get_legend_handles_labels method of the axis object `ax` to get the handles and labels
    # use the zip function to pair the labels and handles together
    # use the dict function to create a dictionary from the paired labels and handles store this in a variable called `unique_labels`
    # use the legend method of the axis object `ax` to plot the legend, use the `unique_labels.values()` and `unique_labels.keys()` to plot the legend
    ...
    
    # return the figure and axis object
    ...

grader.check("plotting-3d-shape")

Examples to test the built functions#

Note you do not need to change the following code, it is provided for you.

import matplotlib
matplotlib.pyplot.close('all')
%matplotlib inline

# Define example 2D shapes
square = np.array([
    [0, 0], [1, 0], [1, 1], [0, 1], [0, 0]  # Closed loop
])

triangle = np.array([
    [0, 0], [2, 0], [1, 2], [0, 0]  # Closed loop
])

circle = np.array([
    [np.cos(theta), np.sin(theta)] for theta in np.linspace(0, 2*np.pi, 100)
])
# Example: Tetrahedron (can be any closed shape)
faces = np.array([
    [-0.5, -0.5, 0],  # Base square vertices
    [0.5, -0.5, 0],
    [0.5, 0.5, 0],
    [-0.5, 0.5, 0],
    [-0.5, -0.5, 0],  # Front triangle vertices 
    [0.5, -0.5, 0],
    [0, 0, 1],
    [0.5, -0.5, 0],   # Right triangle vertices
    [0.5, 0.5, 0], 
    [0, 0, 1],
    [0.5, 0.5, 0],    # Back triangle vertices
    [-0.5, 0.5, 0],
    [0, 0, 1],
    [-0.5, 0.5, 0],   # Left triangle vertices
    [-0.5, -0.5, 0],
    [0, 0, 1], 
    [-0.5, -0.5, 0],
])




# Compute shape properties
square_props = compute_shape_properties(square)
triangle_props = compute_shape_properties(triangle)
circle_props = compute_shape_properties(circle)

# Plot the shapes with centroids
plot_2d_shape_with_centroid(square, "Square")
print(square_props)
plot_2d_shape_with_centroid(triangle, "Triangle")
print(triangle_props)
plot_2d_shape_with_centroid(circle, "Circle Approximation")
print(circle_props)

# call the plot_3d_shape function with the faces array and the title "Pyramid"
plot_3d_shape(faces, "Pyramid")

Question 4 (Points: 84.0): Peano Curve Visualization Using Recursive Fractals#

Problem Statement#

The Peano curve is a self-similar fractal that recursively subdivides a space into a dense, space-filling pattern. Your task is to analyze and modify the given implementation of the Peano curve, which:

  • Uses recursion to generate the Peano curve of a given order.

  • Implements matplotlib.animation to dynamically visualize how the fractal is constructed.

  • Adjusts color dynamically based on the drawing progression.

Question 4-Part 1 (Points: 6.0): Importing Statements#

The first step in any python program is to import the necessary modules. In this question, you will import the necessary modules for the rest of the question.

# Import the necessary modules
# numpy as np
# matplotlib.pyplot as plt
# matplotlib.animation as animation
# from IPython.display import HTML
...

grader.check("import-statement")

Question 4-Part 2 (Points: 20.0): Peano Curve Function#

The Peano curve is one of the earliest examples of a space-filling curve, first described by Giuseppe Peano in 1890. It is a fractal curve that continuously maps a one-dimensional interval onto a two-dimensional space in such a way that, as its recursion depth increases, it completely fills a given area.

Algorithm#

1. Base Case#

If the recursion depth order is 0, return a single point (x, y).

2. Recursive Step#

  • Divide the square into 9 equal sub-squares.

  • Define the movement pattern to traverse the sub-squares in a continuous manner.

  • Recursively compute the Peano curve for each sub-square.

3. Movement Pattern#

The traversal follows this 3ร—3 order: 1 โ†’ 2 โ†’ 3 โ†“ โ†‘ โ†“ 6 โ† 5 โ† 4 โ†“ โ†‘ โ†“ 7 โ†’ 8 โ†’ 9

We will walk you through the implementation step by step.

# create the peano_curve function
# it accepts an order, and optional parameters x, y, and size, with defaults 0, 0, and 1 respectively.
...
    """
    Generates the Peano curve using recursion, a space-filling curve that maps a one-dimensional interval
    onto a two-dimensional space. The function recursively divides a square into 9 equal sub-squares and 
    traverses them in a specific order to form the Peano curve.

    Parameters:
        order (int): The recursion depth of the Peano curve. A higher order results in a more detailed curve.
        x (float): The x-coordinate of the starting point of the curve. Defaults to 0.
        y (float): The y-coordinate of the starting point of the curve. Defaults to 0.
        size (float): The length of one segment of the curve. This determines the size of the entire curve. 
                      Defaults to 1.

    Returns:
        List[Tuple[float, float]]: A list of (x, y) coordinates representing the points of the Peano curve.
                                   The list is ordered according to the traversal of the curve.

    The function works as follows:
    - If the order is 0, it returns a single point, which is a list containing the tuple (x, y).
    - For higher orders, it calculates the step size as the current size divided by 3.
    - It then iterates over a predefined movement pattern for a 3x3 grid, recursively calling itself to 
      generate sub-curves for each sub-square.
    - The results from each recursive call are combined into a single list of points, which is returned as 
      the final Peano curve.
    """
    # if the order is 0, return a single point, a list that contains the tuple (x, y)
    ...
    
    # Peano curve movement pattern (3x3 grid)
    moves = [
        (0, 0), (0, 1), (0, 2), 
        (1, 2), (1, 1), (1, 0), 
        (2, 0), (2, 1), (2, 2)
    ]
    
    # initialize an empty list to store the new points
    ...
    
    # calculate the step size, which is the size of the square divided by 3, you can save this to a variable called step
    ...
    
    # iterate over the moves, extract the dx and dy values
    ...
        # call the peano_curve function recursively to get the sub-curve
        # each time you call the peano_curve function, you should pass in the order - 1, 
        # the new x and y coordinates which is the current x + dx * step and the current y + dy * step
        # and the new size which is the step size
        ...
        
        # extend the list of new points with the sub-curve, use the extend method
        ...
    
    # return the list of new points
    ...

grader.check("peano-curve-function")

Question 4-Part 3 (Points: 18.0): Update Function#

We want to create an update function that will update the line plot of the Peano curve such that the color of the line changes as the animation progresses.

The update function should:

  • Update the line plot of the Peano curve

  • Change the color of the line based on the frame index

  • Return the line plot and the color

# create a function `update`l that accepts a frame, line, x_vals, and y_vals
...
    """Draw the Peano curve dynamically and change line color."""
    
    # Add error handling for the frame index
    # if the frame is less than 0, raise an IndexError
    # if the frame is greater than or equal to the length of the x and y values, raise an IndexError
    ...
    
    # update the line plot of the Peano curve
    # this is done by using the set_data method of the line plot
    # the first argument is the x values of the Peano curve
    # the second argument is the y values of the Peano curve
    # these use the global variables x_vals and y_vals
    # We want to index the x and y values from the start of the list to the frame index
    # frame should not be less than 0 or greater than the length of the x and y values
    ...
    
    # Change color based on frame index
    # we want to use the colormap viridis
    # you can import the colormap from plt.cm.viridis module
    # and index it with the frame index divided by the total number of frames
    # the color of the line can be set with the set_color method of the line object
    ...
    
    # return a tuple containing the line object -- make sure not to delete the , after line.
    return line,

grader.check("update-function")

Question 4-Part 4 (Points: 40.0): Parameters and Animation#

Now that we have the update function, we can create an animation of the Peano curve. We will guide you through the process.

out = plt.ioff()

# set the variable order equal to 3
...

# Call peano_cure with the order
# you can save the output to a variable called `points`
...

# unpacks and restructures the values list
x_vals, y_vals = zip(*points)

# Reduce the number of frames by rendering every other frame.
# Compute `reduced_frames` which is 1/2 the number of frames. Think what the requirements of a frame number are.
...

# use the range method to create a range which has the index of the frames to plot
# the range should start at 0 and end at the length of the x and y values
# the step should be 2
# save the output to a variable frames_to_render
...

# Create figure for animation
# create a figure and axis object, set the figsize to 6, 6
# use the subplots method to create the figure and axis object
...

# set the limits of the axis, set the x and y limits to -0.1 and 1.1
...

# set the ticks of the axis to be empty
# you can use the set_xticks and set_yticks methods to set the ticks to an empty list
...

# set the title of the axis, use an f-string to insert the order variable
# the title should be "Peano Curve (Order {order})", where order is the value of the order variable
# the fontsize should be 14 and the fontweight should be bold
...

# create a line object, set the line width using the optional parameter `lw` to 2, initially the line is empty
# you can use the plot method to create the line object
# the first argument is the x values of the Peano curve
# the second argument is the y values of the Peano curve
# This starts as an empty values
# save the output to a variable called line
# make sure to add a comma after line, the comma ensures that the line object is returned
...

# Create animation
# use the animation.FuncAnimation method to create an animation
# the first argument is the figure object
# the second argument is the update function
# the third argument is the frames to render
# the fourth argument is the interval, which is 10
# the fifth argument is the blit, which is True
# the sixth argument is the fargs, which is a tuple of the line, x_vals, and y_vals
# save the output to a variable ani 
...

# Display the animation in Jupyter Notebook
# use the HTML method to display the animation
# extract the HTML from the animation object, using the to_jshtml method.
# save the output to a variable html
...

out = plt.ion()

# uncomment it to display the animation
html

grader.check("parameters-and-animation")

Question 5 (Points: 63.0): ๐Ÿ”ฅBattle of the Code Realms! ๐Ÿฐโš”๏ธ#

Deep in the mystical land of Pythonia, where logic and randomness collide, two mighty champions prepare for an epic showdown! ๐Ÿ†

๐Ÿ‘Š The Warrior - A fearless brute with unshakable resolve, this battle-hardened fighter relies on consistent, crushing blows to vanquish foes. With 10 damage per swing, they believe in raw strength over fancy tricks. No magic, no luckโ€”just pure, unrelenting steel! โš”๏ธ๐Ÿ’ฅ

๐Ÿ”ฅ The Mage - A cunning spellcaster who harnesses the elements to rain destruction on their enemies! Their attacks are slightly weaker (8 damage), but watch out! Thereโ€™s a 30% chance theyโ€™ll unleash a devastating Fireball for an extra 5 damage! ๐ŸŽ† Will strategy and unpredictability triumph over brute force? ๐Ÿง™โ€โ™‚๏ธ๐Ÿ”ฅ

The rules are simple: They fight until one drops! Who will emerge victorious? The methodical Warrior? Or the chaotic, fireball-flinging Mage?

๐Ÿ’€ One shall stand. One shall fall.

โšก Let the battle begin! โšก

Question 5-Part 1 (Points: 2.0): Importing Functions#

The first step in any python program is to import the necessary modules. In this question, you will import the necessary modules for the rest of the question.

# Import from the abc module, the ABC and abstractmethod classes
...


# Import the random module
...

grader.check("Importing-Functions")

Question 5-Part 2 (Points: 12.0): Implementing the Character Class#

The character class is an abstract base class that defines the structure of a character in a role-playing game. It is a blueprint for creating specific character classes, such as Warrior and Mage.

# create a character class that inherits from the ABC class - the abstract base class
...
    """
    The Character class is an abstract base class (ABC) that represents a character in a role-playing game (RPG).
    This class cannot be instantiated directly and must be inherited by subclasses that implement the abstract methods.

    Attributes:
        name (str): The name of the character.
        hp (int): The hit points (health points) of the character.

    Methods:
        __init__(self, name, hp):
            Initializes a new character with the given name and hit points.
        
        take_damage(self, amount):
            Reduces the character's hit points by the specified amount. If the hit points drop below zero, they are set to zero.
        
        attack(self, target):
            Abstract method that must be implemented by subclasses. Represents an attack on a target character.
    """
    ...
        """
        Initializes a new character with the given name and hit points.

        Args:
            name (str): The name of the character.
            hp (int): The hit points (health points) of the character.
        """
        ...

    ...
    
        """
        Reduces the character's hit points by the specified amount. If the hit points drop below zero, they are set to zero.

        Args:
            amount (int): The amount of damage to inflict on the character.
        """
        ...

    ...
    
        """
        Abstract method that must be implemented by subclasses. Represents an attack on a target character.

        Args:
            target (Character): The target character to attack.
        """
        ...

grader.check("Character-class")

Question 5-Part 3 (Points: 11.0): Implementing the Warrior Class#

The Warrior class is a subclass of the Character class. It inherits the name and hp attributes from the Character class and implements the attack method.

...
    """
    Warrior class that inherits from Character. Represents a warrior character in the RPG game.

    Methods:
        attack(target):
            Attacks the target character, dealing a fixed amount of damage.

    Attributes:
        name (str): The name of the warrior.
        hp (int): The hit points (health) of the warrior.
    """
    ...
        """
        Attacks the target character, dealing a fixed amount of damage.

        Args:
            target (Character): The target character to attack. The target must have a take_damage method and a name attribute.

        The attack method performs the following steps:
        1. Sets a fixed `damage` value of 10.
        2. Calls the `take_damage` method on the target character, passing the `damage` value as an argument.
        3. Prints a message indicating the attack, the damage dealt, and the target's remaining HP.

        Example:
            warrior = Warrior(name="Conan", hp=100)
            enemy = Character(name="Goblin", hp=30)
            warrior.attack(enemy)
            # Output: "Conan attacks Goblin for 10 damage! Goblin HP: 20"
        """
        ...

grader.check("Implement-the-warrior-class")

Question 5-Part 4 (Points: 14.0): Implementing the Mage Class#

The Mage class is a subclass of the Character class. It inherits the name and hp attributes from the Character class and implements the attack method.

# implement the Mage class
...
    """
    Mage class inherits from Character and represents a mage character in the RPG game.

    Methods:
    - attack(target): Attacks the target character with a base damage and has a chance to deal extra fireball damage.

    attack(target):
        This method performs an attack on the target character. The attack consists of a base damage and a chance to deal extra fireball damage.
        
        Parameters:
        - target (Character): The character that is being attacked.

        The attack method works as follows:
        1. Sets a fixed `base_damage` value of 8.
        2. Calculates `fireball_extra` damage, which is an additional 5 damage with a 30% chance. You can use the `random.random()` function to generate a random number between 0 and 1.
            - If the random number is less than 0.3, `fireball_extra` is set to 5.
            - Otherwise, `fireball_extra` is set to 0.
        3. Computes the `total_damage` as the sum of `base_damage` and `fireball_extra`.
        4. Calls the `take_damage` method on the target character, passing the `total_damage` value as an argument.
        5. If `fireball_extra` damage is applied, prints a message indicating that the mage casts Fireball.
        6. Prints a message indicating the attack, the total damage dealt, and the target's remaining HP.

        Example:
            mage = Mage(name="Gandalf", hp=80)
            enemy = Character(name="Orc", hp=50)
            mage.attack(enemy)
            # Output: "Gandalf casts Fireball!" (if fireball_extra damage is applied)
            # Output: "Gandalf attacks Orc for 13 damage! Orc HP: 37" (example with fireball_extra damage)
    """
    ...

grader.check("Mage-class")

Question 5-Part 5 (Points: 17.0): Battle Simulation#

This function simulates a battle between two characters until one of them is defeated. It prints the progress of the battle, including each attack made by the characters, the remaining HP of the characters after each attack, and the outcome of the battle.

# define a function called battle that takes two parameters, character1 and character2
...
    """
    Simulates a battle between two characters until one of them is defeated.

    Parameters:
    character1 (Character): The first character participating in the battle. They deal damage first.
    character2 (Character): The second character participating in the battle. They deal damage second.
    
    Note: if a character has 0 HP or less, they are considered defeated and the battle ends, immediately printing the outcome of the battle.

    The function will print the progress of the battle, including:
    - The start of the battle with the message "Battle Start!".
    - Each attack made by the characters, including the attacker's name, the target's name, the damage dealt, and the target's remaining HP.
    - The remaining HP of the characters after each attack.
    - The outcome of the battle, indicating which character has been defeated and which one is the winner, with messages like "{character_name} has been defeated! {winner_name} wins!".

    Example Outputs:
    - "Battle Start!"
    - "Gandalf attacks Orc for 13 damage! Orc HP: 37"
    - "Orc attacks Gandalf for 10 damage! Gandalf HP: 40"
    - "Gandalf casts Fireball!"
    - "Gandalf attacks Orc for 18 damage! Orc HP: 19"
    - "Orc attacks Gandalf for 12 damage! Gandalf HP: 28"
    - "Orc has been defeated! Gandalf wins!"

    The battle continues in a loop until one of the characters' HP reaches 0.
    """
    ...

grader.check("battle-function")

Question 5-Part 6 (Points: 2.0): Calling the Function#

# Create characters
# instantiate the Warrior and Mage classes with the warrior name "Conan" and the mage name "Gandalf", 
# and 100 and 90 hit points respectively
...

grader.check("calling-the-function")

Question 5-Part 7 (Points: 5.0): Battle Simulation#

Makes the characters battle each other.

# Start the battle between the warrior and the mage, where the warrior deals damage first and the mage deals damage second
...

grader.check("battle-simulation-test")

Question 6 (Points: 59.0): Image Classification Using Random Forests#

Overview#

This question focuses on building an image classification model using Scikit-Image and Scikit-Learn. The task involves loading grayscale images, extracting edge-based features, and training a Random Forest classifier to distinguish between two classes: cats and dogs.

1. Loading Images#

The function load_images_from_folder(folder, label, size=(128, 128)) reads all images from a given folder, converts them to grayscale, applies transformations, and stores them as feature vectors.

2. Image Preprocessing#

The image_transformation(size, img) function:

  • Resizes images to a standard shape (128x128 pixels).

  • Applies Canny edge detection to capture contour-based features.

  • Flattens the resulting image into a 1D feature vector for model training.

3. Dataset Construction#

Images of cats (label = 0) and dogs (label = 1) are loaded from respective directories, combined into X (features) and y (labels).

4. Splitting Data#

A train-test split (80% training, 20% testing) is performed using train_test_split.

5. Training a Random Forest Model#

A Random Forest classifier with 100 trees is trained using the extracted features.

6. Evaluating Performance#

The accuracy of the model is printed for both training and test sets to assess generalization.

Question 6-Part 1 (Points: 4.0): Import Statements#

The first step of any data science project is to import the necessary libraries.

Import the following libraries:

  • os

  • numpy as np

  • matplotlib.pyplot as plt

  • from skimage import io, color, transform, feature

  • from sklearn.ensemble import RandomForestClassifier

  • from sklearn.model_selection import train_test_split

...

import shutil

# this unzips the datasets.zip file into the datasets folder
# do not modify this code
shutil.unpack_archive('datasets.zip', 'datasets')

grader.check("import-statements")

Question 6-Part 2 (Points: 14.0): Image Transformation#

Machine learning models expect that data has a certain shape, however sometimes images have a different shape. They need to be transformed to match the shape of the model. In this case we are going to use a random forest classifier, which expects a 1D feature vector.

Define the image_transformation(size, img) function that:

  • Resizes the image to the given size.

  • Applies Canny edge detection to the image.

  • Flattens the resulting image into a 1D feature vector.

# Define the image_transformation function
# it should take a size and an image
...

    # use the transform.resize function to resize the image to the given size
    # set the anti_aliasing parameter to True
    ...
    
    # use the feature.canny function to apply canny edge detection to the image
    ...
    
    # flatten the resulting image into a 1D feature vector
    ...
    
    # return the flattened image
    ...

grader.check("image-transformation")

Question 6-Part 3 (Points: 11.0): Loading Images from Folder#

It is important to build a utility function that can load images from a folder and return a list of images and their corresponding labels.

Define the load_images_from_folder(folder, label, size=(128, 128)) function that:

  • Takes a folder path, a label, and an optional size parameter (default is (128, 128)).

  • Reads all images from the folder and converts them to grayscale.

  • Applies the image_transformation function to each image.

  • Returns a list of images and their corresponding labels.

# Define the load_images_from_folder function
# it should take a folder path, a label, and an optional size parameter (default is (128, 128))
...
    """
    Load images from a folder, convert them to grayscale, apply image transformation, and return a list of images and their corresponding labels.

    Parameters:
    folder (str): The path to the folder containing images.
    label (str): The label to assign to each image.
    size (tuple): The size to which each image will be resized (default is (128, 128)).

    Returns:
    list: A list of transformed images.
    list: A list of labels corresponding to each image.
    """
    # build an empty list to store the images and labels
    ...
    # loop through the images in the folder
    # you can use os.listdir(folder) to get the list of images
   
    ...
    
        # you can use os.path.join(folder, filename) to get the path to the image
        ...
        
        # read the image using the io.imread function, set the optional argument as_gray to True
        ...
        
        # check if the image is not None
        ...
            
            # apply the image_transformation function to the image
            # image_transformation is defined in the previous cell, as a global function
            ...
            
            # append the transformed image and the label to the lists
            ...
    
    # return the lists of images and labels
    ...

grader.check("load-images-from-folder")

Question 6-Part 4 (Points: 30.0): Training and Evaluating the Model#

In this section we will train a random forest classifier and evaluate its performance.

We will use the load_images_from_folder function to load the images and the image_transformation function to transform the images.

Note: You will need to analyze the results of your model given the hyperparameters provided. It is helpful to first train your model and then build a seperate cell to analyze the results. In this way you do not need to retrain the model every time you want to change the analysis of the results.

np.random.seed(42)

# Load cats and dogs data
# use the load_images_from_folder function to load the images and the image_transformation function to transform the images
# the data is stored in the datasets/train/cats and datasets/train/dogs folders
# the labels are 0 for cats and 1 for dogs
# the size of the images is 128x128
# you need to save the results to the variables cat_images, cat_labels, dog_images, and dog_labels
...

# Combine data
# you need to combine the cat_images and dog_images into a single variable X
# you need to combine the cat_labels and dog_labels into a single variable y
# you can use the + operator to combine the lists
...

# Train-test split
# you need to split the data into training and testing sets
# you can use the train_test_split function to do this
# the test size is 0.2 and the random state is 42
# you should save the results to the variables X_train, X_test, y_train, and y_test
...

# Train Random Forest model
# you need to train a random forest classifier
# you can use the RandomForestClassifier function to do this
# the number of estimators is 100 and the random state is 42
# you should save the results to the variable rf_model
...

# This is a place where you can analyze the results of your model

...

grader.check("Train-and-evaluate-model")

# Run this block of code by pressing Shift + Enter to display the question
from questions._1_practicefinal_q import Question7
Question7().show()

Question 8 (Points: 60.0): ๐ŸŽฏ BONUS: Sudoku Solver โ€“ A Fun & Friendly Guide โœจ#

๐Ÿ“Œ How Does It Work?#

A Sudoku puzzle consists of a 9ร—9 grid where each row, column, and 3ร—3 box must contain the numbers 1 to 9 exactly once. Empty spaces are marked with '.', and our goal is to fill them correctly!

๐Ÿ”ข Steps to Solve Sudoku#

  1. Find an Empty Spot

    • Look for a cell with '.' (empty space). ๐Ÿ•ต๏ธ

  2. Try a Digit

    • Place a number from 1 to 9 and check: โœ… No duplicates in the row
      โœ… No duplicates in the column
      โœ… No duplicates in the 3ร—3 box

  3. Validate the Choice

    • If the digit follows the rules, keep it!

    • If not, remove it and try the next number.

  4. Backtrack if Stuck

    • If no valid digit fits, go back to the last step and try a different number. ๐Ÿ”„

  5. Repeat Until Solved

    • Continue the process until the board is completely filled. ๐ŸŽ‰

๐Ÿงฉ Example Input & Output#

โœ… Input Puzzle:#

Example 1#

Input:

board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]

Output:

[
    ["5","3","4","6","7","8","9","1","2"],
    ["6","7","2","1","9","5","3","4","8"],
    ["1","9","8","3","4","2","5","6","7"],
    ["8","5","9","7","6","1","4","2","3"],
    ["4","2","6","8","5","3","7","9","1"],
    ["7","1","3","9","2","4","8","5","6"],
    ["9","6","1","5","3","7","2","8","4"],
    ["2","8","7","4","1","9","6","3","5"],
    ["3","4","5","2","8","6","1","7","9"]
]

Explanation: The input board is shown above and the only valid solution is shown below.

Constraints#

  • board.length == 9

  • board[i].length == 9

  • board[i][j] is a digit or '.'.

  • It is guaranteed that the input board has only one solution.

Your code should implement a class Solution with a method solveSudoku that takes a 2D list of strings as input and returns a 2D list of strings as output. The output should be the solved sudoku board.

# import required libraries
from typing import List
# define the Solution class
class Solution:
    # Function to solve the Sudoku puzzle
    def solveSudoku(self, board: List[List[str]]) -> None:
...

grader.check("sudoku_solver")

Submitting Assignment#

Please run the following block of code using shift + enter to submit your assignment, you should see your score.

from pykubegrader.submit.submit_assignment import submit_assignment

submit_assignment("week10-practicefinal", "1_practicefinal_q")
Contents