Probabilistic Nonogram Solver.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Probabilistic nonogram solver "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Matplotlib is building the font cache; this may take a moment.\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "from pylab import rcParams\n",
    "plt.style.use('seaborn-whitegrid')\n",
    "rcParams['figure.figsize'] = 10, 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## get_config_distribution\n",
    "Given a list of all possible configurations for a particular row, identify the probability distribution over those rows.\n",
    "\n",
    "As tested below, if there are only 3 possible row configuration: `1,0,0`, `0,1,0`, `1,0,1`, and  the a-priori probability for each of the 3 pixels being filled is `[0.1, 0.9, 0.000]`, then the first row configuration is unlikely, the second is likely, and the third is impossible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_config_distribution(row_configs, a_priori_cell_probs):\n",
    "    \"\"\"\n",
    "    Returns a list of probabilities, one per item in row_configs indicating the probability it's \n",
    "    correct given the a_priori_cell_probs (the probability that the cells of this row are filled).\n",
    "    \"\"\"\n",
    "    row_config_sum_log_probs = []\n",
    "    for row_config in row_configs:\n",
    "        row_config_sum_log_probs.append(\n",
    "            np.sum(np.log(row_config*a_priori_cell_probs + (1-row_config)*(1-a_priori_cell_probs)))\n",
    "        )\n",
    "    \n",
    "    row_config_sum_log_probs = np.array(row_config_sum_log_probs)\n",
    "    \n",
    "    # this is P(we see this row config(i) | the probabilities that individual cells are filled is a_priori_cell_probs)\n",
    "    row_config_probs = np.exp(row_config_sum_log_probs) \n",
    "    \n",
    "    # but then we normalize it so that we have a probability distribution over row_configs\n",
    "    # the theory can probably be tightened up here\n",
    "    config_distribution = row_config_probs/np.sum(row_config_probs)  \n",
    "    return config_distribution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<ipython-input-105-744f41ed9c27>:9: RuntimeWarning: divide by zero encountered in log\n",
      "  np.sum(np.log(row_config*a_priori_cell_probs + (1-row_config)*(1-a_priori_cell_probs)))\n"
     ]
    }
   ],
   "source": [
    "# test get_config_distribution\n",
    "row_configs = np.array([\n",
    "    [1, 0, 0],\n",
    "    [0, 1, 0],\n",
    "    [1, 0, 1],\n",
    "])\n",
    "\n",
    "a_priori_cell_probs = np.array([0.1, 0.9, 0.000])\n",
    "\n",
    "config_distribution = get_config_distribution(row_configs, a_priori_cell_probs)\n",
    "assert np.argmax(config_distribution) == 1\n",
    "assert config_distribution[2] == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## get_posteriori_cell_probs\n",
    "If you have all the row configurations and distribution across the row configs, then you can predict the probability that a pixel will be filled."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_posteriori_cell_probs(row_configs, config_distribution):  \n",
    "    posteriori_cell_probs = None\n",
    "    for i, row_config in enumerate(row_configs):\n",
    "        if posteriori_cell_probs is None:\n",
    "            posteriori_cell_probs = row_config*config_distribution[i]\n",
    "        else:\n",
    "            posteriori_cell_probs += row_config*config_distribution[i]\n",
    "    return posteriori_cell_probs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test get_posteriori_cell_probs\n",
    "config_distribution = [0.2, 0.3, 0.5]  # corresponds to the rows in row_configs\n",
    "posteriori_cell_probs = get_posteriori_cell_probs(row_configs, config_distribution)\n",
    "assert np.all(posteriori_cell_probs == np.array([0.7, 0.3, 0.5]))  # you should be able to do this by hand easily looking at the input\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## generate_row_configs\n",
    "Given a set of \"vals\" corresponding to a single row, and the width of the row, then determine all possible row configurations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_row_configs(vals, width, first_pixels=None):\n",
    "    \"\"\"Given list of ints and a width, generate all possible pixle patterns\n",
    "    \n",
    "    Example: vals = [2,1] width = 5\n",
    "      output: [\n",
    "        [1,1,0,1,0],\n",
    "        [1,1,0,0,1],\n",
    "        [0,1,1,0,1],\n",
    "      ]\n",
    "    \"\"\"\n",
    "    if first_pixels is None:\n",
    "        first_pixels = []\n",
    "        \n",
    "    minimum_width_of_pixels = sum(vals)+len(vals)-1\n",
    "    assert minimum_width_of_pixels <= width, \"the row isn't wide enough for the vals\"\n",
    "    for offset in range(width - (minimum_width_of_pixels) + 1):\n",
    "        if len(vals) == 1:\n",
    "            # then we are in a leaf recursion and we yield\n",
    "            last_pixels = np.zeros(width)\n",
    "            last_pixels[offset:offset+vals[0]] = 1\n",
    "            yield np.concatenate([first_pixels,last_pixels])\n",
    "        else:\n",
    "            # then we are in the middle of the array and we need to recurse\n",
    "            middle_width = offset + vals[0] + 1\n",
    "            middle_pixels = np.zeros(middle_width)\n",
    "            middle_pixels[offset:offset+vals[0]] = 1\n",
    "            sub_vals = vals[1:]\n",
    "            sub_width = width-middle_width\n",
    "            sub_first_pixels = np.concatenate([first_pixels,middle_pixels])\n",
    "            for config in generate_row_configs(sub_vals, sub_width, sub_first_pixels):\n",
    "                yield config     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test generate_row_configs\n",
    "expected = [\n",
    "    [1., 1., 0., 1., 0.],\n",
    "    [1., 1., 0., 0., 1.],\n",
    "    [0., 1., 1., 0., 1.],\n",
    "]\n",
    "for i, row in enumerate(generate_row_configs([2,1],5)):\n",
    "    assert np.all(row == expected[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nonogram\n",
    "Create a class for holding all the nonogram data, updating it, and plotting it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {},
   "outputs": [],
   "source": [
    "ROW = 1\n",
    "COL = 2\n",
    "\n",
    "class Nonogram:    \n",
    "    def __init__(self, rows, cols, height, width, k = 0.1, goal=None):\n",
    "        self.rows = rows  # array of array of ints\n",
    "        self.cols = cols  # array of array of ints\n",
    "        self.height = height  # int\n",
    "        self.width = width  # int\n",
    "        self.k = k  # float from 0 to 1 - how much to weight the update in probability update\n",
    "        self.goal = goal  # height x width matrix of ones and zeros - the correct nonogram completion\n",
    "        \n",
    "        # initialize prior probability for all pixels being filled (50/50 chance plus noise to break symmetry)\n",
    "        self.pixel_probs = np.random.normal(np.zeros([height,width]), 0.001)+0.5\n",
    "        \n",
    "    def _update(self, row_or_col):\n",
    "        if row_or_col == ROW:\n",
    "            width = self.width\n",
    "            height = self.height\n",
    "            rows = self.rows\n",
    "            pixel_probs = self.pixel_probs\n",
    "        else:\n",
    "            width = self.height\n",
    "            height = self.width\n",
    "            rows = self.cols\n",
    "            pixel_probs = self.pixel_probs.transpose()\n",
    "            \n",
    "        for i in range(height):\n",
    "            a_priori_cell_probs = pixel_probs[i]\n",
    "            row_configs = list(generate_row_configs(rows[i], width))\n",
    "            config_distribution = get_config_distribution(row_configs, a_priori_cell_probs)\n",
    "            posteriori_cell_probs = get_posteriori_cell_probs(row_configs, config_distribution)\n",
    "            pixel_probs[i] = (1 - self.k)*a_priori_cell_probs + self.k*posteriori_cell_probs\n",
    "            \n",
    "    def update(self):\n",
    "        self._update(ROW)\n",
    "        self._update(COL)\n",
    "        \n",
    "    def plot(self):\n",
    "        plt.matshow(self.pixel_probs)\n",
    "    \n",
    "    def plot_goal(self):\n",
    "        if self.goal:\n",
    "            plt.matshow(self.goal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<ipython-input-105-744f41ed9c27>:9: RuntimeWarning: divide by zero encountered in log\n",
      "  np.sum(np.log(row_config*a_priori_cell_probs + (1-row_config)*(1-a_priori_cell_probs)))\n"
     ]
    }
   ],
   "source": [
    "# Test simplest nonogram\n",
    "rows = [[1,1],[1],[1]]\n",
    "cols = [[1,1],[1],[1]]\n",
    "height = 3\n",
    "width = 3\n",
    "k = 1\n",
    "nonogram = Nonogram(rows, cols, height, width, k)\n",
    "nonogram.update()\n",
    "nonogram.pixel_probs\n",
    "nonogram.update()\n",
    "assert np.all(nonogram.pixel_probs == np.array(\n",
    "    [[1., 0., 1.],\n",
    "     [0., 1., 0.],\n",
    "     [1., 0., 0.]],\n",
    "))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# parse_nonogram\n",
    "Given text formatted nonograms from https://github.com/mikix/nonogram-db/blob/master/db\n",
    "Parse this into something that you can give to `Nonogram`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 270,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_nonogram(nonotext):\n",
    "    height = None\n",
    "    width = None\n",
    "    rows = []\n",
    "    cols = []\n",
    "    goal = None\n",
    "    collecting_rows = False\n",
    "    collecting_cols = False\n",
    "    for line in nonotext.split('\\n'):\n",
    "        if collecting_rows == True:\n",
    "            if line.strip() == '':\n",
    "                collecting_rows = False\n",
    "            else:\n",
    "                rows.append([int(x) for x in line.split(',')])\n",
    "        if collecting_cols == True:\n",
    "            if line.strip() == '':\n",
    "                collecting_cols = False\n",
    "            else:\n",
    "                cols.append([int(x) for x in line.split(',')])\n",
    "        if line.startswith('rows'):\n",
    "            collecting_rows = True\n",
    "        if line.startswith('columns'):\n",
    "            collecting_cols = True\n",
    "        if line.startswith('height'):\n",
    "            height = int(line.split()[1])\n",
    "        if line.startswith('width'):\n",
    "            width = int(line.split()[1])\n",
    "        if line.startswith('goal'):\n",
    "            goal = 1 * (np.array(list(line.split()[1][1:-1])) == '1')\n",
    "\n",
    "    if goal is not None:\n",
    "        goal = goal.reshape([height, width])\n",
    "        \n",
    "    return {\n",
    "        'rows': rows,\n",
    "        'cols': cols,\n",
    "        'height': height, \n",
    "        'width': width,\n",
    "        'goal': goal,\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Grab some nonotext from https://github.com/mikix/nonogram-db/blob/master/db\n",
    "# This is https://github.com/mikix/nonogram-db/blob/master/db/gnonograms/spade.non\n",
    "nonotext = \"\"\"height 23\n",
    "width 23\n",
    "\n",
    "rows\n",
    "3\n",
    "7\n",
    "9\n",
    "9\n",
    "11\n",
    "11\n",
    "11\n",
    "17\n",
    "19\n",
    "21\n",
    "21\n",
    "23\n",
    "23\n",
    "23\n",
    "21\n",
    "21\n",
    "7,3,7\n",
    "4,3,4\n",
    "5\n",
    "7\n",
    "11\n",
    "15\n",
    "15\n",
    "\n",
    "columns\n",
    "3\n",
    "7\n",
    "9\n",
    "10\n",
    "11,2\n",
    "11,2\n",
    "14,3\n",
    "16,3\n",
    "16,4\n",
    "15,5\n",
    "23\n",
    "23\n",
    "23\n",
    "15,5\n",
    "16,4\n",
    "16,3\n",
    "14,3\n",
    "11,2\n",
    "11,2\n",
    "10\n",
    "9\n",
    "7\n",
    "3\n",
    "\n",
    "goal \"0000000000111000000000000000000111111100000000000000011111111100000000000000111111111000000000000011111111111000000000000111111111110000000000001111111111100000000011111111111111111000001111111111111111111000111111111111111111111001111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111100111111111111111111111000111111101110111111100000011110011100111100000000000001111100000000000000000111111100000000000000111111111110000000000111111111111111000000001111111111111110000\"\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 289,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAksAAAJICAYAAABxKaCsAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/d3fzzAAAACXBIWXMAAAsTAAALEwEAmpwYAAAV/klEQVR4nO3dX2iV9/3A8c+jqaQmiBftxZjTpWu7GssQE9oreyeOQdcWLJ0rCTRSRm+64PrXuepmUEe3q7B1ILuJ3Vilu/Fi24VCCbRFyAEtxqzbhSuzK6WFdTVxMZE8v4v95qrVj0l6js9J8nrBgZ7kOY+f8s2T885zkvMUZVmWAQDANS2regAAgGYmlgAAEmIJACAhlgAAEmIJACAhlgAAEi1VDzAzMxN79+6Nd999N1asWBEDAwOxbt26qseizh555JFob2+PiIg1a9bEgQMHKp6Iejl16lT87Gc/i8OHD8d7770XL7zwQhRFEXfddVfs2bMnli3zM9lC99k1PnPmTHzve9+Lr371qxERsX379vjWt75V7YB8IdPT07Fr1654//33Y2pqKp566qm48847HcufUXksHTt2LKampuK1116LkydPxsGDB+OVV16peizq6OLFi1GWZRw+fLjqUaizQ4cOxdGjR+PWW2+NiIgDBw5Ef39/3H///fHSSy/F8ePHY8uWLRVPyRdx9RqPjo7GE088EX19fRVPRr0cPXo0Vq9eHS+//HJ88skn8fDDD8c999zjWP6MyjOxVqvF5s2bIyJi48aNcfr06Yonot7+/Oc/x7///e/o6+uL3t7eOHnyZNUjUSdr166NwcHBy/dHR0fjvvvui4iIBx54IN56662qRqNOrl7j06dPxxtvvBGPP/547Nq1K8bHxyucjnr45je/Gd///vcjIqIsy1i+fLlj+SqVx9L4+Pjll2ciIpYvXx6XLl2qcCLqrbW1NXbs2BG//vWv48c//nE888wz1niR2Lp1a7S0/O8EdVmWURRFRES0tbXF+fPnqxqNOrl6jb/xjW/Ec889F7/5zW/iK1/5SvziF7+ocDrqoa2tLdrb22N8fDyefvrp6O/vdyxfpfJYam9vj4mJicv3Z2ZmrjgwWfg6Ojri29/+dhRFER0dHbF69er46KOPqh6LBvjs7zRMTEzEqlWrKpyGRtiyZUvce++9l//7zJkzFU9EPXzwwQfR29sbDz30UDz44IOO5atUHkubNm2K4eHhiIg4efJk3H333RVPRL29/vrrcfDgwYiI+PDDD2N8fDxuv/32iqeiETo7O+PEiRMRETE8PBzd3d0VT0S97dixI955552IiHj77bdjw4YNFU/EF/Xxxx9HX19fPPvss7Ft27aIcCxfraj6Qrr//Wu4v/zlL1GWZezfvz++9rWvVTkSdTY1NRUvvvhi/OMf/4iiKOKZZ56JTZs2VT0WdXLu3LnYuXNnHDlyJM6ePRs/+tGPYnp6Ou64444YGBiI5cuXVz0iX9Bn13h0dDT27dsXt9xyS9x2222xb9++K36VgoVnYGAg/vjHP8Ydd9xx+WM//OEPY2BgwLH8/yqPJQCAZlb5y3AAAM1MLAEAJMQSAEBCLAEAJBr2hka1Wq1RuwYAqLuurq5rfryh7/54vX/0WsbGxmL9+vUNnIaqWeOF6b/v4jtbQ0ND0dvb26Bpms9S/INix/LitxTXODvJ42U4AICEWAIASIglAICEWAIASIglAICEWAIASIglAIDEvN5naWZmJvbu3RvvvvturFixIgYGBmLdunX1ng0AoHLzOrN07NixmJqaitdeey1+8IMfxMGDB+s9FwBAU5hXLNVqtdi8eXNERGzcuDFOnz5d16EAAJrFvF6GGx8fj/b29sv3ly9fHpcuXYqWlit3NzY2Nut9Tk5Ozml7Fh5rvDANDQ3NafuOjo45P2YhW4pf047lxc8aX2lesdTe3h4TExOX78/MzHwulCJiTteVWYrXoVlqrPHC1NnZOaftXRtu8XMsL35LcY3rfm24TZs2xfDwcEREnDx5Mu6+++75TQYA0OTmdWZpy5Yt8eabb8Z3vvOdKMsy9u/fX++5AACawrxiadmyZfGTn/yk3rMAADQdb0oJAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJCY1/ssAbNTFEXVI9Bgi2GNl+IlW2AunFkCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJZa0oigaeoOFYK5f1yMjI44DlhSxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAImWqgeATFEUVY8AfEGNPo7Lsmzo/sGZJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCARMt8H/jII49Ee3t7RESsWbMmDhw4ULehAACaxbxi6eLFi1GWZRw+fLje8wAANJWiLMtyrg86depUPPfcc/HlL385Ll26FDt37oyNGzdesU2tVouVK1fOep+Tk5PR2to611FYQOazxiMjIw2ahkbp6OiIs2fPVj0GDdRsa9zd3V31CIvOUnxOvnDhQnR1dV3zc/M6s9Ta2ho7duyIRx99NP72t7/Fk08+GX/605+ipeXK3a1fv37W+xwbG5vT9iw881njzs7OBk1DowwNDUVvb2/VY9BAzbbG8/iZnxtYis/JtVrtup+bVyx1dHTEunXroiiK6OjoiNWrV8dHH30UX/rSl+Y9JABAM5rXX8O9/vrrcfDgwYiI+PDDD2N8fDxuv/32ug4GANAM5nVmadu2bfHiiy/G9u3boyiK2L9//+deggMAWAzmVTgrVqyIn//85/WeBQCg6XhTSgCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCAREvVAyxlRVFUPcJNNTQ0FJ2dnVWPASwyS+176XyUZVn1CAuaM0sAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxdB1FUTT8BgA3w1yfn0ZGRjyffYZYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBItFQ9wHwVRVH1CABA3Jzn5LIsG/5vXI8zSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAACbEEAJAQSwAAiVnF0qlTp6KnpyciIt57773Yvn17fPe73409e/bEzMxMQwcEAKjSDWPp0KFDsXv37rh48WJERBw4cCD6+/vjt7/9bZRlGcePH2/4kAAAVblhLK1duzYGBwcv3x8dHY377rsvIiIeeOCBeOuttxo3HQBAxVputMHWrVvj3Llzl++XZRlFUURERFtbW5w/f/66jx0bG5v1IJOTk3PafmhoaNbb0hw6Ojqs2xJgnRc/a7z4NeMaz6UR6u2GsXS1Zcv+dzJqYmIiVq1add1t169fP+v9jo2NzWn7zs7OWW9LcxgaGore3t6qx6DBrPPiZ40Xv2Zc47IsG7r/Wq123c/N+a/hOjs748SJExERMTw8HN3d3fOfDACgyc05lp5//vkYHByMxx57LKanp2Pr1q2NmAsAoCnM6mW4NWvWxJEjRyLiP69jvvrqqw0dCgCgWXhTSgCAhFgCAEiIJQCAhFgCAEiIJQCAhFgCAEiIJQCARENjqSiKWd9GRkbmtD0AsHTMpRHmc8s4swQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAACJlkbuvCzLWW87NjY2p+2LopjPSADAAjSXRpiPWq123c85swQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAACJWcXSqVOnoqenJyIizpw5E5s3b46enp7o6emJP/zhDw0dEACgSi032uDQoUNx9OjRuPXWWyMiYnR0NJ544ono6+tr+HAAAFW74ZmltWvXxuDg4OX7p0+fjjfeeCMef/zx2LVrV4yPjzd0QACAKhVlWZY32ujcuXOxc+fOOHLkSPz+97+Pr3/963HvvffGK6+8Ep9++mk8//zzn3tMrVaLlStXznqQycnJaG1tnfX2IyMjs96W5tDR0RFnz56tegwazDovftZ48WvGNe7u7m7o/i9cuBBdXV3X/mQ5C3//+9/LRx99tCzLsvzXv/51+eN//etfy97e3ms+ZmRkZDa7vuzMmTNz2j4i3BbYbWhoqPIZ3KyzmzV2W5hr3GhZt8z5r+F27NgR77zzTkREvP3227Fhw4a57gIAYMG44S94X23v3r2xb9++uOWWW+K2226Lffv2NWIuAICmMKtYWrNmTRw5ciQiIjZs2BC/+93vGjoUAECz8KaUAAAJsQQAkBBLAAAJsQQAkBBLAAAJsQQAkBBLAACJOb8pZbMob3xJuy+kKIqG7h/qodHHQYRj4UasAdyc46BKziwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACRaqh6gWZVlWfUIX1hRFFWPsOQthq8jqtforyPfK6rXbN8rxsbGmm6mKjmzBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAAmxBACQEEsAAImWqgegccqyrHqEK4yNjTXdTAtdURRVj7Dk3Yw1aPRxM9f9O5ZZapxZAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBIiCUAgIRYAgBItFQ9ACxmRVFUPQKLQKO/jsqybOj+YaFzZgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAINFS9QCQKYqi6hFg0ZvrcTY0NBSdnZ0NmmbuyrKsegQWOWeWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAASYgkAICGWAAAS6Tt4T09Px65du+L999+PqampeOqpp+LOO++MF154IYqiiLvuuiv27NkTy5ZpLgBgcUpj6ejRo7F69ep4+eWX45NPPomHH3447rnnnujv74/7778/XnrppTh+/Hhs2bLlZs0LAHBTFWVyUZ2JiYkoyzLa29vjn//8Z2zbti2mpqZieHg4iqKIY8eOxZtvvhl79uz53GNrtVqsXLly1oNMTk5Ga2vr/P4vWBDms8YjIyMNmoZG6ejoiLNnz1Y9Bg3UbGvc3d1d9QiLzlJ8Tr5w4UJ0dXVd83PpmaW2traIiBgfH4+nn346+vv746c//enliy62tbXF+fPnr/v49evXz3rIsbGxOW3PwjOfNW6mi3UyO0NDQ9Hb21v1GDRQs62xC+nW31J8Tq7Vatf93A1/2eiDDz6I3t7eeOihh+LBBx+84veTJiYmYtWqVfWZEgCgCaWx9PHHH0dfX188++yzsW3btoj4z0/6J06ciIiI4eFhpz8BgEUtjaVf/epX8emnn8Yvf/nL6OnpiZ6enujv74/BwcF47LHHYnp6OrZu3XqzZgUAuOnS31navXt37N69+3Mff/XVVxs2EABAM/EGSQAACbEEAJAQSwAACbEEAJAQSwAACbEEAJBI3zqAhe2/l6VpFkNDQy5fAtRds32vmw+XbGluziwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAQiwBACTEEgBAoijLsmzEjmu1WiN2CwDQEF1dXdf8eMNiCQBgMfAyHABAQiwBACTEEgBAQiwBACTEEgBA4v8AxJw4GY1n3HgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 720x720 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "nonogram_input = parse_nonogram(nonotext)\n",
    "nonogram = Nonogram(k=.5, **nonogram_input)\n",
    "for i in range(10):\n",
    "    if i % 10 == 0:\n",
    "        print(i)\n",
    "    nonogram.update()\n",
    "nonogram.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This was the best example I found. Not all of the puzzles converge, and you're left with a \"fuzzy\" image and some diverge and you have NO image!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}