Shortest path for knight while avoiding bishop

knight-vs-bishop.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "about-briefing",
   "metadata": {},
   "source": [
    "# Reach Target with Knight\n",
    "\n",
    "Given a chess board, the position of a knight on the board, the position of a bishop on the board and a target destination square, find the shortest path that the knight can take to the target without being attacked by the bishop.\n",
    "\n",
    "## Solution\n",
    "\n",
    "We can interpret this as a graph problem, where the nodes of the graph are the squares on the board that are not attacked by the bishop, and there is an edge between two nodes if they are a knights move apart from each other.\n",
    "\n",
    "There are multiple ways to solve from there; but the most simple would be a breadth first search. A single ended breadth first search would be easier to implement than a double ended search, so let's try to do that first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "sharing-white",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestPath(knight: str, bishop: str, target: str):\n",
    "    (kx, ky), bishop, (tx, ty) = map(coordsFromChessPosition, (knight, bishop, target))\n",
    "    \n",
    "    if (kx, ky) == (tx, ty):\n",
    "        return 0\n",
    "    \n",
    "    q = [(kx, ky)]\n",
    "    seen = set(q)\n",
    "    moves = 1\n",
    "    \n",
    "    while q:\n",
    "        newQ = []\n",
    "        \n",
    "        for kx, ky in q:\n",
    "            # There are 8 knights moves from kx, ky\n",
    "            for dx, dy in [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]:\n",
    "                x, y = kx + dx, ky + dy\n",
    "                \n",
    "                if (\n",
    "                    (x, y) in seen or # We have been here before\n",
    "                    attackedByBishop((x, y), bishop) or # We would be attacked\n",
    "                    not (0 <= x < 8 and 0 <= y < 8) # We are off the board\n",
    "                ):\n",
    "                    # Moving to (x, y) is not viable for some reason.\n",
    "                    continue\n",
    "                    \n",
    "                if (x, y) == (tx, ty):\n",
    "                    return moves\n",
    "                \n",
    "                seen.add((x, y))\n",
    "                newQ.append((x, y))\n",
    "        \n",
    "        q = newQ\n",
    "        moves += 1\n",
    "    \n",
    "    # We could never get to the target.\n",
    "    return -1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "desperate-tumor",
   "metadata": {},
   "source": [
    "## Improving the solution\n",
    "\n",
    "We can see that there are a couple of extra methods that we will need:\n",
    "\n",
    "1. We need a method that can transform chess positions (like \"a5\" or \"h7\") into coordinates (like (0, 4) or (7, 6)).\n",
    "2. We need a method that can determine whether a square is under attack from a bishop\n",
    "\n",
    "## Is a piece under attack?\n",
    "\n",
    "Bishops in chess move diagonally, and can move any number of squares in either diagonal direction. If we consider what this means in terms of the coordinates of the bishop, we get the following:\n",
    "\n",
    "If there is a bishop at position $(b_x, b_y)$ then it can move on the \"positive\" diagonal to $(b_x + i, b_y + i)$ and on the \"negative\" diagonal to $(b_x + i, b_y - i)$ for any $i\\in\\mathbb{Z}$. If we have a piece at position $(p_x, p_y)$, then the bishop will have to move to that square to capture the piece; the difference in positions as a vector will be $(p_x - b_x,p_y - b_y)$. If this difference looks like $(j, j)$ or $(j, -j)$ for some $j\\in\\mathbb{Z}$, then the bishop will be able to move to the piece's square in one move. The piece is under attack!\n",
    "\n",
    "We can now implement a simple method that uses this logic to determine if a piece is under attack by a bishop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "excited-kelly",
   "metadata": {},
   "outputs": [],
   "source": [
    "def attackedByBishop(pieceCoords, bishopCoords):\n",
    "    px, py = pieceCoords\n",
    "    bx, by = bishopCoords\n",
    "    \n",
    "    dx, dy = px - bx, py - by\n",
    "    \n",
    "    return dx == dy or dx == -dy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "scheduled-moore",
   "metadata": {},
   "outputs": [],
   "source": [
    "def coordsFromChessPosition(position):\n",
    "    file, rank = position[:2]\n",
    "    \n",
    "    x = ord(file) - ord('a')\n",
    "    y = int(rank) - 1\n",
    "    \n",
    "    return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "awful-century",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "83.4 µs ± 3.75 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('g1', 'g7', 'c7')\n",
    "shortestPath('g1', 'g7', 'c7')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "regular-drama",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.87 µs ± 35.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('h1', 'e1', 'c8')\n",
    "shortestPath('h1', 'e1', 'c8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "fallen-violation",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "171 µs ± 5.09 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('h1', 'h8', 'a8')\n",
    "shortestPath('h1', 'h8', 'a8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "magnetic-idaho",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "177 µs ± 4.6 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('c8', 'e1', 'h1')\n",
    "shortestPath('c8', 'e1', 'h1')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "controversial-whale",
   "metadata": {},
   "source": [
    "## Improving our solution\n",
    "\n",
    "Currently we are only doing a single sided breadth first search, which will cause us to check far more squares than we need to. We can do a search from the target in tandem with the search from the knights position to have an even faster algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "impressive-ballot",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestPath(knight, bishop, target):\n",
    "    (kx, ky), bishop, (tx, ty) = map(coordsFromChessPosition, (knight, bishop, target))\n",
    "    \n",
    "    if (kx, ky) == (tx, ty):\n",
    "        return 0\n",
    "    \n",
    "    kq = [(kx, ky)]\n",
    "    kseen = set(kq)\n",
    "    \n",
    "    tq = [(tx, ty)]\n",
    "    tseen = set(tq)\n",
    "    \n",
    "    moves = 1\n",
    "    \n",
    "    while kq:\n",
    "        newQ = []\n",
    "        \n",
    "        for kx, ky in kq:\n",
    "            \n",
    "            for dx, dy in [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]:\n",
    "                x, y = kx + dx, ky + dy\n",
    "                \n",
    "                if (\n",
    "                    (x, y) in kseen or # We have been here before\n",
    "                    attackedByBishop((x, y), bishop) or # We would be attacked\n",
    "                    not (0 <= x < 8 and 0 <= y < 8) # We are off the board\n",
    "                ):\n",
    "                    # Moving to (x, y) is not viable for some reason.\n",
    "                    continue\n",
    "                \n",
    "                # Explanation about this below\n",
    "                if (x, y) in tseen:\n",
    "                    return moves\n",
    "                \n",
    "                kseen.add((x, y))\n",
    "                newQ.append((x, y))\n",
    "        \n",
    "        kq, kseen, tq, tseen = tq, tseen, newQ, kseen\n",
    "        moves += 1\n",
    "    \n",
    "    return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "reserved-landing",
   "metadata": {},
   "source": [
    "## Wait a second...\n",
    "\n",
    "The astute among you may be wondering whether checking `if (x, y) in tseen` will work, and that is good, it is maybe not immediately obvious that this is ok; what if you landed somewhere that was less moves away before? The answer is that when (if) the two searches meet, they must meet at their horizon; the point that they meet at will always be the latest point.\n",
    "\n",
    "We can see this due to symmetry. If we land on a point that is not on the horizon of the other search, then the other search would have been to the square that we were on before first.\n",
    "\n",
    "Now that we know our solution is correct, lets see if it is faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "genuine-guitar",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "35.2 µs ± 337 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('g1', 'g7', 'c7')\n",
    "shortestPath('g1', 'g7', 'c7')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "bridal-turkish",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13.1 µs ± 135 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('h1', 'e1', 'c8')\n",
    "shortestPath('h1', 'e1', 'c8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "unnecessary-kruger",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "69.4 µs ± 1.8 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('h1', 'h8', 'a8')\n",
    "shortestPath('h1', 'h8', 'a8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "pending-watson",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32.7 µs ± 1.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit shortestPath('c8', 'e1', 'h1')\n",
    "shortestPath('c8', 'e1', 'h1')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "coordinated-silence",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Our new double-ended breadth first search is much faster for most calculations. It is slower on the second test case (where the knight cannot even move a single square) likely due to the added overhead associated with having two queues and two sets as opposed to only having one of each in the naiive solution.\n",
    "\n",
    "All other solutions are at least a 2x speed up. Not bad!"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}