Loops, Lists
It’s useful to recognize that there’s a common pattern we can use here.
Both the find-starting-cell and find-next-cell searches are looking for the maximum number of carrots. We can make one function, most_carrots, that, given a list of cells, returns the cell with the most carrots. For the find-starting-cell problem, we’ll give this all the potential starting cells. For the find-next-cell, we’ll give it the list of neighbors. By writing this most_carrots carefully, we can make sure it returns the first-given-tied cell in case of a tie for number of carrots.
In addition, we’ll have most_carrots filter out any cells that are outside the grid. This will simplify our later code, since we can trust that it won’t consider illegal cells.
Now, our search is just:
find starting cell possibilities
loop
find best cell in possibilities
if no carrots there, nap
otherwise, eat those carrots
make possible list out of our neighbors
The most_carrots function:
def most_carrots(cells, garden, ncols, nrows):
"""Find cell with most carrots.
Given list of (row, col) coords, return coords w/max carrots.
Cells provided may be outside grid; drop invalid cells.
If zero carrots can be found, returns None.
For example::
>>> garden = [[2, 3],
... [0, 3]]
>>> nrows = len(garden)
>>> ncols = len(garden[1])
For single cell, this should win, as long as it has carrots::
>>> most_carrots([(0, 0)], garden, ncols, nrows)
(0, 0)
If no carrots can be found, return None::
>>> most_carrots([(1, 0)], garden, ncols, nrows)
With a tie (for 3), prefer first-given::
>>> most_carrots([(0, 0), (0, 1), (1, 0), (1, 1)], garden, ncols, nrows)
(0, 1)
Make sure illegal cells aren't considered::
>>> most_carrots([(-1, -1), (0, 0), (2, 2)], garden, ncols, nrows)
(0, 0)
"""
# Make list of (row, col) from cells
# Throw out cells that are outside the garden grid.
legal = [(row, col) for row, col in cells
if 0 <= row < nrows and 0 <= col < ncols]
num_carrots = 0
best = None
for row, col in legal:
if num_carrots < garden[row][col]:
num_carrots = garden[row][col]
best = row, col
return best
And the lunch_count function that uses it:
def lunch_count(garden):
"""Given a garden of nrows of ncols, return carrots eaten."""
# Sanity check that garden is valid
row_lens = [len(row) for row in garden]
assert min(row_lens) == max(row_lens), "Garden not a matrix!"
assert all(all(type(c) is int for c in row) for row in garden), \
"Garden values must be ints!"
# Get number of rows and columns
nrows = len(garden)
ncols = len(garden[0])
# START SOLUTION
eaten = 0
# Find center cells. There can be at most four center cells,
# if both ncols and nrows are odd. Since we're guaranteed that
# there will never be tie of number of carrots in center cells,
# we don't have to worry if a particular cell is duplicated, so
# we can just test all possible center cells.
consider = [
((nrows - 1) // 2, (ncols - 1) // 2),
((nrows - 1) // 2, (ncols - 0) // 2),
((nrows - 0) // 2, (ncols - 1) // 2),
((nrows - 0) // 2, (ncols - 0) // 2)
]
while True:
# Find row, col coords of cell with most carrots
curr = most_carrots(consider, garden, ncols, nrows)
if not curr:
# We can't find any carrots, so take nap & return
return eaten
row, col = curr
# Eat carrots in that cell and mark it as eaten
eaten += garden[row][col]
# print consider, row, col, garden[row][col], eaten
garden[row][col] = 0
# Use the WNES neighbors as our next cells to consider.
# The order here is important --- most_carrots breaks ties
# by using the first-of-ties, so ensure these are WNES
consider = [
(row, col - 1), # W
(row - 1, col), # N
(row, col + 1), # E
(row + 1, col), # S
]