ICS 32 Winter 2022, Notes and Examples: Two-Dimensional Lists

Background

In a project earlier this quarter, you implemented a Connect Four game. The game logic itself — the actual implementation of the rules of the game — was provided in a module called connectfour.py, but even if you didn't look through the module's code, some of the details of its implementation were made clear to you while you worked on the project. Connect Four is a game whose playfield is a two-dimensional grid, with tiles being dropped into columns from the top or popped from columns at the bottom; for that reason, connectfour.py organized the playfield as a two-dimensional list (i.e., a list in which each element is a list), the most natural way to store a simple grid or matrix structure in Python, with the list primarily containing each of the playfield's columns in a sublist, and each element of the sublist being one row of that column. So, for example, the playfield might be represented like this (with some spacing added to make the structure clearer):

[[0, 0, 0, 0, 1, 2],
 [0, 0, 0, 2, 2, 1],
 [0, 0, 0, 0, 1, 1],
 [0, 0, 0, 1, 2, 2],
 [0, 0, 0, 0, 1, 2],
 [0, 0, 2, 1, 1, 2],
 [0, 0, 0, 0, 0, 1]]

We used named constants, as well, so we could refer to the 0, 1, and 2 in our code as EMPTY, RED, and YELLOW, which aided readability further; being able to call things what they are, instead of some encoded version of what they are (e.g., RED instead of 1), is one of the hallmarks of well-written, maintainable code.

While it's important to note that this arrangement was the most convenient way to implement various parts of the game logic — e.g., dropping and popping pieces, which had an effect on only one column (and therefore only one sublist) — you faced the problem that this arrangement wasn't the right one to show to a human user, who would want to see the columns vertically and the rows horizontally. So you had to write a function that could present that same playfield like this:

.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  .  Y  .
.  Y  .  R  .  R  .
R  Y  R  Y  R  R  .
Y  R  R  Y  Y  Y  R

which actually underscores an important point about how you choose data structures when you write programs. The right thing to do is to choose the data structure that leads to the best outcome within your program, so the most important and frequently-used operations can be implemented in a way that is time- and memory-efficient and, hopefully, relatively simple. At the cost of making the problem of printing the board a little more complicated (because we needed to print the board primarily in order of the rows, even though this was different from how the data was stored), all of the other algorithms were made simpler (because so many other things involved only a single column, which means only a single sublist). All in all, this was a good trade, though it might not have seemed like it to you at the time, since I was the primary beneficiary as the author of connectfour.py, and you bore the cost of writing the function to print the board.

Writing functions in Python that process two-dimensional lists might well have been new territory for you when working on that project, but there was relatively little code to write, since so much of th game's logic was provided in connectfour.py. In Project #4, you'll need to implement the game logic for a different game, whose rules are quite different from Connect Four's, but whose playfield is structurally similar — the game is played on a rectangular grid on which jewels of various colors are moved around. As in connectfour.py, a reasonable choice for storing the game board would be a two-dimensional list, but this time you'll be responsible for all of the game logic. So before you embark too far on that journey, it would be wise to spend a little bit of time beefing up your skills at navigating and manipulating two-dimensional lists, and solidifying some prior Python knowledge that turns out to be critical for this kind of problem.

References, mutability, and immutability

When you learn any programming language, part of what you're doing is building up a mental model of what's happening behind the scenes while your program runs. You can achieve a certain amount of success even if your mental model is incomplete (or just plain wrong in places), but you eventually run into issues where you simply need to understand the reality of the language if you want to be able to write programs correctly.

Variables contain references, not objects

When you assign an object into a variable in Python, that variable does not actually store the object. Instead, the variable stores a reference to that object, which you can think of as the location in memory where the object resides. You can get the value of the reference itself by calling the function id, like this:

>>> x = 20563
>>> x
20563
>>> id(x)
55367280

(Note that you might see a different id value than I do, but the id values should be comparatively equal or comparatively different for you when they are for me; what's important here is when an id changes and whether one id is the same as another or different. Note, also, that our implementation of Python handles very small integer values differently from others, so I'm using examples with relatively large numbers, so we can be sure to see the true effect.)

Over the course of a variable's life, it may store different objects at different times, in which case its id changes, also. For example:

>>> x += 1
>>> x
20564
>>> id(x)
55367568

Embedded in the example above is a strong hint that adding 1 to an integer using the += operator does not change the value of the integer object that x refers to; instead, it makes x refer to a different integer, as evidenced by the fact that x's id changed.

Mutability vs. immutability

Python draws a distinction between types whose objects are mutable and types whose objects are immutable. Mutable types are the ones whose objects can be changed; immutable types are the ones whose objects cannot.

For example, integer values are immutable in Python, which means that there's nothing you can do to change an integer object once it's been created; all you can do is create a new integer object. So, in the example above, when we added 1 to x, we were actually creating a new integer value that was 1 greater than the one currently referred to by x.

Meanwhile, lists in Python are mutable, which means that alterations to an existing list change that list, as opposed to building a new one.

>>> a = [1001, 1002, 1003]
>>> id(a)
55035272
>>> a.append(1004)
>>> a
[1001, 1002, 1003, 1004]
>>> id(a)
55035272

The id of a has not changed, which tells us that a is still referring to the same list that it used to, meaning that lists are mutable and append mutates them. (The += operator does, too. The + operator does not, as it turns out; it builds a new list that is the concatenation of the two lists being added together.)

To be sure we understand the practical effect of this, we need to think about what happens when more than one variable refers to the same object, and then we try to modify one variable or the other. Consider first the following example using variables storing integers.

>>> a = 657123
>>> id(a)
55088720
>>> b = a
>>> id(b)
55088720

In this example, a and b are now variables storing a reference to the same integer object. Now consider what would happen if we did this.

>>> a += 1

What effect would this have on the value of b? The answer is none; b will remain unchanged. Since integers are immutable, the act of adding 1 to a caused a new integer object to be created with the value 657124, and a now refers to it, while b still refers to the same object it did before.

>>> a
657124
>>> id(a)
55628976
>>> b
657123
>>> id(b)
55088720

Now let's consider the effect of the mutability of lists in a similar example:

>>> a = [1001, 1002, 1003]
>>> id(a)
55266312
>>> b = a
>>> id(b)
55266312

At this point, a and b are two variables each containing a reference to the same list. (Among other things, this tells us that the assignment of a into b was very cheap, since it was only the reference being assigned; even if a had been a very long list, this would have been a cheap assignment.)

Now we'll mutate one of the lists:

>>> a.append(1004)
>>> a
[1001, 1002, 1003, 1004]
>>> id(a)
55266312
>>> id(b)
55266312
>>> b
[1001, 1002, 1003, 1004]

Lo and behold, mutating one of the lists also mutated the other! This isn't magic; this is simply due to the fact that lists are mutable, and that a and b were both referring to the same list, so mutating that list had the same effect on both variables.

Finally, to be sure we have our heads wrapped all the way around this, we'll consider the effect of mutating the elements of a list, continuing the previous example.

>>> c = a[0]
>>> id(c)
55088736
>>> id(a[0])
55088736
>>> c
1001
>>> c += 1

What do you think the effect of c += 1 is? What values have changed? What values haven't? Let's take a look.

>>> c
1002
>>> id(c)
55628912
>>> a[0]
1001
>>> id(a[0])
55088736
>>> a
[1001, 1002, 1003, 1004]

Since integers are immutable, c += 1 will have created a new integer object with the value 1002. c will now refer to that, but a[0] will not have changed.

Why the mutability distinction matters

The distinction between mutability and immutability might at first seem like nothing more than a curiosity, an implementation detail that doesn't significantly affect the meaning of a Python program. Even if you've never thought of things this way — and even if your mental model about these details hasn't matched this reality — it may not have negatively affected anything you've had to write so far, because many Python programs have the same effect regardless of the mutability of their objects.

The reality, however, is that you eventually reach the point where this distinction is absolutely critical, as we did in this lecture on two-dimensional list algorithms. When iterating over a list a, you have a few options:

Use a for loop that iterates over the list's elements.
```
for x in a:
```
In this case, the variable x will refer to each object in the list a, one per loop iteration. x will refer directly to the objects in the list, but if those objects are immutable (e.g., they're integers), modifying x will have no effect on the list. But in a case where you don't need to modify the list, this is the simplest and (usually) best approach.

Use a for loop that iterates over the indices of the list's elements.
```
for x in range(len(a)):
```
In this case, the variable x will not refer directly to each object in the list. It will instead store the index (i.e., the position within the list) of each element. You can use this index to access or modify the list's elements, and any modifications you make using an index (e.g., x[i] = 3) will take effect on the list. But if you never need to modify the list, this approach is more complicated than it needs to be.

Use a while loop, managing the values of variables that access indices manually, while ensuring that they remain valid (e.g., that they aren't less than 0 or at least as big as the size of the list). This is the trickiest technique, but the most useful when it's difficult to know in advance how far you need to go, or when the condition that gets you out of the loop isn't based only on an index (e.g., the way that we search in Connect Four for four tiles in a row of the same color).

As you can see, the choice here depends at least partly on whether your goal is just to look at elements of the list, as opposed to changing them. Consider a straightforward pair of nested loops like this, assuming that we're trying to increment every element in a two-dimensional list of integers called a:

for i in a:
    for j in i:
        j += 1

At first blush, this technique may appear to work:

The outer loop takes us to each sublist and names each one i temporarily.
The inner loop takes us to each integer in each sublist and names each one j temporarily.

So every integer in every sublist will be visited, and 1 will always be added to each one. The problem is that j contains a reference to an integer, and integers are immutable, so our attempt to add 1 to j does just that: it adds 1 to the temporary variable j, but has no effect on the underlying list.

At this stage, then, we'll have to be more careful about our understanding of how these kinds of things work in Python, as it will be vital if we want to be able to solve these kinds of problems.