04-word-search/wordsearch-solving.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Wordsearch\n",
   8     "Given a text file, consisting of three parts (a grid size, a grid, and a list of words), find:\n",
   9     "* the words present in the grid, \n",
  10     "* the longest word present in the grid, \n",
  11     "* the number of words not present in the grid, \n",
  12     "* the longest word not present that can be formed from the leftover letters\n",
  13     "\n",
  14     "The only words that need be considered are the ones given in the list in the puzzle input.\n",
  15     "\n",
  16     "The puzzle consists of:\n",
  17     "1. A line consisting of _w_`x`_h_, where _w_ and _h_ are integers giving the width and height of the grid.\n",
  18     "2. The grid itself, consisting of _h_ lines each of _w_ letters.\n",
  19     "3. A list of words, one word per line, of arbitrary length. "
  20    ]
  21   },
  22   {
  23    "cell_type": "markdown",
  24    "metadata": {},
  25    "source": [
  26     "## Example\n",
  27     "\n",
  28     "\n",
  29     "`...p.mown.\n",
  30     ".sdse..ee.\n",
  31     ".e.elad.cr\n",
  32     "pi.dtir.ah\n",
  33     "rzsiwovspu\n",
  34     "oawh.kieab\n",
  35     "brow.c.rda\n",
  36     "ecnotops.r\n",
  37     "d.kc.d...b\n",
  38     ".staple...`\n",
  39     "\n",
  40     "```\n",
  41     "fhjpamownq\n",
  42     "wsdseuqeev\n",
  43     "ieaeladhcr\n",
  44     "piedtiriah\n",
  45     "rzsiwovspu\n",
  46     "oawhakieab\n",
  47     "browpcfrda\n",
  48     "ecnotopssr\n",
  49     "dikchdnpnb\n",
  50     "bstapleokr\n",
  51     "```\n",
  52     "\n",
  53     "14 words added;  6 directions\n",
  54     "\n",
  55     "Present: apace cowhides crazies dock knows lived mown pears probed rhubarb rioted staple tops wide\n",
  56     "\n",
  57     "Decoys: adapting bombing boor brick cackles carnal casino chaplets chump coaster coccyxes coddle collies creels crumbled cunt curds curled curlier deepen demeanor dicier dowses ensuing faddish fest fickler foaming gambol garoting gliding gristle grunts guts ibex impugns instants kielbasy lanyard loamier lugs market meanly minuend misprint mitts molested moonshot mucking oaks olives orgasmic pastrami perfect proceed puckered quashed refined regards retraces revel ridges ringlet scoff shinier siren solaria sprain sunder sunup tamped tapes thirds throw tiller times trains tranquil transfix typesets uric wariness welts whimsy winced winced\n",
  58     "\n",
  59     "Decoys: fickler, adapting, chump, foaming, molested, carnal, crumbled, guts, minuend, bombing, winced, coccyxes, solaria, shinier, cackles\n",
  60     "\n",
  61     "All words: adapting, apace, bombing, cackles, carnal, chump, coccyxes, cowhides, crazies, crumbled, dock, fickler, foaming, guts, knows, lived, minuend, molested, mown, pears, probed, rhubarb, rioted, shinier, solaria, staple, tops, wide, winced\n",
  62     "\n",
  63     "Directions:  [('probed', '`(True, 3, 0, <Direction.down: 4>)`'), ('staple', '`(True, 9, 1, <Direction.right: 2>)`'), ('rioted', '`(True, 6, 7, <Direction.upleft: 5>)`'), ('cowhides', '`(True, 8, 3, <Direction.up: 3>)`'), ('tops', '`(True, 7, 4, <Direction.right: 2>)`'), ('knows', '`(True, 8, 2, <Direction.up: 3>)`'), ('lived', '`(True, 2, 4, <Direction.downright: 8>)`'), ('rhubarb', '`(True, 2, 9, <Direction.down: 4>)`'), ('crazies', '`(True, 7, 1, <Direction.up: 3>)`'), ('dock', '`(True, 8, 5, <Direction.up: 3>)`'), ('apace', '`(True, 5, 8, <Direction.up: 3>)`'), ('mown', '`(True, 0, 5, <Direction.right: 2>)`'), ('pears', '`(True, 0, 3, <Direction.downright: 8>)`'), ('wide', '`(True, 4, 4, <Direction.upright: 6>)`')]"
  64    ]
  65   },
  66   {
  67    "cell_type": "code",
  68    "execution_count": 4,
  69    "metadata": {
  70     "collapsed": true
  71    },
  72    "outputs": [],
  73    "source": [
  74     "import string\n",
  75     "import re\n",
  76     "import collections\n",
  77     "import copy\n",
  78     "import os\n",
  79     "\n",
  80     "from enum import Enum\n",
  81     "Direction = Enum('Direction', 'left right up down upleft upright downleft downright')\n",
  82     "    \n",
  83     "delta = {Direction.left: (0, -1),Direction.right: (0, 1), \n",
  84     "         Direction.up: (-1, 0), Direction.down: (1, 0), \n",
  85     "         Direction.upleft: (-1, -1), Direction.upright: (-1, 1), \n",
  86     "         Direction.downleft: (1, -1), Direction.downright: (1, 1)}\n",
  87     "\n",
  88     "cat = ''.join\n",
  89     "wcat = ' '.join\n",
  90     "lcat = '\\n'.join"
  91    ]
  92   },
  93   {
  94    "cell_type": "code",
  95    "execution_count": 5,
  96    "metadata": {
  97     "collapsed": true
  98    },
  99    "outputs": [],
 100    "source": [
 101     "def empty_grid(w, h):\n",
 102     "    return [['.' for c in range(w)] for r in range(h)]"
 103    ]
 104   },
 105   {
 106    "cell_type": "code",
 107    "execution_count": 6,
 108    "metadata": {
 109     "collapsed": true
 110    },
 111    "outputs": [],
 112    "source": [
 113     "def show_grid(grid):\n",
 114     "    return lcat(cat(r) for r in grid)"
 115    ]
 116   },
 117   {
 118    "cell_type": "code",
 119    "execution_count": 7,
 120    "metadata": {
 121     "collapsed": true
 122    },
 123    "outputs": [],
 124    "source": [
 125     "def indices(grid, r, c, l, d):\n",
 126     "    dr, dc = delta[d]\n",
 127     "    w = len(grid[0])\n",
 128     "    h = len(grid)\n",
 129     "    inds = [(r + i * dr, c + i * dc) for i in range(l)]\n",
 130     "    return [(i, j) for i, j in inds\n",
 131     "           if i >= 0\n",
 132     "           if j >= 0\n",
 133     "           if i < h\n",
 134     "           if j < w]"
 135    ]
 136   },
 137   {
 138    "cell_type": "code",
 139    "execution_count": 8,
 140    "metadata": {
 141     "collapsed": true
 142    },
 143    "outputs": [],
 144    "source": [
 145     "def gslice(grid, r, c, l, d):\n",
 146     "    return [grid[i][j] for i, j in indices(grid, r, c, l, d)]"
 147    ]
 148   },
 149   {
 150    "cell_type": "code",
 151    "execution_count": 9,
 152    "metadata": {
 153     "collapsed": true
 154    },
 155    "outputs": [],
 156    "source": [
 157     "def set_grid(grid, r, c, d, word):\n",
 158     "    for (i, j), l in zip(indices(grid, r, c, len(word), d), word):\n",
 159     "        grid[i][j] = l\n",
 160     "    return grid"
 161    ]
 162   },
 163   {
 164    "cell_type": "code",
 165    "execution_count": 10,
 166    "metadata": {
 167     "collapsed": true
 168    },
 169    "outputs": [],
 170    "source": [
 171     "def present(grid, word):\n",
 172     "    w = len(grid[0])\n",
 173     "    h = len(grid)\n",
 174     "    for r in range(h):\n",
 175     "        for c in range(w):\n",
 176     "            for d in Direction:\n",
 177     "                if cat(gslice(grid, r, c, len(word), d)) == word:\n",
 178     "                    return True, r, c, d\n",
 179     "    return False, 0, 0, list(Direction)[0]"
 180    ]
 181   },
 182   {
 183    "cell_type": "code",
 184    "execution_count": 11,
 185    "metadata": {
 186     "collapsed": true
 187    },
 188    "outputs": [],
 189    "source": [
 190     "def read_wordsearch(fn):\n",
 191     "    lines = [l.strip() for l in open(fn).readlines()]\n",
 192     "    w, h = [int(s) for s in lines[0].split('x')]\n",
 193     "    grid = lines[1:h+1]\n",
 194     "    words = lines[h+1:]\n",
 195     "    return w, h, grid, words"
 196    ]
 197   },
 198   {
 199    "cell_type": "code",
 200    "execution_count": 12,
 201    "metadata": {
 202     "scrolled": true
 203    },
 204    "outputs": [
 205     {
 206      "data": {
 207       "text/plain": [
 208        "(['pistrohxegniydutslxt',\n",
 209        "  'wmregunarbpiledsyuoo',\n",
 210        "  'hojminbmutartslrlmgo',\n",
 211        "  'isrsdniiekildabolpll',\n",
 212        "  'tstsnyekentypkalases',\n",
 213        "  'ssnetengcrfetedirgdt',\n",
 214        "  'religstasuslatxauner',\n",
 215        "  'elgcpgatsklglzistilo',\n",
 216        "  'tndlimitationilkasan',\n",
 217        "  'aousropedlygiifeniog',\n",
 218        "  'kilrprepszffsyzqsrhs',\n",
 219        "  'itlaadorableorpccese',\n",
 220        "  'noaeewoodedpngmqicnl',\n",
 221        "  'gmrtoitailingchelrok',\n",
 222        "  'jadsngninetsahtooeic',\n",
 223        "  'xeernighestsailarmtu',\n",
 224        "  'aeabsolvednscumdfnon',\n",
 225        "  'gydammingawlcandornk',\n",
 226        "  'hurlerslvkaccxcinosw',\n",
 227        "  'iqnanoitacifitrofqqi'],\n",
 228        " ['absolved',\n",
 229        "  'adorable',\n",
 230        "  'aeon',\n",
 231        "  'alias',\n",
 232        "  'ancestor',\n",
 233        "  'baritone',\n",
 234        "  'bemusing',\n",
 235        "  'blonds',\n",
 236        "  'bran',\n",
 237        "  'calcite',\n",
 238        "  'candor',\n",
 239        "  'conciseness',\n",
 240        "  'consequent',\n",
 241        "  'cuddle',\n",
 242        "  'damming',\n",
 243        "  'dashboards',\n",
 244        "  'despairing',\n",
 245        "  'dint',\n",
 246        "  'dullard',\n",
 247        "  'dynasty',\n",
 248        "  'employer',\n",
 249        "  'exhorts',\n",
 250        "  'feted',\n",
 251        "  'fill',\n",
 252        "  'flattens',\n",
 253        "  'foghorn',\n",
 254        "  'fortification',\n",
 255        "  'freakish',\n",
 256        "  'frolics',\n",
 257        "  'gall',\n",
 258        "  'gees',\n",
 259        "  'genies',\n",
 260        "  'gets',\n",
 261        "  'hastening',\n",
 262        "  'hits',\n",
 263        "  'hopelessness',\n",
 264        "  'hurlers',\n",
 265        "  'impales',\n",
 266        "  'infix',\n",
 267        "  'inflow',\n",
 268        "  'innumerable',\n",
 269        "  'intentional',\n",
 270        "  'jerkin',\n",
 271        "  'justification',\n",
 272        "  'kitty',\n",
 273        "  'knuckles',\n",
 274        "  'leaving',\n",
 275        "  'like',\n",
 276        "  'limitation',\n",
 277        "  'locoweeds',\n",
 278        "  'loot',\n",
 279        "  'lucking',\n",
 280        "  'lumps',\n",
 281        "  'mercerising',\n",
 282        "  'monickers',\n",
 283        "  'motionless',\n",
 284        "  'naturally',\n",
 285        "  'nighest',\n",
 286        "  'notion',\n",
 287        "  'ogled',\n",
 288        "  'originality',\n",
 289        "  'outings',\n",
 290        "  'pendulous',\n",
 291        "  'piled',\n",
 292        "  'pins',\n",
 293        "  'pithier',\n",
 294        "  'prep',\n",
 295        "  'randomness',\n",
 296        "  'rectors',\n",
 297        "  'redrew',\n",
 298        "  'reformulated',\n",
 299        "  'remoteness',\n",
 300        "  'retaking',\n",
 301        "  'rethink',\n",
 302        "  'rope',\n",
 303        "  'rubier',\n",
 304        "  'sailors',\n",
 305        "  'scowls',\n",
 306        "  'scum',\n",
 307        "  'sepals',\n",
 308        "  'sequencers',\n",
 309        "  'serf',\n",
 310        "  'shoaled',\n",
 311        "  'shook',\n",
 312        "  'sonic',\n",
 313        "  'spottiest',\n",
 314        "  'stag',\n",
 315        "  'stood',\n",
 316        "  'stratum',\n",
 317        "  'strong',\n",
 318        "  'studying',\n",
 319        "  'surtaxing',\n",
 320        "  'tailing',\n",
 321        "  'tears',\n",
 322        "  'teazles',\n",
 323        "  'vans',\n",
 324        "  'wardrobes',\n",
 325        "  'wooded',\n",
 326        "  'worsts',\n",
 327        "  'zings'])"
 328       ]
 329      },
 330      "execution_count": 12,
 331      "metadata": {},
 332      "output_type": "execute_result"
 333     }
 334    ],
 335    "source": [
 336     "width, height, g, ws = read_wordsearch('wordsearch04.txt')\n",
 337     "g, ws"
 338    ]
 339   },
 340   {
 341    "cell_type": "code",
 342    "execution_count": 13,
 343    "metadata": {
 344     "scrolled": true
 345    },
 346    "outputs": [
 347     {
 348      "name": "stdout",
 349      "output_type": "stream",
 350      "text": [
 351       "absolved (True, 16, 2, <Direction.right: 2>)\n",
 352       "adorable (True, 11, 4, <Direction.right: 2>)\n",
 353       "aeon (True, 11, 4, <Direction.down: 4>)\n",
 354       "alias (True, 15, 15, <Direction.left: 1>)\n",
 355       "ancestor (False, 0, 0, <Direction.left: 1>)\n",
 356       "baritone (False, 0, 0, <Direction.left: 1>)\n",
 357       "bemusing (False, 0, 0, <Direction.left: 1>)\n",
 358       "blonds (False, 0, 0, <Direction.left: 1>)\n",
 359       "bran (True, 1, 9, <Direction.left: 1>)\n",
 360       "calcite (True, 19, 9, <Direction.upright: 6>)\n",
 361       "candor (True, 17, 12, <Direction.right: 2>)\n",
 362       "conciseness (False, 0, 0, <Direction.left: 1>)\n",
 363       "consequent (False, 0, 0, <Direction.left: 1>)\n",
 364       "cuddle (False, 0, 0, <Direction.left: 1>)\n",
 365       "damming (True, 17, 2, <Direction.right: 2>)\n",
 366       "dashboards (False, 0, 0, <Direction.left: 1>)\n",
 367       "despairing (False, 0, 0, <Direction.left: 1>)\n",
 368       "dint (False, 0, 0, <Direction.left: 1>)\n",
 369       "dullard (True, 8, 2, <Direction.down: 4>)\n",
 370       "dynasty (True, 3, 4, <Direction.downright: 8>)\n",
 371       "employer (False, 0, 0, <Direction.left: 1>)\n",
 372       "exhorts (True, 0, 8, <Direction.left: 1>)\n",
 373       "feted (True, 5, 10, <Direction.right: 2>)\n",
 374       "fill (True, 9, 14, <Direction.upleft: 5>)\n",
 375       "flattens (True, 10, 10, <Direction.upleft: 5>)\n",
 376       "foghorn (True, 10, 11, <Direction.downright: 8>)\n",
 377       "fortification (True, 19, 16, <Direction.left: 1>)\n",
 378       "freakish (False, 0, 0, <Direction.left: 1>)\n",
 379       "frolics (True, 16, 16, <Direction.up: 3>)\n",
 380       "gall (False, 0, 0, <Direction.left: 1>)\n",
 381       "gees (True, 17, 0, <Direction.upright: 6>)\n",
 382       "genies (True, 5, 7, <Direction.upleft: 5>)\n",
 383       "gets (True, 6, 4, <Direction.upleft: 5>)\n",
 384       "hastening (True, 14, 13, <Direction.left: 1>)\n",
 385       "hits (True, 2, 0, <Direction.down: 4>)\n",
 386       "hopelessness (False, 0, 0, <Direction.left: 1>)\n",
 387       "hurlers (True, 18, 0, <Direction.right: 2>)\n",
 388       "impales (False, 0, 0, <Direction.left: 1>)\n",
 389       "infix (False, 0, 0, <Direction.left: 1>)\n",
 390       "inflow (False, 0, 0, <Direction.left: 1>)\n",
 391       "innumerable (False, 0, 0, <Direction.left: 1>)\n",
 392       "intentional (False, 0, 0, <Direction.left: 1>)\n",
 393       "jerkin (False, 0, 0, <Direction.left: 1>)\n",
 394       "justification (False, 0, 0, <Direction.left: 1>)\n",
 395       "kitty (True, 8, 15, <Direction.upleft: 5>)\n",
 396       "knuckles (True, 17, 19, <Direction.up: 3>)\n",
 397       "leaving (False, 0, 0, <Direction.left: 1>)\n",
 398       "like (True, 3, 11, <Direction.left: 1>)\n",
 399       "limitation (True, 8, 3, <Direction.right: 2>)\n",
 400       "locoweeds (False, 0, 0, <Direction.left: 1>)\n",
 401       "loot (True, 3, 19, <Direction.up: 3>)\n",
 402       "lucking (True, 7, 10, <Direction.upleft: 5>)\n",
 403       "lumps (True, 0, 17, <Direction.down: 4>)\n",
 404       "mercerising (True, 15, 17, <Direction.up: 3>)\n",
 405       "monickers (False, 0, 0, <Direction.left: 1>)\n",
 406       "motionless (True, 13, 1, <Direction.up: 3>)\n",
 407       "naturally (True, 9, 16, <Direction.up: 3>)\n",
 408       "nighest (True, 15, 4, <Direction.right: 2>)\n",
 409       "notion (True, 17, 18, <Direction.up: 3>)\n",
 410       "ogled (True, 1, 18, <Direction.down: 4>)\n",
 411       "originality (False, 0, 0, <Direction.left: 1>)\n",
 412       "outings (False, 0, 0, <Direction.left: 1>)\n",
 413       "pendulous (False, 0, 0, <Direction.left: 1>)\n",
 414       "piled (True, 1, 10, <Direction.right: 2>)\n",
 415       "pins (True, 7, 4, <Direction.upleft: 5>)\n",
 416       "pithier (False, 0, 0, <Direction.left: 1>)\n",
 417       "prep (True, 10, 4, <Direction.right: 2>)\n",
 418       "randomness (False, 0, 0, <Direction.left: 1>)\n",
 419       "rectors (False, 0, 0, <Direction.left: 1>)\n",
 420       "redrew (False, 0, 0, <Direction.left: 1>)\n",
 421       "reformulated (False, 0, 0, <Direction.left: 1>)\n",
 422       "remoteness (False, 0, 0, <Direction.left: 1>)\n",
 423       "retaking (True, 6, 0, <Direction.down: 4>)\n",
 424       "rethink (False, 0, 0, <Direction.left: 1>)\n",
 425       "rope (True, 9, 4, <Direction.right: 2>)\n",
 426       "rubier (True, 0, 4, <Direction.downright: 8>)\n",
 427       "sailors (True, 7, 15, <Direction.up: 3>)\n",
 428       "scowls (False, 0, 0, <Direction.left: 1>)\n",
 429       "scum (True, 16, 11, <Direction.right: 2>)\n",
 430       "sepals (True, 6, 10, <Direction.upright: 6>)\n",
 431       "sequencers (False, 0, 0, <Direction.left: 1>)\n",
 432       "serf (False, 0, 0, <Direction.left: 1>)\n",
 433       "shoaled (True, 11, 18, <Direction.up: 3>)\n",
 434       "shook (False, 0, 0, <Direction.left: 1>)\n",
 435       "sonic (True, 18, 18, <Direction.left: 1>)\n",
 436       "spottiest (False, 0, 0, <Direction.left: 1>)\n",
 437       "stag (True, 7, 8, <Direction.left: 1>)\n",
 438       "stood (False, 0, 0, <Direction.left: 1>)\n",
 439       "stratum (True, 2, 13, <Direction.left: 1>)\n",
 440       "strong (True, 4, 19, <Direction.down: 4>)\n",
 441       "studying (True, 0, 16, <Direction.left: 1>)\n",
 442       "surtaxing (False, 0, 0, <Direction.left: 1>)\n",
 443       "tailing (True, 13, 6, <Direction.right: 2>)\n",
 444       "tears (True, 13, 3, <Direction.up: 3>)\n",
 445       "teazles (True, 4, 10, <Direction.downright: 8>)\n",
 446       "vans (True, 18, 8, <Direction.upright: 6>)\n",
 447       "wardrobes (False, 0, 0, <Direction.left: 1>)\n",
 448       "wooded (True, 12, 5, <Direction.right: 2>)\n",
 449       "worsts (True, 1, 0, <Direction.downright: 8>)\n",
 450       "zings (True, 10, 14, <Direction.upleft: 5>)\n"
 451      ]
 452     }
 453    ],
 454    "source": [
 455     "for w in ws:\n",
 456     "    print(w, present(g, w))"
 457    ]
 458   },
 459   {
 460    "cell_type": "markdown",
 461    "metadata": {},
 462    "source": [
 463     "Which words are present?"
 464    ]
 465   },
 466   {
 467    "cell_type": "code",
 468    "execution_count": 14,
 469    "metadata": {
 470     "scrolled": true
 471    },
 472    "outputs": [
 473     {
 474      "data": {
 475       "text/plain": [
 476        "['absolved',\n",
 477        " 'adorable',\n",
 478        " 'aeon',\n",
 479        " 'alias',\n",
 480        " 'bran',\n",
 481        " 'calcite',\n",
 482        " 'candor',\n",
 483        " 'damming',\n",
 484        " 'dullard',\n",
 485        " 'dynasty',\n",
 486        " 'exhorts',\n",
 487        " 'feted',\n",
 488        " 'fill',\n",
 489        " 'flattens',\n",
 490        " 'foghorn',\n",
 491        " 'fortification',\n",
 492        " 'frolics',\n",
 493        " 'gees',\n",
 494        " 'genies',\n",
 495        " 'gets',\n",
 496        " 'hastening',\n",
 497        " 'hits',\n",
 498        " 'hurlers',\n",
 499        " 'kitty',\n",
 500        " 'knuckles',\n",
 501        " 'like',\n",
 502        " 'limitation',\n",
 503        " 'loot',\n",
 504        " 'lucking',\n",
 505        " 'lumps',\n",
 506        " 'mercerising',\n",
 507        " 'motionless',\n",
 508        " 'naturally',\n",
 509        " 'nighest',\n",
 510        " 'notion',\n",
 511        " 'ogled',\n",
 512        " 'piled',\n",
 513        " 'pins',\n",
 514        " 'prep',\n",
 515        " 'retaking',\n",
 516        " 'rope',\n",
 517        " 'rubier',\n",
 518        " 'sailors',\n",
 519        " 'scum',\n",
 520        " 'sepals',\n",
 521        " 'shoaled',\n",
 522        " 'sonic',\n",
 523        " 'stag',\n",
 524        " 'stratum',\n",
 525        " 'strong',\n",
 526        " 'studying',\n",
 527        " 'tailing',\n",
 528        " 'tears',\n",
 529        " 'teazles',\n",
 530        " 'vans',\n",
 531        " 'wooded',\n",
 532        " 'worsts',\n",
 533        " 'zings']"
 534       ]
 535      },
 536      "execution_count": 14,
 537      "metadata": {},
 538      "output_type": "execute_result"
 539     }
 540    ],
 541    "source": [
 542     "[w for w in ws if present(g, w)[0]]"
 543    ]
 544   },
 545   {
 546    "cell_type": "markdown",
 547    "metadata": {},
 548    "source": [
 549     "What is the longest word that is present?"
 550    ]
 551   },
 552   {
 553    "cell_type": "code",
 554    "execution_count": 15,
 555    "metadata": {},
 556    "outputs": [
 557     {
 558      "data": {
 559       "text/plain": [
 560        "'fortification'"
 561       ]
 562      },
 563      "execution_count": 15,
 564      "metadata": {},
 565      "output_type": "execute_result"
 566     }
 567    ],
 568    "source": [
 569     "sorted([w for w in ws if present(g, w)[0]], key=len)[-1]"
 570    ]
 571   },
 572   {
 573    "cell_type": "markdown",
 574    "metadata": {},
 575    "source": [
 576     "What is the longest word that is absent?"
 577    ]
 578   },
 579   {
 580    "cell_type": "code",
 581    "execution_count": 16,
 582    "metadata": {},
 583    "outputs": [
 584     {
 585      "data": {
 586       "text/plain": [
 587        "'justification'"
 588       ]
 589      },
 590      "execution_count": 16,
 591      "metadata": {},
 592      "output_type": "execute_result"
 593     }
 594    ],
 595    "source": [
 596     "sorted([w for w in ws if not present(g, w)[0]], key=len)[-1]"
 597    ]
 598   },
 599   {
 600    "cell_type": "markdown",
 601    "metadata": {},
 602    "source": [
 603     "How many letters are unused?"
 604    ]
 605   },
 606   {
 607    "cell_type": "code",
 608    "execution_count": 17,
 609    "metadata": {},
 610    "outputs": [
 611     {
 612      "data": {
 613       "text/plain": [
 614        "57"
 615       ]
 616      },
 617      "execution_count": 17,
 618      "metadata": {},
 619      "output_type": "execute_result"
 620     }
 621    ],
 622    "source": [
 623     "g0 = empty_grid(width, height)\n",
 624     "for w in ws:\n",
 625     "    p, r, c, d = present(g, w)\n",
 626     "    if p:\n",
 627     "        set_grid(g0, r, c, d, w)\n",
 628     "len([c for c in cat(cat(l) for l in g0) if c == '.'])"
 629    ]
 630   },
 631   {
 632    "cell_type": "markdown",
 633    "metadata": {},
 634    "source": [
 635     "What is the longest word you can make form the leftover letters?"
 636    ]
 637   },
 638   {
 639    "cell_type": "code",
 640    "execution_count": 18,
 641    "metadata": {
 642     "scrolled": true
 643    },
 644    "outputs": [
 645     {
 646      "data": {
 647       "text/plain": [
 648        "Counter({'a': 4,\n",
 649        "         'b': 1,\n",
 650        "         'c': 5,\n",
 651        "         'd': 3,\n",
 652        "         'e': 1,\n",
 653        "         'g': 2,\n",
 654        "         'i': 5,\n",
 655        "         'j': 2,\n",
 656        "         'k': 3,\n",
 657        "         'l': 2,\n",
 658        "         'm': 3,\n",
 659        "         'n': 3,\n",
 660        "         'p': 3,\n",
 661        "         'q': 5,\n",
 662        "         'r': 3,\n",
 663        "         's': 3,\n",
 664        "         'w': 2,\n",
 665        "         'x': 4,\n",
 666        "         'y': 2,\n",
 667        "         'z': 1})"
 668       ]
 669      },
 670      "execution_count": 18,
 671      "metadata": {},
 672      "output_type": "execute_result"
 673     }
 674    ],
 675    "source": [
 676     "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",
 677     "                  if u == '.']\n",
 678     "unused_letter_count = collections.Counter(unused_letters)\n",
 679     "unused_letter_count"
 680    ]
 681   },
 682   {
 683    "cell_type": "code",
 684    "execution_count": 19,
 685    "metadata": {
 686     "scrolled": true
 687    },
 688    "outputs": [
 689     {
 690      "data": {
 691       "text/plain": [
 692        "['ancestor',\n",
 693        " 'baritone',\n",
 694        " 'bemusing',\n",
 695        " 'blonds',\n",
 696        " 'conciseness',\n",
 697        " 'consequent',\n",
 698        " 'cuddle',\n",
 699        " 'dashboards',\n",
 700        " 'despairing',\n",
 701        " 'dint',\n",
 702        " 'employer',\n",
 703        " 'freakish',\n",
 704        " 'gall',\n",
 705        " 'hopelessness',\n",
 706        " 'impales',\n",
 707        " 'infix',\n",
 708        " 'inflow',\n",
 709        " 'innumerable',\n",
 710        " 'intentional',\n",
 711        " 'jerkin',\n",
 712        " 'justification',\n",
 713        " 'leaving',\n",
 714        " 'locoweeds',\n",
 715        " 'monickers',\n",
 716        " 'originality',\n",
 717        " 'outings',\n",
 718        " 'pendulous',\n",
 719        " 'pithier',\n",
 720        " 'randomness',\n",
 721        " 'rectors',\n",
 722        " 'redrew',\n",
 723        " 'reformulated',\n",
 724        " 'remoteness',\n",
 725        " 'rethink',\n",
 726        " 'scowls',\n",
 727        " 'sequencers',\n",
 728        " 'serf',\n",
 729        " 'shook',\n",
 730        " 'spottiest',\n",
 731        " 'stood',\n",
 732        " 'surtaxing',\n",
 733        " 'wardrobes']"
 734       ]
 735      },
 736      "execution_count": 19,
 737      "metadata": {},
 738      "output_type": "execute_result"
 739     }
 740    ],
 741    "source": [
 742     "unused_words = [w for w in ws if not present(g, w)[0]]\n",
 743     "unused_words"
 744    ]
 745   },
 746   {
 747    "cell_type": "code",
 748    "execution_count": 20,
 749    "metadata": {
 750     "scrolled": true
 751    },
 752    "outputs": [
 753     {
 754      "name": "stdout",
 755      "output_type": "stream",
 756      "text": [
 757       "ancestor Counter({'e': 1, 'a': 1, 's': 1, 'c': 1, 'n': 1, 'o': 1, 'r': 1, 't': 1})\n",
 758       "baritone Counter({'i': 1, 'e': 1, 'a': 1, 'n': 1, 't': 1, 'o': 1, 'r': 1, 'b': 1})\n",
 759       "bemusing Counter({'i': 1, 'e': 1, 's': 1, 'g': 1, 'n': 1, 'b': 1, 'u': 1, 'm': 1})\n",
 760       "blonds Counter({'n': 1, 'l': 1, 's': 1, 'd': 1, 'o': 1, 'b': 1})\n",
 761       "conciseness Counter({'s': 3, 'e': 2, 'n': 2, 'c': 2, 'i': 1, 'o': 1})\n",
 762       "consequent Counter({'e': 2, 'n': 2, 'c': 1, 's': 1, 'q': 1, 'o': 1, 'u': 1, 't': 1})\n",
 763       "cuddle Counter({'d': 2, 'l': 1, 'e': 1, 'u': 1, 'c': 1})\n",
 764       "dashboards Counter({'a': 2, 's': 2, 'd': 2, 'o': 1, 'h': 1, 'r': 1, 'b': 1})\n",
 765       "*despairing Counter({'i': 2, 'n': 1, 'e': 1, 'a': 1, 'p': 1, 'g': 1, 's': 1, 'd': 1, 'r': 1})\n",
 766       "dint Counter({'i': 1, 'd': 1, 'n': 1, 't': 1})\n",
 767       "employer Counter({'e': 2, 'p': 1, 'l': 1, 'y': 1, 'o': 1, 'm': 1, 'r': 1})\n",
 768       "freakish Counter({'f': 1, 'i': 1, 'e': 1, 'a': 1, 's': 1, 'k': 1, 'h': 1, 'r': 1})\n",
 769       "*gall Counter({'l': 2, 'g': 1, 'a': 1})\n",
 770       "hopelessness Counter({'s': 4, 'e': 3, 'n': 1, 'p': 1, 'l': 1, 'h': 1, 'o': 1})\n",
 771       "*impales Counter({'i': 1, 'e': 1, 'a': 1, 'p': 1, 'l': 1, 's': 1, 'm': 1})\n",
 772       "infix Counter({'i': 2, 'f': 1, 'x': 1, 'n': 1})\n",
 773       "inflow Counter({'f': 1, 'i': 1, 'n': 1, 'l': 1, 'w': 1, 'o': 1})\n",
 774       "innumerable Counter({'e': 2, 'n': 2, 'i': 1, 'a': 1, 'l': 1, 'r': 1, 'b': 1, 'u': 1, 'm': 1})\n",
 775       "intentional Counter({'n': 3, 'i': 2, 't': 2, 'e': 1, 'a': 1, 'l': 1, 'o': 1})\n",
 776       "*jerkin Counter({'i': 1, 'e': 1, 'n': 1, 'k': 1, 'j': 1, 'r': 1})\n",
 777       "justification Counter({'i': 3, 't': 2, 'f': 1, 'a': 1, 's': 1, 'c': 1, 'j': 1, 'o': 1, 'u': 1, 'n': 1})\n",
 778       "leaving Counter({'g': 1, 'i': 1, 'e': 1, 'a': 1, 'n': 1, 'l': 1, 'v': 1})\n",
 779       "locoweeds Counter({'e': 2, 'o': 2, 'w': 1, 'l': 1, 'c': 1, 's': 1, 'd': 1})\n",
 780       "monickers Counter({'i': 1, 'e': 1, 'n': 1, 'c': 1, 's': 1, 'k': 1, 'o': 1, 'm': 1, 'r': 1})\n",
 781       "originality Counter({'i': 3, 'a': 1, 'n': 1, 'l': 1, 'y': 1, 'g': 1, 't': 1, 'o': 1, 'r': 1})\n",
 782       "outings Counter({'i': 1, 'n': 1, 's': 1, 'g': 1, 't': 1, 'o': 1, 'u': 1})\n",
 783       "pendulous Counter({'u': 2, 'e': 1, 'n': 1, 'l': 1, 's': 1, 'p': 1, 'd': 1, 'o': 1})\n",
 784       "pithier Counter({'i': 2, 'e': 1, 'p': 1, 't': 1, 'h': 1, 'r': 1})\n",
 785       "randomness Counter({'n': 2, 's': 2, 'e': 1, 'a': 1, 'd': 1, 'o': 1, 'r': 1, 'm': 1})\n",
 786       "rectors Counter({'r': 2, 'e': 1, 's': 1, 'c': 1, 't': 1, 'o': 1})\n",
 787       "redrew Counter({'e': 2, 'r': 2, 'w': 1, 'd': 1})\n",
 788       "reformulated Counter({'e': 2, 'r': 2, 'f': 1, 'a': 1, 'l': 1, 'u': 1, 't': 1, 'd': 1, 'o': 1, 'm': 1})\n",
 789       "remoteness Counter({'e': 3, 's': 2, 'n': 1, 't': 1, 'o': 1, 'r': 1, 'm': 1})\n",
 790       "rethink Counter({'i': 1, 'e': 1, 'n': 1, 'k': 1, 't': 1, 'h': 1, 'r': 1})\n",
 791       "scowls Counter({'s': 2, 'o': 1, 'l': 1, 'w': 1, 'c': 1})\n",
 792       "sequencers Counter({'e': 3, 's': 2, 'n': 1, 'q': 1, 'c': 1, 'u': 1, 'r': 1})\n",
 793       "serf Counter({'f': 1, 'e': 1, 's': 1, 'r': 1})\n",
 794       "shook Counter({'o': 2, 'h': 1, 's': 1, 'k': 1})\n",
 795       "spottiest Counter({'t': 3, 's': 2, 'i': 1, 'e': 1, 'p': 1, 'o': 1})\n",
 796       "stood Counter({'o': 2, 't': 1, 's': 1, 'd': 1})\n",
 797       "surtaxing Counter({'x': 1, 'i': 1, 'a': 1, 's': 1, 'g': 1, 't': 1, 'n': 1, 'u': 1, 'r': 1})\n",
 798       "wardrobes Counter({'r': 2, 'e': 1, 'a': 1, 'w': 1, 's': 1, 'd': 1, 'o': 1, 'b': 1})\n"
 799      ]
 800     }
 801    ],
 802    "source": [
 803     "makeable_words = []\n",
 804     "for w in unused_words:\n",
 805     "    unused_word_count = collections.Counter(w)\n",
 806     "    if all(unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
 807     "        makeable_words += [w]\n",
 808     "        print('*', end='')\n",
 809     "    print(w, unused_word_count)"
 810    ]
 811   },
 812   {
 813    "cell_type": "code",
 814    "execution_count": 21,
 815    "metadata": {},
 816    "outputs": [
 817     {
 818      "data": {
 819       "text/plain": [
 820        "10"
 821       ]
 822      },
 823      "execution_count": 21,
 824      "metadata": {},
 825      "output_type": "execute_result"
 826     }
 827    ],
 828    "source": [
 829     "max(len(w) for w in makeable_words)"
 830    ]
 831   },
 832   {
 833    "cell_type": "code",
 834    "execution_count": 22,
 835    "metadata": {},
 836    "outputs": [
 837     {
 838      "data": {
 839       "text/plain": [
 840        "'despairing'"
 841       ]
 842      },
 843      "execution_count": 22,
 844      "metadata": {},
 845      "output_type": "execute_result"
 846     }
 847    ],
 848    "source": [
 849     "sorted(makeable_words, key=len)[-1]"
 850    ]
 851   },
 852   {
 853    "cell_type": "code",
 854    "execution_count": 23,
 855    "metadata": {
 856     "collapsed": true
 857    },
 858    "outputs": [],
 859    "source": [
 860     "def do_wordsearch_tasks(fn, show_anyway=False):\n",
 861     "    width, height, grid, words = read_wordsearch(fn)\n",
 862     "    used_words = [w for w in words if present(grid, w)[0]]\n",
 863     "    unused_words = [w for w in words if not present(grid, w)[0]]\n",
 864     "    lwp = sorted([w for w in words if present(grid, w)[0]], key=len)[-1]\n",
 865     "    lwps = [w for w in used_words if len(w) == len(lwp)]\n",
 866     "    lwa = sorted(unused_words, key=len)[-1]\n",
 867     "    lwas = [w for w in unused_words if len(w) == len(lwa)]\n",
 868     "    g0 = empty_grid(width, height)\n",
 869     "    for w in words:\n",
 870     "        p, r, c, d = present(grid, w)\n",
 871     "        if p:\n",
 872     "            set_grid(g0, r, c, d, w) \n",
 873     "    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",
 874     "                  if u == '.']\n",
 875     "    unused_letter_count = collections.Counter(unused_letters)\n",
 876     "    makeable_words = []\n",
 877     "    for w in unused_words:\n",
 878     "        unused_word_count = collections.Counter(w)\n",
 879     "        if all(unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
 880     "            makeable_words += [w]\n",
 881     "    lwm = sorted(makeable_words, key=len)[-1]\n",
 882     "    lwms = [w for w in makeable_words if len(w) == len(lwm)]\n",
 883     "    if show_anyway or len(set((len(lwp),len(lwa),len(lwm)))) == 3:\n",
 884     "        print('\\n{}'.format(fn))\n",
 885     "        print('{} words present'.format(len(words) - len(unused_words)))\n",
 886     "        print('Longest word present: {}, {} letters ({})'.format(lwp, len(lwp), lwps))\n",
 887     "        print('Longest word absent: {}, {} letters ({})'.format(lwa, len(lwa), lwas))\n",
 888     "        print('{} unused letters'.format(len([c for c in cat(cat(l) for l in g0) if c == '.'])))\n",
 889     "        print('Longest makeable word: {}, {} ({})'.format(lwm, len(lwm), lwms))"
 890    ]
 891   },
 892   {
 893    "cell_type": "code",
 894    "execution_count": 24,
 895    "metadata": {},
 896    "outputs": [
 897     {
 898      "name": "stdout",
 899      "output_type": "stream",
 900      "text": [
 901       "\n",
 902       "wordsearch04.txt\n",
 903       "58 words present\n",
 904       "Longest word present: fortification, 13 letters (['fortification'])\n",
 905       "Longest word absent: justification, 13 letters (['justification'])\n",
 906       "57 unused letters\n",
 907       "Longest makeable word: despairing, 10 (['despairing'])\n"
 908      ]
 909     }
 910    ],
 911    "source": [
 912     "do_wordsearch_tasks('wordsearch04.txt', show_anyway=True)"
 913    ]
 914   },
 915   {
 916    "cell_type": "code",
 917    "execution_count": 25,
 918    "metadata": {},
 919    "outputs": [
 920     {
 921      "name": "stdout",
 922      "output_type": "stream",
 923      "text": [
 924       "\n",
 925       "wordsearch08.txt\n",
 926       "62 words present\n",
 927       "Longest word present: compassionately, 15 letters (['compassionately'])\n",
 928       "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
 929       "65 unused letters\n",
 930       "Longest makeable word: vacationing, 11 (['vacationing'])\n"
 931      ]
 932     }
 933    ],
 934    "source": [
 935     "do_wordsearch_tasks('wordsearch08.txt')"
 936    ]
 937   },
 938   {
 939    "cell_type": "code",
 940    "execution_count": 26,
 941    "metadata": {
 942     "scrolled": true
 943    },
 944    "outputs": [
 945     {
 946      "name": "stdout",
 947      "output_type": "stream",
 948      "text": [
 949       "\n",
 950       "wordsearch08.txt\n",
 951       "62 words present\n",
 952       "Longest word present: compassionately, 15 letters (['compassionately'])\n",
 953       "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
 954       "65 unused letters\n",
 955       "Longest makeable word: vacationing, 11 (['vacationing'])\n",
 956       "\n",
 957       "wordsearch17.txt\n",
 958       "58 words present\n",
 959       "Longest word present: complementing, 13 letters (['complementing'])\n",
 960       "Longest word absent: upholstering, 12 letters (['domestically', 'upholstering'])\n",
 961       "56 unused letters\n",
 962       "Longest makeable word: plunderer, 9 (['plunderer'])\n",
 963       "\n",
 964       "wordsearch32.txt\n",
 965       "60 words present\n",
 966       "Longest word present: reciprocating, 13 letters (['reciprocating'])\n",
 967       "Longest word absent: parenthesise, 12 letters (['collectibles', 'frontrunners', 'parenthesise'])\n",
 968       "65 unused letters\n",
 969       "Longest makeable word: sultanas, 8 (['sultanas'])\n",
 970       "\n",
 971       "wordsearch52.txt\n",
 972       "51 words present\n",
 973       "Longest word present: prefabricated, 13 letters (['prefabricated'])\n",
 974       "Longest word absent: catastrophic, 12 letters (['capitalistic', 'catastrophic'])\n",
 975       "86 unused letters\n",
 976       "Longest makeable word: unimpressed, 11 (['bloodstream', 'brainstorms', 'reassembles', 'rhapsodises', 'synergistic', 'unimpressed'])\n",
 977       "\n",
 978       "wordsearch62.txt\n",
 979       "58 words present\n",
 980       "Longest word present: diametrically, 13 letters (['diametrically'])\n",
 981       "Longest word absent: streetlights, 12 letters (['harmonically', 'skyrocketing', 'streetlights'])\n",
 982       "59 unused letters\n",
 983       "Longest makeable word: tabernacle, 10 (['falterings', 'tabernacle'])\n",
 984       "\n",
 985       "wordsearch76.txt\n",
 986       "60 words present\n",
 987       "Longest word present: bloodthirstier, 14 letters (['bloodthirstier'])\n",
 988       "Longest word absent: incriminating, 13 letters (['incriminating'])\n",
 989       "59 unused letters\n",
 990       "Longest makeable word: stubbornly, 10 (['leafletted', 'stubbornly'])\n",
 991       "\n",
 992       "wordsearch94.txt\n",
 993       "59 words present\n",
 994       "Longest word present: unforgettable, 13 letters (['unforgettable'])\n",
 995       "Longest word absent: accommodated, 12 letters (['accommodated'])\n",
 996       "69 unused letters\n",
 997       "Longest makeable word: respectably, 11 (['predictions', 'respectably'])\n"
 998      ]
 999     }
1000    ],
1001    "source": [
1002     "for fn in sorted(os.listdir()):\n",
1003     "    if re.match('wordsearch\\d\\d\\.txt', fn):\n",
1004     "        do_wordsearch_tasks(fn)"
1005    ]
1006   },
1007   {
1008    "cell_type": "code",
1009    "execution_count": 27,
1010    "metadata": {
1011     "scrolled": true
1012    },
1013    "outputs": [
1014     {
1015      "name": "stdout",
1016      "output_type": "stream",
1017      "text": [
1018       "absolved (True, 16, 2, <Direction.right: 2>)\n",
1019       "adorable (True, 11, 4, <Direction.right: 2>)\n",
1020       "aeon (True, 11, 4, <Direction.down: 4>)\n",
1021       "alias (True, 15, 15, <Direction.left: 1>)\n",
1022       "ancestor (False, 0, 0, <Direction.left: 1>)\n",
1023       "baritone (False, 0, 0, <Direction.left: 1>)\n",
1024       "bemusing (False, 0, 0, <Direction.left: 1>)\n",
1025       "blonds (False, 0, 0, <Direction.left: 1>)\n",
1026       "bran (True, 1, 9, <Direction.left: 1>)\n",
1027       "calcite (True, 19, 9, <Direction.upright: 6>)\n",
1028       "candor (True, 17, 12, <Direction.right: 2>)\n",
1029       "conciseness (False, 0, 0, <Direction.left: 1>)\n",
1030       "consequent (False, 0, 0, <Direction.left: 1>)\n",
1031       "cuddle (False, 0, 0, <Direction.left: 1>)\n",
1032       "damming (True, 17, 2, <Direction.right: 2>)\n",
1033       "dashboards (False, 0, 0, <Direction.left: 1>)\n",
1034       "despairing (False, 0, 0, <Direction.left: 1>)\n",
1035       "dint (False, 0, 0, <Direction.left: 1>)\n",
1036       "dullard (True, 8, 2, <Direction.down: 4>)\n",
1037       "dynasty (True, 3, 4, <Direction.downright: 8>)\n",
1038       "employer (False, 0, 0, <Direction.left: 1>)\n",
1039       "exhorts (True, 0, 8, <Direction.left: 1>)\n",
1040       "feted (True, 5, 10, <Direction.right: 2>)\n",
1041       "fill (True, 9, 14, <Direction.upleft: 5>)\n",
1042       "flattens (True, 10, 10, <Direction.upleft: 5>)\n",
1043       "foghorn (True, 10, 11, <Direction.downright: 8>)\n",
1044       "fortification (True, 19, 16, <Direction.left: 1>)\n",
1045       "freakish (False, 0, 0, <Direction.left: 1>)\n",
1046       "frolics (True, 16, 16, <Direction.up: 3>)\n",
1047       "gall (False, 0, 0, <Direction.left: 1>)\n",
1048       "gees (True, 17, 0, <Direction.upright: 6>)\n",
1049       "genies (True, 5, 7, <Direction.upleft: 5>)\n",
1050       "gets (True, 6, 4, <Direction.upleft: 5>)\n",
1051       "hastening (True, 14, 13, <Direction.left: 1>)\n",
1052       "hits (True, 2, 0, <Direction.down: 4>)\n",
1053       "hopelessness (False, 0, 0, <Direction.left: 1>)\n",
1054       "hurlers (True, 18, 0, <Direction.right: 2>)\n",
1055       "impales (False, 0, 0, <Direction.left: 1>)\n",
1056       "infix (False, 0, 0, <Direction.left: 1>)\n",
1057       "inflow (False, 0, 0, <Direction.left: 1>)\n",
1058       "innumerable (False, 0, 0, <Direction.left: 1>)\n",
1059       "intentional (False, 0, 0, <Direction.left: 1>)\n",
1060       "jerkin (False, 0, 0, <Direction.left: 1>)\n",
1061       "justification (False, 0, 0, <Direction.left: 1>)\n",
1062       "kitty (True, 8, 15, <Direction.upleft: 5>)\n",
1063       "knuckles (True, 17, 19, <Direction.up: 3>)\n",
1064       "leaving (False, 0, 0, <Direction.left: 1>)\n",
1065       "like (True, 3, 11, <Direction.left: 1>)\n",
1066       "limitation (True, 8, 3, <Direction.right: 2>)\n",
1067       "locoweeds (False, 0, 0, <Direction.left: 1>)\n",
1068       "loot (True, 3, 19, <Direction.up: 3>)\n",
1069       "lucking (True, 7, 10, <Direction.upleft: 5>)\n",
1070       "lumps (True, 0, 17, <Direction.down: 4>)\n",
1071       "mercerising (True, 15, 17, <Direction.up: 3>)\n",
1072       "monickers (False, 0, 0, <Direction.left: 1>)\n",
1073       "motionless (True, 13, 1, <Direction.up: 3>)\n",
1074       "naturally (True, 9, 16, <Direction.up: 3>)\n",
1075       "nighest (True, 15, 4, <Direction.right: 2>)\n",
1076       "notion (True, 17, 18, <Direction.up: 3>)\n",
1077       "ogled (True, 1, 18, <Direction.down: 4>)\n",
1078       "originality (False, 0, 0, <Direction.left: 1>)\n",
1079       "outings (False, 0, 0, <Direction.left: 1>)\n",
1080       "pendulous (False, 0, 0, <Direction.left: 1>)\n",
1081       "piled (True, 1, 10, <Direction.right: 2>)\n",
1082       "pins (True, 7, 4, <Direction.upleft: 5>)\n",
1083       "pithier (False, 0, 0, <Direction.left: 1>)\n",
1084       "prep (True, 10, 4, <Direction.right: 2>)\n",
1085       "randomness (False, 0, 0, <Direction.left: 1>)\n",
1086       "rectors (False, 0, 0, <Direction.left: 1>)\n",
1087       "redrew (False, 0, 0, <Direction.left: 1>)\n",
1088       "reformulated (False, 0, 0, <Direction.left: 1>)\n",
1089       "remoteness (False, 0, 0, <Direction.left: 1>)\n",
1090       "retaking (True, 6, 0, <Direction.down: 4>)\n",
1091       "rethink (False, 0, 0, <Direction.left: 1>)\n",
1092       "rope (True, 9, 4, <Direction.right: 2>)\n",
1093       "rubier (True, 0, 4, <Direction.downright: 8>)\n",
1094       "sailors (True, 7, 15, <Direction.up: 3>)\n",
1095       "scowls (False, 0, 0, <Direction.left: 1>)\n",
1096       "scum (True, 16, 11, <Direction.right: 2>)\n",
1097       "sepals (True, 6, 10, <Direction.upright: 6>)\n",
1098       "sequencers (False, 0, 0, <Direction.left: 1>)\n",
1099       "serf (False, 0, 0, <Direction.left: 1>)\n",
1100       "shoaled (True, 11, 18, <Direction.up: 3>)\n",
1101       "shook (False, 0, 0, <Direction.left: 1>)\n",
1102       "sonic (True, 18, 18, <Direction.left: 1>)\n",
1103       "spottiest (False, 0, 0, <Direction.left: 1>)\n",
1104       "stag (True, 7, 8, <Direction.left: 1>)\n",
1105       "stood (False, 0, 0, <Direction.left: 1>)\n",
1106       "stratum (True, 2, 13, <Direction.left: 1>)\n",
1107       "strong (True, 4, 19, <Direction.down: 4>)\n",
1108       "studying (True, 0, 16, <Direction.left: 1>)\n",
1109       "surtaxing (False, 0, 0, <Direction.left: 1>)\n",
1110       "tailing (True, 13, 6, <Direction.right: 2>)\n",
1111       "tears (True, 13, 3, <Direction.up: 3>)\n",
1112       "teazles (True, 4, 10, <Direction.downright: 8>)\n",
1113       "vans (True, 18, 8, <Direction.upright: 6>)\n",
1114       "wardrobes (False, 0, 0, <Direction.left: 1>)\n",
1115       "wooded (True, 12, 5, <Direction.right: 2>)\n",
1116       "worsts (True, 1, 0, <Direction.downright: 8>)\n",
1117       "zings (True, 10, 14, <Direction.upleft: 5>)\n"
1118      ]
1119     }
1120    ],
1121    "source": [
1122     "width, height, grid, words = read_wordsearch('wordsearch04.txt')\n",
1123     "for w in words:\n",
1124     "    print(w, present(grid, w))"
1125    ]
1126   },
1127   {
1128    "cell_type": "markdown",
1129    "metadata": {},
1130    "source": [
1131     "## Example for question text"
1132    ]
1133   },
1134   {
1135    "cell_type": "code",
1136    "execution_count": 28,
1137    "metadata": {
1138     "collapsed": true
1139    },
1140    "outputs": [],
1141    "source": [
1142     "import copy\n",
1143     "grid =  [['.', '.', '.', 'p', '.', 'm', 'o', 'w', 'n', '.'], ['.', 's', 'd', 's', 'e', '.', '.', 'e', 'e', '.'], ['.', 'e', '.', 'e', 'l', 'a', 'd', '.', 'c', 'r'], ['p', 'i', '.', 'd', 't', 'i', 'r', '.', 'a', 'h'], ['r', 'z', 's', 'i', 'w', 'o', 'v', 's', 'p', 'u'], ['o', 'a', 'w', 'h', '.', 'k', 'i', 'e', 'a', 'b'], ['b', 'r', 'o', 'w', '.', 'c', '.', 'r', 'd', 'a'], ['e', 'c', 'n', 'o', 't', 'o', 'p', 's', '.', 'r'], ['d', '.', 'k', 'c', '.', 'd', '.', '.', '.', 'b'], ['.', 's', 't', 'a', 'p', 'l', 'e', '.', '.', '.']]\n",
1144     "padded_grid =  [['f', 'h', 'j', 'p', 'a', 'm', 'o', 'w', 'n', 'q'], ['w', 's', 'd', 's', 'e', 'u', 'q', 'e', 'e', 'v'], ['i', 'e', 'a', 'e', 'l', 'a', 'd', 'h', 'c', 'r'], ['p', 'i', 'e', 'd', 't', 'i', 'r', 'i', 'a', 'h'], ['r', 'z', 's', 'i', 'w', 'o', 'v', 's', 'p', 'u'], ['o', 'a', 'w', 'h', 'a', 'k', 'i', 'e', 'a', 'b'], ['b', 'r', 'o', 'w', 'p', 'c', 'f', 'r', 'd', 'a'], ['e', 'c', 'n', 'o', 't', 'o', 'p', 's', 's', 'r'], ['d', 'i', 'k', 'c', 'h', 'd', 'n', 'p', 'n', 'b'], ['b', 's', 't', 'a', 'p', 'l', 'e', 'o', 'k', 'r']]\n",
1145     "present_words =  ['probed', 'staple', 'rioted', 'cowhides', 'tops', 'knows', 'lived', 'rhubarb', 'crazies', 'dock', 'apace', 'mown', 'pears', 'wide']\n",
1146     "decoy_words =  ['fickler', 'adapting', 'chump', 'foaming', 'molested', 'carnal', 'crumbled', 'guts', 'minuend', 'bombing', 'winced', 'coccyxes', 'solaria', 'shinier', 'cackles']"
1147    ]
1148   },
1149   {
1150    "cell_type": "code",
1151    "execution_count": 29,
1152    "metadata": {},
1153    "outputs": [
1154     {
1155      "data": {
1156       "text/plain": [
1157        "'fickler, adapting, chump, foaming, molested, carnal, crumbled, guts, minuend, bombing, winced, coccyxes, solaria, shinier, cackles'"
1158       ]
1159      },
1160      "execution_count": 29,
1161      "metadata": {},
1162      "output_type": "execute_result"
1163     }
1164    ],
1165    "source": [
1166     "', '.join(decoy_words)"
1167    ]
1168   },
1169   {
1170    "cell_type": "code",
1171    "execution_count": 30,
1172    "metadata": {},
1173    "outputs": [
1174     {
1175      "data": {
1176       "text/plain": [
1177        "'adapting, apace, bombing, cackles, carnal, chump, coccyxes, cowhides, crazies, crumbled, dock, fickler, foaming, guts, knows, lived, minuend, molested, mown, pears, probed, rhubarb, rioted, shinier, solaria, staple, tops, wide, winced'"
1178       ]
1179      },
1180      "execution_count": 30,
1181      "metadata": {},
1182      "output_type": "execute_result"
1183     }
1184    ],
1185    "source": [
1186     "', '.join(sorted(present_words + decoy_words))"
1187    ]
1188   },
1189   {
1190    "cell_type": "code",
1191    "execution_count": 31,
1192    "metadata": {},
1193    "outputs": [
1194     {
1195      "name": "stdout",
1196      "output_type": "stream",
1197      "text": [
1198       "probed 3 0 6 Direction.down [(3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0)]\n",
1199       "staple 9 1 6 Direction.right [(9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)]\n",
1200       "rioted 6 7 6 Direction.upleft [(6, 7), (5, 6), (4, 5), (3, 4), (2, 3), (1, 2)]\n",
1201       "cowhides 8 3 8 Direction.up [(8, 3), (7, 3), (6, 3), (5, 3), (4, 3), (3, 3), (2, 3), (1, 3)]\n",
1202       "tops 7 4 4 Direction.right [(7, 4), (7, 5), (7, 6), (7, 7)]\n",
1203       "knows 8 2 5 Direction.up [(8, 2), (7, 2), (6, 2), (5, 2), (4, 2)]\n",
1204       "lived 2 4 5 Direction.downright [(2, 4), (3, 5), (4, 6), (5, 7), (6, 8)]\n",
1205       "rhubarb 2 9 7 Direction.down [(2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9)]\n",
1206       "crazies 7 1 7 Direction.up [(7, 1), (6, 1), (5, 1), (4, 1), (3, 1), (2, 1), (1, 1)]\n",
1207       "dock 8 5 4 Direction.up [(8, 5), (7, 5), (6, 5), (5, 5)]\n",
1208       "apace 5 8 5 Direction.up [(5, 8), (4, 8), (3, 8), (2, 8), (1, 8)]\n",
1209       "mown 0 5 4 Direction.right [(0, 5), (0, 6), (0, 7), (0, 8)]\n",
1210       "pears 0 3 5 Direction.downright [(0, 3), (1, 4), (2, 5), (3, 6), (4, 7)]\n",
1211       "wide 4 4 4 Direction.upright [(4, 4), (3, 5), (2, 6), (1, 7)]\n"
1212      ]
1213     },
1214     {
1215      "data": {
1216       "text/plain": [
1217        "[(7, 5), (2, 3), (3, 5)]"
1218       ]
1219      },
1220      "execution_count": 31,
1221      "metadata": {},
1222      "output_type": "execute_result"
1223     }
1224    ],
1225    "source": [
1226     "cts = collections.Counter()\n",
1227     "for w in present_words:\n",
1228     "    _, r, c, d = present(grid, w)\n",
1229     "    inds = indices(grid, r, c, len(w), d)\n",
1230     "    for i in inds:\n",
1231     "        cts[i] += 1\n",
1232     "    print(w, r, c, len(w), d, inds)\n",
1233     "[i for i in cts if cts[i] > 1]"
1234    ]
1235   },
1236   {
1237    "cell_type": "code",
1238    "execution_count": 32,
1239    "metadata": {},
1240    "outputs": [
1241     {
1242      "name": "stdout",
1243      "output_type": "stream",
1244      "text": [
1245       "\n",
1246       "example-wordsearch.txt\n",
1247       "14 words present\n",
1248       "Longest word present: cowhides, 8 letters (['cowhides'])\n",
1249       "Longest word absent: molested, 8 letters (['adapting', 'coccyxes', 'crumbled', 'molested'])\n",
1250       "27 unused letters\n",
1251       "Longest makeable word: shinier, 7 (['shinier'])\n"
1252      ]
1253     }
1254    ],
1255    "source": [
1256     "do_wordsearch_tasks('example-wordsearch.txt', show_anyway=True)"
1257    ]
1258   },
1259   {
1260    "cell_type": "code",
1261    "execution_count": 33,
1262    "metadata": {},
1263    "outputs": [
1264     {
1265      "name": "stdout",
1266      "output_type": "stream",
1267      "text": [
1268       "..........\n",
1269       "..........\n",
1270       "....l.....\n",
1271       ".....i....\n",
1272       "......v...\n",
1273       ".......e..\n",
1274       "........d.\n",
1275       "..........\n",
1276       "..........\n",
1277       "..........\n"
1278      ]
1279     }
1280    ],
1281    "source": [
1282     "g = empty_grid(10, 10)\n",
1283     "set_grid(g, 2, 4, Direction.downright, 'lived')\n",
1284     "print(show_grid(g))"
1285    ]
1286   },
1287   {
1288    "cell_type": "code",
1289    "execution_count": 34,
1290    "metadata": {},
1291    "outputs": [
1292     {
1293      "name": "stdout",
1294      "output_type": "stream",
1295      "text": [
1296       "..........\n",
1297       ".......e..\n",
1298       "....l.d...\n",
1299       ".....i....\n",
1300       "....w.v...\n",
1301       ".......e..\n",
1302       "........d.\n",
1303       "..........\n",
1304       "..........\n",
1305       ".staple...\n"
1306      ]
1307     }
1308    ],
1309    "source": [
1310     "g = empty_grid(10, 10)\n",
1311     "set_grid(g, 2, 4, Direction.downright, 'lived')\n",
1312     "set_grid(g, 4, 4, Direction.upright, 'wide')\n",
1313     "set_grid(g, 9, 1, Direction.right, 'staple')\n",
1314     "print(show_grid(g))"
1315    ]
1316   },
1317   {
1318    "cell_type": "code",
1319    "execution_count": 35,
1320    "metadata": {},
1321    "outputs": [
1322     {
1323      "name": "stdout",
1324      "output_type": "stream",
1325      "text": [
1326       "..........\n",
1327       "...s......\n",
1328       "...e......\n",
1329       "...d......\n",
1330       "...i......\n",
1331       "...h......\n",
1332       "...w......\n",
1333       "...o......\n",
1334       "...c......\n",
1335       "..........\n"
1336      ]
1337     }
1338    ],
1339    "source": [
1340     "g = empty_grid(10, 10)\n",
1341     "set_grid(g, 8, 3, Direction.up, 'cowhides')\n",
1342     "print(show_grid(g))"
1343    ]
1344   },
1345   {
1346    "cell_type": "code",
1347    "execution_count": 36,
1348    "metadata": {},
1349    "outputs": [
1350     {
1351      "name": "stdout",
1352      "output_type": "stream",
1353      "text": [
1354       "..........\n",
1355       "..........\n",
1356       "..........\n",
1357       "..........\n",
1358       "..........\n",
1359       "..........\n",
1360       "brow......\n",
1361       "..........\n",
1362       "..........\n",
1363       "..........\n"
1364      ]
1365     }
1366    ],
1367    "source": [
1368     "# Example of word in grid that is English but isn't in the words listed in the puzzle.\n",
1369     "g = empty_grid(10, 10)\n",
1370     "set_grid(g, 6, 0, Direction.right, 'brow')\n",
1371     "print(show_grid(g))"
1372    ]
1373   },
1374   {
1375    "cell_type": "code",
1376    "execution_count": 42,
1377    "metadata": {},
1378    "outputs": [
1379     {
1380      "name": "stdout",
1381      "output_type": "stream",
1382      "text": [
1383       "fhj.a....q\n",
1384       "w....uq..v\n",
1385       "i.a....h..\n",
1386       "..e....i..\n",
1387       "..........\n",
1388       "....a.....\n",
1389       "....p.f...\n",
1390       "........s.\n",
1391       ".i..h.npn.\n",
1392       "b......okr\n"
1393      ]
1394     },
1395     {
1396      "data": {
1397       "text/plain": [
1398        "'aaabeffhhhiiijknnoppqqrsuvw'"
1399       ]
1400      },
1401      "execution_count": 42,
1402      "metadata": {},
1403      "output_type": "execute_result"
1404     }
1405    ],
1406    "source": [
1407     "unused_grid = copy.deepcopy(padded_grid)\n",
1408     "for w in present_words:\n",
1409     "    _, r, c, d = present(grid, w)\n",
1410     "    set_grid(unused_grid, r, c, d, '.' * len(w))\n",
1411     "print(show_grid(unused_grid))\n",
1412     "cat(sorted(c for l in unused_grid for c in l if c in string.ascii_letters))"
1413    ]
1414   },
1415   {
1416    "cell_type": "code",
1417    "execution_count": null,
1418    "metadata": {
1419     "collapsed": true
1420    },
1421    "outputs": [],
1422    "source": []
1423   }
1424  ],
1425  "metadata": {
1426   "kernelspec": {
1427    "display_name": "Python 3",
1428    "language": "python",
1429    "name": "python3"
1430   },
1431   "language_info": {
1432    "codemirror_mode": {
1433     "name": "ipython",
1434     "version": 3
1435    },
1436    "file_extension": ".py",
1437    "mimetype": "text/x-python",
1438    "name": "python",
1439    "nbconvert_exporter": "python",
1440    "pygments_lexer": "ipython3",
1441    "version": "3.5.2+"
1442   }
1443  },
1444  "nbformat": 4,
1445  "nbformat_minor": 1
1446 }