CS 463G & 663: (Intro to) AI
  • Schedule
  • About
  • Assignments
  • Resources
    • AIMA textbook
    • UK Academic Calendar
    • UK Examination Schedule

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.

AssignmentDownload ZIP
  • README.md
  • hw1.py
  • check_hw1.py
# 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()
← Homework 1 assignmentDownload package →