2018_09_SpiralRegion.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "Oq1xibzMT1Wl"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import time\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "import requests\n",
    "from bs4 import BeautifulSoup\n",
    "import itertools\n",
    "from copy import deepcopy as dcopy,copy\n",
    "from skimage.morphology import label\n",
    "from scipy.ndimage import measurements\n",
    "import sys\n",
    "import numba as nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "ICTfvjZUT1Wr"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Shade some cells in the grid below such that the set of shaded cells is connected, has 90-degree rotational symmetry about its center, and contains the same number of shaded cells in each outlined region. The answer to this puzzle is the smallest possible product of the areas of the connected groups of empty squares in the completed grid. — (Note: This post has been edited 2018-09-04 to change the answer to the smallest possible product of areas of connected groups of empty squares.)\n"
     ]
    }
   ],
   "source": [
    "# Interesting puzzle. The tempting first choice is to set the rotation \n",
    "# around the centre point and have a max fill of 6 cells for\n",
    "# each region which doesn't give any solution (the long group bottom\n",
    "# right I guess). Offsetting and padding give options as do reducing \n",
    "# the number of cells filled per group.I've looped through the options\n",
    "# below but none of the other options gave a valid solution before I \n",
    "# got to the published solution. I played around a bit more and\n",
    "# don't think any more padding would improve but haven't proved it\n",
    "\n",
    "url='https://www.janestreet.com/puzzles/spiral-region/'\n",
    "res = requests.get(url)\n",
    "soup = BeautifulSoup(res.content, 'html.parser')\n",
    "x =[text for text in soup.body.stripped_strings]\n",
    "\n",
    "print(\" \".join(x[7:15]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "U9Yh1D3HT1Ws"
   },
   "source": [
    "### Puzzle details\n",
    "<img src=\"https://www.janestreet.com/puzzles/20180904_spiral_region.png\" width=\"250\" >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "0VI0NM6ET1Wt"
   },
   "outputs": [],
   "source": [
    "# set up the groups\n",
    "groups = np.array([[19, 19, 19,  1,  1,  2,  2,  3,  3,  3,  4,  4,  4,  4],\n",
    "                   [19, 19,  5,  1,  1,  1,  2,  2,  3,  3,  3,  3,  4,  4],\n",
    "                   [19,  5,  5,  1,  6,  6,  6,  2,  2,  7,  7,  3,  3,  4],\n",
    "                   [ 5,  5,  5,  9,  6, 10,  6,  6,  2,  7,  8,  8,  4,  4],\n",
    "                   [ 9,  5,  9,  9, 10, 10, 10, 11,  2,  7,  8,  8,  8,  2],\n",
    "                   [ 9,  5,  9, 10, 10, 12, 10, 11,  2,  7,  7,  7,  8,  2],\n",
    "                   [ 9,  9,  9,  9, 12, 12, 11, 11,  2, 13,  8,  8,  8,  2],\n",
    "                   [14,  9,  9, 12, 12, 11, 11,  2,  2, 13,  2,  2,  2,  2],\n",
    "                   [14, 14, 12, 12,  2,  2,  2,  2, 13, 13, 13, 15, 15,  2],\n",
    "                   [14, 16, 16, 17,  2, 18, 18, 18, 18, 13, 13, 13, 15,  2],\n",
    "                   [14, 14, 16, 17,  2,  2, 18,  0, 18, 20, 20, 15, 15,  2],\n",
    "                   [16, 16, 16, 17, 17,  2,  2,  0,  0,  0, 20, 20, 15,  2],\n",
    "                   [16, 17, 16, 17, 17, 17,  2,  2,  0,  0, 20, 20, 15,  2],\n",
    "                   [16, 17, 17, 17, 17, 17, 17,  2,  2,  2,  2,  2,  2,  2]]\n",
    "                  ,dtype=int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 374
    },
    "id": "zexQ8t1kT1W3",
    "outputId": "7c2aec4e-d2fb-45d8-fc7e-679051faafed"
   },
   "outputs": [],
   "source": [
    "class Matrix():\n",
    "    def __init__(self,groups,max_cells,offset):\n",
    "        self.groups = groups\n",
    "        self.max_cells = max_cells\n",
    "        self.fixed =  np.ones((7,7),dtype=int)*-1 \n",
    "        self.offset = offset\n",
    "        self.solution = []\n",
    "        self.end_flag = 0\n",
    "        \n",
    "    # solve by backtracking only considering the 7x7 grid \n",
    "    # which gets rotated\n",
    "    def solve(self):\n",
    "        if self.end_flag == 0:\n",
    "            for row in range(7):\n",
    "                for col in range(7):\n",
    "                    if self.fixed[row,col] == -1:\n",
    "                        for digit in range(2):\n",
    "                            if self.possible(digit,row,col):\n",
    "                                self.fixed[row,col] = digit\n",
    "                                self.solve()\n",
    "                                self.fixed[row,col] = -1\n",
    "                        return\n",
    "                    \n",
    "            big = self.get_big(self.fixed)\n",
    "            self.solution.append(dcopy(big))\n",
    "\n",
    "    def possible(self,digit,row,col):\n",
    "        x = copy(self.fixed)\n",
    "        x[row,col] == digit\n",
    "        big =self.get_big(x)\n",
    " \n",
    "        #check connectivity\n",
    "        if np.max(label(big[:-1,:-1]!=0,connectivity=1)) > 1:\n",
    "            return False\n",
    "            \n",
    "        # check the number counts as determined above are not\n",
    "        # breached\n",
    "        if not self.test_totals(big,self.groups,self.max_cells):\n",
    "            return False\n",
    "\n",
    "        return True\n",
    "   \n",
    "    @staticmethod\n",
    "    @nb.njit\n",
    "    #test the count per cell is not breached\n",
    "    def test_totals(x,groups,max_cells):\n",
    "        for group in range(21):                         \n",
    "            if np.sum(np.ravel(x)[np.ravel(groups)==group]>0) > max_cells:\n",
    "                  return False \n",
    "            if np.sum(np.ravel(x)[np.ravel(groups)==group] != 0) < max_cells :\n",
    "                  return False     \n",
    "        return True\n",
    "    \n",
    "    #code to turn the 7x7 grid into a 14x14 grid with rotational\n",
    "    #symmetry. Can make a smaller grid and then pad.\n",
    "    def get_big(self,x):\n",
    "        x1 = dcopy(x)\n",
    "        x2 = dcopy(x)\n",
    "        x3 = dcopy(x)\n",
    "        if self.offset == 0:\n",
    "            x1 = np.rot90(x1 ,1)\n",
    "            x2 = np.rot90(x2 ,2) \n",
    "            x3 = np.rot90(x3, 3)\n",
    "            y = np.block([[x,x3],[x1,x2]])\n",
    "        \n",
    "        if self.offset == 1:\n",
    "            x1 = np.rot90(x1[:,:-1] ,1)\n",
    "            x2 = np.rot90(x2[:-1,:-1] ,2) \n",
    "            x3 = np.rot90(x3[:-1,:], 3)   \n",
    "            y = np.block([[x,x3],[x1,x2]])\n",
    "            y = np.pad(y,((0,1),(0,1)),'constant',constant_values=0)\n",
    "        \n",
    "        if self.offset == 2:\n",
    "            x1 = np.rot90(x1[:,:-1] ,1)\n",
    "            x2 = np.rot90(x2[:-1,:-1] ,2) \n",
    "            x3 = np.rot90(x3[:-1,:], 3)   \n",
    "            y = np.block([[x,x3],[x1,x2]])\n",
    "            y = np.pad(y,((1,0),(0,1)),'constant',constant_values=0)\n",
    "        \n",
    "        if self.offset == 3:\n",
    "            x1 = np.rot90(x1[:,:-1] ,1)\n",
    "            x2 = np.rot90(x2[:-1,:-1] ,2) \n",
    "            x3 = np.rot90(x3[:-1,:], 3)   \n",
    "            y = np.block([[x,x3],[x1,x2]])\n",
    "            y = np.pad(y,((0,1),(1,0)),'constant',constant_values=0)\n",
    "            \n",
    "        if self.offset == 4:\n",
    "            x1 = np.rot90(x1[:,:-1] ,1)\n",
    "            x2 = np.rot90(x2[:-1,:-1] ,2) \n",
    "            x3 = np.rot90(x3[:-1,:], 3)   \n",
    "            y = np.block([[x,x3],[x1,x2]])\n",
    "            y = np.pad(y,((1,0),(1,0)),'constant',constant_values=0)\n",
    "\n",
    "        return y\n",
    "   \n",
    "    # work out the area for the solution\n",
    "    def areas(self,grid):\n",
    "        labels, num = measurements.label(grid==0)\n",
    "        areas = measurements.sum(grid==0, labels, index=range(1, num+1))\n",
    "        return np.prod(areas)\n",
    "  \n",
    "    # print out the solution\n",
    "    def print_best(self):\n",
    "        if len(self.solution) == 0:\n",
    "            print(\"No solutions\")\n",
    "        else:\n",
    "            area =np.zeros(len(self.solution))\n",
    "            for i in range(len(self.solution)):\n",
    "                area[i] = self.areas(self.solution[i])\n",
    "            best = self.solution[np.argmin(area)]\n",
    "            print(\"\\n***SOLVED***\")\n",
    "            print(\"Area for solution is :{:,.0f}\\n\".format(np.min(area)))\n",
    "            self.grid_print(groups,best)\n",
    "\n",
    "    # function to print the solution\n",
    "    def grid_print(self,groups,numbers):\n",
    "        fig,ax = plt.subplots(1,2,figsize=(8,4))\n",
    "        x = np.array((numbers).astype('int').astype('str'))\n",
    "        x[x==\"0\"] =\"\"\n",
    "        x[x==\"1\"] =\"+\"\n",
    "        ax1 = sns.heatmap(groups,annot=x,cbar=False,cmap=\"tab20b\",fmt=\"\",linewidths=1,ax=ax[0])\n",
    "        ax1.axis(\"off\")\n",
    "        ax2 = sns.heatmap(numbers,cbar=False,cmap=\"Greys\",center=2,fmt=\"\",linewidths=1,ax=ax[1],linecolor=\"grey\")\n",
    "        ax2.axis(\"off\")\n",
    "        plt.tight_layout()\n",
    "   \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 374
    },
    "id": "zexQ8t1kT1W3",
    "outputId": "7c2aec4e-d2fb-45d8-fc7e-679051faafed"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Per range number of cells :5, Offset:1\n",
      "\n",
      "***SOLVED***\n",
      "Area for solution is :1,203,200\n",
      "\n",
      "Solution took 3.0692 seconds\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjgAAAEYCAYAAABRMYxdAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAiKklEQVR4nO3df2xV9f3H8Vfbe+kPS7c4M6vBYrHIoF+gVxhsiFGIjlnRJbDF3M6GQXWgNNYiOAHj9S4Cy/iVYllRBsXQ0RgHiRMZjKXZ1OBwwC0rBbFlHcigEOOIdFKp3f3+cb/3a5PVlnvP53JPPzwf/97r875v7/XmnXPOvaSEw2EBAADYJDXZAwAAAJjGggMAAKzDggMAAKzDggMAAKzDggMAAKzj6ed2vmIFIF4pV3rHYDDIZw2AuAQCgV4/a/pbcNRWe8zIAPmzRxrrJaI180d1jluStP31R4z1oq3yikbHLUmqrioy1ou2NtW2OW5JUtnsfGO9RLQeXTLJcUuSfr18n7GeyZbpXrQVC7/f7/hx6+vrjbVM99za6tkLBAKOW8Fg0FjLdC9Rs7ntNR0I/x+Yfg16wykqAABgHRYcAABgHRYcAABgHRYcAABgHRYcAABgHccLzuGTTVq1s8rELEZbpnuFo25U+fzvuq6F+OTmZuiuyTcY643I92n2zKWuayWiBwADAUdwAACAdVhwAACAdfr9ob+vUvHqInV1d+nS5U5d7OzQE5ufkiTNuWeWxg/zJa1lurdi+ffl9aYqI8Or7OxBWrWyWJJUVxdS4+GzSWshPg9Ov0lpqSnyelOVnp6qbzx0syTprwf+pX+euRRzb8njG+VJ8yojPUvXZebo+fItkqTte2rU3LI/aa1E9ABgIIl7wamatVJS5DqXvU0NWji9Iu4hTLZM9xYv2S0pct3MlCnDVL3+PVe0EJ83d0YWydzcDA0vyNY7737sqLe85jFJketcJt1RrNrty1zRSkQPAAYSTlEBAADrsOAAAADrxH2KKmrs0NEaO3S0iVmMtkz3mo+eU/PRc65rIT7t7Z1qb+801jveFtLxtpDrWonoAcBAwBEcAABgHRYcAABgHRYcAABgnZRwONzX7X3eCAB9SLnSOwaDQT5rAMQlEAj0+lnDERwAAGCdfr9F1VZ7zMgD5c8eaawXba3eOtNx6+nS7ZKkmT+qc9ySpO2vP2KsZ7LVs1de0ei4VV1VZKzVs7epts1xq2x2vitbpnvR1qNLJjluSdKvl+8z1ou2YuH3+x0/bn19vSQpEAg4bklSMBiU5L7ZTM4lfTmb256n9OVz5e925Uz+zXr23PY8pS9n6w1HcAAAgHVYcAAAgHVYcAAAgHVYcAAAgHVYcAAAgHUcLziHTzZp1c4qE7MYN+TGQk2bVJ7sMf5L4agbVT7/u67tuVVubobumnyD61puNyLfp9kzlyZ7DAC4qjiCAwAArMOCAwAArNPvD/19lYpXF6mru0uXLnfqYmeHntj8lCRpzj2zNH6Yz9R8cSm5f4XSUr3yejKUkZ6t0gdWSZLePlSnk2cbkzbXiuXfl9ebqowMr7KzB2nVymJJUl1dSI2Hzya951YPTr9Jaakp8npTlZ6eqm88dLMk6a8H/qV/nrmUtJbbLXl8ozxpXmWkZ+m6zBw9X75FkrR9T42aW/YndzgASLC4F5yqWSslRa7B2dvUoIXTK4wN5dS23y+WFLkGp/C2KdqzrzrJE0UsXrJbUuSamSlThql6/Xuu6rnVmzsjy1puboaGF2TrnXc/dkXL7ZbXPCYpcg3OpDuKVbt9WZInAoCrh1NUAADAOiw4AADAOnGfoooaO3S0xg4dbWIW406fa9bpc83JHuO/NB89p+aj51zbc6v29k61t3e6ruV2x9tCOt4WSvYYAHBVcQQHAABYhwUHAABYhwUHAABYJyUcDvd1e583AkAfUq70jsFgkM8aAHEJBAK9ftZwBAcAAFin329RtdUeM/JA+bNHSpJWb53puPV06XbjrZk/qnPckqTtrz8iSdrV6Pwf+SwuqjbWMt2LtsorGh23JKm6qshYL9oKtW5y3PIVlBlr9extqm1z3CqbnW+s1bP36JJJjlu/Xr4v5v/G7/c7ftz6+npJUiAQcNySpGAwKMnsbG5rme4lajYTr2n09TT9/jA5m5tfAzf/P9objuAAAADrsOAAAADrsOAAAADrsOAAAADrsOAAAADrOF5wDp9s0qqdVSZmMW7IjYWaNsnMN5AKR92o8vnfNdJqbf5E2351xEjLdM/0bNeK5r+d0q/W7DLSys3N0F2TbzDSSkQPAAYCjuAAAADrsOAAAADr9PtDf1+l4tVF6uru0qXLnbrY2aEnNj8lSZpzzyyNH+YzNV9cSu5fobRUr7yeDGWkZ6v0gVWSpLcP1enk2caYWiuWf19eb6oyMrzKzh6kVSuLJUl1dSE1Hj4bU2vt0v36ous/utzZrc86urTymfckSQ+WDNe3imI/hWCyZ3q2a8XSyq36oqtbnZ2X1XGxUz8r3yJJKpl9t8aOy4+p9eD0m5SWmiKvN1Xp6an6xkM3S5L+euBf+ueZSzHPZroHAANJ3AtO1ayVkiLX4OxtatDC6RXGhnJq2+8XS4pcg1N42xTt2Vcdd2vxkt2SItfgTJkyTNXr34u7VblsoqTIdS7v//mMSp74n7hbpnumZ7tWLFtbKilyDc6f/3hETywojrv15s7Iwpybm6HhBdl6592PHc1mugcAAwmnqAAAgHVYcAAAgHXiPkUVNXboaI0dOtrELMadPtes0+eajbSaj55T89FzRloFhderoPB6Iy3TPdOzXSsKx+SpcEyekVZ7e6fa2zuNtBLRA4CBgCM4AADAOiw4AADAOiw4AADAOinhcLiv2/u8EQD6kHKldwwGg3zWAIhLIBDo9bOGIzgAAMA6/X6LavXWmUYe6OnS7cZ6iWg11E5y3JKkqbP3SZJ2NTr/Rz6LiyI/UNi+18xrkHtf5LmanM1Eq2evvKLRcau6qkiSFGrd5LjlKyiTJK1+8g7HLUl6et0hY71o69ElZt67v16+z1gv2oqF3+93/Lj19fXGWj17gUDAcSsYDEoy+zxNzCUlZjbTrwF/t9hbbn6epmfrDUdwAACAdVhwAACAdVhwAACAdVhwAACAdVhwAACAdRwvOENuLNS0SWa+SWOyZdrXc30aOXlpssfoVejDDq3YetpIq7X5E2371REjrUT0TGn+2yn9as0uY70hBeM07ccvGOuZNCLfp9kz3fneBYBE4QgOAACwDgsOAACwTr8/9PdVSu5fobRUr7yeDGWkZ6v0gVWSpLcP1enk2caktUwbN32jUlO9SvNmyZueo28/tEWSdOJAjT45sz+ps81beUJdX4R16fP/6NPPulW2olWSNPcHN2rCqMExtdYu3a8vuv6jy53d+qyjSyufeU+S9GDJcH2r6IaYZzPdM2Vp5VZ90dWtzs7L6rjYqZ+Vb5Eklcy+W2PH5cfcK1nwqtI8g+RNz1JGVo5Kn4n8iNXbv1unkx+8Z3L0mC15fKM8aV5lpGfpuswcPf9/z3X7nho1tyT3vQsAiRb3grPt94slRa6bKbxtivbsq457CJMt0w7ufExS5BqcmwqKdezdZUme6EsbFt0mKXINzu79F7S4dEjcrcplEyVFrpl5/89nVPLE/ziazXTPlGVrSyVFrsH58x+P6IkFxY5629bMkhS5Bqdw4oPa85sXnI5ozPKayHt3RL5Pk+4oVu1297x3ASDROEUFAACsw4IDAACsE/cpqqjT55p1+lyziVmMtky70B7ShfZQssfole/2bPluzzbSKii8XgWF1xtpJaJnSuGYPBWOyTPWO916UKdbDxrrmXS8LaTjbe587wJAonAEBwAAWIcFBwAAWIcFBwAAWIcFBwAAWCclHA73dXufNwJAH1Ku9I7BYJDPGgBxCQQCvX7WcAQHAABYp9+viTfUTjLyQFNn75Mkrd4603Hr6dLtkszMFp3L9PNs3+v8eebet91Yy3Tv/1sH1jtuSVLu+PmSpPKKRset6qoiSVKodZPjlq+gTJK0+sk7HLck6el1h4z1TLZ69ky+BrEIBAKOHzcYDEqS/H6/45Yk1ddH/ukNk7O5+Xma6Jn8m0kD4+/mttlMvp6me4l6f/SGIzgAAMA6LDgAAMA6LDgAAMA6LDgAAMA6rlpwhtxYqGmTypM9RsKFPuzQiq2nXdtzq+EF2XqkxNy/H2XSkIJxmvbjF1zXSkQPAAYCVy04AAAAJrDgAAAA6/T7OzhXQ8n9K5SW6pXXk6GM9GyVPrBKkvT2oTqdPNuY3OEMmrfyhLq+COvS5//Rp591q2xFqyRp7g9u1IRRg5Pec6uFlcPl8aQqPT1VWVlpenbRCEnSG2+e0bEPLiZ1tpIFryrNM0je9CxlZOWo9JnIbzy8/bt1OvnBe0lrJaIHAAOJKxacbb9fLClyDU7hbVO0Z191kidKjA2LbpMUuWZm9/4LWlw6xFU9t1q1tkVS5BqciROuV922U0me6Evb1sySFLnOpXDig9rzmxdc0UpEDwAGEk5RAQAA67DgAAAA67jiFFXU6XPNOn2uOdljJJzv9mz5bs92bc+tWlo71NLakewxenW69aBOtx50XSsRPQAYCDiCAwAArMOCAwAArMOCAwAArMOCAwAArJMSDof7ur3PGwGgDylXesdgMMhnDYC4BAKBXj9rOIIDAACs0+/XxBtqJxl5oKmz90mSVm+d6bj1dOl2SWZmi87Vvtf5XJKUe992Y71oa9ldZl6Dpe+Ye67//zwPrHfckqTc8fMlSeUVjY5b1VVFkqRQ6ybHLV9BmbGW6V60tfrJOxy3JOnpdYckmX0NYhEIBBw/bjAYNNYy3Yu2/H6/41Z9feSf3TD9PE3OZqJlunetzJao5+nm/0d7wxEcAABgHRYcAABgHRYcAABgHRYcAABgHRacKxT6sEMrtp5O9hi9yivyafqSpUZapp9n6Ohprdiw10hreEG2HinJM9Jq/tsp/WrNLiMt0z3TswHAtYgFBwAAWIcFBwAAWKff38G51s1beUJdX4R16fP/6NPPulW2olWSNPcHN2rCqMFJne0nL2+Ux+uVNzNLmTk5enTzFklSw4Ya/f39/TG1TD/Pec+/pq6ubl36vEufdnSqbPG2SM9/pyaMGRpTa2HlcHk8qUpPT1VWVpqeXTRCkvTGm2d07IOLMbWWVm7VF13d6uy8rI6LnfpZ+RZJUsnsuzV2XH5MLdM907MBwLWMBacfGxbdJilybcru/Re0uHRIkif60pa5j0mKXIMzprhYO5cvi7tl+nlu+PnDkd7R09r99jEtnndf3K1Va1skRa7BmTjhetVtOxV3a9naUkmR61z+/McjemJBcdwt0z3TswHAtYxTVAAAwDosOAAAwDqcorpCvtuz5bs9O9lj9OpUY0inGkNGWqafp2/UEPlGmTmt19LaoZbWDiOtwjF5Khxj5ivnpnumZwOAaxFHcAAAgHVYcAAAgHVYcAAAgHVYcAAAgHVSwuFwX7f3eSMA9CHlSu8YDAb5rAEQl0Ag0OtnDUdwAACAdfr9mnhD7SQjDzR19j5jPbe2evaW3eW8t/Qdc62evfYD6x23csfPN9bq2SuvaHTcqq4qkiTtKH7AcWvGrrckSaufvMNxS5KeXnfIWM9kq2fP5GsQi0Ag4Phxg8GgsVbPnt/vd9yqr6833nLz82S22AyE94eb/x/tDUdwAACAdVhwAACAdVhwAACAdVhwAACAdaxecL6e69PIyUtd1zItr8in6UvcOVvo6Gmt2LA32WP8lxtGj9a4ykpjvSEF4zTtxy8Y6wEAnLF6wQEAANcmFhwAAGCdfn8HZyAaN32jUlO9SvNmyZueo28/tEWSdOJAjT45sz9pLdN+8vJGebxeeTOzlJmTo0c3R2Zr2FCjv7+f3NnmPf+aurq6denzLn3a0amyxdskSXP9d2rCmKFJm+uetWuU6vHKk5mhQYMHa+pLL0mSjtTW6vyhQzH3Sha8qjTPIHnTs5SRlaPSZyK/P/H279bp5AfvGZ0dAHDlrFxwDu58TFLkupmbCop17N1lrmiZtmVuZLa8Ip/GFBdr53L3zLbh5w9LilyDs/vtY1o8774kTxTxp8oFkiLX4Ay9914dXLvWUW/bmlmSItfgFE58UHt+84LTEQEABnCKCgAAWIcFBwAAWMfKU1RRF9pDutAecl3LtFONIZ1qdOdsvlFD5Bs1JNlj/JePm5r0cVOTsd7p1oM63XrQWA8A4AxHcAAAgHVYcAAAgHVYcAAAgHVYcAAAgHVSwuFwX7f3eSMA9CHlSu8YDAb5rAEQl0Ag0OtnDUdwAACAdfr9mvixOeVGHmjk5mpJUkPtJMetqbP3GW8tu8t5S5KWvmOuF221H1jvuCVJuePnG+tFW+UVjY5bklRdVWSsF23tKH7AcWvGrrckuft5unm2WAQCAcePGwwGJUl+v99xS5Lq6+uN9dzaMt0bCLOZeK9JZt9vJmeLzmX6ebp5tt5wBAcAAFiHBQcAAFiHBQcAAFiHBQcAAFjHVQvO13N9Gjl5qSt7eUU+TV/ivpYkhY6e1ooNe13XkqThBdl6pCTPWM+UG0aP1rjKymSPAQBIEFctOAAAACaw4AAAAOv0+zs4V8O46RuVmupVmjdL3vQcffuhLZKkEwdq9MmZ/Unt/eTljfJ4vfJmZikzJ0ePbo60GjbU6O/vJ68lSfOef01dXd269HmXPu3oVNnibZKkuf47NWHM0KS1JGlh5XB5PKlKT09VVlaanl00QpL0xptndOyDizH3TLln7RqlerzyZGZo0ODBmvrSS5KkI7W1On/oUNLmAgCY5YoF5+DOxyRFrpm5qaBYx95d5prelrmRVl6RT2OKi7VzuTtakrTh5w9Lilw3s/vtY1o87z5XtCRp1doWSZFrcCZOuF5120456pnyp8oFkiLX4Ay9914dXLs2yRMBABKBU1QAAMA6LDgAAMA6rjhFFXWhPaQL7SFX9k41hnSq0X0tSfKNGiLfqCGua0lSS2uHWlo7jPVM+bipSR83NSV7DABAgnAEBwAAWIcFBwAAWIcFBwAAWIcFBwAAWCclHA73dXufNwJAH1Ku9I7BYJDPGgBxCQQCvX7WcAQHAABYp9+viR+bU27kgUZurjbWi7aW3TXJcWvpO/uMtXr2yisaHbeqq4qMtUz3EjXbjuIHHLdm7HrLla2evfaaTY5buY+XGWv17Jl8f8TC7/c7ftz6+npjLdO9aCsQCDhuBYNBSeafp8nZTLR69tz8/nDb3+1afH/0hiM4AADAOiw4AADAOiw4AADAOiw4AADAOo4XnKwRw3XTnEdMzGK0JUl5RT5NX7LUWM+U4QXZeqQkL9ljXBUmn+sNo0drXGWlkZabhT46pRV7diV7DAAY0DiCAwAArMOCAwAArNPv7+B8lVufW6gUj0ep6elKuy5LGS88K0k6//ob+nfzsaS1JOknL2+Ux+uVNzNLmTk5enTzFklSw4Ya/f39/TH3TFlYOVweT6rS01OVlZWmZxeNkCS98eYZHfvgYtLmSgSTz/WetWuU6vHKk5mhQYMHa+pLL0mSjtTW6vyhQ8ZnT5Z59VvV1d2tS12X9Wlnp8rqtkiS5k6+WxNuzU/ucAAwwMS94PzjxVWSItfNfO3OiTq7uS7uIUy2JGnL3MckRa7BGVNcrJ3LlznqmbJqbYukyHUpEydcr7ptp5I8UeKYfK5/qlwgKXINztB779XBtWuNzOg2G/ylkiLX4Ow+ekSLpxUneSIAGLg4RQUAAKzDggMAAKwT9ymqqM+Ot+iz4y0mZjHakqRTjSGdagwZ65nS0tqhltaOZI9xVZh8rh83NenjpiYjLTfz3ZIn3y3Xxs8IAECicAQHAABYhwUHAABYhwUHAABYhwUHAABYJyUcDvd1e583AkAfUq70jsFgkM8aAHEJBAK9ftZwBAcAAFin36+JH5tTbuSBRm6uliQ9N3Wh49aLDauMt7bNWO+4JUklO+ZLksorGh23qquKJEmhJxsctyTJt26qsZ7JluletLWj+AHHrRm73jLWMt2LttprNjluSVLu42WSzL53Y+H3+x0/bn19vSQpEAg4bklSMBiUZHY2nmfyegPh72ZiNpNzSQPjNegNR3AAAIB1WHAAAIB1WHAAAIB1WHAAAIB1HC84WSOG66Y5j5iYxbj8sbdpxjMPG2l9s/Bmfad8qpGWadkFX1fej0e6rpWInik3jB6tcZWVyR6jV6ZnC310Siv27DLWA4CBgCM4AADAOiw4AADAOv3+Ds5XufW5hUrxeJSanq6067KU8cKzkqTzr7+hfzcfMzZgPOauf1Ieb5oGZaYrc3CW5r8SOdy/55W31Hrgw5ha3/vFD5XmTZMnw6tB2em6f3XklFfj1n062/iR8dljcfuCcUrxpCotPU1pWV6NeObbkqQzvzuhix98krRWInqm3LN2jVI9XnkyMzRo8GBNfeklSdKR2lqdP3QoaXMlYrZ59VvV1d2tS12X9Wlnp8rqtkiS5k6+WxNuzTc5OgC4TtwLzj9ejPxAXtaI4franRN1dnOdsaGcenn+OkmRa3B808Zrxy9fi7v1h2d/KylyDc6wKd/SX6rN/LCdCR+uOSgpcp3L9RNv0qnfxL9YmmwlomfKnyoXSIpc5zL03nt1cO3aJE/0JdOzbfCXSopcg7P76BEtnlbseEYAGCg4RQUAAKzDggMAAKwT9ymqqM+Ot+iz4y0mZjGu7fAJtR0+YaR1vvmMzjefMdIyraP1gjpaL7iulYieKR83NenjpqZkj9Er07P5bsmT75Y8Yz0AGAg4ggMAAKzDggMAAKzDggMAAKzDggMAAKyTEg6H+7q9zxsBoA8pV3rHYDDIZw2AuAQCgV4/aziCAwAArNPv18SPzSk38kAjN1cb60Vbz01d6Lj1YkPkF5m3zVjvuCVJJTvmS5LKKxodt6qrioy1evZCTzr/NWbfusi/rD5p8hLHLUna9+5ySWZna6t1/uvJ+bNHGmv17LXXbHLcyn28zFirZ8/kezcWfr/f8ePW19cba5nuRVuBQMBxKxgMGmuZ7kVbbn4NbJ/N5HtNMvuaJmq23nAEBwAAWIcFBwAAWIcFBwAAWIcFBwAAWMfxgpM1YrhumvOIiVmMtiQpf+xtmvHMw8Z614Lsgq8r78cjjfV8vnwtXTLTSMvkbIdPNmnVziojrUT0TAp9dEor9uxK9hgAcFVxBAcAAFiHBQcAAFin39/B+Sq3PrdQKR6PUtPTlXZdljJeeFaSdP71N/Tv5th+M8RkS5Lmrn9SHm+aBmWmK3Nwlua/UilJ2vPKW2o98GHMvWvB7QvGKcWTqrT0NKVleTXimW9Lks787oQufvBJzL2NrzwurzdNWZnpysnJ1JbayO8f1dTs0f73W5I2W8Wri9TV3aVLlzt1sbNDT2x+SpI0555ZGj/MF1MrET2T5tVvVVd3ty51XdannZ0qq9siSZo7+W5NuDU/qbMBQKLFveD848XID+RljRiur905UWc318U9hMmWJL08f52kyDU4vmnjteOXrznqXQs+XHNQUuQ6l+sn3qRTv3H2w3aP/bRGUuQanOL779Cy5dtdMVvVrJWSItfM7G1q0MLpFXG3EtEzaYO/VFLkGpzdR49o8bTiJE8EAFcPp6gAAIB1WHAAAIB14j5FFfXZ8RZ9djy2ayquRkuS2g6fUNvhE8Z614KO1gvqaL1grBcKtSkUajPSMjnb2KGjNXboaCOtRPRM8t2SJ98teckeAwCuKo7gAAAA67DgAAAA67DgAAAA67DgAAAA66SEw+G+bu/zRgDoQ8qV3jEYDPJZAyAugUCg188ajuAAAADr9Ps18eemLjTyQC82rDLWS0Rr24z1jluSVLJjvrFetFVe0ei4JUnVVUXGetHWpMlLHLckad+7y431EtFqq3X2y85R+bNHGutFW+01mxy3JCn38TJJZt8fsfD7/Y4ft76+XpIUCAQctyQpGAwa60VbJp+niVbPnsnnafo1uFb+bm7+/8DNs/WGIzgAAMA6LDgAAMA6LDgAAMA6LDgAAMA6jhec/LG3acYzD5uYxdW+WXizvlM+1XUtt/P58rV0yUzXtUw7fLJJq3ZWJXuMXoU+OqUVe3YlewwAuKo4ggMAAKzDggMAAKzT7+/gfJW565+Ux5umQZnpyhycpfmvVEqS9rzylloPfGhswGT73i9+qDRvmjwZXg3KTtf9qyOn4xq37tPZxo+S1nK7ja88Lq83TVmZ6crJydSW2nJJUk3NHu1/vyVpLdMqXl2kru4uXbrcqYudHXpi81OSpDn3zNL4Yb6kzjavfqu6urt1qeuyPu3sVFndFknS3Ml3a8Kt+UmdDQASLe4F5+X56yRFrsHxTRuvHb98zdhQbvKHZ38rKXLdzLAp39Jfqhtc0XK7x35aIyly3Uzx/Xdo2fLtrmiZVjVrpaTINTh7mxq0cHpFkif60gZ/qaTINTi7jx7R4mnFSZ4IAK4eTlEBAADrsOAAAADrxH2KKqrt8Am1HT5hYhZXO998Ruebz7iu5XahUJtCoTbXtUwbO3S0xg4dnewxeuW7JU++W/KSPQYAXFUcwQEAANZhwQEAANZhwQEAANZhwQEAANZJCYfDfd3e540A0IeUK71jMBjkswZAXAKBQK+fNRzBAQAA1un3a+LPTV1o5IFebFglSdo2Y73jVsmO+ZLMzGZyLunL2Uw+T9OzlVc0Om5VVxUZa/XsTZq8xHFr37vLjbfaao85bklS/uyRxnrRVnvNJsctScp9vEyS2fdHLPx+v+PHra+vN9Yy3UtEKxAIOG5JUjAYNNYz2TLdi7aulfeHm5+n6fdHbziCAwAArMOCAwAArMOCAwAArMOCAwAArON4wckfe5tmPPOwiVn0zcKb9Z3yqUZakrtnQ+x8vnwtXTLTdS1JOnyySat2VrmuJUmhj05pxZ5dxnoAMBBwBAcAAFiHBQcAAFin39/B+Spz1z8pjzdNgzLTlTk4S/NfqZQk7XnlLbUe+DCm1vd+8UOledPkyfBqUHa67l8dOa3UuHWfzjZ+ZNVsiN3GVx6X15umrMx05eRkakttuSSppmaP9r/fkrSWJFW8ukhd3V26dLlTFzs79MTmpyRJc+6ZpfHDfElrSdK8+q3q6u7Wpa7L+rSzU2V1WyRJcyffrQm35sfcA4CBJO4F5+X56yRFrnPxTRuvHb98Le4h/vDsbyVFrnMZNuVb+kt1Q9wtt8+G2D320xpJketmiu+/Q8uWb3dFS5KqZq2UFLluZm9TgxZOr3BFS5I2+EslRa7B2X30iBZPK3bUA4CBhFNUAADAOiw4AADAOnGfoopqO3xCbYdPmJhF55vP6HzzGSMtyd2zIXahUJtCoTbXtSRp7NDRGjt0tOtakuS7JU++W/KM9QBgIOAIDgAAsA4LDgAAsA4LDgAAsA4LDgAAsE5KOBzu6/Y+bwSAPqRc6R2DwSCfNQDiEggEev2s4QgOAACwTr9fE39u6kIjD/RiwypJ0rYZ6x23SnbMd2XLdG8gzFZe0ei4JUnVVUXGem5tme4NhNliEQgEHD9uMBg01jLdc2vLdI/Z7GqZ7iVqtt5wBAcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFiHBQcAAFgnJRwO93V7nzcCQB9SrvSOwWCQzxoAcQkEAr1+1vS34AAAAAw4nKICAADWYcEBAADWYcEBAADWYcEBAADWYcEBAADWYcEBAADW+V/uVbEy4MjUeAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 576x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Looking at the puzzle have options\n",
    "# none of the other offsets or max fills work\n",
    "# so have just displayed the solution\n",
    "\n",
    "overall_start = time.perf_counter()\n",
    "\n",
    "for offset,max_fill in itertools.product(range(1,2),range(5,6)):\n",
    "    \n",
    "    start = time.perf_counter()\n",
    "    print(\"Per range number of cells :{}, Offset:{}\".format(max_fill,offset))\n",
    "    test = Matrix(groups,max_fill,offset)\n",
    "    test.solve()\n",
    "    stop =  time.perf_counter()\n",
    "    test.print_best()\n",
    "    print('Solution took {:0.4f} seconds'.format((stop-start)))\n",
    "\n",
    "#rint('\\nAll options took {:0.4f} seconds'.format((stop-overall_start)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 374
    },
    "id": "zexQ8t1kT1W3",
    "outputId": "7c2aec4e-d2fb-45d8-fc7e-679051faafed"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The smallest product we were able to find is 1203200 , which results from the shading shown on the left. Congrats to those of you who found it!\n"
     ]
    }
   ],
   "source": [
    "url='https://www.janestreet.com/puzzles/solutions/september-2018-solution/'\n",
    "res = requests.get(url)\n",
    "soup = BeautifulSoup(res.content, 'html.parser')\n",
    "x =[text for text in soup.body.stripped_strings]\n",
    "\n",
    "print(\" \".join(x[7:10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ld_NFUIfT1W9"
   },
   "source": [
    "### Puzzle solution\n",
    "<img src=\"https://www.janestreet.com/puzzles/20181001_spiral_ans.png\" width=\"300\" >"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution= np.array([[1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0],\n",
    "                    [1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0],\n",
    "                    [1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0],\n",
    "                    [1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0],\n",
    "                    [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0],\n",
    "                    [0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0],\n",
    "                    [0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0],\n",
    "                    [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0],\n",
    "                    [1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0],\n",
    "                    [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0],\n",
    "                    [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0],\n",
    "                    [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0],\n",
    "                    [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0],\n",
    "                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],dtype =int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "include_colab_link": true,
   "name": "JaneSt-Feb18.ipynb",
   "provenance": []
  },
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}