wordsearch/wordsearch-solving.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 106,
   6    "metadata": {
   7     "collapsed": false
   8    },
   9    "outputs": [],
  10    "source": [
  11     "import string\n",
  12     "import re\n",
  13     "import collections\n",
  14     "import copy\n",
  15     "import os\n",
  16     "\n",
  17     "from enum import Enum\n",
  18     "Direction = Enum('Direction', 'left right up down upleft upright downleft downright')\n",
  19     "    \n",
  20     "delta = {Direction.left: (0, -1),Direction.right: (0, 1), \n",
  21     "         Direction.up: (-1, 0), Direction.down: (1, 0), \n",
  22     "         Direction.upleft: (-1, -1), Direction.upright: (-1, 1), \n",
  23     "         Direction.downleft: (1, -1), Direction.downright: (1, 1)}\n",
  24     "\n",
  25     "cat = ''.join\n",
  26     "wcat = ' '.join\n",
  27     "lcat = '\\n'.join"
  28    ]
  29   },
  30   {
  31    "cell_type": "code",
  32    "execution_count": 46,
  33    "metadata": {
  34     "collapsed": true
  35    },
  36    "outputs": [],
  37    "source": [
  38     "def empty_grid(w, h):\n",
  39     "    return [['.' for c in range(w)] for r in range(h)]"
  40    ]
  41   },
  42   {
  43    "cell_type": "code",
  44    "execution_count": 47,
  45    "metadata": {
  46     "collapsed": true
  47    },
  48    "outputs": [],
  49    "source": [
  50     "def show_grid(grid):\n",
  51     "    return lcat(cat(r) for r in grid)"
  52    ]
  53   },
  54   {
  55    "cell_type": "code",
  56    "execution_count": 48,
  57    "metadata": {
  58     "collapsed": true
  59    },
  60    "outputs": [],
  61    "source": [
  62     "def indices(grid, r, c, l, d):\n",
  63     "    dr, dc = delta[d]\n",
  64     "    w = len(grid[0])\n",
  65     "    h = len(grid)\n",
  66     "    inds = [(r + i * dr, c + i * dc) for i in range(l)]\n",
  67     "    return [(i, j) for i, j in inds\n",
  68     "           if i >= 0\n",
  69     "           if j >= 0\n",
  70     "           if i < h\n",
  71     "           if j < w]"
  72    ]
  73   },
  74   {
  75    "cell_type": "code",
  76    "execution_count": 49,
  77    "metadata": {
  78     "collapsed": true
  79    },
  80    "outputs": [],
  81    "source": [
  82     "def gslice(grid, r, c, l, d):\n",
  83     "    return [grid[i][j] for i, j in indices(grid, r, c, l, d)]"
  84    ]
  85   },
  86   {
  87    "cell_type": "code",
  88    "execution_count": 50,
  89    "metadata": {
  90     "collapsed": true
  91    },
  92    "outputs": [],
  93    "source": [
  94     "def set_grid(grid, r, c, d, word):\n",
  95     "    for (i, j), l in zip(indices(grid, r, c, len(word), d), word):\n",
  96     "        grid[i][j] = l\n",
  97     "    return grid"
  98    ]
  99   },
 100   {
 101    "cell_type": "code",
 102    "execution_count": 51,
 103    "metadata": {
 104     "collapsed": true
 105    },
 106    "outputs": [],
 107    "source": [
 108     "def could_add(grid, r, c, d, word):\n",
 109     "    s = gslice(grid, r, c, len(word), d)\n",
 110     "    return re.fullmatch(cat(s), word)"
 111    ]
 112   },
 113   {
 114    "cell_type": "code",
 115    "execution_count": 52,
 116    "metadata": {
 117     "collapsed": true
 118    },
 119    "outputs": [],
 120    "source": [
 121     "def present(grid, word):\n",
 122     "    w = len(grid[0])\n",
 123     "    h = len(grid)\n",
 124     "    for r in range(h):\n",
 125     "        for c in range(w):\n",
 126     "            for d in Direction:\n",
 127     "                if cat(gslice(grid, r, c, len(word), d)) == word:\n",
 128     "                    return True, r, c, d\n",
 129     "    return False, 0, 0, list(Direction)[0]"
 130    ]
 131   },
 132   {
 133    "cell_type": "code",
 134    "execution_count": 53,
 135    "metadata": {
 136     "collapsed": true
 137    },
 138    "outputs": [],
 139    "source": [
 140     "def pad_grid(g0):\n",
 141     "    grid = copy.deepcopy(g0)\n",
 142     "    w = len(grid[0])\n",
 143     "    h = len(grid)\n",
 144     "    for r in range(h):\n",
 145     "        for c in range(w):\n",
 146     "            if grid[r][c] == '.':\n",
 147     "                grid[r][c] = random_wordsearch_letter()\n",
 148     "    return grid"
 149    ]
 150   },
 151   {
 152    "cell_type": "code",
 153    "execution_count": 54,
 154    "metadata": {
 155     "collapsed": false
 156    },
 157    "outputs": [],
 158    "source": [
 159     "def read_wordsearch(fn):\n",
 160     "    lines = [l.strip() for l in open(fn).readlines()]\n",
 161     "    w, h = [int(s) for s in lines[0].split('x')]\n",
 162     "    grid = lines[1:h+1]\n",
 163     "    words = lines[h+1:]\n",
 164     "    return w, h, grid, words"
 165    ]
 166   },
 167   {
 168    "cell_type": "code",
 169    "execution_count": 77,
 170    "metadata": {
 171     "collapsed": false,
 172     "scrolled": true
 173    },
 174    "outputs": [
 175     {
 176      "data": {
 177       "text/plain": [
 178        "(['iisnoitpircserpoacos',\n",
 179        "  'eohgiodnpgbeautypoar',\n",
 180        "  'arsllorcsnestdomofne',\n",
 181        "  'irfdeemseirrgarnlfrb',\n",
 182        "  'tclumpingkoeasevoedm',\n",
 183        "  'hetobsibecgftdcmgrvi',\n",
 184        "  'isesrepoeuelmsriyset',\n",
 185        "  'eknaodouusnoedetoxes',\n",
 186        "  'vldwiarsoiogsstiedue',\n",
 187        "  'ehealcegdsuidsesuifi',\n",
 188        "  'dirrsiidnesepmdaelnc',\n",
 189        "  'nierrrsdeibuwpegriga',\n",
 190        "  'sprirrsyebniednusirb',\n",
 191        "  'eeboraisahmieeaycnnw',\n",
 192        "  'irrrnbrnepcmanhriuug',\n",
 193        "  'tjasdypeykuanppetiot',\n",
 194        "  'nuvaaaicssndonrppmer',\n",
 195        "  'areeioassenyocoaooze',\n",
 196        "  'hellesoamalabruptest',\n",
 197        "  'csygsfyosinightclubs'],\n",
 198        " ['abruptest',\n",
 199        "  'apology',\n",
 200        "  'assumed',\n",
 201        "  'barricades',\n",
 202        "  'beauty',\n",
 203        "  'bravely',\n",
 204        "  'bravos',\n",
 205        "  'burlier',\n",
 206        "  'chanties',\n",
 207        "  'clumping',\n",
 208        "  'coached',\n",
 209        "  'coffers',\n",
 210        "  'coyness',\n",
 211        "  'decriminalisation',\n",
 212        "  'detoxes',\n",
 213        "  'differs',\n",
 214        "  'duelled',\n",
 215        "  'duplicating',\n",
 216        "  'elaborates',\n",
 217        "  'embroils',\n",
 218        "  'encirclement',\n",
 219        "  'erogenous',\n",
 220        "  'facsimiled',\n",
 221        "  'festers',\n",
 222        "  'flickering',\n",
 223        "  'fusible',\n",
 224        "  'gluiest',\n",
 225        "  'golfers',\n",
 226        "  'interpolations',\n",
 227        "  'involved',\n",
 228        "  'irony',\n",
 229        "  'lithographed',\n",
 230        "  'nabbed',\n",
 231        "  'nightclubs',\n",
 232        "  'oblongs',\n",
 233        "  'optics',\n",
 234        "  'orphaned',\n",
 235        "  'overstates',\n",
 236        "  'paining',\n",
 237        "  'papery',\n",
 238        "  'perjures',\n",
 239        "  'prescriptions',\n",
 240        "  'prissier',\n",
 241        "  'rallies',\n",
 242        "  'rebated',\n",
 243        "  'reneges',\n",
 244        "  'saleswomen',\n",
 245        "  'scrolls',\n",
 246        "  'searing',\n",
 247        "  'slobbering',\n",
 248        "  'soups',\n",
 249        "  'sucking',\n",
 250        "  'tenderer',\n",
 251        "  'thieved',\n",
 252        "  'timbers',\n",
 253        "  'toiletries',\n",
 254        "  'unabashed',\n",
 255        "  'warriors',\n",
 256        "  'wimpy',\n",
 257        "  'wriest'])"
 258       ]
 259      },
 260      "execution_count": 77,
 261      "metadata": {},
 262      "output_type": "execute_result"
 263     }
 264    ],
 265    "source": [
 266     "width, height, g, ws = read_wordsearch('wordsearch1.txt')\n",
 267     "g, ws"
 268    ]
 269   },
 270   {
 271    "cell_type": "code",
 272    "execution_count": 78,
 273    "metadata": {
 274     "collapsed": false,
 275     "scrolled": true
 276    },
 277    "outputs": [
 278     {
 279      "name": "stdout",
 280      "output_type": "stream",
 281      "text": [
 282       "abruptest (True, 18, 11, <Direction.right: 2>)\n",
 283       "apology (True, 0, 16, <Direction.down: 4>)\n",
 284       "assumed (True, 18, 7, <Direction.upright: 6>)\n",
 285       "barricades (True, 14, 5, <Direction.up: 3>)\n",
 286       "beauty (True, 1, 10, <Direction.right: 2>)\n",
 287       "bravely (True, 13, 2, <Direction.down: 4>)\n",
 288       "bravos (False, 0, 0, <Direction.left: 1>)\n",
 289       "burlier (False, 0, 0, <Direction.left: 1>)\n",
 290       "chanties (True, 19, 0, <Direction.up: 3>)\n",
 291       "clumping (True, 4, 1, <Direction.right: 2>)\n",
 292       "coached (True, 17, 13, <Direction.upleft: 5>)\n",
 293       "coffers (True, 0, 17, <Direction.down: 4>)\n",
 294       "coyness (True, 17, 13, <Direction.left: 1>)\n",
 295       "decriminalisation (False, 0, 0, <Direction.left: 1>)\n",
 296       "detoxes (True, 7, 13, <Direction.right: 2>)\n",
 297       "differs (False, 0, 0, <Direction.left: 1>)\n",
 298       "duelled (False, 0, 0, <Direction.left: 1>)\n",
 299       "duplicating (False, 0, 0, <Direction.left: 1>)\n",
 300       "elaborates (False, 0, 0, <Direction.left: 1>)\n",
 301       "embroils (True, 3, 4, <Direction.down: 4>)\n",
 302       "encirclement (False, 0, 0, <Direction.left: 1>)\n",
 303       "erogenous (True, 2, 10, <Direction.down: 4>)\n",
 304       "facsimiled (False, 0, 0, <Direction.left: 1>)\n",
 305       "festers (False, 0, 0, <Direction.left: 1>)\n",
 306       "flickering (False, 0, 0, <Direction.left: 1>)\n",
 307       "fusible (False, 0, 0, <Direction.left: 1>)\n",
 308       "gluiest (True, 11, 18, <Direction.upleft: 5>)\n",
 309       "golfers (True, 8, 11, <Direction.up: 3>)\n",
 310       "interpolations (False, 0, 0, <Direction.left: 1>)\n",
 311       "involved (False, 0, 0, <Direction.left: 1>)\n",
 312       "irony (True, 11, 1, <Direction.downright: 8>)\n",
 313       "lithographed (False, 0, 0, <Direction.left: 1>)\n",
 314       "nabbed (True, 14, 7, <Direction.upright: 6>)\n",
 315       "nightclubs (True, 19, 10, <Direction.right: 2>)\n",
 316       "oblongs (False, 0, 0, <Direction.left: 1>)\n",
 317       "optics (True, 17, 16, <Direction.up: 3>)\n",
 318       "orphaned (True, 17, 14, <Direction.up: 3>)\n",
 319       "overstates (False, 0, 0, <Direction.left: 1>)\n",
 320       "paining (True, 15, 13, <Direction.upleft: 5>)\n",
 321       "papery (True, 18, 15, <Direction.up: 3>)\n",
 322       "perjures (True, 12, 1, <Direction.down: 4>)\n",
 323       "prescriptions (True, 0, 14, <Direction.left: 1>)\n",
 324       "prissier (True, 15, 6, <Direction.up: 3>)\n",
 325       "rallies (False, 0, 0, <Direction.left: 1>)\n",
 326       "rebated (False, 0, 0, <Direction.left: 1>)\n",
 327       "reneges (False, 0, 0, <Direction.left: 1>)\n",
 328       "saleswomen (False, 0, 0, <Direction.left: 1>)\n",
 329       "scrolls (True, 2, 8, <Direction.left: 1>)\n",
 330       "searing (True, 8, 13, <Direction.downright: 8>)\n",
 331       "slobbering (False, 0, 0, <Direction.left: 1>)\n",
 332       "soups (True, 9, 9, <Direction.upleft: 5>)\n",
 333       "sucking (True, 7, 9, <Direction.up: 3>)\n",
 334       "tenderer (True, 5, 2, <Direction.down: 4>)\n",
 335       "thieved (True, 4, 0, <Direction.down: 4>)\n",
 336       "timbers (True, 6, 19, <Direction.up: 3>)\n",
 337       "toiletries (False, 0, 0, <Direction.left: 1>)\n",
 338       "unabashed (False, 0, 0, <Direction.left: 1>)\n",
 339       "warriors (True, 8, 3, <Direction.down: 4>)\n",
 340       "wimpy (True, 11, 12, <Direction.downleft: 7>)\n",
 341       "wriest (True, 13, 19, <Direction.upleft: 5>)\n"
 342      ]
 343     }
 344    ],
 345    "source": [
 346     "for w in ws:\n",
 347     "    print(w, present(g, w))"
 348    ]
 349   },
 350   {
 351    "cell_type": "markdown",
 352    "metadata": {},
 353    "source": [
 354     "Which words are present?"
 355    ]
 356   },
 357   {
 358    "cell_type": "code",
 359    "execution_count": 79,
 360    "metadata": {
 361     "collapsed": false
 362    },
 363    "outputs": [
 364     {
 365      "data": {
 366       "text/plain": [
 367        "['abruptest',\n",
 368        " 'apology',\n",
 369        " 'assumed',\n",
 370        " 'barricades',\n",
 371        " 'beauty',\n",
 372        " 'bravely',\n",
 373        " 'chanties',\n",
 374        " 'clumping',\n",
 375        " 'coached',\n",
 376        " 'coffers',\n",
 377        " 'coyness',\n",
 378        " 'detoxes',\n",
 379        " 'embroils',\n",
 380        " 'erogenous',\n",
 381        " 'gluiest',\n",
 382        " 'golfers',\n",
 383        " 'irony',\n",
 384        " 'nabbed',\n",
 385        " 'nightclubs',\n",
 386        " 'optics',\n",
 387        " 'orphaned',\n",
 388        " 'paining',\n",
 389        " 'papery',\n",
 390        " 'perjures',\n",
 391        " 'prescriptions',\n",
 392        " 'prissier',\n",
 393        " 'scrolls',\n",
 394        " 'searing',\n",
 395        " 'soups',\n",
 396        " 'sucking',\n",
 397        " 'tenderer',\n",
 398        " 'thieved',\n",
 399        " 'timbers',\n",
 400        " 'warriors',\n",
 401        " 'wimpy',\n",
 402        " 'wriest']"
 403       ]
 404      },
 405      "execution_count": 79,
 406      "metadata": {},
 407      "output_type": "execute_result"
 408     }
 409    ],
 410    "source": [
 411     "[w for w in ws if present(g, w)[0]]"
 412    ]
 413   },
 414   {
 415    "cell_type": "markdown",
 416    "metadata": {},
 417    "source": [
 418     "What is the longest word that is present?"
 419    ]
 420   },
 421   {
 422    "cell_type": "code",
 423    "execution_count": 88,
 424    "metadata": {
 425     "collapsed": false
 426    },
 427    "outputs": [
 428     {
 429      "data": {
 430       "text/plain": [
 431        "'prescriptions'"
 432       ]
 433      },
 434      "execution_count": 88,
 435      "metadata": {},
 436      "output_type": "execute_result"
 437     }
 438    ],
 439    "source": [
 440     "sorted([w for w in ws if present(g, w)[0]], key=len)[-1]"
 441    ]
 442   },
 443   {
 444    "cell_type": "markdown",
 445    "metadata": {},
 446    "source": [
 447     "What is the longest word that is absent?"
 448    ]
 449   },
 450   {
 451    "cell_type": "code",
 452    "execution_count": 89,
 453    "metadata": {
 454     "collapsed": false
 455    },
 456    "outputs": [
 457     {
 458      "data": {
 459       "text/plain": [
 460        "'decriminalisation'"
 461       ]
 462      },
 463      "execution_count": 89,
 464      "metadata": {},
 465      "output_type": "execute_result"
 466     }
 467    ],
 468    "source": [
 469     "sorted([w for w in ws if not present(g, w)[0]], key=len)[-1]"
 470    ]
 471   },
 472   {
 473    "cell_type": "markdown",
 474    "metadata": {},
 475    "source": [
 476     "How many letters are unused?"
 477    ]
 478   },
 479   {
 480    "cell_type": "code",
 481    "execution_count": 82,
 482    "metadata": {
 483     "collapsed": false
 484    },
 485    "outputs": [
 486     {
 487      "data": {
 488       "text/plain": [
 489        "143"
 490       ]
 491      },
 492      "execution_count": 82,
 493      "metadata": {},
 494      "output_type": "execute_result"
 495     }
 496    ],
 497    "source": [
 498     "g0 = empty_grid(width, height)\n",
 499     "for w in ws:\n",
 500     "    p, r, c, d = present(g, w)\n",
 501     "    if p:\n",
 502     "        set_grid(g0, r, c, d, w)\n",
 503     "len([c for c in cat(cat(l) for l in g0) if c == '.'])"
 504    ]
 505   },
 506   {
 507    "cell_type": "markdown",
 508    "metadata": {},
 509    "source": [
 510     "What is the longest word you can make form the leftover letters?"
 511    ]
 512   },
 513   {
 514    "cell_type": "code",
 515    "execution_count": 83,
 516    "metadata": {
 517     "collapsed": false,
 518     "scrolled": true
 519    },
 520    "outputs": [
 521     {
 522      "data": {
 523       "text/plain": [
 524        "Counter({'a': 11,\n",
 525        "         'b': 2,\n",
 526        "         'c': 3,\n",
 527        "         'd': 10,\n",
 528        "         'e': 21,\n",
 529        "         'f': 3,\n",
 530        "         'g': 4,\n",
 531        "         'h': 2,\n",
 532        "         'i': 15,\n",
 533        "         'k': 2,\n",
 534        "         'l': 3,\n",
 535        "         'm': 7,\n",
 536        "         'n': 10,\n",
 537        "         'o': 13,\n",
 538        "         'p': 3,\n",
 539        "         'r': 9,\n",
 540        "         's': 12,\n",
 541        "         't': 2,\n",
 542        "         'u': 6,\n",
 543        "         'v': 2,\n",
 544        "         'y': 2,\n",
 545        "         'z': 1})"
 546       ]
 547      },
 548      "execution_count": 83,
 549      "metadata": {},
 550      "output_type": "execute_result"
 551     }
 552    ],
 553    "source": [
 554     "unused_letters = [l for l, u in zip((c for c in cat(cat(l) for l in g)), (c for c in cat(cat(l) for l in g0)))\n",
 555     "                  if u == '.']\n",
 556     "unused_letter_count = collections.Counter(unused_letters)\n",
 557     "unused_letter_count"
 558    ]
 559   },
 560   {
 561    "cell_type": "code",
 562    "execution_count": 84,
 563    "metadata": {
 564     "collapsed": false
 565    },
 566    "outputs": [
 567     {
 568      "data": {
 569       "text/plain": [
 570        "['bravos',\n",
 571        " 'burlier',\n",
 572        " 'decriminalisation',\n",
 573        " 'differs',\n",
 574        " 'duelled',\n",
 575        " 'duplicating',\n",
 576        " 'elaborates',\n",
 577        " 'encirclement',\n",
 578        " 'facsimiled',\n",
 579        " 'festers',\n",
 580        " 'flickering',\n",
 581        " 'fusible',\n",
 582        " 'interpolations',\n",
 583        " 'involved',\n",
 584        " 'lithographed',\n",
 585        " 'oblongs',\n",
 586        " 'overstates',\n",
 587        " 'rallies',\n",
 588        " 'rebated',\n",
 589        " 'reneges',\n",
 590        " 'saleswomen',\n",
 591        " 'slobbering',\n",
 592        " 'toiletries',\n",
 593        " 'unabashed']"
 594       ]
 595      },
 596      "execution_count": 84,
 597      "metadata": {},
 598      "output_type": "execute_result"
 599     }
 600    ],
 601    "source": [
 602     "unused_words = [w for w in ws if not present(g, w)[0]]\n",
 603     "unused_words"
 604    ]
 605   },
 606   {
 607    "cell_type": "code",
 608    "execution_count": 85,
 609    "metadata": {
 610     "collapsed": false
 611    },
 612    "outputs": [
 613     {
 614      "name": "stdout",
 615      "output_type": "stream",
 616      "text": [
 617       "*bravos Counter({'v': 1, 'b': 1, 'a': 1, 's': 1, 'o': 1, 'r': 1})\n",
 618       "*burlier Counter({'r': 2, 'b': 1, 'u': 1, 'l': 1, 'i': 1, 'e': 1})\n",
 619       "*decriminalisation Counter({'i': 4, 'n': 2, 'a': 2, 's': 1, 'l': 1, 'd': 1, 'e': 1, 'r': 1, 't': 1, 'm': 1, 'o': 1, 'c': 1})\n",
 620       "*differs Counter({'f': 2, 's': 1, 'i': 1, 'd': 1, 'e': 1, 'r': 1})\n",
 621       "*duelled Counter({'d': 2, 'e': 2, 'l': 2, 'u': 1})\n",
 622       "*duplicating Counter({'i': 2, 'g': 1, 'n': 1, 'a': 1, 'l': 1, 'd': 1, 't': 1, 'p': 1, 'u': 1, 'c': 1})\n",
 623       "*elaborates Counter({'a': 2, 'e': 2, 'b': 1, 's': 1, 'l': 1, 'o': 1, 'r': 1, 't': 1})\n",
 624       "*encirclement Counter({'e': 3, 'n': 2, 'c': 2, 'm': 1, 't': 1, 'l': 1, 'i': 1, 'r': 1})\n",
 625       "*facsimiled Counter({'i': 2, 's': 1, 'm': 1, 'a': 1, 'f': 1, 'l': 1, 'd': 1, 'e': 1, 'c': 1})\n",
 626       "*festers Counter({'s': 2, 'e': 2, 'f': 1, 'r': 1, 't': 1})\n",
 627       "*flickering Counter({'i': 2, 'g': 1, 'n': 1, 'f': 1, 'l': 1, 'e': 1, 'k': 1, 'r': 1, 'c': 1})\n",
 628       "*fusible Counter({'s': 1, 'e': 1, 'f': 1, 'b': 1, 'i': 1, 'l': 1, 'u': 1})\n",
 629       "*interpolations Counter({'n': 2, 'i': 2, 'o': 2, 't': 2, 's': 1, 'a': 1, 'l': 1, 'e': 1, 'p': 1, 'r': 1})\n",
 630       "*involved Counter({'v': 2, 'n': 1, 'l': 1, 'i': 1, 'o': 1, 'e': 1, 'd': 1})\n",
 631       "*lithographed Counter({'h': 2, 'g': 1, 'a': 1, 'r': 1, 'l': 1, 'i': 1, 'o': 1, 'e': 1, 'p': 1, 'd': 1, 't': 1})\n",
 632       "*oblongs Counter({'o': 2, 'b': 1, 'g': 1, 'n': 1, 'l': 1, 's': 1})\n",
 633       "*overstates Counter({'s': 2, 'e': 2, 't': 2, 'v': 1, 'a': 1, 'o': 1, 'r': 1})\n",
 634       "*rallies Counter({'l': 2, 's': 1, 'a': 1, 'i': 1, 'e': 1, 'r': 1})\n",
 635       "*rebated Counter({'e': 2, 'b': 1, 'a': 1, 'd': 1, 'r': 1, 't': 1})\n",
 636       "*reneges Counter({'e': 3, 's': 1, 'g': 1, 'n': 1, 'r': 1})\n",
 637       "saleswomen Counter({'s': 2, 'e': 2, 'm': 1, 'n': 1, 'a': 1, 'l': 1, 'o': 1, 'w': 1})\n",
 638       "*slobbering Counter({'b': 2, 's': 1, 'g': 1, 'n': 1, 'i': 1, 'o': 1, 'e': 1, 'l': 1, 'r': 1})\n",
 639       "*toiletries Counter({'i': 2, 'e': 2, 't': 2, 's': 1, 'l': 1, 'o': 1, 'r': 1})\n",
 640       "*unabashed Counter({'a': 2, 'b': 1, 'n': 1, 'h': 1, 's': 1, 'd': 1, 'e': 1, 'u': 1})\n"
 641      ]
 642     }
 643    ],
 644    "source": [
 645     "makeable_words = []\n",
 646     "for w in unused_words:\n",
 647     "    unused_word_count = collections.Counter(w)\n",
 648     "    if all(l in unused_letter_count and unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
 649     "        makeable_words += [w]\n",
 650     "        print('*', end='')\n",
 651     "    print(w, unused_word_count)"
 652    ]
 653   },
 654   {
 655    "cell_type": "code",
 656    "execution_count": 86,
 657    "metadata": {
 658     "collapsed": false
 659    },
 660    "outputs": [
 661     {
 662      "data": {
 663       "text/plain": [
 664        "17"
 665       ]
 666      },
 667      "execution_count": 86,
 668      "metadata": {},
 669      "output_type": "execute_result"
 670     }
 671    ],
 672    "source": [
 673     "max(len(w) for w in makeable_words)"
 674    ]
 675   },
 676   {
 677    "cell_type": "code",
 678    "execution_count": 90,
 679    "metadata": {
 680     "collapsed": false
 681    },
 682    "outputs": [
 683     {
 684      "data": {
 685       "text/plain": [
 686        "'decriminalisation'"
 687       ]
 688      },
 689      "execution_count": 90,
 690      "metadata": {},
 691      "output_type": "execute_result"
 692     }
 693    ],
 694    "source": [
 695     "sorted(makeable_words, key=len)[-1]"
 696    ]
 697   },
 698   {
 699    "cell_type": "code",
 700    "execution_count": 103,
 701    "metadata": {
 702     "collapsed": false
 703    },
 704    "outputs": [],
 705    "source": [
 706     "def do_wordsearch_tasks(fn):\n",
 707     "    width, height, grid, words = read_wordsearch(fn)\n",
 708     "    unused_words = [w for w in words if not present(grid, w)[0]]\n",
 709     "    lwp = sorted([w for w in words if present(grid, w)[0]], key=len)[-1]\n",
 710     "    lwa = sorted(unused_words, key=len)[-1]\n",
 711     "    g0 = empty_grid(width, height)\n",
 712     "    for w in words:\n",
 713     "        p, r, c, d = present(grid, w)\n",
 714     "        if p:\n",
 715     "            set_grid(g0, r, c, d, w) \n",
 716     "    unused_letters = [l for l, u in zip((c for c in cat(cat(l) for l in grid)), (c for c in cat(cat(l) for l in g0)))\n",
 717     "                  if u == '.']\n",
 718     "    unused_letter_count = collections.Counter(unused_letters)\n",
 719     "    makeable_words = []\n",
 720     "    for w in unused_words:\n",
 721     "        unused_word_count = collections.Counter(w)\n",
 722     "        if all(l in unused_letter_count and unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
 723     "            makeable_words += [w]\n",
 724     "    lwm = sorted(makeable_words, key=len)[-1]\n",
 725     "    print('\\n{}'.format(fn))\n",
 726     "    print('Longest word present: {}, {} letters'.format(lwp, len(lwp)))\n",
 727     "    print('Longest word absent: {}, {} letters'.format(lwa, len(lwa)))\n",
 728     "    print('{} unused letters'.format(len([c for c in cat(cat(l) for l in g0) if c == '.'])))\n",
 729     "    print('Longest makeable word: {}, {}'.format(lwm, len(lwm)))"
 730    ]
 731   },
 732   {
 733    "cell_type": "code",
 734    "execution_count": 112,
 735    "metadata": {
 736     "collapsed": false
 737    },
 738    "outputs": [
 739     {
 740      "name": "stdout",
 741      "output_type": "stream",
 742      "text": [
 743       "\n",
 744       "wordsearch00.txt\n",
 745       "Longest word present: yellowing, 9 letters\n",
 746       "Longest word absent: sequined, 8 letters\n",
 747       "147 unused letters\n",
 748       "Longest makeable word: pettiest, 8\n",
 749       "\n",
 750       "wordsearch01.txt\n",
 751       "Longest word present: soubriquets, 11 letters\n",
 752       "Longest word absent: swallowing, 10 letters\n",
 753       "124 unused letters\n",
 754       "Longest makeable word: extradited, 10\n",
 755       "\n",
 756       "wordsearch02.txt\n",
 757       "Longest word present: unattended, 10 letters\n",
 758       "Longest word absent: runabouts, 9 letters\n",
 759       "120 unused letters\n",
 760       "Longest makeable word: runabouts, 9\n",
 761       "\n",
 762       "wordsearch03.txt\n",
 763       "Longest word present: indemnifications, 16 letters\n",
 764       "Longest word absent: propagandised, 13 letters\n",
 765       "129 unused letters\n",
 766       "Longest makeable word: propagandised, 13\n",
 767       "\n",
 768       "wordsearch04.txt\n",
 769       "Longest word present: ostentatiously, 14 letters\n",
 770       "Longest word absent: oleomargarine, 13 letters\n",
 771       "128 unused letters\n",
 772       "Longest makeable word: oleomargarine, 13\n",
 773       "\n",
 774       "wordsearch05.txt\n",
 775       "Longest word present: straightjacketing, 17 letters\n",
 776       "Longest word absent: grandiloquence, 14 letters\n",
 777       "115 unused letters\n",
 778       "Longest makeable word: multivitamins, 13\n",
 779       "\n",
 780       "wordsearch06.txt\n",
 781       "Longest word present: inflorescence, 13 letters\n",
 782       "Longest word absent: extinguished, 12 letters\n",
 783       "159 unused letters\n",
 784       "Longest makeable word: convocations, 12\n",
 785       "\n",
 786       "wordsearch07.txt\n",
 787       "Longest word present: hypothesising, 13 letters\n",
 788       "Longest word absent: nonrenewable, 12 letters\n",
 789       "127 unused letters\n",
 790       "Longest makeable word: nonrenewable, 12\n",
 791       "\n",
 792       "wordsearch08.txt\n",
 793       "Longest word present: misrepresents, 13 letters\n",
 794       "Longest word absent: predominates, 12 letters\n",
 795       "125 unused letters\n",
 796       "Longest makeable word: predominates, 12\n",
 797       "\n",
 798       "wordsearch09.txt\n",
 799       "Longest word present: counterattacks, 14 letters\n",
 800       "Longest word absent: overstepping, 12 letters\n",
 801       "125 unused letters\n",
 802       "Longest makeable word: constituents, 12\n",
 803       "\n",
 804       "wordsearch10.txt\n",
 805       "Longest word present: cheerlessness, 13 letters\n",
 806       "Longest word absent: gregariously, 12 letters\n",
 807       "142 unused letters\n",
 808       "Longest makeable word: gregariously, 12\n",
 809       "\n",
 810       "wordsearch11.txt\n",
 811       "Longest word present: petitioners, 11 letters\n",
 812       "Longest word absent: overdosing, 10 letters\n",
 813       "137 unused letters\n",
 814       "Longest makeable word: needlessly, 10\n",
 815       "\n",
 816       "wordsearch12.txt\n",
 817       "Longest word present: propagandises, 13 letters\n",
 818       "Longest word absent: fluorescent, 11 letters\n",
 819       "130 unused letters\n",
 820       "Longest makeable word: fluorescent, 11\n",
 821       "\n",
 822       "wordsearch13.txt\n",
 823       "Longest word present: preregisters, 12 letters\n",
 824       "Longest word absent: undergrowth, 11 letters\n",
 825       "113 unused letters\n",
 826       "Longest makeable word: undergrowth, 11\n",
 827       "\n",
 828       "wordsearch14.txt\n",
 829       "Longest word present: dispossessing, 13 letters\n",
 830       "Longest word absent: sweatshirts, 11 letters\n",
 831       "116 unused letters\n",
 832       "Longest makeable word: sweatshirts, 11\n",
 833       "\n",
 834       "wordsearch15.txt\n",
 835       "Longest word present: retrenching, 11 letters\n",
 836       "Longest word absent: quadruples, 10 letters\n",
 837       "119 unused letters\n",
 838       "Longest makeable word: cavillings, 10\n",
 839       "\n",
 840       "wordsearch16.txt\n",
 841       "Longest word present: cantankerously, 14 letters\n",
 842       "Longest word absent: amorphousness, 13 letters\n",
 843       "101 unused letters\n",
 844       "Longest makeable word: amorphousness, 13\n",
 845       "\n",
 846       "wordsearch17.txt\n",
 847       "Longest word present: appreciating, 12 letters\n",
 848       "Longest word absent: unreasoning, 11 letters\n",
 849       "114 unused letters\n",
 850       "Longest makeable word: unreasoning, 11\n",
 851       "\n",
 852       "wordsearch18.txt\n",
 853       "Longest word present: rehabilitates, 13 letters\n",
 854       "Longest word absent: interlarding, 12 letters\n",
 855       "135 unused letters\n",
 856       "Longest makeable word: interlarding, 12\n",
 857       "\n",
 858       "wordsearch19.txt\n",
 859       "Longest word present: predetermines, 13 letters\n",
 860       "Longest word absent: prosperously, 12 letters\n",
 861       "127 unused letters\n",
 862       "Longest makeable word: kneecapping, 11\n"
 863      ]
 864     }
 865    ],
 866    "source": [
 867     "for fn in sorted(os.listdir()):\n",
 868     "    if re.match('wordsearch\\d\\d\\.txt', fn):\n",
 869     "        do_wordsearch_tasks(fn)"
 870    ]
 871   },
 872   {
 873    "cell_type": "code",
 874    "execution_count": null,
 875    "metadata": {
 876     "collapsed": true
 877    },
 878    "outputs": [],
 879    "source": []
 880   }
 881  ],
 882  "metadata": {
 883   "kernelspec": {
 884    "display_name": "Python 3",
 885    "language": "python",
 886    "name": "python3"
 887   },
 888   "language_info": {
 889    "codemirror_mode": {
 890     "name": "ipython",
 891     "version": 3
 892    },
 893    "file_extension": ".py",
 894    "mimetype": "text/x-python",
 895    "name": "python",
 896    "nbconvert_exporter": "python",
 897    "pygments_lexer": "ipython3",
 898    "version": "3.5.2+"
 899   }
 900  },
 901  "nbformat": 4,
 902  "nbformat_minor": 0
 903 }