Practice with grids
Happy puppies
We have a grid of puppies. We’ll use ‘p’ to indicate a puppy at a given position.
None, 'p', 'p'
None, 'p', None
None, None, 'p'
'p', None, None
A puppy is happy if it is next to another puppy. “Next to” means there is another puppy up, down, left, right, or diagonal of the given puppy.
Write a function to return the coordinates (row, column) of all the happy puppies in a grid.
def find_happy(grid):
Q: Given a puppy at (x, y)
, how can you tell if it is happy?
Hint: Start with a definition that a puppy is happy only if there is a puppy directly above it. Plan out and code the entire problem. Then work to broaden your definition of what it means to be happy.
A simple algorithm
 start a list of tuples for happy puppies
 for every row
 for every column
 if there is a puppy here and it is happy
 append the coordinates to the list
 if there is a puppy here and it is happy
 for every column
Code for checking if a puppy is there
def is_puppy(grid, row, column):
if grid[row][column] == 'p':
return True
return False
Notice that we can return True
if we find a puppy and then in all other
situations, return False
. We don’t need an else
.
It is a good idea to write short functions that do one thing well
Code for checking if a puppy is happy (up only)
def is_happy(grid, row, column):
if row  1 >= 0 and is_puppy(grid, row  1, column):
return True
return False
This uses a guard
. We first check if row  1 >= 0
. If this fails, then we
are outside of the grid, and we never check whether a puppy is there. Only if
this works, then we check for a puppy at (row  1, column)
. Without the guard,
we would create a list indexing error every time we went outside the grid.
The rest of the code
def find_happy(grid):
happy = []
for row in range(len(grid)):
for column in range(len(grid[row])):
if is_puppy(grid, row, column) and is_happy(grid, row, column):
happy.append((row, column))
return happy
We can run this with:
grid = [
[None, 'p', 'p'],
[None, 'p', None],
[None, None, 'p'],
['p', None, None],
]
print(find_happy(grid))
This will print:
[(1, 1)]
because there is only one happy puppy using our restricted definition.
Code for checking if a puppy is happy (all directions)
Now that we are confident that we have the right idea, we can expand our definition of what it means for a puppy to be happy:
def is_happy(grid, row, column):
num_rows = len(grid)
num_columns = len(grid[0])
# up
if row  1 >= 0 and is_puppy(grid, row  1, column):
return True
# down
if row + 1 < num_rows and is_puppy(grid, row + 1, column):
return True
# left
if column  1 >= 0 and is_puppy(grid, row, column  1):
return True
# right
if column + 1 < num_columns and is_puppy(grid, row, column + 1):
return True
# diagonal up left
if row  1 >= 0 and column  1 >= 0 and is_puppy(grid, row  1, column  1):
return True
# diagonal down left
if row + 1 < num_rows and column  1 >= 0 and is_puppy(grid, row + 1, column  1):
return True
# diagonal up right
if row  1 >= 0 and column + 1 < num_columns and is_puppy(grid, row  1, column + 1):
return True
# diagonal down right
if row + 1 < num_rows and column + 1 < num_columns and is_puppy(grid, row + 1, column + 1):
return True
return False
If we rerun this code, it prints:
[(0, 1), (0, 2), (1, 1), (2, 2)]
Three puppies are happy! One puppy is sad. 😥
Pretty printing a grid
We have seen this print function before:
def print_grid(grid):
for row in grid:
for item in row:
print(item, end=' ')
print()
When we call it:
fruits = [
['apple', 'pear', 'guava'],
['orange', 'banana', 'peach'],
['melon', 'mango', 'kiwi']
]
print_grid(fruits)
we get a grid that is not well aligned:
apple pear guava
orange banana peach
melon mango kiwi
It would be nice if we could instead print the grid so that all the column widths lined up:
apple pear guava
orange banana peach
melon mango kiwi
Let’s write a pretty print function:
def pretty_print_grid(grid):
Q: How do you know how wide to make each column?
Q: How do you know how many spaces to add after each item?
A simple algorithm, in two parts
collect a list of the maximum widths for each column

start an empty list

loop through all of the columns
 keep track of the maximum width
 loop through all rows
 for each item in that column
 check if its length > maximum width seen so far if it is, set the maximum to this value
 for each item in that column
 append the maximum width to the list

now that we have a maximum width for each column…
pretty print the grid
 for each row in the grid
 for each item, width in the zip of (row, widths)
 calculate the padding needed
 print item
 print padding
 print newline
 for each item, width in the zip of (row, widths)
Collecting the maximum width for each column
We need to first collect the maximum width of each column:
def maximum_widths(grid):
widths = []
for col in range(len(grid[0])):
col_width = None
for row in range(len(grid)):
item_width = len(grid[row][col])
if col_width is None or item_width > col_width:
col_width = item_width
widths.append(col_width)
return widths
Notice that we need to set col_width = None
at the start of the loop when we
look at a given column. This is because we need a maximum width calculated
separately for each column.
How many spaces do we need?
Imagine we are trying to print an item with a length of 5, but the column width
is 10 characters. How many spaces do we need to add? 10  5 = 5
. However, we
should add one because we want one space between each column. We can calculate
this as:
spaces_needed = width  len(item) + 1
Pretty print
Now we can write a function to do the pretty printing:
def pretty_print_grid(grid):
widths = maximum_widths(grid)
for row in grid:
for item, width in zip(row, widths):
spaces_needed = width  len(item) + 1
print(item, end=' ' * spaces_needed)
print()
We use zip to iterate over the items in each column and the widths needed for each column.
Running the code
If you run this code:
fruits = [
['apple', 'pear', 'guava'],
['orange', 'banana', 'peach'],
['melon', 'mango', 'kiwi']
]
pretty_print_grid(fruits)
Then it prints:
apple pear guava
orange banana peach
melon mango kiwi
Handling grids with mixed types
Suppose we have a grid like this:
hodge_podge = [
[1, 2, 3, 4, 5],
[50, 123, 4.32, None, 43.21],
['so','much','amaze',':)', True]
]
How would we modify the code so it could handle this? All we need to do is
modify two lines of code. One is in our maximum_widths()
function:
item_width = len(grid[row][col])
This won’t work on integers because we can’t take the len()
of an integer. So
we can change this line to:
item_width = len(str(grid[row][col]))
Likewise, in pretty_print()
, we need to change this line:
spaces_needed = width  len(item) + 1
to
spaces_needed = width  len(str(item)) + 1
Using str()
converts whatever is in the grid to a string before we take its
length.
We can now run:
hodge_podge = [
[1, 2, 3, 4, 5],
[50, 123, 4.32, None, 43.21],
['so','much','amaze',':)', True]
]
pretty_print_grid(hodge_podge)
and this prints:
1 2 3 4 5
50 123 4.32 None 43.21
so much amaze :) True
An alternative decomposition
The decomposition we did above might not seem natural to you. How did we come up with this particular decomposition? How did we know to use a zip? How do we know how many functions to use?
Here is an alternative decomposition, that works from the top down and might match your thinking process more closely. Your first thought might be — I need to print this grid — so you start by writing this algorithm:
pretty print the grid
 for each row in grid
 for each column in the grid
 print item
 calculate how many spaces I should add
 print needed spaces
 print a newline
 for each column in the grid
If you think this way, you have designed the main algorithm first. Now you have a piece of this algorithm that needs more work — calculate how many spaces I should add. This is a sign that you likely need a separate function!
So let’s write a separate algorithm for that function:
calculate spaces to add
 find maximum width of column
 spaces to add = maximum width of column  length of my item + 1
OK, this gets us closer, but we still have another piece that needs more work — find maximum width of a column
So now we need one more algorithm for that:
find maximum width of a column
 keep track of the maximum width
 loop through all rows
 for each item in that column
 check if its length > maximum width seen so far
 set the maximum to this value
 check if its length > maximum width seen so far
 for each item in that column
 return the maximum width
Notice that we only need to find the maximum width of one column at a time in this last step. But also notice that we will recalculate this every time we need it. That is maybe OK!
Here is code that follows this decomposition:
def maximum_width(grid, column):
num_rows = len(grid)
maximum = 0
for row in range(num_rows):
length = len(grid[row][column])
if length > maximum:
maximum = length
return maximum
def spaces_to_add(grid, row, column):
width = maximum_width(grid, column)
num_spaces = width  len(grid[row][column]) + 1
return num_spaces
def pretty_print_grid(grid):
num_rows = len(grid)
num_columns = len(grid[0])
for row in range(num_rows):
for column in range(num_columns):
print(grid[row][column], end='')
num_spaces = spaces_to_add(grid, row, column)
print(' ' * num_spaces, end='')
print()
This code works just as well to solve this problem!