Find A Way

faw.gif

FAW.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'retina'\n",
    "\n",
    "from IPython.display import display\n",
    "from ipywidgets import interact\n",
    "import matplotlib.animation as animation\n",
    "from matplotlib import pyplot as plt\n",
    "from tqdm import tqdm_notebook as tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "MOVES = ((0, 1), (-1, 0), (1, 0), (0, -1))\n",
    "\n",
    "def draw(path = None):\n",
    "    fig, ax = plt.subplots()\n",
    "    if path:\n",
    "        x, y = zip(*path)\n",
    "        ax.plot(x, y, 'go-')\n",
    "    if (FORBIDDEN):\n",
    "        x, y = zip(*FORBIDDEN)\n",
    "        ax.plot(x, y, 'ro')\n",
    "    plt.axis('equal')\n",
    "    plt.axis('off')\n",
    "\n",
    "def next_pos(pos):\n",
    "    for delta in MOVES:\n",
    "        yield pos[0] + delta[0], pos[1] + delta[1]\n",
    "\n",
    "def intersects(path):\n",
    "    as_set = set(path)\n",
    "    return FORBIDDEN & as_set or len(path) != len(as_set)\n",
    "\n",
    "def in_bound(pos):\n",
    "    return 0 <= pos[0] < X and 0 <= pos[1] < Y\n",
    "\n",
    "def bt(path):\n",
    "    PBAR.update()\n",
    "    if intersects(path): return\n",
    "    if len(path) == X * Y - len(FORBIDDEN):\n",
    "        RBAR.update()\n",
    "        SOLUTIONS.append(path)\n",
    "        return\n",
    "    last = path[-1]\n",
    "    for pos in next_pos(last):\n",
    "        if in_bound(pos):\n",
    "            bt(path + [pos])\n",
    "            \n",
    "def str2conf(string):\n",
    "    lines = list(filter(None, string.splitlines()))\n",
    "    Y, X = len(lines), len(lines[0])\n",
    "    res = []\n",
    "    for y, line in enumerate(lines):\n",
    "        for x, e in enumerate(line):\n",
    "            if e == '*': res.append((x, Y - y - 1))\n",
    "            if e == 'S': START = (x, Y - y - 1)\n",
    "    FORBIDDEN = frozenset(res)\n",
    "    return X, Y, FORBIDDEN, START, []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "X, Y, FORBIDDEN, START, SOLUTIONS = str2conf(\"\"\"\n",
    "\n",
    ".......\n",
    ".*...*.\n",
    "...*...\n",
    "S......\n",
    "\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAvwAAAH0CAYAAABB4/l/AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAWJQAAFiUBSVIk8AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEeNJREFUeJzt3cFtGwe7heFvjKzdiFNDNgLcSJAs\n719BTNCp4N5lgKSQAFrINTiNqADNXYiJE1i2KCkkz5z/eZa2CQx0NOIreUazrOs6AABAp1eXPgAA\nAOB0BD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzw\nAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT\n/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADF\nBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBA\nMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAA\nUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8A\nABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUOybSx8Aj1v2\ny5uZuZqZ1zNzOzPX627947JHhV3y2CSTXfLYJJNd8rRssqzreulj4AuW/XI1M+9m5rsH/vrDzLxf\nd+v1eY8Ku+SxSSa75LFJJrvkadtE8Ida9sv3M/PLfP2yq7uZ+WHdrb+d56iwSx6bZLJLHptkskue\nxk0Ef6DDd5W/z3H3WNzNzNstfZe5VXbJY5NMdsljk0x2ydO6iZt2M72b47d5NTM/nfBY+MQueWyS\nyS55bJLJLnkqN/ET/jCHm0M+PuOl327xJpKtsEsem2SySx6bZLJLnuZNBH+YZb/8z8z876WPAwCA\no/xn3a3/d+mD+BqX9OR5fekDAADgaPHtJvjz3F76AAAAOFp8u3nwVp7n3ukdf/3YljVf17dVNslk\nlzw2yWSXPC/YxG/p4WkOJ/GHJ77sxsl/WnbJY5NMdsljk0x2ydO8ieDP9H7uf7frMe5m5ucTHguf\n2CWPTTLZJY9NMtklT+Umgj/Q4QEOP87jn3B/PuUt/r+SGtglj00y2SWPTTLZJU/rJoI/1Lpbf52Z\ntzNz84V/cjP3T3fbxCOdW9glj00y2SWPTTLZJU/jJn4P/wY8cBOJG3YCHHa5mvtfx3U7M9d2uSyb\nZLJLHptkskuelgYT/Bux7Je/hlp363LJYwEA+G/R0GAu6QEAgGKCHwAAigl+AAAoJvgBAKCY4AcA\ngGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgB\nAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+\nAAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKC\nHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY\n4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAo\nJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAA\nigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcAgGKCHwAAigl+AAAoJvgBAKCY4AcA\ngGKCHwAAigl+AAAoJvgBAKCY4AcAgGLLuq6XPgYeseyXNzPz8W9/9O26W/+41PFwsCxvZuZqZl7P\nzO3MXM9ql0s6nCv/2MS5cnl2yWOTUN5X4rQ0mOAPtuyXq5l5NzPfPfDXH2bm/bpbr897VMzy+C6z\n2uWcnCuZ7JLHJqG8r8RpO1cEf6hlv3w/M7/M1y+7upuZH9bd+tt5jopZjt9lVrucg3Mlk13y2CSU\n95U4jeeK4A90+K7y9znuHou7mXm7pe8yN2t5+i5+InNazpVMdsljk1DeV+K0nitu2s30bo7f5tXM\n/HTCY+ETu+SxSSa75LFJJrvkqdzET/jDPHBzyLE2eRPJZizP38UNV6fhXMlklzw2CeV9JU7zufLN\npQ+Az1y94HXRn2wbZ5c8z93k47Jf/tUD4V9hlzy+fp2W95U8tZu4pCfP6zO/juPYJY+PLZyWc+y0\nvK/kqd1E8Oe5PfPrOI5d8vjYwmk5x07L+0qe2k1c0pPnuXd6x98hvnF2yfPcj238tZZb1nwN7Fa9\nYBNfv07L+0qe2k38hD/M4Q3vwxNfduON8sTW5+3ixqrTca5ksksem4TyvhKn+VwR/Jnez/3vdj3G\n3cz8fMJj4RO75LFJJrvksUkmu+Sp3ETwBzo8wOHHefwT7s+nvMX/V1KF9Wm7eDjK6TlXMtklj01C\neV+J03quCP5Q6279dWbezszNF/7Jzdw/3W0Tj3SusR63i8efn49zJZNd8tgklPeVOI3nigdvbcAD\nN1y5uS3B/UNTrub+13Hdzsy1aysvy7mS6bDLP84Vu1yWcyWU95U4LeeK4N+IZb/8NdS6Wz2dBr7A\nuQLHca7AcRrOFZf0AABAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBA\nMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAA\nUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8A\nABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEP\nAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzw\nAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT\n/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADF\nBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBAMcEPAADFBD8AABQT/AAAUEzwAwBA\nMcEPAADFlnVdL30MPGLZL29m5uPf/ujbdbf+canj4d5hl6uZeT0ztzNzbZfLcq6EWj4/V2a1yyU5\nVzJ5X8nTcq4I/mDLfrmamXcz890Df/1hZt6vu/X6vEeFXfLYJNTy+C6z2uWcnCuZ7JKnbRPBH2rZ\nL9/PzC/z9cuu7mbmh3W3/naeo8IueWwSajl+l1ntcg7OlUx2ydO4ieAPdPiu8vc57h6Lu5l5u6Xv\nMrfKLnlsEmp5+i5+0n9azpVMdsnTuombdjO9m+O3eTUzP53wWPjELnlskskueWySyS55KjfxE/4w\nD9wccqxN3kSyFXbJY5NQy/N3cSPvaThXMtklT/Mm31z6APjM1QteF/3JtnHP3eXjsl/+1QPhxZwr\np+VrWB5fv7rYJU/81y+X9OR5febXcRwf3x62PC1fw/L42MJpxZ9jgj/P7Zlfx3F8fHvY8rR8Dcvj\nYwunFX+OuaQnz3Pv9I6/Q3zjnvvxjb+ub6tecK2lc+W0fA3L4+tXoObrxbeq+X3FT/jDHE7iD098\n2Y2T/7Tskscmodbn7eKG3dNxrmSyS57mTQR/pvdz/7tdj3E3Mz+f8Fj4xC55bJLJLnlskskueSo3\nEfyBDg9w+HEe/4T78ylv8f+V1MAueWwSan3aLh66dXrOlUx2ydO6ieAPte7WX2fm7czcfOGf3Mz9\n09028UjnFnbJY5NQ63G7zGqXc3GuZLJLnsZNPHhrAx64icQNOwHskuewydXc/4q025m5tkmA5fNd\nXLN/Wc6VTHbJ07KJ4N+IZb/8NdS6Wz1xI4RdAIB0LukBAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBi\ngh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCg\nmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAA\nKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8A\nAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAH\nAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4\nAQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJ\nfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBigh8AAIoJfgAAKCb4AQCgmOAHAIBi\ngh8AAIoJfgAAKCb4AQCgmOAHAIBiy7qulz4GHrHslzcz8/Fvf/Ttulv/uNTxcM8ueQ6bXM3M65m5\nnZlrm1yeXfLYJJNd8rRsIviDLfvlambezcx3D/z1h5l5v+7W6/MeFXbJY5NMdsljk0x2ydO2ieAP\nteyX72fml/n6ZVd3M/PDult/O89RYZc8Nslklzw2yWSXPI2bCP5Ah+8qf5/j7rG4m5m3W/ouc6vs\nkscmmeySxyaZ7JKndRM37WZ6N8dv82pmfjrhsfCJXfLYJJNd8tgkk13yVG7iJ/xhHrgR9FhuGD0h\nu+SxSSa75LFJJrvkad7km0sfAJ+5esHroj/ZNu65u3xc9su/eiC8mE0y2SWPTTLZJU98g7mkJ8/r\nM7+O4/j4AgAPiW8EwZ/n9syv4zg+vgDAQ+IbwSU9eZ57p3f8HeIb99yPb/x1fVvVfK3lltklj00y\n2SXPCzaJbzA/4Q9zOIk/PPFlN07+07JLHptksksem2SyS57mTQR/pvdz/7tdj3E3Mz+f8Fj4xC55\nbJLJLnlskskueSo3EfyBDg9w+HEe/4T78ylv8f+V1MAueWySyS55bJLJLnlaNxH8odbd+uvMvJ2Z\nmy/8k5u5f7rbJh7p3MIueWySyS55bJLJLnkaN/HgrQ043ERyNfe/9ul2Zq63cL1YO7vksUkmu+Sx\nSSa75GnZRPADAEAxl/QAAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPAD\nAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8\nAABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUE\nPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAx\nwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQ\nTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAA\nFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8A\nAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPAD\nAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8\nAABQTPADAEAxwQ8AAMUEPwAAFBP8AABQTPADAEAxwQ8AAMUEPwAAFBP8AABQ7P8BB5/9E5BiEzMA\nAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10f3d1550>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 250,
       "width": 382
      }
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "IN_GITHUB = True        \n",
    "\n",
    "if IN_GITHUB:\n",
    "\n",
    "    bt([START]) \n",
    "    if SOLUTIONS: draw(SOLUTIONS[0])\n",
    "        \n",
    "else:\n",
    "    \n",
    "    with tqdm(unit = \"path\", unit_scale = True) as PBAR: \n",
    "        with tqdm(unit = \"solutions\", bar_format = '{l_bar}') as RBAR: \n",
    "            bt([START]) \n",
    "\n",
    "    if SOLUTIONS:        \n",
    "        @interact(n=(0,len(SOLUTIONS)-1))\n",
    "        def draw_sol(n):\n",
    "            return draw(SOLUTIONS[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(X,Y))\n",
    "ax.set_axis_off()\n",
    "ax.set_xlim(-.1,X - .9)\n",
    "ax.set_ylim(-.1,Y - .9)\n",
    "ax.set_aspect('equal')\n",
    "ln, = ax.plot([],[],'go-')\n",
    "\n",
    "def init():\n",
    "    ax.plot(*zip(*FORBIDDEN), 'ro')\n",
    "    return ln\n",
    "\n",
    "def update(i):\n",
    "    ln.set_data(*zip(*SOLUTIONS[i]))\n",
    "    return ln\n",
    "\n",
    "ani = animation.FuncAnimation(\n",
    "    fig, \n",
    "    update, \n",
    "    range(len(SOLUTIONS)),  \n",
    "    init_func = init,\n",
    ")\n",
    "ani.save('faw.gif', writer = animation.ImageMagickFileWriter(fps = 5))\n",
    "plt.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "another_level = \"\"\"\n",
    "......\n",
    "......\n",
    ".S**..\n",
    ".*....\n",
    ".*....\n",
    "..*..*\n",
    "*.....\n",
    "......\n",
    "\"\"\""
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

Find A Way is a really addictive game…