2020-09-23_word-exists-in-grid.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem was asked by Coursera.\n",
    "\n",
    "Given a 2D board of characters and a word, find if the word exists in the grid.\n",
    "\n",
    "The word can be constructed from letters of sequentially adjacent cell, where \"adjacent\" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.\n",
    "\n",
    "For example, given the following board:\n",
    "```\n",
    "[\n",
    "  ['A','B','C','E'],\n",
    "  ['S','F','C','S'],\n",
    "  ['A','D','E','E']\n",
    "]\n",
    "```\n",
    "`exists(board, \"ABCCED\")` returns `true`, `exists(board, \"SEE\")` returns `true`, `exists(board, \"ABCB\")` returns `false`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exists(board, word):\n",
    "    \"\"\"Return True if word exists on board, False if not.\n",
    "    \n",
    "    A word exists if the word can be constructed from letters of sequentially adjacent cells on board,\n",
    "    where adjacent cells are horizontally or vertically neighbouring.\n",
    "    \"\"\"\n",
    "    N, M = dim(board)\n",
    "    for i in range(N):\n",
    "        for j in range(M):\n",
    "            if exists_from_coord(board, word, i, j):\n",
    "                return True\n",
    "    return False\n",
    "\n",
    "def exists_from_coord(board, word, i, j, i_word=0, visited=None):\n",
    "    \"\"\"Return True if word[i_word:] exists on board starting from coordinates (i, j), False if not.\"\"\"\n",
    "    if visited is None:\n",
    "        visited = set()\n",
    "    visited.add((i, j))\n",
    "    \n",
    "    if i_word == len(word):\n",
    "        return True\n",
    "    elif board[i][j] != word[i_word]:\n",
    "        return False\n",
    "    else:\n",
    "        for i_next, j_next in next_coord(board, i, j, visited):\n",
    "            if exists_from_coord(board, word, i_next, j_next, i_word + 1, visited):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "def next_coord(board, i, j, visited):\n",
    "    \"\"\"Return the unvisited coordinates adjacent to (i, j) on board.\"\"\"\n",
    "    moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "    coords = [(i + move[0], j + move[1]) for move in moves]\n",
    "    return [\n",
    "        (i_next, j_next) for i_next, j_next in coords \n",
    "        if is_valid_unvisited_coord(board, i_next, j_next, visited)\n",
    "    ]\n",
    "\n",
    "def is_valid_unvisited_coord(board, i, j, visited):\n",
    "    \"\"\"Return True if coordinate (i, j) is a valid unvisited coordinate on board, False if not.\"\"\"\n",
    "    N, M = dim(board)\n",
    "    return (i, j) not in visited and i >= 0 and i < N and j >= 0 and j < M\n",
    "\n",
    "def dim(board):\n",
    "    return len(board), len(board[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "board = [\n",
    "  ['A','B','C','E'],\n",
    "  ['S','F','C','S'],\n",
    "  ['A','D','E','E']\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exists(board, \"ABCCED\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exists(board, \"SEE\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exists(board, \"ABCB\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exists(board, \"\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}