{
"cells": [
{
"cell_type": "markdown",
"id": "5a451b18",
"metadata": {},
"source": [
"NAME:"
]
},
{
"cell_type": "markdown",
"id": "5112bda3-5774-4eee-9dcb-5893136ac5dc",
"metadata": {},
"source": [
"# UE5 Fundamentals of Algorithms\n",
"# Lab 11: Graphs/Matrix"
]
},
{
"cell_type": "markdown",
"id": "3054b63b-5b4a-4b07-a129-71951eaee576",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"id": "6892d60b-b418-486b-a1db-008652e04457",
"metadata": {},
"source": [
"## How to Get Out of a Maze?\n",
"\n",
"In this exercise, you will write an algorithm to navigate out of a maze. The maze will be represented as a 2D matrix (discrete coordinates), which will serve as the data structure for storage and traversal. The starting point of the traversal will always be at the coordinates `(0, 0)` in the top-left corner, and the endpoint will be the bottom-right corner (in the case of the example below, `(9, 9)`). Walls with a value of `1` are impassable, and you also cannot move outside the matrix. Movement is possible in 8 directions: up, down, left, right, and their corresponding diagonals. In this exercise, you will explore three traversal methods. Note that there can be multiple different, but all valid, solutions."
]
},
{
"cell_type": "markdown",
"id": "56b3cb10-e5e1-4c1e-8a38-948b97b2ad47",
"metadata": {},
"source": [
"**Question 1.1 -** Run the program below, which loads the maze and includes a display function. Identify one of the paths leading to the exit. Modify the code to display walls using `#` instead of `1`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5de72656-1ea0-4662-afd7-7d3c60c77612",
"metadata": {},
"outputs": [],
"source": [
"maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]\n",
"\n",
"\n",
"def display_maze(l):\n",
" print('\\n'.join([''.join([\"# \" if item == 1 else str(item) + \" \" for item in row]) \n",
" for row in l]))\n",
" \n",
"display_maze(maze)"
]
},
{
"cell_type": "markdown",
"id": "d56f24af-bf15-488c-8439-4a02b183964a",
"metadata": {
"tags": []
},
"source": [
"Give a valid path (that links the top left corner with the bottom-right corner) using the cell coordinates. E.g. `(0, 0), (1, 0) ... (9, 9)`\n",
"```\n",
"* 0 0 0 1 0 0 0 0 0\n",
"* 0 0 0 1 0 0 0 0 0\n",
"* 0 0 0 1 0 0 0 0 0\n",
"* 0 0 0 1 0 0 0 0 0\n",
"* 0 0 0 1 0 0 0 0 0\n",
"* * * * * * 0 0 0 0\n",
"0 0 0 0 1 * 0 0 0 0\n",
"0 0 0 0 1 * 0 0 0 0\n",
"0 0 0 0 1 * 0 0 0 0\n",
"0 0 0 0 0 * * * * *\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "480e043f-9041-4462-a2b8-cdfd0b5a9253",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "25c7e63ee2eb469bb88bfac786552ba8",
"grade": false,
"grade_id": "cell-b7d96dc4683b1703",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"path = [\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()\n",
"]"
]
},
{
"cell_type": "markdown",
"id": "4b8613a0-7a9d-40b3-9786-33811bb079fc",
"metadata": {
"tags": []
},
"source": [
"Write an algorithm that draws the path on a given maze (using `*`). Make sur you coupy the maze values using `[row[:] for row in maze]`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "82eb2cca-bc6b-46b0-8bb6-867023701fe0",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "28320543044ad11fad2d9ecf671b1b4d",
"grade": false,
"grade_id": "cell-35b9fc43128af1f4",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def display_path_on_maze(maze, path):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3e47e24b-7c77-4a73-b793-7294058f966d",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"display_path_on_maze(maze, path)"
]
},
{
"cell_type": "markdown",
"id": "10287b07-ed9e-4a62-844f-1831d1be46a5",
"metadata": {},
"source": [
"Write a function that checks if a path is valid for the maze given previously.\n",
"\n",
"1. The path must start at (0, 0) and end at (n-1, m-1).\n",
"2. Each cell in the path must be accessible (value 0).\n",
"3. The movement between consecutive cells must be valid (one of 8 directions).\n",
"4. The next cell must be within bounds and accessible.\n",
"5. The final cell must be accessible."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3968dce5-9ed6-45f9-8814-c097851c9291",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "92d658b3e9e418dba0591194fbd6f501",
"grade": false,
"grade_id": "cell-aac5bf14c89fadb2",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def is_valid_path(maze, path):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "27c1fa22-bfa1-4c10-820c-13b3ffc35f1d",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert is_valid_path(maze, path)\n",
"assert not is_valid_path(maze, [(0, 0)])\n",
"assert not is_valid_path(maze, [(-1, -1)])"
]
},
{
"cell_type": "markdown",
"id": "3887d798-7d13-4bfd-9d5b-e9357e998bca",
"metadata": {},
"source": [
"**Question 1.2 -** Write a function `neighbors` that returns all the neighbors of a cell (i.e., all other cells accessible from this cell)."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2363dbae-a62e-4f3a-b399-c8f172b6bd09",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "27ebce61a4229f4207efdfa1694fdad0",
"grade": false,
"grade_id": "cell-a45a6dc113f72b51",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def neighbors(maze, x, y):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9554f674-f8c2-4784-9de0-7f553db68802",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert set(neighbors(maze, 0, 0)) == {(1, 0), (1, 1), (0, 1)} # the top left cell has 3 neighbors\n",
"assert set(neighbors(maze, 1, 1)) == {(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)}"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c08bf511-16e4-4d7e-9641-9e6aec991cc9",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"neighbors(maze, 4, 5)"
]
},
{
"cell_type": "markdown",
"id": "a8290326-ce83-4824-b7eb-22b45983032d",
"metadata": {},
"source": [
"Write a function that calls the `neighbors` and returns all the values from a given point, make sure they are all zeros."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1048003e-f4e2-4ace-a953-818750f36934",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "83d7271ac5c83fb629735140a9fddc84",
"grade": false,
"grade_id": "cell-8ff7571fa5dfcf65",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def neighbor_values_from_point(maze, x, y):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1285617c-f3c8-4c03-a002-2e18bb8efc00",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert all(v == 0 for v in neighbor_values_from_point(maze, 4, 5))"
]
},
{
"cell_type": "markdown",
"id": "7b0c72c0-c1bc-4783-8ea9-e83860763070",
"metadata": {},
"source": [
"Propose an algorithm to determine if there is a path connecting the entry and the exit. In this question, you will use a depth-first search (DFS) approach with a recursive implementation. The stopping condition for your search algorithm is reached if you are on the exit cell or if all neighbors have been visited. The algorithm should return `True` if a path exists, or `False` if it does not. You may use the `neighbors` function written previously."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5c839ee8-6339-4235-975a-fdc0190e5821",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "882e14fb59d0b1b7209b7402a4a165b3",
"grade": false,
"grade_id": "cell-6e874315f3dd952b",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def exist_dfs(maze, x0=0, y0=0, visited=None):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "995d1bf9-5fd1-4011-828f-26044ee8a184",
"metadata": {},
"source": [
"Write tests."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "23e09473-c451-43fe-aa63-c8151c1ce01b",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert exist_dfs(maze)\n",
"assert not exist_dfs([[0, 1], [1, 1]])\n",
"assert exist_dfs([[0, 1], [0, 0]])"
]
},
{
"cell_type": "markdown",
"id": "db449e33-b3b2-4525-a8fe-cd5fffa0bb23",
"metadata": {},
"source": [
"**Exercise 1.3 -** We now use a _breadth-first search (BFS)_ algorithm with an _iterative_ implementation to determine if an exit exists."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b4ca764e-e1f7-4e17-9b03-dcadde3434c9",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "1a48ff76370ffffb0025515e27d8fb45",
"grade": false,
"grade_id": "cell-07e7d9e3ea11477c",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def exist_bfs(maze):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "1a131d46-7f70-4c3d-b8c3-4df7c6f8ce1e",
"metadata": {},
"source": [
"Compare to the dfs."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8380bc3a-fbd6-4405-a08d-1770af316bf8",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert exist_bfs(maze)\n",
"assert exist_bfs([[0, 1], [1, 1]]) == exist_dfs([[0, 1], [1, 1]])\n",
"assert exist_bfs([[0, 1], [0, 0]]) == exist_dfs([[0, 1], [0, 0]])"
]
},
{
"cell_type": "markdown",
"id": "10e47cd3-948e-44a5-9172-9ad540978310",
"metadata": {},
"source": [
"Now implement a backtracking approach to provide the path to the exit. To achieve this use a dictionnary to store the `previous` step before processing the node.\n",
"\n",
"1. If no path exists (`previous` is empty), return None.\n",
"2. Initialize the path with the end position: `path = [end]`.\n",
"3. While the current position is not the start, set `(x, y) = previous[y][x]` and append `(x, y)` to the path.\n",
"4. Reverse the path to get it from start to end."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5f54b7dc-4a6a-4382-9c0e-eb57bbd38dc1",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "7b745dade6cdc1b21e51205af80778b2",
"grade": false,
"grade_id": "cell-8284f5069db6e454",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def path_bfs(maze):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "markdown",
"id": "327f6930-2a62-4b38-a5a4-8f53f3a360a1",
"metadata": {},
"source": [
"# Bonus questions"
]
},
{
"cell_type": "markdown",
"id": "03a90755-ff99-4839-a0be-ab09854f340e",
"metadata": {
"tags": []
},
"source": [
"Write a function that generates an empty maze:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4ef141a5-e2fb-4fd4-b186-6e5bd1f0f463",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "662fda73fc5249cfeae27e8865fa96e2",
"grade": false,
"grade_id": "cell-75d2a2d7b53d889d",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def generate_empty_maze(rows, cols):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f19ddefd-b4e8-497d-a704-97a3e0c3de6b",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}