04-wordsearch/wordsearch-creation.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 65,
   6    "metadata": {
   7     "collapsed": false
   8    },
   9    "outputs": [],
  10    "source": [
  11     "import string\n",
  12     "import re\n",
  13     "import random\n",
  14     "import collections\n",
  15     "import copy\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": 66,
  33    "metadata": {
  34     "collapsed": false
  35    },
  36    "outputs": [],
  37    "source": [
  38     "# all_words = [w.strip() for w in open('/usr/share/dict/british-english').readlines()\n",
  39     "#             if all(c in string.ascii_lowercase for c in w.strip())]\n",
  40     "# words = [w for w in all_words\n",
  41     "#          if not any(w in w2 for w2 in all_words if w != w2)]\n",
  42     "# open('wordsearch-words', 'w').write(lcat(words))"
  43    ]
  44   },
  45   {
  46    "cell_type": "code",
  47    "execution_count": 67,
  48    "metadata": {
  49     "collapsed": false
  50    },
  51    "outputs": [],
  52    "source": [
  53     "# ws_words = [w.strip() for w in open('wordsearch-words').readlines()\n",
  54     "#             if all(c in string.ascii_lowercase for c in w.strip())]\n",
  55     "# ws_words[:10]"
  56    ]
  57   },
  58   {
  59    "cell_type": "code",
  60    "execution_count": 68,
  61    "metadata": {
  62     "collapsed": true
  63    },
  64    "outputs": [],
  65    "source": [
  66     "ws_words = [w.strip() for w in open('/usr/share/dict/british-english').readlines()\n",
  67     "            if all(c in string.ascii_lowercase for c in w.strip())]"
  68    ]
  69   },
  70   {
  71    "cell_type": "code",
  72    "execution_count": 69,
  73    "metadata": {
  74     "collapsed": true
  75    },
  76    "outputs": [],
  77    "source": [
  78     "def empty_grid(w, h):\n",
  79     "    return [['.' for c in range(w)] for r in range(h)]"
  80    ]
  81   },
  82   {
  83    "cell_type": "code",
  84    "execution_count": 70,
  85    "metadata": {
  86     "collapsed": true
  87    },
  88    "outputs": [],
  89    "source": [
  90     "def show_grid(grid):\n",
  91     "    return lcat(cat(r) for r in grid)"
  92    ]
  93   },
  94   {
  95    "cell_type": "code",
  96    "execution_count": 71,
  97    "metadata": {
  98     "collapsed": false
  99    },
 100    "outputs": [
 101     {
 102      "name": "stdout",
 103      "output_type": "stream",
 104      "text": [
 105       "..........\n",
 106       "..........\n",
 107       "..........\n",
 108       "..........\n",
 109       "..........\n",
 110       "..........\n",
 111       "..........\n",
 112       "..........\n",
 113       "..........\n",
 114       "..........\n"
 115      ]
 116     }
 117    ],
 118    "source": [
 119     "grid = empty_grid(10, 10)\n",
 120     "print(show_grid(grid))"
 121    ]
 122   },
 123   {
 124    "cell_type": "code",
 125    "execution_count": 72,
 126    "metadata": {
 127     "collapsed": true
 128    },
 129    "outputs": [],
 130    "source": [
 131     "def indices(grid, r, c, l, d):\n",
 132     "    dr, dc = delta[d]\n",
 133     "    w = len(grid[0])\n",
 134     "    h = len(grid)\n",
 135     "    inds = [(r + i * dr, c + i * dc) for i in range(l)]\n",
 136     "    return [(i, j) for i, j in inds\n",
 137     "           if i >= 0\n",
 138     "           if j >= 0\n",
 139     "           if i < h\n",
 140     "           if j < w]"
 141    ]
 142   },
 143   {
 144    "cell_type": "code",
 145    "execution_count": 73,
 146    "metadata": {
 147     "collapsed": true
 148    },
 149    "outputs": [],
 150    "source": [
 151     "def gslice(grid, r, c, l, d):\n",
 152     "    return [grid[i][j] for i, j in indices(grid, r, c, l, d)]"
 153    ]
 154   },
 155   {
 156    "cell_type": "code",
 157    "execution_count": 74,
 158    "metadata": {
 159     "collapsed": true
 160    },
 161    "outputs": [],
 162    "source": [
 163     "def set_grid(grid, r, c, d, word):\n",
 164     "    for (i, j), l in zip(indices(grid, r, c, len(word), d), word):\n",
 165     "        grid[i][j] = l\n",
 166     "    return grid"
 167    ]
 168   },
 169   {
 170    "cell_type": "code",
 171    "execution_count": 75,
 172    "metadata": {
 173     "collapsed": false
 174    },
 175    "outputs": [
 176     {
 177      "name": "stdout",
 178      "output_type": "stream",
 179      "text": [
 180       "..........\n",
 181       "..........\n",
 182       "...t......\n",
 183       "....e.....\n",
 184       ".....s....\n",
 185       "......t...\n",
 186       ".......w..\n",
 187       "........o.\n",
 188       ".........r\n",
 189       "..........\n"
 190      ]
 191     }
 192    ],
 193    "source": [
 194     "set_grid(grid, 2, 3, Direction.downright, 'testword')\n",
 195     "print(show_grid(grid))"
 196    ]
 197   },
 198   {
 199    "cell_type": "code",
 200    "execution_count": 76,
 201    "metadata": {
 202     "collapsed": false
 203    },
 204    "outputs": [
 205     {
 206      "data": {
 207       "text/plain": [
 208        "'..e.....'"
 209       ]
 210      },
 211      "execution_count": 76,
 212      "metadata": {},
 213      "output_type": "execute_result"
 214     }
 215    ],
 216    "source": [
 217     "cat(gslice(grid, 3, 2, 15, Direction.right))"
 218    ]
 219   },
 220   {
 221    "cell_type": "code",
 222    "execution_count": 77,
 223    "metadata": {
 224     "collapsed": false
 225    },
 226    "outputs": [
 227     {
 228      "data": {
 229       "text/plain": [
 230        "<_sre.SRE_Match object; span=(0, 4), match='keen'>"
 231       ]
 232      },
 233      "execution_count": 77,
 234      "metadata": {},
 235      "output_type": "execute_result"
 236     }
 237    ],
 238    "source": [
 239     "re.match(cat(gslice(grid, 3, 2, 4, Direction.right)), 'keen')"
 240    ]
 241   },
 242   {
 243    "cell_type": "code",
 244    "execution_count": 78,
 245    "metadata": {
 246     "collapsed": false
 247    },
 248    "outputs": [
 249     {
 250      "data": {
 251       "text/plain": [
 252        "<_sre.SRE_Match object; span=(0, 3), match='kee'>"
 253       ]
 254      },
 255      "execution_count": 78,
 256      "metadata": {},
 257      "output_type": "execute_result"
 258     }
 259    ],
 260    "source": [
 261     "re.match(cat(gslice(grid, 3, 2, 3, Direction.right)), 'keen')"
 262    ]
 263   },
 264   {
 265    "cell_type": "code",
 266    "execution_count": 79,
 267    "metadata": {
 268     "collapsed": false
 269    },
 270    "outputs": [],
 271    "source": [
 272     "re.fullmatch(cat(gslice(grid, 3, 2, 3, Direction.right)), 'keen')"
 273    ]
 274   },
 275   {
 276    "cell_type": "code",
 277    "execution_count": 80,
 278    "metadata": {
 279     "collapsed": true
 280    },
 281    "outputs": [],
 282    "source": [
 283     "re.match(cat(gslice(grid, 3, 2, 4, Direction.right)), 'kine')"
 284    ]
 285   },
 286   {
 287    "cell_type": "code",
 288    "execution_count": 81,
 289    "metadata": {
 290     "collapsed": true
 291    },
 292    "outputs": [],
 293    "source": [
 294     "def could_add(grid, r, c, d, word):\n",
 295     "    s = gslice(grid, r, c, len(word), d)\n",
 296     "    return re.fullmatch(cat(s), word)"
 297    ]
 298   },
 299   {
 300    "cell_type": "code",
 301    "execution_count": 82,
 302    "metadata": {
 303     "collapsed": false
 304    },
 305    "outputs": [
 306     {
 307      "data": {
 308       "text/plain": [
 309        "<_sre.SRE_Match object; span=(0, 4), match='keen'>"
 310       ]
 311      },
 312      "execution_count": 82,
 313      "metadata": {},
 314      "output_type": "execute_result"
 315     }
 316    ],
 317    "source": [
 318     "could_add(grid, 3, 2, Direction.right, 'keen')"
 319    ]
 320   },
 321   {
 322    "cell_type": "code",
 323    "execution_count": 83,
 324    "metadata": {
 325     "collapsed": false
 326    },
 327    "outputs": [],
 328    "source": [
 329     "could_add(grid, 3, 2, Direction.right, 'kine')"
 330    ]
 331   },
 332   {
 333    "cell_type": "code",
 334    "execution_count": 84,
 335    "metadata": {
 336     "collapsed": false
 337    },
 338    "outputs": [
 339     {
 340      "data": {
 341       "text/plain": [
 342        "<Direction.downleft: 7>"
 343       ]
 344      },
 345      "execution_count": 84,
 346      "metadata": {},
 347      "output_type": "execute_result"
 348     }
 349    ],
 350    "source": [
 351     "random.choice(list(Direction))"
 352    ]
 353   },
 354   {
 355    "cell_type": "code",
 356    "execution_count": 129,
 357    "metadata": {
 358     "collapsed": true
 359    },
 360    "outputs": [],
 361    "source": [
 362     "def fill_grid(grid, words, word_count, max_attempts=10000):\n",
 363     "    attempts = 0\n",
 364     "    added_words = []\n",
 365     "    w = len(grid[0])\n",
 366     "    h = len(grid)\n",
 367     "    while len(added_words) < word_count and attempts < max_attempts:\n",
 368     "        attempts += 1\n",
 369     "        r = random.randrange(w)\n",
 370     "        c = random.randrange(h)\n",
 371     "        word = random.choice(words)\n",
 372     "        d = random.choice(list(Direction))\n",
 373     "        if len(word) >=4 and not any(word in w2 for w2 in added_words) and could_add(grid, r, c, d, word):\n",
 374     "            set_grid(grid, r, c, d, word)\n",
 375     "            added_words += [word]\n",
 376     "            attempts = 0\n",
 377     "    return grid, added_words"
 378    ]
 379   },
 380   {
 381    "cell_type": "code",
 382    "execution_count": 86,
 383    "metadata": {
 384     "collapsed": false
 385    },
 386    "outputs": [
 387     {
 388      "data": {
 389       "text/plain": [
 390        "40"
 391       ]
 392      },
 393      "execution_count": 86,
 394      "metadata": {},
 395      "output_type": "execute_result"
 396     }
 397    ],
 398    "source": [
 399     "g = empty_grid(20, 20)\n",
 400     "g, ws = fill_grid(g, ws_words, 40)\n",
 401     "len(ws)"
 402    ]
 403   },
 404   {
 405    "cell_type": "code",
 406    "execution_count": 87,
 407    "metadata": {
 408     "collapsed": false
 409    },
 410    "outputs": [
 411     {
 412      "name": "stdout",
 413      "output_type": "stream",
 414      "text": [
 415       "l.fiestasrsnorffas..\n",
 416       "a....s..e.a.cawing..\n",
 417       "c..gt.dv.re.strongly\n",
 418       "i..n..aecmbp....y...\n",
 419       "m.eo.uthzoa.of..l.s.\n",
 420       "od.lq.esozslhhlyo.k.\n",
 421       "ns.e.r.se.ureanoh.r.\n",
 422       "o.wby.t.aw.foin.u.u.\n",
 423       "ca.o....i.a.to.d.rms\n",
 424       "en..l...lerrs.d.i.sk\n",
 425       "no...l..i.snalgarn.n\n",
 426       "un....a.crappiest.gi\n",
 427       ".y.....mdepraved..dw\n",
 428       ".mgniggolricochet.ey\n",
 429       ".o..pensivelyibmozil\n",
 430       ".u.......curd.....fd\n",
 431       ".sseitudlevehsid..id\n",
 432       "...litchis..romut.ri\n",
 433       ".understands......et\n",
 434       "....nagilooh......v.\n",
 435       "40 words added\n",
 436       "understands crappiest archery mallows depraved cawing rawest curd tiny tiddlywinks fiestas zombi duties ricochet uneconomical hope litchis strongly verified logging handing anonymous quaver flours boost holy saffrons errs hooligan male belong tumor dishevel fuzzed raglans pensively murks dents cilia doors\n"
 437      ]
 438     }
 439    ],
 440    "source": [
 441     "print(show_grid(g))\n",
 442     "print(len(ws), 'words added')\n",
 443     "print(wcat(ws))"
 444    ]
 445   },
 446   {
 447    "cell_type": "code",
 448    "execution_count": 88,
 449    "metadata": {
 450     "collapsed": true
 451    },
 452    "outputs": [],
 453    "source": [
 454     "def present(grid, word):\n",
 455     "    w = len(grid[0])\n",
 456     "    h = len(grid)\n",
 457     "    for r in range(h):\n",
 458     "        for c in range(w):\n",
 459     "            for d in Direction:\n",
 460     "                if cat(gslice(grid, r, c, len(word), d)) == word:\n",
 461     "                    return True, r, c, d\n",
 462     "    return False, 0, 0, list(Direction)[0]"
 463    ]
 464   },
 465   {
 466    "cell_type": "code",
 467    "execution_count": 89,
 468    "metadata": {
 469     "collapsed": false,
 470     "scrolled": true
 471    },
 472    "outputs": [
 473     {
 474      "name": "stdout",
 475      "output_type": "stream",
 476      "text": [
 477       "understands (True, 18, 1, <Direction.right: 2>)\n",
 478       "crappiest (True, 11, 8, <Direction.right: 2>)\n",
 479       "archery (True, 1, 10, <Direction.downleft: 7>)\n",
 480       "mallows (True, 12, 7, <Direction.upleft: 5>)\n",
 481       "depraved (True, 12, 8, <Direction.right: 2>)\n",
 482       "cawing (True, 1, 12, <Direction.right: 2>)\n",
 483       "rawest (True, 9, 11, <Direction.upleft: 5>)\n",
 484       "curd (True, 15, 9, <Direction.right: 2>)\n",
 485       "tiny (True, 8, 12, <Direction.upright: 6>)\n",
 486       "tiddlywinks (True, 18, 19, <Direction.up: 3>)\n",
 487       "fiestas (True, 0, 2, <Direction.right: 2>)\n",
 488       "zombi (True, 14, 17, <Direction.left: 1>)\n",
 489       "duties (True, 16, 7, <Direction.left: 1>)\n",
 490       "ricochet (True, 13, 9, <Direction.right: 2>)\n",
 491       "uneconomical (True, 11, 0, <Direction.up: 3>)\n",
 492       "hope (True, 5, 13, <Direction.upleft: 5>)\n",
 493       "litchis (True, 17, 3, <Direction.right: 2>)\n",
 494       "strongly (True, 2, 12, <Direction.right: 2>)\n",
 495       "verified (True, 19, 18, <Direction.up: 3>)\n",
 496       "logging (True, 13, 8, <Direction.left: 1>)\n",
 497       "handing (True, 5, 12, <Direction.downright: 8>)\n",
 498       "anonymous (True, 8, 1, <Direction.down: 4>)\n",
 499       "quaver (True, 5, 4, <Direction.upright: 6>)\n",
 500       "flours (True, 4, 13, <Direction.downright: 8>)\n",
 501       "boost (True, 3, 10, <Direction.downleft: 7>)\n",
 502       "holy (True, 6, 16, <Direction.up: 3>)\n",
 503       "saffrons (True, 0, 17, <Direction.left: 1>)\n",
 504       "errs (True, 9, 9, <Direction.right: 2>)\n",
 505       "hooligan (True, 19, 11, <Direction.left: 1>)\n",
 506       "male (True, 3, 9, <Direction.downright: 8>)\n",
 507       "belong (True, 7, 3, <Direction.up: 3>)\n",
 508       "tumor (True, 17, 16, <Direction.left: 1>)\n",
 509       "dishevel (True, 16, 15, <Direction.left: 1>)\n",
 510       "fuzzed (True, 7, 11, <Direction.upleft: 5>)\n",
 511       "raglans (True, 10, 16, <Direction.left: 1>)\n",
 512       "pensively (True, 14, 4, <Direction.right: 2>)\n",
 513       "murks (True, 8, 18, <Direction.up: 3>)\n",
 514       "dents (True, 5, 1, <Direction.upright: 6>)\n",
 515       "cilia (True, 11, 8, <Direction.up: 3>)\n",
 516       "doors (True, 9, 14, <Direction.upleft: 5>)\n"
 517      ]
 518     }
 519    ],
 520    "source": [
 521     "for w in ws:\n",
 522     "    print(w, present(g, w))"
 523    ]
 524   },
 525   {
 526    "cell_type": "code",
 527    "execution_count": 125,
 528    "metadata": {
 529     "collapsed": true
 530    },
 531    "outputs": [],
 532    "source": [
 533     "def interesting(grid, words):\n",
 534     "    dirs = set(present(grid, w)[3] for w in words)\n",
 535     "    return len(words) > 40 and len(dirs) + 1 >= len(delta)"
 536    ]
 537   },
 538   {
 539    "cell_type": "code",
 540    "execution_count": 126,
 541    "metadata": {
 542     "collapsed": false
 543    },
 544    "outputs": [
 545     {
 546      "data": {
 547       "text/plain": [
 548        "False"
 549       ]
 550      },
 551      "execution_count": 126,
 552      "metadata": {},
 553      "output_type": "execute_result"
 554     }
 555    ],
 556    "source": [
 557     "interesting(g, ws)"
 558    ]
 559   },
 560   {
 561    "cell_type": "code",
 562    "execution_count": 131,
 563    "metadata": {
 564     "collapsed": true
 565    },
 566    "outputs": [],
 567    "source": [
 568     "def interesting_grid():\n",
 569     "    boring = True\n",
 570     "    while boring:\n",
 571     "        grid = empty_grid(20, 20)\n",
 572     "        grid, words = fill_grid(grid, ws_words, 80)\n",
 573     "        boring = not interesting(grid, words)\n",
 574     "    return grid, words"
 575    ]
 576   },
 577   {
 578    "cell_type": "code",
 579    "execution_count": 132,
 580    "metadata": {
 581     "collapsed": false
 582    },
 583    "outputs": [
 584     {
 585      "name": "stdout",
 586      "output_type": "stream",
 587      "text": [
 588       "....gnixof...keem...\n",
 589       "feihc.spollawvase..s\n",
 590       "p.h.shs..snetsafnun.\n",
 591       "aeiy.adt..plehdowned\n",
 592       "rmcfmzhennaturali.h.\n",
 593       "abkake.pteebyelawsay\n",
 594       "dlcweln.lnmvrdrawllr\n",
 595       "ealnes.s.aeeieslaroe\n",
 596       ".zaelreffidclwl...gs\n",
 597       ".omtisadeelbst.bg.ei\n",
 598       ".noantr...tunet.o.nm\n",
 599       "serigamchamoixbemnsb\n",
 600       "sd.tnuu..lleterls..e\n",
 601       "e.dounf..dekcalsu..s\n",
 602       "gyegtcfknobetatser.t\n",
 603       "rlkeshskcelf..ploptr\n",
 604       "alon.l..sriahdawnsgi\n",
 605       "lac..y..gnittilps.od\n",
 606       ".eyeball..denedragse\n",
 607       ".r..ygnamsecstirg.hs\n",
 608       "57 words added;  7 directions\n",
 609       "chamoix staunchly keeling wive inns restate settlements byelaws blurt help foxing flecks orals differ unfastens mangy hymens wallops negotiate bestrides largess dawns nobler chief eyeball splitting bleed halogens clamor parade emblazoned hairs meek earmuff slacked retell scented gardened natural grits misery drawl gosh smog stung coked knob tune really secs plop alphas vase downed hazels hick fawn\n"
 610      ]
 611     }
 612    ],
 613    "source": [
 614     "g, ws = interesting_grid()\n",
 615     "print(show_grid(g))\n",
 616     "print(len(ws), 'words added; ', len(set(present(g, w)[3] for w in ws)), 'directions')\n",
 617     "print(wcat(ws))"
 618    ]
 619   },
 620   {
 621    "cell_type": "code",
 622    "execution_count": 94,
 623    "metadata": {
 624     "collapsed": true
 625    },
 626    "outputs": [],
 627    "source": [
 628     "def datafile(name, sep='\\t'):\n",
 629     "    \"\"\"Read key,value pairs from file.\n",
 630     "    \"\"\"\n",
 631     "    with open(name) as f:\n",
 632     "        for line in f:\n",
 633     "            splits = line.split(sep)\n",
 634     "            yield [splits[0], int(splits[1])]"
 635    ]
 636   },
 637   {
 638    "cell_type": "code",
 639    "execution_count": 95,
 640    "metadata": {
 641     "collapsed": true
 642    },
 643    "outputs": [],
 644    "source": [
 645     "def normalise(frequencies):\n",
 646     "    \"\"\"Scale a set of frequencies so they sum to one\n",
 647     "    \n",
 648     "    >>> sorted(normalise({1: 1, 2: 0}).items())\n",
 649     "    [(1, 1.0), (2, 0.0)]\n",
 650     "    >>> sorted(normalise({1: 1, 2: 1}).items())\n",
 651     "    [(1, 0.5), (2, 0.5)]\n",
 652     "    >>> sorted(normalise({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS\n",
 653     "    [(1, 0.333...), (2, 0.333...), (3, 0.333...)]\n",
 654     "    >>> sorted(normalise({1: 1, 2: 2, 3: 1}).items())\n",
 655     "    [(1, 0.25), (2, 0.5), (3, 0.25)]\n",
 656     "    \"\"\"\n",
 657     "    length = sum(f for f in frequencies.values())\n",
 658     "    return collections.defaultdict(int, ((k, v / length) \n",
 659     "        for (k, v) in frequencies.items()))\n"
 660    ]
 661   },
 662   {
 663    "cell_type": "code",
 664    "execution_count": 96,
 665    "metadata": {
 666     "collapsed": false
 667    },
 668    "outputs": [],
 669    "source": [
 670     "english_counts = collections.Counter(dict(datafile('count_1l.txt')))\n",
 671     "normalised_english_counts = normalise(english_counts)"
 672    ]
 673   },
 674   {
 675    "cell_type": "code",
 676    "execution_count": 97,
 677    "metadata": {
 678     "collapsed": false
 679    },
 680    "outputs": [],
 681    "source": [
 682     "wordsearch_counts = collections.Counter(cat(ws_words))\n",
 683     "normalised_wordsearch_counts = normalise(wordsearch_counts)"
 684    ]
 685   },
 686   {
 687    "cell_type": "code",
 688    "execution_count": 118,
 689    "metadata": {
 690     "collapsed": false
 691    },
 692    "outputs": [],
 693    "source": [
 694     "normalised_wordsearch_counts = normalise(collections.Counter(normalised_wordsearch_counts) + collections.Counter({l: 0.05 for l in string.ascii_lowercase}))"
 695    ]
 696   },
 697   {
 698    "cell_type": "code",
 699    "execution_count": 98,
 700    "metadata": {
 701     "collapsed": true
 702    },
 703    "outputs": [],
 704    "source": [
 705     "def weighted_choice(d):\n",
 706     "    \"\"\"Generate random item from a dictionary of item counts\n",
 707     "    \"\"\"\n",
 708     "    target = random.uniform(0, sum(d.values()))\n",
 709     "    cuml = 0.0\n",
 710     "    for (l, p) in d.items():\n",
 711     "        cuml += p\n",
 712     "        if cuml > target:\n",
 713     "            return l\n",
 714     "    return None\n",
 715     "\n",
 716     "def random_english_letter():\n",
 717     "    \"\"\"Generate a random letter based on English letter counts\n",
 718     "    \"\"\"\n",
 719     "    return weighted_choice(normalised_english_counts)\n",
 720     "\n",
 721     "def random_wordsearch_letter():\n",
 722     "    \"\"\"Generate a random letter based on wordsearch letter counts\n",
 723     "    \"\"\"\n",
 724     "    return weighted_choice(normalised_wordsearch_counts)"
 725    ]
 726   },
 727   {
 728    "cell_type": "code",
 729    "execution_count": 99,
 730    "metadata": {
 731     "collapsed": false
 732    },
 733    "outputs": [
 734     {
 735      "data": {
 736       "text/plain": [
 737        "'aaaaaaaaaabcdddeeeeeeeeeeeefffffgghhhhhhhhhiiiiiiikllmnnnnnnnooooooooprrrrssssssssssssttttttuuvwwwww'"
 738       ]
 739      },
 740      "execution_count": 99,
 741      "metadata": {},
 742      "output_type": "execute_result"
 743     }
 744    ],
 745    "source": [
 746     "cat(sorted(random_english_letter() for i in range(100)))"
 747    ]
 748   },
 749   {
 750    "cell_type": "code",
 751    "execution_count": 100,
 752    "metadata": {
 753     "collapsed": false
 754    },
 755    "outputs": [
 756     {
 757      "data": {
 758       "text/plain": [
 759        "'aaaaaaccccdddeeeeeeeeeeeeeeeeeeeffgghhiiiiikkklllmmmnnnnnnooooooppprrrrrrrrssssssssttttttuuuuuuvwyyy'"
 760       ]
 761      },
 762      "execution_count": 100,
 763      "metadata": {},
 764      "output_type": "execute_result"
 765     }
 766    ],
 767    "source": [
 768     "cat(sorted(random_wordsearch_letter() for i in range(100)))"
 769    ]
 770   },
 771   {
 772    "cell_type": "code",
 773    "execution_count": 101,
 774    "metadata": {
 775     "collapsed": false
 776    },
 777    "outputs": [
 778     {
 779      "data": {
 780       "text/plain": [
 781        "'e'"
 782       ]
 783      },
 784      "execution_count": 101,
 785      "metadata": {},
 786      "output_type": "execute_result"
 787     }
 788    ],
 789    "source": [
 790     "random_wordsearch_letter()"
 791    ]
 792   },
 793   {
 794    "cell_type": "code",
 795    "execution_count": 102,
 796    "metadata": {
 797     "collapsed": true
 798    },
 799    "outputs": [],
 800    "source": [
 801     "def pad_grid(g0):\n",
 802     "    grid = copy.deepcopy(g0)\n",
 803     "    w = len(grid[0])\n",
 804     "    h = len(grid)\n",
 805     "    for r in range(h):\n",
 806     "        for c in range(w):\n",
 807     "            if grid[r][c] == '.':\n",
 808     "                grid[r][c] = random_wordsearch_letter()\n",
 809     "    return grid"
 810    ]
 811   },
 812   {
 813    "cell_type": "code",
 814    "execution_count": 103,
 815    "metadata": {
 816     "collapsed": false
 817    },
 818    "outputs": [
 819     {
 820      "name": "stdout",
 821      "output_type": "stream",
 822      "text": [
 823       "nwtautoimmuneeyinsdl\n",
 824       "majorlyerasescmcider\n",
 825       "edthrallednxlcawoeaa\n",
 826       "gnizeensbnahwwgpsksr\n",
 827       "rmisrksiosgiitndtaep\n",
 828       "rioigoeopeglbnegsesu\n",
 829       "esurnrbdifecihtniust\n",
 830       "eeauuieimddlgiiigqan\n",
 831       "srcplooscrlufestosve\n",
 832       "pdcasmhemaonrgialcel\n",
 833       "lguvrepkcrekennronru\n",
 834       "ensesmtiesrtiogocwcr\n",
 835       "niadpnetulasgpdfeesi\n",
 836       "dgthgreoonavhsorinyv\n",
 837       "inilpehmnrnntuaeeoae\n",
 838       "dioesnmnocstennpolcm\n",
 839       "etniwvredwtidnmfdshm\n",
 840       "sgsoaarunyyoslurstts\n",
 841       "tetoyisimdmaderetlaf\n",
 842       "ettflightasnlclquasi\n"
 843      ]
 844     }
 845    ],
 846    "source": [
 847     "padded = pad_grid(g)\n",
 848     "print(show_grid(padded))"
 849    ]
 850   },
 851   {
 852    "cell_type": "code",
 853    "execution_count": 104,
 854    "metadata": {
 855     "collapsed": false
 856    },
 857    "outputs": [
 858     {
 859      "name": "stdout",
 860      "output_type": "stream",
 861      "text": [
 862       "...autoimmune.......\n",
 863       "majorlyerases.m..d..\n",
 864       "..thralledn...a..e..\n",
 865       "gnizeens..a..wg.sk..\n",
 866       ".m.s..si..g.i.ndtae.\n",
 867       ".i.ig.eo..gl..egses.\n",
 868       ".s.rnrbd..ec.htniust\n",
 869       ".eauuiei.ddlg.iigqan\n",
 870       "srcploos..lufestosve\n",
 871       "p.casmhe.aonrgial.el\n",
 872       "lguv.ep.crekennro.ru\n",
 873       "ense.m.i.s..iogoc.cr\n",
 874       "niad.netulasgp.fee.i\n",
 875       "dgt..reo....hs.r.nyv\n",
 876       "ini..ehm....t.ae.oa.\n",
 877       "dio..nm.o...en.p.lc.\n",
 878       "etn.w..e.w..d.....h.\n",
 879       "s.so....n.yoslurs.t.\n",
 880       "t.t......dmaderetlaf\n",
 881       "...flight.s.l..quasi\n"
 882      ]
 883     }
 884    ],
 885    "source": [
 886     "print(show_grid(g))"
 887    ]
 888   },
 889   {
 890    "cell_type": "code",
 891    "execution_count": 105,
 892    "metadata": {
 893     "collapsed": false,
 894     "scrolled": true
 895    },
 896    "outputs": [
 897     {
 898      "name": "stdout",
 899      "output_type": "stream",
 900      "text": [
 901       "thralled (True, 2, 2, <Direction.right: 2>)\n",
 902       "slung (True, 9, 4, <Direction.up: 3>)\n",
 903       "freighted (True, 8, 12, <Direction.down: 4>)\n",
 904       "townhouse (True, 18, 2, <Direction.upright: 6>)\n",
 905       "salute (True, 12, 11, <Direction.left: 1>)\n",
 906       "phoebes (True, 10, 6, <Direction.up: 3>)\n",
 907       "faltered (True, 18, 19, <Direction.left: 1>)\n",
 908       "laywomen (True, 19, 12, <Direction.upleft: 5>)\n",
 909       "squeaked (True, 8, 17, <Direction.up: 3>)\n",
 910       "perforating (True, 15, 15, <Direction.up: 3>)\n",
 911       "iodise (True, 4, 7, <Direction.down: 4>)\n",
 912       "lacier (True, 8, 10, <Direction.downleft: 7>)\n",
 913       "autoimmune (True, 0, 3, <Direction.right: 2>)\n",
 914       "tinging (True, 16, 1, <Direction.up: 3>)\n",
 915       "snagged (True, 1, 10, <Direction.down: 4>)\n",
 916       "splendidest (True, 8, 0, <Direction.down: 4>)\n",
 917       "roughed (True, 10, 9, <Direction.upright: 6>)\n",
 918       "crevasse (True, 11, 18, <Direction.up: 3>)\n",
 919       "lone (True, 15, 17, <Direction.up: 3>)\n",
 920       "ecologists (True, 12, 16, <Direction.up: 3>)\n",
 921       "sponge (True, 13, 13, <Direction.up: 3>)\n",
 922       "magnetising (True, 1, 14, <Direction.down: 4>)\n",
 923       "sneezing (True, 3, 7, <Direction.left: 1>)\n",
 924       "virulent (True, 13, 19, <Direction.up: 3>)\n",
 925       "flight (True, 19, 3, <Direction.right: 2>)\n",
 926       "sirup (True, 4, 3, <Direction.down: 4>)\n",
 927       "yacht (True, 13, 18, <Direction.down: 4>)\n",
 928       "random (True, 13, 15, <Direction.downleft: 7>)\n",
 929       "accusations (True, 7, 2, <Direction.down: 4>)\n",
 930       "wiled (True, 3, 13, <Direction.downleft: 7>)\n",
 931       "paved (True, 8, 3, <Direction.down: 4>)\n",
 932       "majorly (True, 1, 0, <Direction.right: 2>)\n",
 933       "miser (True, 4, 1, <Direction.down: 4>)\n",
 934       "memoir (True, 11, 5, <Direction.up: 3>)\n",
 935       "emends (True, 14, 5, <Direction.downright: 8>)\n",
 936       "slurs (True, 17, 12, <Direction.right: 2>)\n",
 937       "clunk (True, 6, 11, <Direction.down: 4>)\n",
 938       "erases (True, 1, 7, <Direction.right: 2>)\n",
 939       "quasi (True, 19, 15, <Direction.right: 2>)\n"
 940      ]
 941     }
 942    ],
 943    "source": [
 944     "for w in ws:\n",
 945     "    print(w, present(padded, w))"
 946    ]
 947   },
 948   {
 949    "cell_type": "code",
 950    "execution_count": 141,
 951    "metadata": {
 952     "collapsed": false
 953    },
 954    "outputs": [],
 955    "source": [
 956     "def decoys(grid, words, all_words, limit=100):\n",
 957     "    decoy_words = []\n",
 958     "    dlen_limit = max(len(w) for w in words)\n",
 959     "    while len(words) + len(decoy_words) < limit:\n",
 960     "        d = random.choice(all_words)\n",
 961     "        if d not in words and len(d) >= 4 and len(d) <= dlen_limit and not present(grid, d)[0]:\n",
 962     "            decoy_words += [d]\n",
 963     "    return decoy_words"
 964    ]
 965   },
 966   {
 967    "cell_type": "code",
 968    "execution_count": 135,
 969    "metadata": {
 970     "collapsed": false
 971    },
 972    "outputs": [
 973     {
 974      "data": {
 975       "text/plain": [
 976        "['incisor',\n",
 977        " 'steeled',\n",
 978        " 'immobility',\n",
 979        " 'undertakings',\n",
 980        " 'exhorts',\n",
 981        " 'hairnet',\n",
 982        " 'placarded',\n",
 983        " 'sackful',\n",
 984        " 'covenanting',\n",
 985        " 'invoking',\n",
 986        " 'deltas',\n",
 987        " 'nonplus',\n",
 988        " 'exactest',\n",
 989        " 'eggs',\n",
 990        " 'tercentenary',\n",
 991        " 'angelic',\n",
 992        " 'relearning',\n",
 993        " 'ardors',\n",
 994        " 'imprints',\n",
 995        " 'chamoix',\n",
 996        " 'governance',\n",
 997        " 'rampart',\n",
 998        " 'estuary',\n",
 999        " 'poltroons',\n",
1000        " 'expect',\n",
1001        " 'restaurant',\n",
1002        " 'ashrams',\n",
1003        " 'illuminates',\n",
1004        " 'reprises',\n",
1005        " 'seismology',\n",
1006        " 'announce',\n",
1007        " 'tomorrows',\n",
1008        " 'carcinogenics',\n",
1009        " 'duplex',\n",
1010        " 'transmitters',\n",
1011        " 'prosier',\n",
1012        " 'anther',\n",
1013        " 'masticates',\n",
1014        " 'raunchy',\n",
1015        " 'briefs',\n",
1016        " 'poniard',\n",
1017        " 'daunted',\n",
1018        " 'topmasts',\n",
1019        " 'mynas']"
1020       ]
1021      },
1022      "execution_count": 135,
1023      "metadata": {},
1024      "output_type": "execute_result"
1025     }
1026    ],
1027    "source": [
1028     "ds = decoys(padded, ws, ws_words)\n",
1029     "ds"
1030    ]
1031   },
1032   {
1033    "cell_type": "code",
1034    "execution_count": 108,
1035    "metadata": {
1036     "collapsed": false,
1037     "scrolled": true
1038    },
1039    "outputs": [
1040     {
1041      "name": "stdout",
1042      "output_type": "stream",
1043      "text": [
1044       "thralled (True, 2, 2, <Direction.right: 2>)\n",
1045       "slung (True, 9, 4, <Direction.up: 3>)\n",
1046       "freighted (True, 8, 12, <Direction.down: 4>)\n",
1047       "townhouse (True, 18, 2, <Direction.upright: 6>)\n",
1048       "salute (True, 12, 11, <Direction.left: 1>)\n",
1049       "phoebes (True, 10, 6, <Direction.up: 3>)\n",
1050       "faltered (True, 18, 19, <Direction.left: 1>)\n",
1051       "laywomen (True, 19, 12, <Direction.upleft: 5>)\n",
1052       "squeaked (True, 8, 17, <Direction.up: 3>)\n",
1053       "perforating (True, 15, 15, <Direction.up: 3>)\n",
1054       "iodise (True, 4, 7, <Direction.down: 4>)\n",
1055       "lacier (True, 8, 10, <Direction.downleft: 7>)\n",
1056       "autoimmune (True, 0, 3, <Direction.right: 2>)\n",
1057       "tinging (True, 16, 1, <Direction.up: 3>)\n",
1058       "snagged (True, 1, 10, <Direction.down: 4>)\n",
1059       "splendidest (True, 8, 0, <Direction.down: 4>)\n",
1060       "roughed (True, 10, 9, <Direction.upright: 6>)\n",
1061       "crevasse (True, 11, 18, <Direction.up: 3>)\n",
1062       "lone (True, 15, 17, <Direction.up: 3>)\n",
1063       "ecologists (True, 12, 16, <Direction.up: 3>)\n",
1064       "sponge (True, 13, 13, <Direction.up: 3>)\n",
1065       "magnetising (True, 1, 14, <Direction.down: 4>)\n",
1066       "sneezing (True, 3, 7, <Direction.left: 1>)\n",
1067       "virulent (True, 13, 19, <Direction.up: 3>)\n",
1068       "flight (True, 19, 3, <Direction.right: 2>)\n",
1069       "sirup (True, 4, 3, <Direction.down: 4>)\n",
1070       "yacht (True, 13, 18, <Direction.down: 4>)\n",
1071       "random (True, 13, 15, <Direction.downleft: 7>)\n",
1072       "accusations (True, 7, 2, <Direction.down: 4>)\n",
1073       "wiled (True, 3, 13, <Direction.downleft: 7>)\n",
1074       "paved (True, 8, 3, <Direction.down: 4>)\n",
1075       "majorly (True, 1, 0, <Direction.right: 2>)\n",
1076       "miser (True, 4, 1, <Direction.down: 4>)\n",
1077       "memoir (True, 11, 5, <Direction.up: 3>)\n",
1078       "emends (True, 14, 5, <Direction.downright: 8>)\n",
1079       "slurs (True, 17, 12, <Direction.right: 2>)\n",
1080       "clunk (True, 6, 11, <Direction.down: 4>)\n",
1081       "erases (True, 1, 7, <Direction.right: 2>)\n",
1082       "quasi (True, 19, 15, <Direction.right: 2>)\n",
1083       "leakiest (False, 0, 0, <Direction.left: 1>)\n",
1084       "lumpiest (False, 0, 0, <Direction.left: 1>)\n",
1085       "bastion (False, 0, 0, <Direction.left: 1>)\n",
1086       "steamier (False, 0, 0, <Direction.left: 1>)\n",
1087       "elegant (False, 0, 0, <Direction.left: 1>)\n",
1088       "slogging (False, 0, 0, <Direction.left: 1>)\n",
1089       "rejects (False, 0, 0, <Direction.left: 1>)\n",
1090       "gaze (False, 0, 0, <Direction.left: 1>)\n",
1091       "swopping (False, 0, 0, <Direction.left: 1>)\n",
1092       "resonances (False, 0, 0, <Direction.left: 1>)\n",
1093       "treasonous (False, 0, 0, <Direction.left: 1>)\n",
1094       "corm (False, 0, 0, <Direction.left: 1>)\n",
1095       "abuses (False, 0, 0, <Direction.left: 1>)\n",
1096       "toga (False, 0, 0, <Direction.left: 1>)\n",
1097       "upcountry (False, 0, 0, <Direction.left: 1>)\n",
1098       "scrawled (False, 0, 0, <Direction.left: 1>)\n",
1099       "cellar (False, 0, 0, <Direction.left: 1>)\n",
1100       "skinflint (False, 0, 0, <Direction.left: 1>)\n",
1101       "wasteland (False, 0, 0, <Direction.left: 1>)\n",
1102       "madman (False, 0, 0, <Direction.left: 1>)\n",
1103       "lash (False, 0, 0, <Direction.left: 1>)\n"
1104      ]
1105     }
1106    ],
1107    "source": [
1108     "for w in ws + ds:\n",
1109     "    print(w, present(padded, w))"
1110    ]
1111   },
1112   {
1113    "cell_type": "code",
1114    "execution_count": 142,
1115    "metadata": {
1116     "collapsed": false
1117    },
1118    "outputs": [
1119     {
1120      "name": "stdout",
1121      "output_type": "stream",
1122      "text": [
1123       ".strigger.essegassum\n",
1124       "acselacs.tapri..pgcr\n",
1125       "moeclienterr.em.uaie\n",
1126       "apisearsclmo.kvpmntp\n",
1127       "lebpg..ohlucfaeaespe\n",
1128       "ifbi.ev.aafeesr.urol\n",
1129       "riae.el.iwfse.o.oqss\n",
1130       "evcsr...n..sd.dv..r.\n",
1131       "pestdewels..e.aw.ut.\n",
1132       "mrlimmersionrl.ob.e.\n",
1133       "iyllatnemadnufwls.nl\n",
1134       "..sdboomovulesivl.ri\n",
1135       ".eiepsreggij.tdeljif\n",
1136       "dkwn.atread..oereiat\n",
1137       "uais..efile..pnihlhi\n",
1138       "rhkripelyt.illsnst.n\n",
1139       "iweekendunotablete.g\n",
1140       "nfondlyrytsenohsuo..\n",
1141       "g.mriffa....naysnp..\n",
1142       ".meatspoodle.within.\n",
1143       "cstriggerpessegassum\n",
1144       "acselacsytapriijpgcr\n",
1145       "moeclienterrtemnuaie\n",
1146       "apisearsclmookvpmntp\n",
1147       "lebpgatohlucfaeaespe\n",
1148       "ifbisevxaafeesrlurol\n",
1149       "riaehelciwfseioioqss\n",
1150       "evcsrkuynpasdfdvetrq\n",
1151       "pestdewelsniegawkutd\n",
1152       "mrlimmersionrloobuel\n",
1153       "iyllatnemadnufwlsanl\n",
1154       "dwsdboomovulesivlyri\n",
1155       "oeiepsreggijntdeljif\n",
1156       "dkwnkatreadvnoereiat\n",
1157       "uaiscuefilehapnihlhi\n",
1158       "rhkripelytqillsnsten\n",
1159       "iweekendunotabletetg\n",
1160       "nfondlyrytsenohsuocc\n",
1161       "gemriffanternaysnpef\n",
1162       "bmeatspoodleswithing\n",
1163       "62 words added;  8 directions\n",
1164       "Present: adore affirm ages boom burs chain client dens during earmuff feeder file fiver fondly fundamentally hairnet hake honesty ills immersion imperil jiggers jilt kiwis lama leap legs lifting meat muss nays notable nutshells optic oval overtly ovule pies poet poodle process quavers repels ripely sake scabbiest scale scope sears simpers slewed snag spume stop tread trigger turfs wallet weekend widen within wolverines\n",
1165       "Decoys: chitchats colloquium conveyances convulsively debates dieting dudes dumpster dwarfed experienced feasibility festooning groupie grunted highfalutin humanise incubuses infiltrate ingratiated jotting linearly lotus masculines meanders nucleuses plunks ponderously prerecording riskiest scavenging splashier sportsmanship strawberry twirler unjustified wariness wavy yeast\n"
1166      ]
1167     }
1168    ],
1169    "source": [
1170     "g, ws = interesting_grid()\n",
1171     "p = pad_grid(g)\n",
1172     "ds = decoys(p, ws, ws_words)\n",
1173     "print(show_grid(g))\n",
1174     "print(show_grid(p))\n",
1175     "print(len(ws), 'words added; ', len(set(present(g, w)[3] for w in ws)), 'directions')\n",
1176     "print('Present:', wcat(sorted(ws)))\n",
1177     "print('Decoys:', wcat(sorted(ds)))"
1178    ]
1179   },
1180   {
1181    "cell_type": "code",
1182    "execution_count": 143,
1183    "metadata": {
1184     "collapsed": false,
1185     "scrolled": true
1186    },
1187    "outputs": [
1188     {
1189      "name": "stdout",
1190      "output_type": "stream",
1191      "text": [
1192       "0\n",
1193       "1\n",
1194       "2\n",
1195       "3\n",
1196       "4\n",
1197       "5\n",
1198       "6\n",
1199       "7\n",
1200       "8\n",
1201       "9\n",
1202       "10\n",
1203       "11\n",
1204       "12\n",
1205       "13\n",
1206       "14\n",
1207       "15\n",
1208       "16\n",
1209       "17\n",
1210       "18\n",
1211       "19\n",
1212       "20\n",
1213       "21\n",
1214       "22\n",
1215       "23\n",
1216       "24\n",
1217       "25\n",
1218       "26\n",
1219       "27\n",
1220       "28\n",
1221       "29\n",
1222       "30\n",
1223       "31\n",
1224       "32\n",
1225       "33\n",
1226       "34\n",
1227       "35\n",
1228       "36\n",
1229       "37\n",
1230       "38\n",
1231       "39\n",
1232       "40\n",
1233       "41\n",
1234       "42\n",
1235       "43\n",
1236       "44\n",
1237       "45\n",
1238       "46\n",
1239       "47\n",
1240       "48\n",
1241       "49\n",
1242       "50\n",
1243       "51\n",
1244       "52\n",
1245       "53\n",
1246       "54\n",
1247       "55\n",
1248       "56\n",
1249       "57\n",
1250       "58\n",
1251       "59\n",
1252       "60\n",
1253       "61\n",
1254       "62\n",
1255       "63\n",
1256       "64\n",
1257       "65\n",
1258       "66\n",
1259       "67\n",
1260       "68\n",
1261       "69\n",
1262       "70\n",
1263       "71\n",
1264       "72\n",
1265       "73\n",
1266       "74\n",
1267       "75\n",
1268       "76\n",
1269       "77\n",
1270       "78\n",
1271       "79\n",
1272       "80\n",
1273       "81\n",
1274       "82\n",
1275       "83\n",
1276       "84\n",
1277       "85\n",
1278       "86\n",
1279       "87\n",
1280       "88\n",
1281       "89\n",
1282       "90\n",
1283       "91\n",
1284       "92\n",
1285       "93\n",
1286       "94\n",
1287       "95\n",
1288       "96\n",
1289       "97\n",
1290       "98\n",
1291       "99\n"
1292      ]
1293     }
1294    ],
1295    "source": [
1296     "for i in range(100):\n",
1297     "    print(i)\n",
1298     "    g, ws = interesting_grid()\n",
1299     "    p = pad_grid(g)\n",
1300     "    ds = decoys(p, ws, ws_words)\n",
1301     "    with open('wordsearch{:02}.txt'.format(i), 'w') as f:\n",
1302     "        f.write('20x20\\n')\n",
1303     "        f.write(show_grid(p))\n",
1304     "        f.write('\\n')\n",
1305     "        f.write(lcat(sorted(ws + ds)))\n",
1306     "    with open('wordsearch-solution{:02}.txt'.format(i), 'w') as f:\n",
1307     "        f.write('20x20\\n')\n",
1308     "        f.write(show_grid(g))\n",
1309     "        f.write('\\n')\n",
1310     "        f.write(lcat(sorted(ws)) + '\\n\\n')\n",
1311     "        f.write(lcat(sorted(ds)))"
1312    ]
1313   },
1314   {
1315    "cell_type": "code",
1316    "execution_count": null,
1317    "metadata": {
1318     "collapsed": true
1319    },
1320    "outputs": [],
1321    "source": []
1322   }
1323  ],
1324  "metadata": {
1325   "kernelspec": {
1326    "display_name": "Python 3",
1327    "language": "python",
1328    "name": "python3"
1329   },
1330   "language_info": {
1331    "codemirror_mode": {
1332     "name": "ipython",
1333     "version": 3
1334    },
1335    "file_extension": ".py",
1336    "mimetype": "text/x-python",
1337    "name": "python",
1338    "nbconvert_exporter": "python",
1339    "pygments_lexer": "ipython3",
1340    "version": "3.5.2"
1341   }
1342  },
1343  "nbformat": 4,
1344  "nbformat_minor": 0
1345 }