Remember the happy puppies?

`happy_puppies.py`

¶**NOTES**

- Copy
`happy_puppies.py`

from Friday's lecture to today's workspace

In [ ]:

```
%%file happy_puppies.py
def is_happy(grid, row, column):
if grid[row][column] != 'p':
return False
if row - 1 >= 0 and grid[row - 1][column] == 'p':
return True
if row + 1 < len(grid) and grid[row + 1][column] == 'p':
return True
if column - 1 >= 0 and grid[row][column - 1] == 'p':
return True
if column + 1 < len(grid[row]) and grid[row][column + 1] == 'p':
return True
if row - 1 >= 0 and column - 1 >= 0 and grid[row - 1][column - 1] == 'p':
return True
if row + 1 < len(grid) and column - 1 >= 0 and grid[row + 1][column - 1] == 'p':
return True
if row - 1 >= 0 and column + 1 < len(grid[row]) and grid[row - 1][column + 1] == 'p':
return True
if row + 1 < len(grid) and column + 1 < len(grid[row]) and grid[row + 1][column + 1] == 'p':
return True
return False
def find_happy(grid):
happy = []
for row in range(len(grid)):
for column in range(len(grid[row])):
if is_happy(grid, row, column):
happy.append((row, column))
return happy
grid = [
[None, 'p', 'p'],
['p', None, None],
[None, None, 'p']
]
find_happy(grid)
```

```
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
```

Breaking research! Puppies are actually happy if the are within barking distance of another puppy.

Let's update our code so that `is_happy`

returns `True`

is there is another puppy within **two squares** of the given puppy.

To search two squares in each direction, we'll need to check 5 x 5 - 1 = **24** total positions!

😱

`continue`

¶In [ ]:

```
print('A','B')
print('---')
for a in range(4):
for b in range(4):
if b > a:
continue
print(a,b)
```

**NOTES**

- Walk through this code
- Explain that
`continue`

skips to the next iteration of the inner-most loop- i.e. the "b" loop in our example

`min`

, `max`

¶In [ ]:

```
print(min(3, 7))
```

In [ ]:

```
print(max(2, 8))
```

`radius`

steps of a given index.

**NOTES**

- Draw this out
- draw 0 through 9
- pick a position
- draw the window around that position
- when the window does not extend beyond a boundary, there are not problems
- what are the two boundaries?
`0`

,`len(items)-1`

- we want the window to go from
`pos-size`

to`pos+size+1`

, unless it runs into a boundary first- draw out examples of
`pos-size`

. When`pos-size`

is negative, what value do we want to use instead? - draw out examples of
`pos+size+1`

. When`pos+size+1`

is >`len(items)-1`

, what value do we want to use instead?

- draw out examples of
- observe how the
`min`

and`max`

clauses enforce the boundary constraints

```
index = 3, radius = 2
0 1 2 3 4 5 6 7 8 9
[....^....]
index = 1, radius = 3
0 1 2 3 4 5 6 7 8 9
[......^......] # what we would get
[..^......] # what we want
index = 8, radius = 3
0 1 2 3 4 5 6 7 8 9
[......^......] # What we would get
[......^..] # What we want
```

In [ ]:

```
def get_window(items, index, radius):
"""Return the items within `radius` steps from `index`. """
# What is the lower bound of the range?
# What is the upper bound of the range?
# Iterate through that range and grab the items
window = []
return window
```

In [ ]:

```
def get_window(items, index, radius):
"""Return the items within `radius` steps from `index`. """
window = []
min_bound = max(0, index - radius)
max_bound = min(len(items), index + radius + 1)
for position in range(min_bound, max_bound):
window.append(items[position])
return window
```

In [ ]:

```
numbers = list(range(10))
print(get_window(numbers, 3, 1))
```

In [ ]:

```
print(get_window(numbers, 4, 2))
```

In [ ]:

```
print(get_window(numbers, 8, 2))
```

In [ ]:

```
print(get_window(numbers, 1, 5))
```

Let's use these two new techniques to address our happy puppy problem.

`more_happy_puppies.py`

¶**NOTES**

- draw out the search problem in terms of a box around a position
- show how we want to truncate the box if it extends beyond the edges of the grid
- use the
`min`

/`max`

technique to set the ranges for the row and column positions

- what do we want to do at the middle position? how do we know we are on the middle position?

In [ ]:

```
def is_happy(grid, row, column, radius=1):
if grid[row][column] != 'p':
return False
row_lower_bound = max(0, row - radius)
row_upper_bound = min(len(grid), row + radius + 1)
for r in range(row_lower_bound, row_upper_bound):
col_lower_bound = max(0, column - radius)
col_upper_bound = min(len(grid[row]), column + radius + 1)
for c in range(col_lower_bound, col_upper_bound):
if r == row and c == column: # middle position doesn't count
continue
if grid[r][c] == 'p':
return True
return False
def find_happy(grid, radius=1):
happy = []
for row in range(len(grid)):
for column in range(len(grid[row])):
if is_happy(grid, row, column, radius):
happy.append((row, column))
return happy
grid = [
[None, 'p', 'p'],
['p', None, None],
[None, None, 'p']
]
find_happy(grid, radius=2)
```

**NOTES**

**Goal**: help the students develop confidence in designing more complex logic through drawing out the problemDRAW IT OUT

- draw an example grid
- demonstrate the different directions we need to test
- do we need to check both left AND right? No.
- 4 directions needed. Name them. (e.g. "right", "down", "down-right", "down-left")

- write out tests

Write out

`has_three_in_a_row`

- for each position in the grid, if it has three in a row in any of our 4 directions, return True

Now implement the 4 directions

**Draw out**the range for the row and the column- Highlight the boundary conditions: min and max values
- Code an early return for violated boundary conditions
- Code the loop over the variable dimension(s)
- "right" and "down" have a constant in one dimension
- use
`zip`

for variables in both dimensions- make sure the steps are synced correctly: have both ranges start at the
`row`

,`column`

position and move out.

- make sure the steps are synced correctly: have both ranges start at the

- for each direction, add a test
- include a positive and a negative test

In [ ]:

```
def has_three_right(grid, row, column, value):
if column + 3 > len(grid[row]):
return False
for c in range(column, column + 3):
if grid[row][c] != value:
return False
return True
def has_three_down_right(grid, row, column, value):
if column + 3 > len(grid[row]):
return False
if row + 3 > len(grid):
return False
for r, c in zip(range(row, row + 3), range(column, column + 3)):
if grid[r][c] != value:
return False
return True
def has_three_down(grid, row, column, value):
if row + 3 > len(grid):
return False
for r in range(row, row + 3):
if grid[r][column] != value:
return False
return True
def has_three_down_left(grid, row, column, value):
if column - 2 < 0:
return False
if row + 3 > len(grid):
return False
for r, c in zip(range(row, row + 3), range(column, column - 3, -1)):
if grid[r][c] != value:
return False
return True
def has_three_in_a_row(grid, value='X'):
for row in range(len(grid)):
for column in range(len(grid[row])):
if has_three_right(grid, row, column, value) \
or has_three_down_right(grid, row, column, value) \
or has_three_down(grid, row, column, value) \
or has_three_down_left(grid, row, column, value):
return True
return False
```

In [ ]:

```
from three_in_a_row import has_three_in_a_row, has_three_right
def test_has_three_in_a_row_right():
grid = [
[0, 0, 1],
[0, 1, 0],
[1, 1, 1]
]
assert has_three_right(grid, 2, 0, 1) # grid, row, column, value
assert not has_three_right(grid, 2, 0, 0) # grid, row, column, value
assert not has_three_right(grid, 0, 0, 0) # grid, row, column, value
assert not has_three_right(grid, 1, 1, 1) # make sure I don't run out of bounds
def test_has_three_in_a_row():
grid = [
[1, 0, 1],
[0, 1, 0],
[1, 1, 0]
]
assert has_three_in_a_row(grid, value=1)
def test_not_has_three_in_a_row():
grid = [
[1, 0, 1],
[0, 1, 0],
[0, 1, 0]
]
assert not has_three_in_a_row(grid, value=1)
def test_has_three_0_in_a_row():
grid = [
[1, 0, 1],
[0, 0, 0],
[0, 1, 0]
]
assert not has_three_in_a_row(grid, value=0)
```

- 2D logic
`continue`

`min`

,`max`

, and`range`

to handle boundary conditions- Searching a 2D subgrid