Daily Coading Problem 23.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2e8bb9a0",
   "metadata": {},
   "source": [
    "# Daily Coading Problem 23"
   ]
  },
  {
   "cell_type": "raw",
   "id": "08a7c432",
   "metadata": {},
   "source": [
    "This problem was asked by Google.\n",
    "\n",
    "You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.\n",
    "\n",
    "Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.\n",
    "\n",
    "For example, given the following board:\n",
    "\n",
    "[[f, f, f, f],\n",
    "[t, t, f, t],\n",
    "[f, f, f, f],\n",
    "[f, f, f, f]]\n",
    "\n",
    "and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "587bf787",
   "metadata": {},
   "source": [
    "# Solution\n",
    "\n",
    "The idea here is to use either BFS or DFS to explore the board, starting from the start coordinate, and keep track of what we've seen so far as well as the steps from the start until we find the end coordinate.\n",
    "\n",
    "In our case, we'll use BFS. We'll create a queue and initialize it with our start coordinate, along with a count of 0. We'll also initialize a seen set to ensure we only add coordinates we haven't seen before.\n",
    "\n",
    "Then, as long as there's something still in the queue, we'll dequeue from the queue and first check if it's our target coordinate -- if it is, then we can just immediately return the count. Otherwise, we'll get the valid neighbours of the coordinate we're working with (valid means not off the board and not a wall), and enqueue them to the end of the queue.\n",
    "\n",
    "To make sure the code doesn't get too messy, we'll define some helper functions: walkable, which returns whether or not a tile is valid, and get_walkable_neighbours which returns the valid neighbours of a coordinate.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "eb300304",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "# Given a row and column, returns whether that tile is walkable.\n",
    "def walkable(board, row, col):\n",
    "    if row < 0 or row >= len(board):\n",
    "        return False\n",
    "    if col < 0 or col >= len(board[0]):\n",
    "        return False\n",
    "    return not board[row][col]\n",
    "\n",
    "# Gets walkable neighbouring tiles.\n",
    "def get_walkable_neighbours(board, row, col):\n",
    "    return [(r, c) for r, c in [\n",
    "        (row, col - 1),\n",
    "        (row - 1, col),\n",
    "        (row + 1, col),\n",
    "        (row, col + 1)]\n",
    "        if walkable(board, r, c)\n",
    "    ]\n",
    "# Finding shortest path\n",
    "def shortest_path(board, start, end):\n",
    "    seen = set()\n",
    "    queue = deque([(start, 0)])\n",
    "    while queue:\n",
    "        coords, count = queue.popleft()\n",
    "        if coords == end:\n",
    "            return count\n",
    "        seen.add(coords)\n",
    "        neighbours = get_walkable_neighbours(board, coords[0], coords[1])\n",
    "        queue.extend((neighbour, count + 1) for neighbour in neighbours\n",
    "                if neighbour not in seen)\n",
    "\n",
    "board = [[False, False, False, False],\n",
    "        [True, True, False, True],\n",
    "        [False, False, False, False],\n",
    "        [False, False, False, False]]\n",
    "\n",
    "print(shortest_path(board, (3, 0), (0, 0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "747a7054",
   "metadata": {},
   "source": [
    "This code should run in O(M * N) time and space, since in the worst case we need to examine the entire board to find our target coordinate."
   ]
  }
 ],
 "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}