Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC108 Lab 7: Nested Lists & Loops

October 30th – November 3rd 2023

1 Introduction

Welcome to your seventh lab in CSC108! The lab for this week will (rather extensively) test your knowledge of lists and loops. You should be familiar with loop conditions and list slicing before you start on the lab. The starter code for this week is named lab7.py.

2 Problem Introduction

This lab consists of one large problem, which is broken up into three smaller parts to make it more manageable.

The overarching problem we want to solve for this lab is:

Given a representation of a 2D surface (as nested list of 1’s and 0’s), find the area of the largest rectangle that is present on the surface. A rectangle in this case is a m ×n portion of the surface such that all positions within this portion contain a 1. In other words, this means that the rectangle we are finding has to be a solid rectangle that is unbroken and continuous. The area of this rectangle then, is the number of 1’s that it contains (equal to m × n). This problem by itself might be harder than it looks, so lets first look at how we might solve a subset of the problem, as detailed in the paragraph below.

Instead of trying to figure out what the area of the largest rectangle in the whole matrix is, we first figure out what the area of the largest rectangle is for a given point on the matrix. This means that for a given x, y coordinate on the matrix, we figure out the area of the largest rectangle whose top left corner starts at that point.

Take for example this nested list: 

If we look at the position <2, 0> (0 indexing), we see that there are two potential rectangles that can be formed. One length-wise which produces a rectangle of area 5 (red), and one height-wise which produces a rectangle of area 2 (green). We want our function for this sub-problem to return the largest of these rectangles, and so in this case it would return 5. Keep in mind that rectangles need not be only one row or column, they could consist of multiple rows and columns, like the one you see at position <1, 2> with an area of 6 (blue), which happens to be the largest rectangle in the whole matrix.

Admittedly, this problem is harder than those seen in the previous labs, so here are some guiding points to get you started. You must complete the tasks below in order, as each task builds on the previous one, and for each function you need to make use of the previous one as a helper.

1. First, make sure the function longest chain that you’ve written last week is correct. You’ll need to use this function for the next part. If you didn’t get it quite right last week, don’t worry, this is your chance to fix it before you continue with this lab!

2. Once you have completed the helper function, you can start implementing largest at position, which makes use of longest chain. The main idea here is to loop through every row at the specified column and check how many consecutive 1’s there are on each row (beginning at that column). We suggest drawing this out on paper and coming up with a few test cases yourself to try to visualise it. It really is quite interesting. Note: visualisation is an important tactic programmers use to help problem solve, this is a chance for you to practice this skill!

3. While looping through the rows, you’ll find that you need about three variables, one to keep track of the maximum sized rectangle you’ve seen so far, and another to keep track of the number of rows you’ve seen. We’ll leave the third variable for you to figure out, but it has something to do with the longest chain function you just wrote. It’s important to note that in order for longest chain to work properly, you’ll need to pass it a list that starts at the position that you are interested in, so there’s some list slicing to do on each row here. Once you have the loop set up and have all the variables updating correctly, some simple arithmetic in every loop should be able to get you the rectangle size on each iteration. The idea here is that for every loop, you need to calculate the largest rectangle that you can form from the part of the matrix you’ve seen so far. And the largest of these rectangles is the largest rectangle at this position. (This step is the most tricky!)

4. Finally, once largest at position is working correctly, the final function is easy to implement. Implement largest in matrix by looping through each position in the matrix and calling largest at position. The largest rectangle in the matrix must be the largest rectangle in all of the positions.

3 Demo application

We are distributing a demo application called lab7 demo application.py for the purpose of assisting you with this lab. This demo application allows you to randomly generate a matrix and run largest at position or largest in matrix on it. You can also provide your own matrix. We hope this lends a hand in helping you tackle the lab!

4 Sanity Checks

Often we forget to do our own sanity checks, so this is a reminder. Have you:

1. written at least 3 doctests per function and ensured that they pass? (you must do this)

2. considered edge cases in your doctests?

3. uploaded your file to MarkUs and run the student tester?

Remember: you should be running the student tester and using the student correctness and style results to refine your submission. Submit your code often and ahead of time!

Did you know?!? that you can lookup PyTA error codes on the PyTA documentation site? If you get style error, PyTA produces an error code (shown as E####) in the feedback file to the left of the error. It turns out that the PyTA documentation actually explains why the error occurs and even how to fix it!

5 Final Check!

Once you are finished, submit lab7.py to MarkUs. All done! This lab exercise was a small taste of what is known as an algo-rithmic question. If you found it fun, you’ll learn more about algorithms in CSC236 and CSC263 (and other year 3 and 4 courses).

For those of you who finished early and like a challenge, the instructor solution for largest at position is implemented in just 5 lines of code, including the return statement. Take a crack at beating that :) (and let us know on Piazza if you do!)