wordsearch/wordsearch-creation.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 2,
   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": 3,
  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": 4,
  48    "metadata": {
  49     "collapsed": false
  50    },
  51    "outputs": [
  52     {
  53      "data": {
  54       "text/plain": [
  55        "['aardvarks',\n",
  56        " 'abaci',\n",
  57        " 'abacuses',\n",
  58        " 'abaft',\n",
  59        " 'abalones',\n",
  60        " 'abandoned',\n",
  61        " 'abandoning',\n",
  62        " 'abandonment',\n",
  63        " 'abandons',\n",
  64        " 'abased']"
  65       ]
  66      },
  67      "execution_count": 4,
  68      "metadata": {},
  69      "output_type": "execute_result"
  70     }
  71    ],
  72    "source": [
  73     "ws_words = [w.strip() for w in open('wordsearch-words').readlines()\n",
  74     "            if all(c in string.ascii_lowercase for c in w.strip())]\n",
  75     "ws_words[:10]"
  76    ]
  77   },
  78   {
  79    "cell_type": "code",
  80    "execution_count": 5,
  81    "metadata": {
  82     "collapsed": true
  83    },
  84    "outputs": [],
  85    "source": [
  86     "def empty_grid(w, h):\n",
  87     "    return [['.' for c in range(w)] for r in range(h)]"
  88    ]
  89   },
  90   {
  91    "cell_type": "code",
  92    "execution_count": 6,
  93    "metadata": {
  94     "collapsed": true
  95    },
  96    "outputs": [],
  97    "source": [
  98     "def show_grid(grid):\n",
  99     "    return lcat(cat(r) for r in grid)"
 100    ]
 101   },
 102   {
 103    "cell_type": "code",
 104    "execution_count": 7,
 105    "metadata": {
 106     "collapsed": false
 107    },
 108    "outputs": [
 109     {
 110      "name": "stdout",
 111      "output_type": "stream",
 112      "text": [
 113       "..........\n",
 114       "..........\n",
 115       "..........\n",
 116       "..........\n",
 117       "..........\n",
 118       "..........\n",
 119       "..........\n",
 120       "..........\n",
 121       "..........\n",
 122       "..........\n"
 123      ]
 124     }
 125    ],
 126    "source": [
 127     "grid = empty_grid(10, 10)\n",
 128     "print(show_grid(grid))"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 8,
 134    "metadata": {
 135     "collapsed": true
 136    },
 137    "outputs": [],
 138    "source": [
 139     "def indices(grid, r, c, l, d):\n",
 140     "    dr, dc = delta[d]\n",
 141     "    w = len(grid[0])\n",
 142     "    h = len(grid)\n",
 143     "    inds = [(r + i * dr, c + i * dc) for i in range(l)]\n",
 144     "    return [(i, j) for i, j in inds\n",
 145     "           if i >= 0\n",
 146     "           if j >= 0\n",
 147     "           if i < h\n",
 148     "           if j < w]"
 149    ]
 150   },
 151   {
 152    "cell_type": "code",
 153    "execution_count": 9,
 154    "metadata": {
 155     "collapsed": true
 156    },
 157    "outputs": [],
 158    "source": [
 159     "def gslice(grid, r, c, l, d):\n",
 160     "    return [grid[i][j] for i, j in indices(grid, r, c, l, d)]"
 161    ]
 162   },
 163   {
 164    "cell_type": "code",
 165    "execution_count": 10,
 166    "metadata": {
 167     "collapsed": true
 168    },
 169    "outputs": [],
 170    "source": [
 171     "def set_grid(grid, r, c, d, word):\n",
 172     "    for (i, j), l in zip(indices(grid, r, c, len(word), d), word):\n",
 173     "        grid[i][j] = l\n",
 174     "    return grid"
 175    ]
 176   },
 177   {
 178    "cell_type": "code",
 179    "execution_count": 11,
 180    "metadata": {
 181     "collapsed": false
 182    },
 183    "outputs": [
 184     {
 185      "name": "stdout",
 186      "output_type": "stream",
 187      "text": [
 188       "..........\n",
 189       "..........\n",
 190       "...t......\n",
 191       "....e.....\n",
 192       ".....s....\n",
 193       "......t...\n",
 194       ".......w..\n",
 195       "........o.\n",
 196       ".........r\n",
 197       "..........\n"
 198      ]
 199     }
 200    ],
 201    "source": [
 202     "set_grid(grid, 2, 3, Direction.downright, 'testword')\n",
 203     "print(show_grid(grid))"
 204    ]
 205   },
 206   {
 207    "cell_type": "code",
 208    "execution_count": 12,
 209    "metadata": {
 210     "collapsed": false
 211    },
 212    "outputs": [
 213     {
 214      "data": {
 215       "text/plain": [
 216        "'..e.....'"
 217       ]
 218      },
 219      "execution_count": 12,
 220      "metadata": {},
 221      "output_type": "execute_result"
 222     }
 223    ],
 224    "source": [
 225     "cat(gslice(grid, 3, 2, 15, Direction.right))"
 226    ]
 227   },
 228   {
 229    "cell_type": "code",
 230    "execution_count": 13,
 231    "metadata": {
 232     "collapsed": false
 233    },
 234    "outputs": [
 235     {
 236      "data": {
 237       "text/plain": [
 238        "<_sre.SRE_Match object; span=(0, 4), match='keen'>"
 239       ]
 240      },
 241      "execution_count": 13,
 242      "metadata": {},
 243      "output_type": "execute_result"
 244     }
 245    ],
 246    "source": [
 247     "re.match(cat(gslice(grid, 3, 2, 4, Direction.right)), 'keen')"
 248    ]
 249   },
 250   {
 251    "cell_type": "code",
 252    "execution_count": 14,
 253    "metadata": {
 254     "collapsed": false
 255    },
 256    "outputs": [
 257     {
 258      "data": {
 259       "text/plain": [
 260        "<_sre.SRE_Match object; span=(0, 3), match='kee'>"
 261       ]
 262      },
 263      "execution_count": 14,
 264      "metadata": {},
 265      "output_type": "execute_result"
 266     }
 267    ],
 268    "source": [
 269     "re.match(cat(gslice(grid, 3, 2, 3, Direction.right)), 'keen')"
 270    ]
 271   },
 272   {
 273    "cell_type": "code",
 274    "execution_count": 15,
 275    "metadata": {
 276     "collapsed": false
 277    },
 278    "outputs": [],
 279    "source": [
 280     "re.fullmatch(cat(gslice(grid, 3, 2, 3, Direction.right)), 'keen')"
 281    ]
 282   },
 283   {
 284    "cell_type": "code",
 285    "execution_count": 16,
 286    "metadata": {
 287     "collapsed": true
 288    },
 289    "outputs": [],
 290    "source": [
 291     "re.match(cat(gslice(grid, 3, 2, 4, Direction.right)), 'kine')"
 292    ]
 293   },
 294   {
 295    "cell_type": "code",
 296    "execution_count": 17,
 297    "metadata": {
 298     "collapsed": true
 299    },
 300    "outputs": [],
 301    "source": [
 302     "def could_add(grid, r, c, d, word):\n",
 303     "    s = gslice(grid, r, c, len(word), d)\n",
 304     "    return re.fullmatch(cat(s), word)"
 305    ]
 306   },
 307   {
 308    "cell_type": "code",
 309    "execution_count": 18,
 310    "metadata": {
 311     "collapsed": false
 312    },
 313    "outputs": [
 314     {
 315      "data": {
 316       "text/plain": [
 317        "<_sre.SRE_Match object; span=(0, 4), match='keen'>"
 318       ]
 319      },
 320      "execution_count": 18,
 321      "metadata": {},
 322      "output_type": "execute_result"
 323     }
 324    ],
 325    "source": [
 326     "could_add(grid, 3, 2, Direction.right, 'keen')"
 327    ]
 328   },
 329   {
 330    "cell_type": "code",
 331    "execution_count": 19,
 332    "metadata": {
 333     "collapsed": false
 334    },
 335    "outputs": [],
 336    "source": [
 337     "could_add(grid, 3, 2, Direction.right, 'kine')"
 338    ]
 339   },
 340   {
 341    "cell_type": "code",
 342    "execution_count": 20,
 343    "metadata": {
 344     "collapsed": false
 345    },
 346    "outputs": [
 347     {
 348      "data": {
 349       "text/plain": [
 350        "<Direction.up: 3>"
 351       ]
 352      },
 353      "execution_count": 20,
 354      "metadata": {},
 355      "output_type": "execute_result"
 356     }
 357    ],
 358    "source": [
 359     "random.choice(list(Direction))"
 360    ]
 361   },
 362   {
 363    "cell_type": "code",
 364    "execution_count": 21,
 365    "metadata": {
 366     "collapsed": true
 367    },
 368    "outputs": [],
 369    "source": [
 370     "def fill_grid(grid, words, word_count, max_attempts= 1000):\n",
 371     "    attempts = 0\n",
 372     "    added_words = []\n",
 373     "    w = len(grid[0])\n",
 374     "    h = len(grid)\n",
 375     "    while len(added_words) < word_count and attempts < max_attempts:\n",
 376     "        attempts += 1\n",
 377     "        r = random.randrange(w)\n",
 378     "        c = random.randrange(h)\n",
 379     "        word = random.choice(words)\n",
 380     "        d = random.choice(list(Direction))\n",
 381     "        if could_add(grid, r, c, d, word):\n",
 382     "            set_grid(grid, r, c, d, word)\n",
 383     "            added_words += [word]\n",
 384     "            attempts = 0\n",
 385     "    return grid, added_words"
 386    ]
 387   },
 388   {
 389    "cell_type": "code",
 390    "execution_count": 22,
 391    "metadata": {
 392     "collapsed": false
 393    },
 394    "outputs": [
 395     {
 396      "data": {
 397       "text/plain": [
 398        "35"
 399       ]
 400      },
 401      "execution_count": 22,
 402      "metadata": {},
 403      "output_type": "execute_result"
 404     }
 405    ],
 406    "source": [
 407     "g = empty_grid(20, 20)\n",
 408     "g, ws = fill_grid(g, ws_words, 40)\n",
 409     "len(ws)"
 410    ]
 411   },
 412   {
 413    "cell_type": "code",
 414    "execution_count": 23,
 415    "metadata": {
 416     "collapsed": false
 417    },
 418    "outputs": [
 419     {
 420      "name": "stdout",
 421      "output_type": "stream",
 422      "text": [
 423       "......swoopingg.l.up\n",
 424       "..dunsnapped.n.i..ne\n",
 425       ".cee.gninarci.m...er\n",
 426       "sotpt......k.pmv..mv\n",
 427       "euirca.d..c.n.a...pa\n",
 428       "snduo.o.eo.e.lgs..ld\n",
 429       "itndny.ctks.i.nos.oe\n",
 430       "rroev.lsrsss..ifr.ys\n",
 431       "eycno.eb.aeub.ttebas\n",
 432       "tmetyr..asgetmuemebe\n",
 433       "nerie....tvuu.dsraln\n",
 434       "in.adbdmbecls.etocei\n",
 435       "w..loeu.lilu..s.fh.d\n",
 436       "...rtl.e.ec.l...eimw\n",
 437       "..oac.d.v..y.e..rnao\n",
 438       ".nrhgniknilsc.n..gyd\n",
 439       ".pignippay...l.i..f.\n",
 440       ".n..skcenrehtael..l.\n",
 441       "g....popinjays.s..y.\n",
 442       "gnimmugspuds.relppus\n",
 443       "35 words added\n",
 444       "ineluctably limpness countrymen slinking beaching restocking vellum convoyed winterises tusked leathernecks sugarcoated mayfly mulching popinjays magnitudes unsnapped prudential yapping spuds softest boron craning unemployable reformers bicycles swooping recondite dowdiness gumming pervades beveled valises suppler prated\n"
 445      ]
 446     }
 447    ],
 448    "source": [
 449     "print(show_grid(g))\n",
 450     "print(len(ws), 'words added')\n",
 451     "print(wcat(ws))"
 452    ]
 453   },
 454   {
 455    "cell_type": "code",
 456    "execution_count": 24,
 457    "metadata": {
 458     "collapsed": true
 459    },
 460    "outputs": [],
 461    "source": [
 462     "def present(grid, word):\n",
 463     "    w = len(grid[0])\n",
 464     "    h = len(grid)\n",
 465     "    for r in range(h):\n",
 466     "        for c in range(w):\n",
 467     "            for d in Direction:\n",
 468     "                if cat(gslice(grid, r, c, len(word), d)) == word:\n",
 469     "                    return True, r, c, d\n",
 470     "    return False, 0, 0, list(Direction)[0]"
 471    ]
 472   },
 473   {
 474    "cell_type": "code",
 475    "execution_count": 25,
 476    "metadata": {
 477     "collapsed": false,
 478     "scrolled": true
 479    },
 480    "outputs": [
 481     {
 482      "name": "stdout",
 483      "output_type": "stream",
 484      "text": [
 485       "ineluctably (True, 16, 15, <Direction.upleft: 5>)\n",
 486       "limpness (True, 0, 16, <Direction.downleft: 7>)\n",
 487       "countrymen (True, 2, 1, <Direction.down: 4>)\n",
 488       "slinking (True, 15, 11, <Direction.left: 1>)\n",
 489       "beaching (True, 8, 17, <Direction.down: 4>)\n",
 490       "restocking (True, 9, 5, <Direction.upright: 6>)\n",
 491       "vellum (True, 14, 8, <Direction.upright: 6>)\n",
 492       "convoyed (True, 4, 4, <Direction.down: 4>)\n",
 493       "winterises (True, 12, 0, <Direction.up: 3>)\n",
 494       "tusked (True, 9, 12, <Direction.upleft: 5>)\n",
 495       "leathernecks (True, 17, 15, <Direction.left: 1>)\n",
 496       "sugarcoated (True, 11, 12, <Direction.upleft: 5>)\n",
 497       "mayfly (True, 13, 18, <Direction.down: 4>)\n",
 498       "mulching (True, 11, 7, <Direction.downleft: 7>)\n",
 499       "popinjays (True, 18, 5, <Direction.right: 2>)\n",
 500       "magnitudes (True, 3, 14, <Direction.down: 4>)\n",
 501       "unsnapped (True, 1, 3, <Direction.right: 2>)\n",
 502       "prudential (True, 3, 3, <Direction.down: 4>)\n",
 503       "yapping (True, 16, 9, <Direction.left: 1>)\n",
 504       "spuds (True, 19, 7, <Direction.right: 2>)\n",
 505       "softest (True, 5, 15, <Direction.down: 4>)\n",
 506       "boron (True, 11, 5, <Direction.downleft: 7>)\n",
 507       "craning (True, 2, 11, <Direction.left: 1>)\n",
 508       "unemployable (True, 0, 18, <Direction.down: 4>)\n",
 509       "reformers (True, 14, 16, <Direction.up: 3>)\n",
 510       "bicycles (True, 11, 8, <Direction.downright: 8>)\n",
 511       "swooping (True, 0, 6, <Direction.right: 2>)\n",
 512       "recondite (True, 10, 2, <Direction.up: 3>)\n",
 513       "dowdiness (True, 15, 19, <Direction.up: 3>)\n",
 514       "gumming (True, 19, 6, <Direction.left: 1>)\n",
 515       "pervades (True, 0, 19, <Direction.down: 4>)\n",
 516       "beveled (True, 8, 12, <Direction.downleft: 7>)\n",
 517       "valises (True, 3, 15, <Direction.downleft: 7>)\n",
 518       "suppler (True, 19, 19, <Direction.left: 1>)\n",
 519       "prated (True, 16, 1, <Direction.upright: 6>)\n"
 520      ]
 521     }
 522    ],
 523    "source": [
 524     "for w in ws:\n",
 525     "    print(w, present(g, w))"
 526    ]
 527   },
 528   {
 529    "cell_type": "code",
 530    "execution_count": 26,
 531    "metadata": {
 532     "collapsed": true
 533    },
 534    "outputs": [],
 535    "source": [
 536     "def interesting(grid, words):\n",
 537     "    dirs = set(present(grid, w)[3] for w in words)\n",
 538     "    return len(words) > 35 and len(words) < 40 and len(dirs) + 1 >= len(delta)"
 539    ]
 540   },
 541   {
 542    "cell_type": "code",
 543    "execution_count": 27,
 544    "metadata": {
 545     "collapsed": false
 546    },
 547    "outputs": [
 548     {
 549      "data": {
 550       "text/plain": [
 551        "False"
 552       ]
 553      },
 554      "execution_count": 27,
 555      "metadata": {},
 556      "output_type": "execute_result"
 557     }
 558    ],
 559    "source": [
 560     "interesting(g, ws)"
 561    ]
 562   },
 563   {
 564    "cell_type": "code",
 565    "execution_count": 28,
 566    "metadata": {
 567     "collapsed": true
 568    },
 569    "outputs": [],
 570    "source": [
 571     "def interesting_grid():\n",
 572     "    boring = True\n",
 573     "    while boring:\n",
 574     "        grid = empty_grid(20, 20)\n",
 575     "        grid, words = fill_grid(grid, ws_words, 40)\n",
 576     "        boring = not interesting(grid, words)\n",
 577     "    return grid, words"
 578    ]
 579   },
 580   {
 581    "cell_type": "code",
 582    "execution_count": 29,
 583    "metadata": {
 584     "collapsed": false
 585    },
 586    "outputs": [
 587     {
 588      "name": "stdout",
 589      "output_type": "stream",
 590      "text": [
 591       "..reittonk..ss......\n",
 592       "tinctured.wcee.....w\n",
 593       "serutats.oyozm....o.\n",
 594       "b....s..l.eoia...m.r\n",
 595       "e.b.y.lf..lpsd..bgye\n",
 596       "a.ist.no..less.ssrgm\n",
 597       "m.gtfi.lo.orae.n.ura\n",
 598       "edaei..i.cwi.mo..mor\n",
 599       "demrn..b..in.m...psk\n",
 600       "epya...e..sgm....ile\n",
 601       "slsg...l..hi.....nrd\n",
 602       "tekisyassesdepeebeum\n",
 603       "rtec.gninretni...sfo\n",
 604       "oiinsetse..baggy.snd\n",
 605       "ynn....p..sebircsaui\n",
 606       "egs.noitasiretupmocf\n",
 607       "r.....artefacts....y\n",
 608       "s.....seilaog.winosi\n",
 609       ".....eyelidsegener.n\n",
 610       "regicidesesopatxuj.g\n",
 611       "38 words added;  7 directions\n",
 612       "wombs persimmons computerisation ascribes coopering goalies beamed modifying insets cigarets statures libels remarked baggy juxtaposes mesdames grumpiness artefacts skeins assizes inflow depleting beeped reneges interning yellowish regicides eyelids cools orgy nifty knottier destroyers unfurls tinctured bigamy winos essays\n"
 613      ]
 614     }
 615    ],
 616    "source": [
 617     "g, ws = interesting_grid()\n",
 618     "print(show_grid(g))\n",
 619     "print(len(ws), 'words added; ', len(set(present(g, w)[3] for w in ws)), 'directions')\n",
 620     "print(wcat(ws))"
 621    ]
 622   },
 623   {
 624    "cell_type": "code",
 625    "execution_count": 30,
 626    "metadata": {
 627     "collapsed": true
 628    },
 629    "outputs": [],
 630    "source": [
 631     "def datafile(name, sep='\\t'):\n",
 632     "    \"\"\"Read key,value pairs from file.\n",
 633     "    \"\"\"\n",
 634     "    with open(name) as f:\n",
 635     "        for line in f:\n",
 636     "            splits = line.split(sep)\n",
 637     "            yield [splits[0], int(splits[1])]"
 638    ]
 639   },
 640   {
 641    "cell_type": "code",
 642    "execution_count": 31,
 643    "metadata": {
 644     "collapsed": true
 645    },
 646    "outputs": [],
 647    "source": [
 648     "def normalise(frequencies):\n",
 649     "    \"\"\"Scale a set of frequencies so they sum to one\n",
 650     "    \n",
 651     "    >>> sorted(normalise({1: 1, 2: 0}).items())\n",
 652     "    [(1, 1.0), (2, 0.0)]\n",
 653     "    >>> sorted(normalise({1: 1, 2: 1}).items())\n",
 654     "    [(1, 0.5), (2, 0.5)]\n",
 655     "    >>> sorted(normalise({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS\n",
 656     "    [(1, 0.333...), (2, 0.333...), (3, 0.333...)]\n",
 657     "    >>> sorted(normalise({1: 1, 2: 2, 3: 1}).items())\n",
 658     "    [(1, 0.25), (2, 0.5), (3, 0.25)]\n",
 659     "    \"\"\"\n",
 660     "    length = sum(f for f in frequencies.values())\n",
 661     "    return collections.defaultdict(int, ((k, v / length) \n",
 662     "        for (k, v) in frequencies.items()))\n"
 663    ]
 664   },
 665   {
 666    "cell_type": "code",
 667    "execution_count": 32,
 668    "metadata": {
 669     "collapsed": false
 670    },
 671    "outputs": [],
 672    "source": [
 673     "english_counts = collections.Counter(dict(datafile('count_1l.txt')))\n",
 674     "normalised_english_counts = normalise(english_counts)"
 675    ]
 676   },
 677   {
 678    "cell_type": "code",
 679    "execution_count": 34,
 680    "metadata": {
 681     "collapsed": false
 682    },
 683    "outputs": [],
 684    "source": [
 685     "wordsearch_counts = collections.Counter(cat(ws_words))\n",
 686     "normalised_wordsearch_counts = normalise(wordsearch_counts)"
 687    ]
 688   },
 689   {
 690    "cell_type": "code",
 691    "execution_count": 35,
 692    "metadata": {
 693     "collapsed": true
 694    },
 695    "outputs": [],
 696    "source": [
 697     "def weighted_choice(d):\n",
 698     "    \"\"\"Generate random item from a dictionary of item counts\n",
 699     "    \"\"\"\n",
 700     "    target = random.uniform(0, sum(d.values()))\n",
 701     "    cuml = 0.0\n",
 702     "    for (l, p) in d.items():\n",
 703     "        cuml += p\n",
 704     "        if cuml > target:\n",
 705     "            return l\n",
 706     "    return None\n",
 707     "\n",
 708     "def random_english_letter():\n",
 709     "    \"\"\"Generate a random letter based on English letter counts\n",
 710     "    \"\"\"\n",
 711     "    return weighted_choice(normalised_english_counts)\n",
 712     "\n",
 713     "def random_wordsearch_letter():\n",
 714     "    \"\"\"Generate a random letter based on wordsearch letter counts\n",
 715     "    \"\"\"\n",
 716     "    return weighted_choice(normalised_wordsearch_counts)"
 717    ]
 718   },
 719   {
 720    "cell_type": "code",
 721    "execution_count": 36,
 722    "metadata": {
 723     "collapsed": false
 724    },
 725    "outputs": [
 726     {
 727      "data": {
 728       "text/plain": [
 729        "'aaaaaaaabcccddddeeeeeeeeeeeeeeefffggghhhhhiiiiiillllmnnnnnnoooooooooprrsssssssssssssttttttttuuuvwwwy'"
 730       ]
 731      },
 732      "execution_count": 36,
 733      "metadata": {},
 734      "output_type": "execute_result"
 735     }
 736    ],
 737    "source": [
 738     "cat(sorted(random_english_letter() for i in range(100)))"
 739    ]
 740   },
 741   {
 742    "cell_type": "code",
 743    "execution_count": 37,
 744    "metadata": {
 745     "collapsed": false
 746    },
 747    "outputs": [
 748     {
 749      "data": {
 750       "text/plain": [
 751        "'aaaaaabcccddddddeeeeeeggggghhiiiiiiiiiiiiklllmmmmnnnnnnnnnnoooooooooppprrrrrrrrrssssssttttttuuuwwwyy'"
 752       ]
 753      },
 754      "execution_count": 37,
 755      "metadata": {},
 756      "output_type": "execute_result"
 757     }
 758    ],
 759    "source": [
 760     "cat(sorted(random_wordsearch_letter() for i in range(100)))"
 761    ]
 762   },
 763   {
 764    "cell_type": "code",
 765    "execution_count": 38,
 766    "metadata": {
 767     "collapsed": false
 768    },
 769    "outputs": [
 770     {
 771      "data": {
 772       "text/plain": [
 773        "'a'"
 774       ]
 775      },
 776      "execution_count": 38,
 777      "metadata": {},
 778      "output_type": "execute_result"
 779     }
 780    ],
 781    "source": [
 782     "random_wordsearch_letter()"
 783    ]
 784   },
 785   {
 786    "cell_type": "code",
 787    "execution_count": 39,
 788    "metadata": {
 789     "collapsed": true
 790    },
 791    "outputs": [],
 792    "source": [
 793     "def pad_grid(g0):\n",
 794     "    grid = copy.deepcopy(g0)\n",
 795     "    w = len(grid[0])\n",
 796     "    h = len(grid)\n",
 797     "    for r in range(h):\n",
 798     "        for c in range(w):\n",
 799     "            if grid[r][c] == '.':\n",
 800     "                grid[r][c] = random_wordsearch_letter()\n",
 801     "    return grid"
 802    ]
 803   },
 804   {
 805    "cell_type": "code",
 806    "execution_count": 40,
 807    "metadata": {
 808     "collapsed": false
 809    },
 810    "outputs": [
 811     {
 812      "name": "stdout",
 813      "output_type": "stream",
 814      "text": [
 815       "streittonkorsssatnal\n",
 816       "tincturedswceedrlnuw\n",
 817       "serutatsloyozmeieiot\n",
 818       "baanfsollleoiasnlmar\n",
 819       "ewblyhlfetlpsdyvbgye\n",
 820       "aeistonoeilessassrgm\n",
 821       "mlgtfitloioraeenwura\n",
 822       "edaeiupiscwiamoygmor\n",
 823       "demrnasbhcinsmiiapsk\n",
 824       "epyakraedrsgmolsnile\n",
 825       "slsgtuoloihireneonrd\n",
 826       "tekisyassesdepeebeum\n",
 827       "rtecigninretnincesfo\n",
 828       "oiinsetseddbaggydsnd\n",
 829       "ynnnsfapcfsebircsaui\n",
 830       "egsonoitasiretupmocf\n",
 831       "raioelartefactseawfy\n",
 832       "speonsseilaogrwinosi\n",
 833       "wrndfeyelidsegenerln\n",
 834       "regicidesesopatxujrg\n"
 835      ]
 836     }
 837    ],
 838    "source": [
 839     "padded = pad_grid(g)\n",
 840     "print(show_grid(padded))"
 841    ]
 842   },
 843   {
 844    "cell_type": "code",
 845    "execution_count": 41,
 846    "metadata": {
 847     "collapsed": false
 848    },
 849    "outputs": [
 850     {
 851      "name": "stdout",
 852      "output_type": "stream",
 853      "text": [
 854       "..reittonk..ss......\n",
 855       "tinctured.wcee.....w\n",
 856       "serutats.oyozm....o.\n",
 857       "b....s..l.eoia...m.r\n",
 858       "e.b.y.lf..lpsd..bgye\n",
 859       "a.ist.no..less.ssrgm\n",
 860       "m.gtfi.lo.orae.n.ura\n",
 861       "edaei..i.cwi.mo..mor\n",
 862       "demrn..b..in.m...psk\n",
 863       "epya...e..sgm....ile\n",
 864       "slsg...l..hi.....nrd\n",
 865       "tekisyassesdepeebeum\n",
 866       "rtec.gninretni...sfo\n",
 867       "oiinsetse..baggy.snd\n",
 868       "ynn....p..sebircsaui\n",
 869       "egs.noitasiretupmocf\n",
 870       "r.....artefacts....y\n",
 871       "s.....seilaog.winosi\n",
 872       ".....eyelidsegener.n\n",
 873       "regicidesesopatxuj.g\n"
 874      ]
 875     }
 876    ],
 877    "source": [
 878     "print(show_grid(g))"
 879    ]
 880   },
 881   {
 882    "cell_type": "code",
 883    "execution_count": 42,
 884    "metadata": {
 885     "collapsed": false,
 886     "scrolled": true
 887    },
 888    "outputs": [
 889     {
 890      "name": "stdout",
 891      "output_type": "stream",
 892      "text": [
 893       "wombs (True, 1, 19, <Direction.downleft: 7>)\n",
 894       "persimmons (True, 14, 7, <Direction.upright: 6>)\n",
 895       "computerisation (True, 15, 18, <Direction.left: 1>)\n",
 896       "ascribes (True, 14, 17, <Direction.left: 1>)\n",
 897       "coopering (True, 1, 11, <Direction.down: 4>)\n",
 898       "goalies (True, 17, 12, <Direction.left: 1>)\n",
 899       "beamed (True, 3, 0, <Direction.down: 4>)\n",
 900       "modifying (True, 11, 19, <Direction.down: 4>)\n",
 901       "insets (True, 13, 2, <Direction.right: 2>)\n",
 902       "cigarets (True, 12, 3, <Direction.up: 3>)\n",
 903       "statures (True, 2, 7, <Direction.left: 1>)\n",
 904       "libels (True, 6, 7, <Direction.down: 4>)\n",
 905       "remarked (True, 3, 19, <Direction.down: 4>)\n",
 906       "baggy (True, 13, 11, <Direction.right: 2>)\n",
 907       "juxtaposes (True, 19, 17, <Direction.left: 1>)\n",
 908       "mesdames (True, 7, 13, <Direction.up: 3>)\n",
 909       "grumpiness (True, 4, 17, <Direction.down: 4>)\n",
 910       "artefacts (True, 16, 6, <Direction.right: 2>)\n",
 911       "skeins (True, 10, 2, <Direction.down: 4>)\n",
 912       "assizes (True, 6, 12, <Direction.up: 3>)\n",
 913       "inflow (True, 6, 5, <Direction.upright: 6>)\n",
 914       "depleting (True, 7, 1, <Direction.down: 4>)\n",
 915       "beeped (True, 11, 16, <Direction.left: 1>)\n",
 916       "reneges (True, 18, 17, <Direction.left: 1>)\n",
 917       "interning (True, 12, 13, <Direction.left: 1>)\n",
 918       "yellowish (True, 2, 10, <Direction.down: 4>)\n",
 919       "regicides (True, 19, 0, <Direction.right: 2>)\n",
 920       "eyelids (True, 18, 5, <Direction.right: 2>)\n",
 921       "cools (True, 7, 9, <Direction.upleft: 5>)\n",
 922       "orgy (True, 7, 18, <Direction.up: 3>)\n",
 923       "nifty (True, 8, 4, <Direction.up: 3>)\n",
 924       "knottier (True, 0, 9, <Direction.left: 1>)\n",
 925       "destroyers (True, 8, 0, <Direction.down: 4>)\n",
 926       "unfurls (True, 14, 18, <Direction.up: 3>)\n",
 927       "tinctured (True, 1, 0, <Direction.right: 2>)\n",
 928       "bigamy (True, 4, 2, <Direction.down: 4>)\n",
 929       "winos (True, 17, 14, <Direction.right: 2>)\n",
 930       "essays (True, 11, 9, <Direction.left: 1>)\n"
 931      ]
 932     }
 933    ],
 934    "source": [
 935     "for w in ws:\n",
 936     "    print(w, present(padded, w))"
 937    ]
 938   },
 939   {
 940    "cell_type": "code",
 941    "execution_count": 51,
 942    "metadata": {
 943     "collapsed": false
 944    },
 945    "outputs": [],
 946    "source": [
 947     "def decoys(grid, words, all_words, limit=60):\n",
 948     "    decoy_words = []\n",
 949     "    dlen_limit = max(len(w) for w in words)\n",
 950     "    while len(words) + len(decoy_words) < limit:\n",
 951     "        d = random.choice(all_words)\n",
 952     "        if d not in words and len(d) < dlen_limit and not present(grid, d)[0]:\n",
 953     "            decoy_words += [d]\n",
 954     "    return decoy_words"
 955    ]
 956   },
 957   {
 958    "cell_type": "code",
 959    "execution_count": 52,
 960    "metadata": {
 961     "collapsed": false
 962    },
 963    "outputs": [
 964     {
 965      "data": {
 966       "text/plain": [
 967        "['ditches',\n",
 968        " 'fuzes',\n",
 969        " 'antivirals',\n",
 970        " 'chronology',\n",
 971        " 'yacked',\n",
 972        " 'percentages',\n",
 973        " 'heftier',\n",
 974        " 'inimitably',\n",
 975        " 'conveys',\n",
 976        " 'remaindered',\n",
 977        " 'retaken',\n",
 978        " 'reckoned',\n",
 979        " 'emery',\n",
 980        " 'squats',\n",
 981        " 'tenderfoots',\n",
 982        " 'sociology',\n",
 983        " 'arbutuses',\n",
 984        " 'betook',\n",
 985        " 'coniferous',\n",
 986        " 'gambled',\n",
 987        " 'crouching']"
 988       ]
 989      },
 990      "execution_count": 52,
 991      "metadata": {},
 992      "output_type": "execute_result"
 993     }
 994    ],
 995    "source": [
 996     "ds = decoys(padded, ws, ws_words)\n",
 997     "ds"
 998    ]
 999   },
1000   {
1001    "cell_type": "code",
1002    "execution_count": 53,
1003    "metadata": {
1004     "collapsed": false,
1005     "scrolled": true
1006    },
1007    "outputs": [
1008     {
1009      "name": "stdout",
1010      "output_type": "stream",
1011      "text": [
1012       "freckled (False, 0, 0, <Direction.left: 1>)\n",
1013       "transcripts (False, 0, 0, <Direction.left: 1>)\n",
1014       "dinnering (False, 0, 0, <Direction.left: 1>)\n",
1015       "insulating (False, 0, 0, <Direction.left: 1>)\n",
1016       "regurgitates (False, 0, 0, <Direction.left: 1>)\n",
1017       "drouthes (False, 0, 0, <Direction.left: 1>)\n",
1018       "cocky (False, 0, 0, <Direction.left: 1>)\n",
1019       "stodgy (False, 0, 0, <Direction.left: 1>)\n",
1020       "bestrides (False, 0, 0, <Direction.left: 1>)\n",
1021       "perceives (False, 0, 0, <Direction.left: 1>)\n",
1022       "waned (False, 0, 0, <Direction.left: 1>)\n",
1023       "pisses (False, 0, 0, <Direction.left: 1>)\n",
1024       "alienating (False, 0, 0, <Direction.left: 1>)\n",
1025       "hyperbolas (False, 0, 0, <Direction.left: 1>)\n",
1026       "yeshivoth (False, 0, 0, <Direction.left: 1>)\n",
1027       "allured (False, 0, 0, <Direction.left: 1>)\n",
1028       "outstaying (False, 0, 0, <Direction.left: 1>)\n",
1029       "bureaus (False, 0, 0, <Direction.left: 1>)\n",
1030       "tragedians (False, 0, 0, <Direction.left: 1>)\n",
1031       "wooed (False, 0, 0, <Direction.left: 1>)\n",
1032       "unwary (False, 0, 0, <Direction.left: 1>)\n",
1033       "provoking (False, 0, 0, <Direction.left: 1>)\n",
1034       "curies (False, 0, 0, <Direction.left: 1>)\n",
1035       "deviltry (False, 0, 0, <Direction.left: 1>)\n",
1036       "wooly (False, 0, 0, <Direction.left: 1>)\n",
1037       "abysmally (False, 0, 0, <Direction.left: 1>)\n",
1038       "ladled (False, 0, 0, <Direction.left: 1>)\n",
1039       "tamable (False, 0, 0, <Direction.left: 1>)\n",
1040       "minors (False, 0, 0, <Direction.left: 1>)\n",
1041       "aortas (False, 0, 0, <Direction.left: 1>)\n",
1042       "souses (False, 0, 0, <Direction.left: 1>)\n",
1043       "heinously (False, 0, 0, <Direction.left: 1>)\n",
1044       "cardiac (False, 0, 0, <Direction.left: 1>)\n",
1045       "peons (True, 17, 1, <Direction.right: 2>)\n",
1046       "karate (False, 0, 0, <Direction.left: 1>)\n",
1047       "tansy (False, 0, 0, <Direction.left: 1>)\n",
1048       "unruly (False, 0, 0, <Direction.left: 1>)\n",
1049       "absently (False, 0, 0, <Direction.left: 1>)\n",
1050       "pads (False, 0, 0, <Direction.left: 1>)\n",
1051       "ditches (False, 0, 0, <Direction.left: 1>)\n",
1052       "fuzes (False, 0, 0, <Direction.left: 1>)\n",
1053       "antivirals (False, 0, 0, <Direction.left: 1>)\n",
1054       "chronology (False, 0, 0, <Direction.left: 1>)\n",
1055       "yacked (False, 0, 0, <Direction.left: 1>)\n",
1056       "percentages (False, 0, 0, <Direction.left: 1>)\n",
1057       "heftier (False, 0, 0, <Direction.left: 1>)\n",
1058       "inimitably (False, 0, 0, <Direction.left: 1>)\n",
1059       "conveys (False, 0, 0, <Direction.left: 1>)\n",
1060       "remaindered (False, 0, 0, <Direction.left: 1>)\n",
1061       "retaken (False, 0, 0, <Direction.left: 1>)\n",
1062       "reckoned (False, 0, 0, <Direction.left: 1>)\n",
1063       "emery (False, 0, 0, <Direction.left: 1>)\n",
1064       "squats (False, 0, 0, <Direction.left: 1>)\n",
1065       "tenderfoots (False, 0, 0, <Direction.left: 1>)\n",
1066       "sociology (False, 0, 0, <Direction.left: 1>)\n",
1067       "arbutuses (False, 0, 0, <Direction.left: 1>)\n",
1068       "betook (False, 0, 0, <Direction.left: 1>)\n",
1069       "coniferous (False, 0, 0, <Direction.left: 1>)\n",
1070       "gambled (False, 0, 0, <Direction.left: 1>)\n",
1071       "crouching (False, 0, 0, <Direction.left: 1>)\n"
1072      ]
1073     }
1074    ],
1075    "source": [
1076     "for w in ws + ds:\n",
1077     "    print(w, present(padded, w))"
1078    ]
1079   },
1080   {
1081    "cell_type": "code",
1082    "execution_count": 54,
1083    "metadata": {
1084     "collapsed": false
1085    },
1086    "outputs": [
1087     {
1088      "name": "stdout",
1089      "output_type": "stream",
1090      "text": [
1091       "ihaceglstcongealedim\n",
1092       "locnlanmecdwsieyieyp\n",
1093       "uslrbacimdmedruyirfo\n",
1094       "hyacaascsatireeaiefm\n",
1095       "epyatooheutryldpifum\n",
1096       "chiuantaedrivgeouihe\n",
1097       "diehehdftsionrsdmoil\n",
1098       "ylrnpsounaonhspadtrs\n",
1099       "linhegiglgirgcidagug\n",
1100       "gsaornesallliseilnwo\n",
1101       "nlnenigpsnnhllsrlins\n",
1102       "ityvuprergselipdohyi\n",
1103       "mstismocwduusngeygsw\n",
1104       "oextoooincnhksshsuci\n",
1105       "cmiiprvfanedcwuctook\n",
1106       "ersnptyiaclippingsur\n",
1107       "biauindcemostlysietd\n",
1108       "rflpebesmsskrepppsil\n",
1109       "yssorgnileereouepyna\n",
1110       "taeaeweathercockswgs\n",
1111       "36 words added;  7 directions\n",
1112       "Present: acceding alloys annulled becomingly chorusing chugs clashes clayier clippings congealed dullness espies firmest groovy groupers hogans huffy kiwis matins mostly outmoded perks pommels punitive reeling scouting sixty soppier soughing specifics syphilis taillights tromping unrepeatable weathercocks wispy\n",
1113       "Decoys: belittled buzzwords climbs congaed criterions drifters exteriors filial flattery gambolling haversacks insiders interferon leukaemia liabilities mavens mentalities padlocking ptarmigans puking retarded seaming skimpiness wanderers\n"
1114      ]
1115     }
1116    ],
1117    "source": [
1118     "g, ws = interesting_grid()\n",
1119     "p = pad_grid(g)\n",
1120     "ds = decoys(p, ws, ws_words)\n",
1121     "print(show_grid(p))\n",
1122     "print(len(ws), 'words added; ', len(set(present(g, w)[3] for w in ws)), 'directions')\n",
1123     "print('Present:', wcat(sorted(ws)))\n",
1124     "print('Decoys:', wcat(sorted(ds)))"
1125    ]
1126   },
1127   {
1128    "cell_type": "code",
1129    "execution_count": 55,
1130    "metadata": {
1131     "collapsed": false
1132    },
1133    "outputs": [
1134     {
1135      "name": "stdout",
1136      "output_type": "stream",
1137      "text": [
1138       "0\n",
1139       "1\n",
1140       "2\n",
1141       "3\n",
1142       "4\n",
1143       "5\n",
1144       "6\n",
1145       "7\n",
1146       "8\n",
1147       "9\n",
1148       "10\n",
1149       "11\n",
1150       "12\n",
1151       "13\n",
1152       "14\n",
1153       "15\n",
1154       "16\n",
1155       "17\n",
1156       "18\n",
1157       "19\n"
1158      ]
1159     }
1160    ],
1161    "source": [
1162     "for i in range(20):\n",
1163     "    print(i)\n",
1164     "    g, ws = interesting_grid()\n",
1165     "    p = pad_grid(g)\n",
1166     "    ds = decoys(p, ws, ws_words)\n",
1167     "    with open('wordsearch{:02}.txt'.format(i), 'w') as f:\n",
1168     "        f.write('20x20\\n')\n",
1169     "        f.write(show_grid(p))\n",
1170     "        f.write('\\n')\n",
1171     "        f.write(lcat(sorted(ws + ds)))\n",
1172     "    with open('wordsearch-solution{:02}.txt'.format(i), 'w') as f:\n",
1173     "        f.write('20x20\\n')\n",
1174     "        f.write(show_grid(g))\n",
1175     "        f.write('\\n')\n",
1176     "        f.write(lcat(sorted(ws)) + '\\n\\n')\n",
1177     "        f.write(lcat(sorted(ds)))"
1178    ]
1179   },
1180   {
1181    "cell_type": "code",
1182    "execution_count": null,
1183    "metadata": {
1184     "collapsed": true
1185    },
1186    "outputs": [],
1187    "source": []
1188   }
1189  ],
1190  "metadata": {
1191   "kernelspec": {
1192    "display_name": "Python 3",
1193    "language": "python",
1194    "name": "python3"
1195   },
1196   "language_info": {
1197    "codemirror_mode": {
1198     "name": "ipython",
1199     "version": 3
1200    },
1201    "file_extension": ".py",
1202    "mimetype": "text/x-python",
1203    "name": "python",
1204    "nbconvert_exporter": "python",
1205    "pygments_lexer": "ipython3",
1206    "version": "3.5.2+"
1207   }
1208  },
1209  "nbformat": 4,
1210  "nbformat_minor": 0
1211 }