Solving a nonogram

passion.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "from pathlib import Path\n",
    "from collections import namedtuple\n",
    "\n",
    "Puzle = namedtuple('Puzle', 'rows cols')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "orsted = Puzle(\n",
    "    rows = [[2], [2], [6], [8], [2, 2, 2], [2, 2, 2], [2, 2], [2, 2], [8], [6]],\n",
    "    cols = [[6], [8], [2, 2], [6, 2], [6, 2], [2, 2], [8], [6]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = json.loads(Path('passion.json').read_text())\n",
    "puzle = Puzle(cols = data['vertical'], rows = data['horizontal'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_value(spec, spaces, n_space):\n",
    "    oo = [False]*spaces[0]\n",
    "    for s, n in zip(spec, spaces[1:]):\n",
    "        oo.extend([True]*s)\n",
    "        oo.extend([False]*(n+1))\n",
    "    oo.extend([True]*spec[-1])\n",
    "    oo.extend([False]*(n_space-sum(spaces)))\n",
    "    return oo\n",
    "    \n",
    "def val2str(val):\n",
    "    return '>'+''.join('x' if y else ' ' for y in val)+'<'\n",
    "    \n",
    "def col_configs(spec, n_space=None, n_tot=None):\n",
    "    \"\"\"\n",
    "    Generate known configs for a column with n_space additional spaces\n",
    "    \"\"\"\n",
    "    spaces = [0]*len(spec)\n",
    "    if n_space is None:\n",
    "        n_space =  n_tot - (sum(spec) + len(spec) -1)\n",
    "    if n_space<=0:\n",
    "        if n_space==0: # check here to avoid edge case in loop\n",
    "            yield make_value(spec, spaces, n_space)\n",
    "        return\n",
    "    while True:\n",
    "        yield make_value(spec, spaces, n_space)\n",
    "        j = 0\n",
    "        if sum(spaces)==n_space:\n",
    "            i = 0\n",
    "            while spaces[i]==0:\n",
    "                i+=1\n",
    "            spaces[i]=0\n",
    "            j=i+1\n",
    "        if j==len(spaces):\n",
    "            break\n",
    "        spaces[j]+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ">xxx xxx<\n"
     ]
    }
   ],
   "source": [
    "for v in col_configs([3,3], 0):\n",
    "    print(val2str(v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> xx < False\n",
      "> xx < False\n",
      "> xxxxxx < False\n",
      "> xxxxxxxx < False\n",
      "> xx xx xx < False\n",
      "> xx xx xx < False\n",
      "> xx xx < False\n",
      "> xx xx < False\n",
      "> xxxxxxxx < False\n",
      "> xxxxxx < False\n"
     ]
    }
   ],
   "source": [
    "# rowdat is constant, state of rows is tracked by index vector \n",
    "def make_rowdat(rows):\n",
    "    rowdat = [\n",
    "        [False]+make_value(r[::-1], [0]*len(r), 1)\n",
    "        for r in rows\n",
    "    ]\n",
    "    idx0 = [len(r)-1 for r in rowdat]\n",
    "    return rowdat, idx0\n",
    "\n",
    "rows = orsted.rows\n",
    "cols = orsted.cols\n",
    "rowdat, idx0= make_rowdat(rows)\n",
    "\n",
    "for r,i in zip(rowdat,idx0):\n",
    "    print(val2str(r), r[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# idx points to the most recent value used in this row\n",
    "# if row[i] is False, a space was output and more spaces can be added (as long as there is time to empty buffer)\n",
    "def next_idx(rowdat, idx, column_val):\n",
    "    ni = []\n",
    "    for r, i,cv in zip(rowdat, idx, column_val):\n",
    "        ri = r[i]\n",
    "        if not ri:\n",
    "            # last output was space\n",
    "            if not cv:\n",
    "                # we need a space here as well\n",
    "                ni.append(i)\n",
    "            else:\n",
    "                # advance idx to indicate that we ouptut True (next field will be True or out of bounds by construction)\n",
    "                if i==0:\n",
    "                    return None\n",
    "                ni.append(i-1)\n",
    "        else:\n",
    "            # last output was True and we are forced to advance and output next field\n",
    "            j=i-1\n",
    "            rj = r[j] # content we must output\n",
    "            if not rj==cv:\n",
    "                # does not match column requirement\n",
    "                return None\n",
    "            ni.append(i-1)\n",
    "    return ni"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> xx <\n",
      "> xx <\n",
      "> xxxxxx <\n",
      "> xxxxxxxx <\n",
      "> xx xx xx <\n",
      "> xx xx xx <\n",
      "> xx xx <\n",
      "> xx xx <\n",
      "> xxxxxxxx <\n",
      "> xxxxxx <\n",
      ">xxxxxx    < [2, 2, 6, 8, 8, 8, 6, 6, 9, 7]\n",
      "> xxxxxx   < [3, 2, 6, 8, 8, 8, 5, 6, 9, 7]\n",
      ">  xxxxxx  < [3, 3, 6, 8, 8, 8, 5, 5, 9, 7]\n",
      ">   xxxxxx < [3, 3, 7, 8, 8, 8, 5, 5, 8, 7]\n",
      ">    xxxxxx< [3, 3, 7, 9, 8, 8, 5, 5, 8, 6]\n"
     ]
    }
   ],
   "source": [
    "for r in rowdat:\n",
    "    print(val2str(r))\n",
    "\n",
    "n_rows = len(rows)\n",
    "for val in col_configs(cols[0], n_tot=n_rows):\n",
    "    idx = next_idx(rowdat, idx0, val)\n",
    "    print(val2str(val), idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def match_cols(rowdat, idx, col_specs):\n",
    "    print(f'Check called for {len(col_specs)} columns')\n",
    "    if not col_specs:\n",
    "        return []\n",
    "    n_row = len(idx)\n",
    "    col = col_specs[0]\n",
    "    col_rest = col_specs[1:]\n",
    "    column_count = len(col_specs)\n",
    "    for val in col_configs(col, n_tot=n_row):\n",
    "        idx_next = next_idx(rowdat, idx, val)\n",
    "        if not idx_next:\n",
    "            continue\n",
    "        # final value of i must be 0 or 1, and i can only decrease by 1 per column\n",
    "        if any(i>column_count for i in idx_next):\n",
    "            continue            \n",
    "        sol = match_cols(rowdat, idx_next, col_rest)\n",
    "        if sol is not None:\n",
    "            return [val]+sol\n",
    "        \n",
    "tgt = puzle\n",
    "#tgt = orsted\n",
    "rowdat, idx0 = make_rowdat(tgt.rows)\n",
    "res = match_cols(rowdat, idx0, tgt.cols)\n",
    "res_rows = zip(*res)\n",
    "for r in res_rows:\n",
    "    print(val2str(r))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5522"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res_rows = list(zip(*res))\n",
    "Path('passion_res.json').write_text(json.dumps(res_rows))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "■■■■■■■   ■ ■  ■■ ■   ■■■■■■■\n",
      "■     ■ ■ ■  ■ ■ ■ ■■ ■     ■\n",
      "■ ■■■ ■     ■ ■ ■ ■■  ■ ■■■ ■\n",
      "■ ■■■ ■ ■■■ ■■■■ ■■ ■ ■ ■■■ ■\n",
      "■ ■■■ ■  ■      ■ ■   ■ ■■■ ■\n",
      "■     ■ ■■ ■■  ■■■■■■ ■     ■\n",
      "■■■■■■■ ■ ■ ■ ■ ■ ■ ■ ■■■■■■■\n",
      "         ■■■       ■         \n",
      "■■■■■ ■■■■ ■   ■■■■ ■■ ■ ■ ■ \n",
      "■ ■■ ■  ■ ■ ■■ ■■ ■ ■    ■   \n",
      "■ ■■■ ■   ■  ■■■■■■■ ■ ■  ■■■\n",
      "  ■  ■ ■■   ■■   ■■■  ■ ■■  ■\n",
      "  ■ ■ ■ ■■■ ■ ■■■        ■ ■ \n",
      " ■ ■ ■ ■       ■■  ■■  ■■   ■\n",
      " ■■■■ ■■■  ■■  ■ ■   ■   ■■■ \n",
      "■■■■ ■  ■■■■  ■ ■ ■■■ ■■■  ■■\n",
      "■   ■■■■  ■■   ■ ■■    ■■■   \n",
      "■■■■ ■ ■    ■■■      ■ ■   ■ \n",
      "■   ■ ■■ ■   ■■■■■■ ■■   ■■  \n",
      "■  ■ ■ ■ ■  ■■     ■ ■■ ■■ ■■\n",
      "■ ■  ■■ ■ ■ ■ ■■  ■ ■■■■■■■■ \n",
      "        ■■■         ■   ■■ ■ \n",
      "■■■■■■■ ■ ■■■  ■■■ ■■ ■ ■ ■  \n",
      "■     ■  ■ ■  ■   ■■■   ■  ■■\n",
      "■ ■■■ ■ ■  ■   ■ ■■ ■■■■■ ■■■\n",
      "■ ■■■ ■ ■■  ■■■ ■  ■■ ■      \n",
      "■ ■■■ ■ ■■■  ■■■■■■    ■■■■  \n",
      "■     ■ ■ ■ ■■     ■ ■   ■ ■ \n",
      "■■■■■■■ ■■■ ■ ■■■     ■ ■   ■\n"
     ]
    }
   ],
   "source": [
    "for row in res_rows:\n",
    "    print(''.join('■' if v else ' ' for v in row))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "res_rows = json.loads(Path('passion_res.json').read_text())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "aa = np.array(res_rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x24819617eb0>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPsAAAD8CAYAAACxd9IeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAANlklEQVR4nO3dT8hl9X3H8fe3id2oi7H+6WBtbcVFSxZj5yEULMUSGqwU1EVKXYQphEwWESJkEbGLuJSihqyESR0yKdYS0FQpoY1IQLKRPI9YHTtpTYtNjcOM4kJdteq3i+dYnkzu89zrPffc3+/O9/2C4bnPufec871n7uc5557f+f1OZCaSLn6/0roASeth2KUiDLtUhGGXijDsUhGGXSqiSdgj4taI+LeI+GlE3Nuihlki4rWIeDkiXoyI7UY1nIyI8xFxes+0KyLimYh4dfh5qJO67o+Inw/b68WIuG3NNV0XET+MiDMR8UpEfGWY3nR7HVBX2+217nb2iPgE8O/AnwCvAz8G7srMf11rITNExGvAVma+1bCGPwLeA76TmZ8apv018HZmPjD8cTyUmV/roK77gfcy88F11rKnpsPA4cx8ISIuB3aAO4C/pOH2OqCuP6fh9mqxZ/808NPM/M/M/B/g74HbG9TRpcx8Dnj7gsm3A6eGx6fY/eCs1T51NZWZZzPzheHxu8AZ4Foab68D6mqqRdivBf57z++v08GGGCTwg4jYiYjjrYvZ45rMPAu7HyTg6sb17HV3RLw0HOav/evFRyLieuAm4Hk62l4X1AUNt1eLsMeMab1cs3tzZv4+8KfAl4dDV+3vEeAG4AhwFnioRRERcRnwBHBPZr7TooZZZtTVdHu1CPvrwHV7fv8N4I0GdfySzHxj+Hke+B67Xzl6cG74HvjR98HzjesBIDPPZeYHmfkh8C0abK+IuITdQD2WmU8Ok5tvr1l1td5eLcL+Y+DGiPjtiPhV4C+ApxvU8Qsi4tLhZAoRcSnwWeD0wXOtzdPAseHxMeCphrX8v48CNbiTNW+viAjgUeBMZj6856mm22u/ulpvLzJz7f+A29g9I/8fwF+1qGFGTb8D/Mvw75VWdQGPs3uI97/sHgV9Afg14Fng1eHnFZ3U9bfAy8BL7Abs8Jpr+kN2vwK+BLw4/Lut9fY6oK6m22vtTW+S2vAKOqkIwy4VYdilIgy7VIRhl4poGvbOLkkF+qwJ+qyrx5qgz7p6qKn1nr35Bpihx5qgz7p6rAn6rKt5Ta3DLmlNRl1UExG3At8EPgH8TWY+MOf1F90VPEePHp1kuTs7O0uvd8y888xb9rLrXWXNb775JlddddVCrx3zfnqVmbM6my0f9mUGobgYwz7VFYi7l1cvt94x884zb9nLrnfKmg8y5v30ar+wjzmMdxAKaYOMCXvPg1BIusAnR8y70CAUQ5ND8zORUnVjwr7QIBSZeQI4ARfnd3ZpU4w5jO9yEApJsy29Z8/M9yPibuCf2W16O5mZr4wppse+9WPO1rY6wzxvuQfVNaamKdc7VSvAlPNOZdltsdbBK+Ydxm/ihp2qOalV81mrwLYKe6s/yGMsUPPKm94kbRDDLhVh2KUiDLtUhGGXihhzUc1aTdlhoVUT2FTzbmILQqumtTE27TPpnl0qwrBLRRh2qQjDLhVh2KUiDLtUhGGXitiYdvZN1Gs77FTddu251jf37FIRhl0qwrBLRRh2qQjDLhVh2KUibHqbUK+jvE6lWhfXTeOeXSrCsEtFGHapCMMuFWHYpSIMu1SEYZeKGNXOHhGvAe8CHwDvZ+bWKoqaZRPbUqfs4tqqXXrKu9pONW+PQ4W3sIqLav44M99awXIkTcjDeKmIsWFP4AcRsRMRx1dRkKRpjD2Mvzkz34iIq4FnIuInmfnc3hcMfwT8QyA1Fqs6yRAR9wPvZeaDB7zmwJX1eMKj184dm3iCrpWLbfy6BWqe+YKlD+Mj4tKIuPyjx8BngdPLLk/StMYcxl8DfG/4K/NJ4O8y85/GFLOJe40xerwjaq93cZ3q/c5zMX0mV3YYv9DK5hzGb6JN/PA77+LzbqKVH8ZL2iyGXSrCsEtFGHapCMMuFWHYpSLWOpT00aNH2d7eXucqm5ryKrgeh6Gect4e32+Ptrb272Xunl0qwrBLRRh2qQjDLhVh2KUiDLtUxFqb3nZ2drrsZdRjr6gpm+3G6HF7tBokpNd59+OeXSrCsEtFGHapCMMuFWHYpSIMu1SEYZeKWGs7+zyb2Ja67HLnLbvXm1OM0ep6hk3sAjvFet2zS0UYdqkIwy4VYdilIgy7VIRhl4roqultKq2awHpttjnoPfV6R9RN7GraW9fpuXv2iDgZEecj4vSeaVdExDMR8erw89C0ZUoaa5HD+G8Dt14w7V7g2cy8EXh2+F1Sx+aGPTOfA96+YPLtwKnh8SngjhXXJWnFlj1Bd01mngUYfl69upIkTWHyE3QRcRw4PvV6JB1s2T37uYg4DDD8PL/fCzPzRGZuZeb+N6GSNLllw/40cGx4fAx4ajXlSJpKLNDO+DhwC3AlcA74OvAPwHeB3wR+BnwuMy88ifdLtra2ctm7uI5p7x6z7CmHdJ6qHb7HmmC6tuVeuyEvu9x5Fqh55gvmfmfPzLv2eeoz88uS1Asvl5WKMOxSEYZdKsKwS0UYdqkIu7jSbpTXVk03mzjK61SmHHm2RZfera39r11zzy4VYdilIgy7VIRhl4ow7FIRhl0qwrBLRXTVzr6JwwVPdQfYMXptOx6j1+6kU613imsh3LNLRRh2qQjDLhVh2KUiDLtUhGGXiuiq6e0gU3UXhOm6fLYaEXeeqZoEW90RdZ4e1zuGXVwlHciwS0UYdqkIwy4VYdilIgy7VIRhl4pY5C6uJ4E/A85n5qeGafcDXwTeHF52X2Z+f+7KIpr0+WzVTbVVd9Be72ra4xDWvQ6dPfI6ipkzL7Jn/zZw64zp38jMI8O/uUGX1NbcsGfmc8Dce69L6tuY7+x3R8RLEXEyIg6trCJJk1g27I8ANwBHgLPAQ/u9MCKOR8R2RGwvuS5JKzD3BB1ARFwP/ONHJ+gWfW7Gaz1BtwaeoOt/vfO0OkE3q5DDe369Ezi9zHIkrc/cLq4R8ThwC3BlRLwOfB24JSKOAAm8BnxpFcVM1fVyym6qB7kYjwqmGol3nh675c7TomvtQV1c54Y9M++aMfnRpSqR1IxX0ElFGHapCMMuFWHYpSIMu1SEYZeK6Goo6RZD785bb6u7mvbaRj/lHWKnMtUVklO+nylqds8uFWHYpSIMu1SEYZeKMOxSEYZdKqKrprdWXVxbDW7QqkmoVZffMQoOQLH0vPtxzy4VYdilIgy7VIRhl4ow7FIRhl0qwrBLRXTVzj7GVN1UW3VxHaO39t1VmOr/qNU1GC0+V+7ZpSIMu1SEYZeKMOxSEYZdKsKwS0VsTNPbmCaSVuttNe88rZqTDrKJ3ZBbLfegbXHQXVzn7tkj4rqI+GFEnImIVyLiK8P0KyLimYh4dfh5aJnCJa3HIofx7wNfzczfBf4A+HJE/B5wL/BsZt4IPDv8LqlTc8OemWcz84Xh8bvAGeBa4Hbg1PCyU8AdUxUpabyPdYIuIq4HbgKeB67JzLOw+wcBuHrVxUlanYVP0EXEZcATwD2Z+c6iJxgi4jhwfLnyJK3KQnv2iLiE3aA/lplPDpPPRcTh4fnDwPlZ82bmiczcysz9TxNKmtwiZ+MDeBQ4k5kP73nqaeDY8PgY8NTqy5O0Koscxt8MfB54OSJeHKbdBzwAfDcivgD8DPjcvAUdPXqU7e3tpQqdsutlj3cXHaPXO5O2Wm+razAO0qKL69ywZ+aPgP3W/JnVliNpKl4uKxVh2KUiDLtUhGGXijDsUhFr7eK6s7PT5WisY7TqatprV9RltRrFt9euxN7FVdLSDLtUhGGXijDsUhGGXSrCsEtFGHapiK6Gku7xDqKtujFOOe+yyx277DHrnUqvXXq9i6ukpRl2qQjDLhVh2KUiDLtUhGGXiuiq6e0gUzbN9HgH2FZaNRfO06o78FRa1OSeXSrCsEtFGHapCMMuFWHYpSIMu1SEYZeKmNvOHhHXAd8Bfh34EDiRmd+MiPuBLwJvDi+9LzO/P1WhF6MxbdZj2p3HaDU8cqs2+qmuhZhquVtbW/s+t8hFNe8DX83MFyLicmAnIp4ZnvtGZj64gholTWyRWzafBc4Oj9+NiDPAtVMXJmm1PtZ39oi4HrgJeH6YdHdEvBQRJyPi0Iprk7RCC4c9Ii4DngDuycx3gEeAG4Aj7O75H9pnvuMRsR0R2yuoV9KSFgp7RFzCbtAfy8wnATLzXGZ+kJkfAt8CPj1r3sw8kZlbmbn/mQNJk5sb9tg9XfkocCYzH94z/fCel90JnF59eZJWZZGz8TcDnwdejogXh2n3AXdFxBEggdeAL01SYVFjmoSm7Graat5WTWAX06i3i5yN/xEw6x3bpi5tEK+gk4ow7FIRhl0qwrBLRRh2qQjDLhWxMUNJ9zjs8lhTdVPtsT17rFZ3vJ2qW26Lu/S6Z5eKMOxSEYZdKsKwS0UYdqkIwy4V0VXTW49325xSj90ne71b7lTzjulKPOXItFP8H7lnl4ow7FIRhl0qwrBLRRh2qQjDLhVh2KUi1t3O/hbwX3t+v3KY1pOPVdMa28p/oa5WXWAvsBHbaowVbud1fdZ/a78nomX/5YjY7u1OMT3WBH3W1WNN0GddPdTkYbxUhGGXimgd9hON1z9LjzVBn3X1WBP0WVfzmpp+Z5e0Pq337JLWxLBLRRh2qQjDLhVh2KUi/g94EiDin2hdOAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.spy(aa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "jupytext": {
   "formats": "ipynb,py:percent"
  },
  "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
}