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

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
  • 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

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

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
• 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!