☰ Contents Nested and 2D Structures

Sitting with Friends

Student: OK, now that we’ve done that, what does the program look like to check if there are enough seats next to each other?
Prof: Ah great question. I think this is a good one to break down into a helper and then answer the overall question. Let’s build it up. Back to the image – say we want 3 seats together. The top row has enough, right?
Three rows of theater seats facing a stage: row 1 has 4 seats, row 2 has 5, row 3 has 6. Taken seats are shaded.
Student: Right.
Prof: Did you need to look at any of the other rows to determine that?
Student: I guess not?
Prof: That’s interesting, because whether or not a row has enough seats is just a property of one boolean[] array, not of the whole theater.
Student: I can see that.
Prof: And then if any row has enough seats next to each other, then the theater itself has such a row.
Student: Yeah, I buy that.
Prof: OK, so let’s write the helper first. What do you think it takes as arguments?
Student: I guess just boolean[] row?
Prof: Anything else? Will it always check for 3 seats in a row?
Student: Oh right, so I guess also an int for how many seats we want.
Prof: And in our simple example for now, what does it return?
Student: A single boolean – whether or not the row had enough seats
Prof: This one is worth tracing from the beginning! It has some interesting ideas. It’s kind of a counter loop, but it also has another pattern – a search that returns as soon as it finds the answer. The return in the loop returns from the whole method. So if we ever find target adjacent seats, we return true immediately. We only return false if we get through the whole array without finding a sequence like that.
Student: It’s also weird because we don’t use seats at all in the method. So we say theater.rowHasSeats(top, 3) but we never use any of the fields from theater.
Prof: That’s a good observation! Helper methods are often like that; they just work with the data they are given. The methods that call them will look up the right data for them to use.
Student: OK so let’s build the method that uses seats?
Prof: Right. I would say this is a search method on the seats array. It returns true as soon as it finds a row with enough seats, using the helper.
Student: Huh, so it’s kind of like a nested loop, but the inner loop is inside another method.
Prof: That’s right! I think the tricky logic is mostly in the helper – the incremental counter. So I find that I can read this a little easier because each method has its own job.
Student: Could you write it as one bigger nested loop and get the same answers?
Prof: Absolutely. This breakdown is more about how I chose to think about the problem. There are many ways to make it work!

Practice

Here is a later showing, where the only three free seats together are in the bottom row:

boolean[] lateTop = { false, true, true, false, true, false };
boolean[] lateMiddle = { true, true, false, true, true };
boolean[] lateBottom = { false, true, true, true };
boolean[][] lateSeats = { lateTop, lateMiddle, lateBottom };
Theater late = new Theater(lateSeats);

How many times does each call below call rowHasSeats, and what does it produce?

theater.hasSeats(3) calls rowHasSeats time(s) and produces
late.hasSeats(3) calls rowHasSeats time(s) and produces
late.hasSeats(4) calls rowHasSeats time(s) and produces