This example is thanks to Jill Su, contributed in an earlier edition of this book.
Student: Professor, I have a question. I was getting seats at a movie for me and some friends this weekend. They had assigned seats, and a whole screen that showed the number of empty seats, and also options like “find 3 seats together”. How would I program that?
Prof: Great question. I’m going to lift out a specific, simple version for our discussion – for each seat we will just track a single
boolean for if it is occupied or not. We can grow it into something more complex later if we want.Student: I’m OK with that.
Prof: Let’s think about what data we need to store – what types might make sense based on what we’ve seen?
Student: I guess there are a lot of seats, so an array?
Prof: Ah interesting idea; arrays will almost certainly be involved. Let’s look at a picture to help guide our thinking.
Prof: Let’s first start by making three definitions, one per row. What might that look like?
Student: Hmm there would be three rows. Like
boolean[] topRow = { true, false, true, true, true, true }; and then the second row would be like { true, false, false, false, true }Prof: Good. So I see you’ve picked
true for “seat available” and false for “not available”. Seems good. So then we need a little new insight if we want to represent the whole theater – we can store all of these array references in another array.Student: In another array?
Prof: That’s right. We can have types like
boolean[][] which means “array of array of booleans”. Or, super precisely, “array of references to boolean arrays”. Let’s write the code and look at a memory diagram.Prof: So if we wanted to represent this as a record, we might have something like this:
record Theater(boolean[][] seats) { }and then we can start to ask questions like “how many empty seats”.
Student: Ah, ok, so you’re thinking like
int emptySeats() as a method on Theater?Prof: Right, and getting that right will teach us about arrays of arrays. What do you think the loop will look like?
Student: Well, it’s like a counter pattern, right? We learned about those.
Prof: Indeed. If we have a loop that just needs to look at all the elements of a 2d array and count them, we can use a nested loop that matches the idea of nested arrays:
Student: OK, I think I get it. So each time through the outer loop,
row stores one of the array references. Then the inner loop works with that.Prof: Right!
Practice
Trace
theater.emptySeats(). For each run of the outer loop, how many times does the inner loop’s body run, and what is howMany when the inner loop finishes?row is top: the inner body runs times, and then howMany is row is middle: the inner body runs times, and then howMany is row is bottom: the inner body runs times, and then howMany is