Homework 1 Starter Files
Keys, Doors, and Shortest Paths
Browse every file included in the Homework 1 starter package.
Select a filename below to show its complete contents. These are the same files included in the downloadable ZIP, so this page can be used for a live walkthrough in class.
# Homework 1 starter
This package contains everything needed to develop and check Homework 1.
## Files
- `hw1.py`: the only file you edit and submit.
- `check_hw1.py`: public examples and a legal-path checker.
## Run the public checks
```bash
python check_hw1.py
```
The checker validates path format, movement, keys, doors, and the public shortest lengths. It does not reveal the hidden tests or the required state representation.
Upload only `hw1.py` to Canvas.ROAD = 0
DOOR = 1
WALL = 2
KEY = 3
EXIT = 4
PLAYER = 5
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
def find_tile(grid: list[list[int]], tile: int) -> tuple[int, int]:
"""Return the coordinate of the first matching tile."""
for row, values in enumerate(grid):
for col, value in enumerate(values):
if value == tile:
return row, col
raise ValueError(f"tile {tile} is missing")
def neighbors(row: int, col: int, height: int, width: int):
"""Yield orthogonally adjacent coordinates inside the grid."""
for d_row, d_col in DIRECTIONS:
next_row = row + d_row
next_col = col + d_col
if 0 <= next_row < height and 0 <= next_col < width:
yield next_row, next_col
class Solution:
def shortest_path(
self, grid: list[list[int]]
) -> list[tuple[int, int]] | None:
"""Return a shortest legal path, or None when none exists."""
raise NotImplementedError("Implement Homework 1 here")from hw1 import Solution
ROAD, DOOR, WALL, KEY, EXIT, PLAYER = range(6)
def find_tile(grid, target):
return next(
(row, col)
for row, values in enumerate(grid)
for col, tile in enumerate(values)
if tile == target
)
def path_is_legal(grid, path):
if not path:
return False
board = [row[:] for row in grid]
height = len(board)
width = len(board[0])
start = find_tile(board, PLAYER)
goal = find_tile(board, EXIT)
if path[0] != start:
return False
keys = 0
previous = start
for step in path[1:]:
if not (
isinstance(step, tuple)
and len(step) == 2
and all(isinstance(value, int) for value in step)
):
return False
row, col = step
if not (0 <= row < height and 0 <= col < width):
return False
if abs(row - previous[0]) + abs(col - previous[1]) != 1:
return False
tile = board[row][col]
if tile == WALL:
return False
if tile == KEY:
keys += 1
board[row][col] = ROAD
elif tile == DOOR:
if keys == 0:
return False
keys -= 1
board[row][col] = ROAD
previous = step
return path[-1] == goal
CASES = [
(
[[4, 2, 1, 3], [0, 5, 0, 2], [2, 3, 1, 0]],
3,
),
(
[
[1, 0, 3, 2, 1],
[2, 3, 0, 0, 1],
[3, 0, 3, 0, 2],
[0, 4, 1, 5, 2],
[2, 1, 2, 3, 0],
],
5,
),
(
[
[2, 0, 0, 2, 2, 2, 2, 0, 0, 3, 0, 2, 0, 1, 2],
[1, 0, 2, 0, 2, 1, 3, 0, 2, 0, 3, 0, 0, 2, 2],
[1, 2, 2, 0, 2, 2, 3, 0, 2, 3, 0, 2, 2, 0, 0],
[0, 2, 5, 1, 2, 1, 0, 2, 2, 0, 2, 0, 2, 3, 0],
[0, 0, 0, 0, 1, 2, 0, 3, 2, 0, 3, 0, 3, 0, 2],
[2, 0, 3, 0, 2, 0, 3, 0, 0, 0, 1, 0, 3, 3, 1],
[0, 1, 0, 0, 1, 1, 2, 0, 2, 2, 0, 1, 2, 3, 2],
[2, 1, 0, 0, 2, 2, 1, 0, 2, 0, 3, 0, 4, 2, 0],
[0, 0, 0, 0, 2, 1, 0, 0, 2, 2, 2, 2, 0, 0, 0],
[0, 2, 0, 2, 2, 3, 0, 3, 2, 0, 3, 1, 1, 2, 2],
],
None,
),
]
def main():
solution = Solution()
for number, (grid, expected_length) in enumerate(CASES, 1):
try:
result = solution.shortest_path([row[:] for row in grid])
except NotImplementedError:
print("shortest_path: TODO")
return
if expected_length is None:
assert result is None, f"case {number}: expected None"
else:
assert path_is_legal(grid, result), f"case {number}: illegal path"
assert len(result) == expected_length, (
f"case {number}: expected length {expected_length}, "
f"received {len(result)}"
)
print(f"case {number}: passed")
if __name__ == "__main__":
main()