X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=04-wordsearch%2Fwordsearch-creation.ipynb;fp=04-wordsearch%2Fwordsearch-creation.ipynb;h=0000000000000000000000000000000000000000;hb=76d7dcd5ad275f76e38a33a45e0fbdf2948c6b29;hp=8a81e740d1d85a109a7a6dd6ad45c2c4cf548056;hpb=3afec0b916cae5ebd717b3d15c71ff9205e144f1;p=ou-summer-of-code-2017.git

diff --git a/04-wordsearch/wordsearch-creation.ipynb b/04-wordsearch/wordsearch-creation.ipynb
deleted file mode 100644
index 8a81e74..0000000
--- a/04-wordsearch/wordsearch-creation.ipynb
+++ /dev/null
@@ -1,1345 +0,0 @@
-{
- "cells": [
-  {
-   "cell_type": "code",
-   "execution_count": 65,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "import string\n",
-    "import re\n",
-    "import random\n",
-    "import collections\n",
-    "import copy\n",
-    "\n",
-    "from enum import Enum\n",
-    "Direction = Enum('Direction', 'left right up down upleft upright downleft downright')\n",
-    "    \n",
-    "delta = {Direction.left: (0, -1),Direction.right: (0, 1), \n",
-    "         Direction.up: (-1, 0), Direction.down: (1, 0), \n",
-    "         Direction.upleft: (-1, -1), Direction.upright: (-1, 1), \n",
-    "         Direction.downleft: (1, -1), Direction.downright: (1, 1)}\n",
-    "\n",
-    "cat = ''.join\n",
-    "wcat = ' '.join\n",
-    "lcat = '\\n'.join"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 66,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "# all_words = [w.strip() for w in open('/usr/share/dict/british-english').readlines()\n",
-    "#             if all(c in string.ascii_lowercase for c in w.strip())]\n",
-    "# words = [w for w in all_words\n",
-    "#          if not any(w in w2 for w2 in all_words if w != w2)]\n",
-    "# open('wordsearch-words', 'w').write(lcat(words))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 67,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "# ws_words = [w.strip() for w in open('wordsearch-words').readlines()\n",
-    "#             if all(c in string.ascii_lowercase for c in w.strip())]\n",
-    "# ws_words[:10]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 68,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "ws_words = [w.strip() for w in open('/usr/share/dict/british-english').readlines()\n",
-    "            if all(c in string.ascii_lowercase for c in w.strip())]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 69,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def empty_grid(w, h):\n",
-    "    return [['.' for c in range(w)] for r in range(h)]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 70,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def show_grid(grid):\n",
-    "    return lcat(cat(r) for r in grid)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 71,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n",
-      "..........\n"
-     ]
-    }
-   ],
-   "source": [
-    "grid = empty_grid(10, 10)\n",
-    "print(show_grid(grid))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 72,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def indices(grid, r, c, l, d):\n",
-    "    dr, dc = delta[d]\n",
-    "    w = len(grid[0])\n",
-    "    h = len(grid)\n",
-    "    inds = [(r + i * dr, c + i * dc) for i in range(l)]\n",
-    "    return [(i, j) for i, j in inds\n",
-    "           if i >= 0\n",
-    "           if j >= 0\n",
-    "           if i < h\n",
-    "           if j < w]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 73,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def gslice(grid, r, c, l, d):\n",
-    "    return [grid[i][j] for i, j in indices(grid, r, c, l, d)]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 74,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def set_grid(grid, r, c, d, word):\n",
-    "    for (i, j), l in zip(indices(grid, r, c, len(word), d), word):\n",
-    "        grid[i][j] = l\n",
-    "    return grid"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 75,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "..........\n",
-      "..........\n",
-      "...t......\n",
-      "....e.....\n",
-      ".....s....\n",
-      "......t...\n",
-      ".......w..\n",
-      "........o.\n",
-      ".........r\n",
-      "..........\n"
-     ]
-    }
-   ],
-   "source": [
-    "set_grid(grid, 2, 3, Direction.downright, 'testword')\n",
-    "print(show_grid(grid))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 76,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "'..e.....'"
-      ]
-     },
-     "execution_count": 76,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "cat(gslice(grid, 3, 2, 15, Direction.right))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 77,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "<_sre.SRE_Match object; span=(0, 4), match='keen'>"
-      ]
-     },
-     "execution_count": 77,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "re.match(cat(gslice(grid, 3, 2, 4, Direction.right)), 'keen')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 78,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "<_sre.SRE_Match object; span=(0, 3), match='kee'>"
-      ]
-     },
-     "execution_count": 78,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "re.match(cat(gslice(grid, 3, 2, 3, Direction.right)), 'keen')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 79,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "re.fullmatch(cat(gslice(grid, 3, 2, 3, Direction.right)), 'keen')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 80,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "re.match(cat(gslice(grid, 3, 2, 4, Direction.right)), 'kine')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 81,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def could_add(grid, r, c, d, word):\n",
-    "    s = gslice(grid, r, c, len(word), d)\n",
-    "    return re.fullmatch(cat(s), word)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 82,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "<_sre.SRE_Match object; span=(0, 4), match='keen'>"
-      ]
-     },
-     "execution_count": 82,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "could_add(grid, 3, 2, Direction.right, 'keen')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 83,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "could_add(grid, 3, 2, Direction.right, 'kine')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 84,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "<Direction.downleft: 7>"
-      ]
-     },
-     "execution_count": 84,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "random.choice(list(Direction))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 129,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def fill_grid(grid, words, word_count, max_attempts=10000):\n",
-    "    attempts = 0\n",
-    "    added_words = []\n",
-    "    w = len(grid[0])\n",
-    "    h = len(grid)\n",
-    "    while len(added_words) < word_count and attempts < max_attempts:\n",
-    "        attempts += 1\n",
-    "        r = random.randrange(w)\n",
-    "        c = random.randrange(h)\n",
-    "        word = random.choice(words)\n",
-    "        d = random.choice(list(Direction))\n",
-    "        if len(word) >=4 and not any(word in w2 for w2 in added_words) and could_add(grid, r, c, d, word):\n",
-    "            set_grid(grid, r, c, d, word)\n",
-    "            added_words += [word]\n",
-    "            attempts = 0\n",
-    "    return grid, added_words"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 86,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "40"
-      ]
-     },
-     "execution_count": 86,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "g = empty_grid(20, 20)\n",
-    "g, ws = fill_grid(g, ws_words, 40)\n",
-    "len(ws)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 87,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "l.fiestasrsnorffas..\n",
-      "a....s..e.a.cawing..\n",
-      "c..gt.dv.re.strongly\n",
-      "i..n..aecmbp....y...\n",
-      "m.eo.uthzoa.of..l.s.\n",
-      "od.lq.esozslhhlyo.k.\n",
-      "ns.e.r.se.ureanoh.r.\n",
-      "o.wby.t.aw.foin.u.u.\n",
-      "ca.o....i.a.to.d.rms\n",
-      "en..l...lerrs.d.i.sk\n",
-      "no...l..i.snalgarn.n\n",
-      "un....a.crappiest.gi\n",
-      ".y.....mdepraved..dw\n",
-      ".mgniggolricochet.ey\n",
-      ".o..pensivelyibmozil\n",
-      ".u.......curd.....fd\n",
-      ".sseitudlevehsid..id\n",
-      "...litchis..romut.ri\n",
-      ".understands......et\n",
-      "....nagilooh......v.\n",
-      "40 words added\n",
-      "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"
-     ]
-    }
-   ],
-   "source": [
-    "print(show_grid(g))\n",
-    "print(len(ws), 'words added')\n",
-    "print(wcat(ws))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 88,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def present(grid, word):\n",
-    "    w = len(grid[0])\n",
-    "    h = len(grid)\n",
-    "    for r in range(h):\n",
-    "        for c in range(w):\n",
-    "            for d in Direction:\n",
-    "                if cat(gslice(grid, r, c, len(word), d)) == word:\n",
-    "                    return True, r, c, d\n",
-    "    return False, 0, 0, list(Direction)[0]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 89,
-   "metadata": {
-    "collapsed": false,
-    "scrolled": true
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "understands (True, 18, 1, <Direction.right: 2>)\n",
-      "crappiest (True, 11, 8, <Direction.right: 2>)\n",
-      "archery (True, 1, 10, <Direction.downleft: 7>)\n",
-      "mallows (True, 12, 7, <Direction.upleft: 5>)\n",
-      "depraved (True, 12, 8, <Direction.right: 2>)\n",
-      "cawing (True, 1, 12, <Direction.right: 2>)\n",
-      "rawest (True, 9, 11, <Direction.upleft: 5>)\n",
-      "curd (True, 15, 9, <Direction.right: 2>)\n",
-      "tiny (True, 8, 12, <Direction.upright: 6>)\n",
-      "tiddlywinks (True, 18, 19, <Direction.up: 3>)\n",
-      "fiestas (True, 0, 2, <Direction.right: 2>)\n",
-      "zombi (True, 14, 17, <Direction.left: 1>)\n",
-      "duties (True, 16, 7, <Direction.left: 1>)\n",
-      "ricochet (True, 13, 9, <Direction.right: 2>)\n",
-      "uneconomical (True, 11, 0, <Direction.up: 3>)\n",
-      "hope (True, 5, 13, <Direction.upleft: 5>)\n",
-      "litchis (True, 17, 3, <Direction.right: 2>)\n",
-      "strongly (True, 2, 12, <Direction.right: 2>)\n",
-      "verified (True, 19, 18, <Direction.up: 3>)\n",
-      "logging (True, 13, 8, <Direction.left: 1>)\n",
-      "handing (True, 5, 12, <Direction.downright: 8>)\n",
-      "anonymous (True, 8, 1, <Direction.down: 4>)\n",
-      "quaver (True, 5, 4, <Direction.upright: 6>)\n",
-      "flours (True, 4, 13, <Direction.downright: 8>)\n",
-      "boost (True, 3, 10, <Direction.downleft: 7>)\n",
-      "holy (True, 6, 16, <Direction.up: 3>)\n",
-      "saffrons (True, 0, 17, <Direction.left: 1>)\n",
-      "errs (True, 9, 9, <Direction.right: 2>)\n",
-      "hooligan (True, 19, 11, <Direction.left: 1>)\n",
-      "male (True, 3, 9, <Direction.downright: 8>)\n",
-      "belong (True, 7, 3, <Direction.up: 3>)\n",
-      "tumor (True, 17, 16, <Direction.left: 1>)\n",
-      "dishevel (True, 16, 15, <Direction.left: 1>)\n",
-      "fuzzed (True, 7, 11, <Direction.upleft: 5>)\n",
-      "raglans (True, 10, 16, <Direction.left: 1>)\n",
-      "pensively (True, 14, 4, <Direction.right: 2>)\n",
-      "murks (True, 8, 18, <Direction.up: 3>)\n",
-      "dents (True, 5, 1, <Direction.upright: 6>)\n",
-      "cilia (True, 11, 8, <Direction.up: 3>)\n",
-      "doors (True, 9, 14, <Direction.upleft: 5>)\n"
-     ]
-    }
-   ],
-   "source": [
-    "for w in ws:\n",
-    "    print(w, present(g, w))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 125,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def interesting(grid, words):\n",
-    "    dirs = set(present(grid, w)[3] for w in words)\n",
-    "    return len(words) > 40 and len(dirs) + 1 >= len(delta)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 126,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "False"
-      ]
-     },
-     "execution_count": 126,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "interesting(g, ws)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 131,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def interesting_grid():\n",
-    "    boring = True\n",
-    "    while boring:\n",
-    "        grid = empty_grid(20, 20)\n",
-    "        grid, words = fill_grid(grid, ws_words, 80)\n",
-    "        boring = not interesting(grid, words)\n",
-    "    return grid, words"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 132,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "....gnixof...keem...\n",
-      "feihc.spollawvase..s\n",
-      "p.h.shs..snetsafnun.\n",
-      "aeiy.adt..plehdowned\n",
-      "rmcfmzhennaturali.h.\n",
-      "abkake.pteebyelawsay\n",
-      "dlcweln.lnmvrdrawllr\n",
-      "ealnes.s.aeeieslaroe\n",
-      ".zaelreffidclwl...gs\n",
-      ".omtisadeelbst.bg.ei\n",
-      ".noantr...tunet.o.nm\n",
-      "serigamchamoixbemnsb\n",
-      "sd.tnuu..lleterls..e\n",
-      "e.dounf..dekcalsu..s\n",
-      "gyegtcfknobetatser.t\n",
-      "rlkeshskcelf..ploptr\n",
-      "alon.l..sriahdawnsgi\n",
-      "lac..y..gnittilps.od\n",
-      ".eyeball..denedragse\n",
-      ".r..ygnamsecstirg.hs\n",
-      "57 words added;  7 directions\n",
-      "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"
-     ]
-    }
-   ],
-   "source": [
-    "g, ws = interesting_grid()\n",
-    "print(show_grid(g))\n",
-    "print(len(ws), 'words added; ', len(set(present(g, w)[3] for w in ws)), 'directions')\n",
-    "print(wcat(ws))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 94,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def datafile(name, sep='\\t'):\n",
-    "    \"\"\"Read key,value pairs from file.\n",
-    "    \"\"\"\n",
-    "    with open(name) as f:\n",
-    "        for line in f:\n",
-    "            splits = line.split(sep)\n",
-    "            yield [splits[0], int(splits[1])]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 95,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def normalise(frequencies):\n",
-    "    \"\"\"Scale a set of frequencies so they sum to one\n",
-    "    \n",
-    "    >>> sorted(normalise({1: 1, 2: 0}).items())\n",
-    "    [(1, 1.0), (2, 0.0)]\n",
-    "    >>> sorted(normalise({1: 1, 2: 1}).items())\n",
-    "    [(1, 0.5), (2, 0.5)]\n",
-    "    >>> sorted(normalise({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS\n",
-    "    [(1, 0.333...), (2, 0.333...), (3, 0.333...)]\n",
-    "    >>> sorted(normalise({1: 1, 2: 2, 3: 1}).items())\n",
-    "    [(1, 0.25), (2, 0.5), (3, 0.25)]\n",
-    "    \"\"\"\n",
-    "    length = sum(f for f in frequencies.values())\n",
-    "    return collections.defaultdict(int, ((k, v / length) \n",
-    "        for (k, v) in frequencies.items()))\n"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 96,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "english_counts = collections.Counter(dict(datafile('count_1l.txt')))\n",
-    "normalised_english_counts = normalise(english_counts)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 97,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "wordsearch_counts = collections.Counter(cat(ws_words))\n",
-    "normalised_wordsearch_counts = normalise(wordsearch_counts)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 118,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "normalised_wordsearch_counts = normalise(collections.Counter(normalised_wordsearch_counts) + collections.Counter({l: 0.05 for l in string.ascii_lowercase}))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 98,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def weighted_choice(d):\n",
-    "    \"\"\"Generate random item from a dictionary of item counts\n",
-    "    \"\"\"\n",
-    "    target = random.uniform(0, sum(d.values()))\n",
-    "    cuml = 0.0\n",
-    "    for (l, p) in d.items():\n",
-    "        cuml += p\n",
-    "        if cuml > target:\n",
-    "            return l\n",
-    "    return None\n",
-    "\n",
-    "def random_english_letter():\n",
-    "    \"\"\"Generate a random letter based on English letter counts\n",
-    "    \"\"\"\n",
-    "    return weighted_choice(normalised_english_counts)\n",
-    "\n",
-    "def random_wordsearch_letter():\n",
-    "    \"\"\"Generate a random letter based on wordsearch letter counts\n",
-    "    \"\"\"\n",
-    "    return weighted_choice(normalised_wordsearch_counts)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 99,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "'aaaaaaaaaabcdddeeeeeeeeeeeefffffgghhhhhhhhhiiiiiiikllmnnnnnnnooooooooprrrrssssssssssssttttttuuvwwwww'"
-      ]
-     },
-     "execution_count": 99,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "cat(sorted(random_english_letter() for i in range(100)))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 100,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "'aaaaaaccccdddeeeeeeeeeeeeeeeeeeeffgghhiiiiikkklllmmmnnnnnnooooooppprrrrrrrrssssssssttttttuuuuuuvwyyy'"
-      ]
-     },
-     "execution_count": 100,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "cat(sorted(random_wordsearch_letter() for i in range(100)))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 101,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "'e'"
-      ]
-     },
-     "execution_count": 101,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "random_wordsearch_letter()"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 102,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def pad_grid(g0):\n",
-    "    grid = copy.deepcopy(g0)\n",
-    "    w = len(grid[0])\n",
-    "    h = len(grid)\n",
-    "    for r in range(h):\n",
-    "        for c in range(w):\n",
-    "            if grid[r][c] == '.':\n",
-    "                grid[r][c] = random_wordsearch_letter()\n",
-    "    return grid"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 103,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "nwtautoimmuneeyinsdl\n",
-      "majorlyerasescmcider\n",
-      "edthrallednxlcawoeaa\n",
-      "gnizeensbnahwwgpsksr\n",
-      "rmisrksiosgiitndtaep\n",
-      "rioigoeopeglbnegsesu\n",
-      "esurnrbdifecihtniust\n",
-      "eeauuieimddlgiiigqan\n",
-      "srcplooscrlufestosve\n",
-      "pdcasmhemaonrgialcel\n",
-      "lguvrepkcrekennronru\n",
-      "ensesmtiesrtiogocwcr\n",
-      "niadpnetulasgpdfeesi\n",
-      "dgthgreoonavhsorinyv\n",
-      "inilpehmnrnntuaeeoae\n",
-      "dioesnmnocstennpolcm\n",
-      "etniwvredwtidnmfdshm\n",
-      "sgsoaarunyyoslurstts\n",
-      "tetoyisimdmaderetlaf\n",
-      "ettflightasnlclquasi\n"
-     ]
-    }
-   ],
-   "source": [
-    "padded = pad_grid(g)\n",
-    "print(show_grid(padded))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 104,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "...autoimmune.......\n",
-      "majorlyerases.m..d..\n",
-      "..thralledn...a..e..\n",
-      "gnizeens..a..wg.sk..\n",
-      ".m.s..si..g.i.ndtae.\n",
-      ".i.ig.eo..gl..egses.\n",
-      ".s.rnrbd..ec.htniust\n",
-      ".eauuiei.ddlg.iigqan\n",
-      "srcploos..lufestosve\n",
-      "p.casmhe.aonrgial.el\n",
-      "lguv.ep.crekennro.ru\n",
-      "ense.m.i.s..iogoc.cr\n",
-      "niad.netulasgp.fee.i\n",
-      "dgt..reo....hs.r.nyv\n",
-      "ini..ehm....t.ae.oa.\n",
-      "dio..nm.o...en.p.lc.\n",
-      "etn.w..e.w..d.....h.\n",
-      "s.so....n.yoslurs.t.\n",
-      "t.t......dmaderetlaf\n",
-      "...flight.s.l..quasi\n"
-     ]
-    }
-   ],
-   "source": [
-    "print(show_grid(g))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 105,
-   "metadata": {
-    "collapsed": false,
-    "scrolled": true
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "thralled (True, 2, 2, <Direction.right: 2>)\n",
-      "slung (True, 9, 4, <Direction.up: 3>)\n",
-      "freighted (True, 8, 12, <Direction.down: 4>)\n",
-      "townhouse (True, 18, 2, <Direction.upright: 6>)\n",
-      "salute (True, 12, 11, <Direction.left: 1>)\n",
-      "phoebes (True, 10, 6, <Direction.up: 3>)\n",
-      "faltered (True, 18, 19, <Direction.left: 1>)\n",
-      "laywomen (True, 19, 12, <Direction.upleft: 5>)\n",
-      "squeaked (True, 8, 17, <Direction.up: 3>)\n",
-      "perforating (True, 15, 15, <Direction.up: 3>)\n",
-      "iodise (True, 4, 7, <Direction.down: 4>)\n",
-      "lacier (True, 8, 10, <Direction.downleft: 7>)\n",
-      "autoimmune (True, 0, 3, <Direction.right: 2>)\n",
-      "tinging (True, 16, 1, <Direction.up: 3>)\n",
-      "snagged (True, 1, 10, <Direction.down: 4>)\n",
-      "splendidest (True, 8, 0, <Direction.down: 4>)\n",
-      "roughed (True, 10, 9, <Direction.upright: 6>)\n",
-      "crevasse (True, 11, 18, <Direction.up: 3>)\n",
-      "lone (True, 15, 17, <Direction.up: 3>)\n",
-      "ecologists (True, 12, 16, <Direction.up: 3>)\n",
-      "sponge (True, 13, 13, <Direction.up: 3>)\n",
-      "magnetising (True, 1, 14, <Direction.down: 4>)\n",
-      "sneezing (True, 3, 7, <Direction.left: 1>)\n",
-      "virulent (True, 13, 19, <Direction.up: 3>)\n",
-      "flight (True, 19, 3, <Direction.right: 2>)\n",
-      "sirup (True, 4, 3, <Direction.down: 4>)\n",
-      "yacht (True, 13, 18, <Direction.down: 4>)\n",
-      "random (True, 13, 15, <Direction.downleft: 7>)\n",
-      "accusations (True, 7, 2, <Direction.down: 4>)\n",
-      "wiled (True, 3, 13, <Direction.downleft: 7>)\n",
-      "paved (True, 8, 3, <Direction.down: 4>)\n",
-      "majorly (True, 1, 0, <Direction.right: 2>)\n",
-      "miser (True, 4, 1, <Direction.down: 4>)\n",
-      "memoir (True, 11, 5, <Direction.up: 3>)\n",
-      "emends (True, 14, 5, <Direction.downright: 8>)\n",
-      "slurs (True, 17, 12, <Direction.right: 2>)\n",
-      "clunk (True, 6, 11, <Direction.down: 4>)\n",
-      "erases (True, 1, 7, <Direction.right: 2>)\n",
-      "quasi (True, 19, 15, <Direction.right: 2>)\n"
-     ]
-    }
-   ],
-   "source": [
-    "for w in ws:\n",
-    "    print(w, present(padded, w))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 141,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [],
-   "source": [
-    "def decoys(grid, words, all_words, limit=100):\n",
-    "    decoy_words = []\n",
-    "    dlen_limit = max(len(w) for w in words)\n",
-    "    while len(words) + len(decoy_words) < limit:\n",
-    "        d = random.choice(all_words)\n",
-    "        if d not in words and len(d) >= 4 and len(d) <= dlen_limit and not present(grid, d)[0]:\n",
-    "            decoy_words += [d]\n",
-    "    return decoy_words"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 135,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "['incisor',\n",
-       " 'steeled',\n",
-       " 'immobility',\n",
-       " 'undertakings',\n",
-       " 'exhorts',\n",
-       " 'hairnet',\n",
-       " 'placarded',\n",
-       " 'sackful',\n",
-       " 'covenanting',\n",
-       " 'invoking',\n",
-       " 'deltas',\n",
-       " 'nonplus',\n",
-       " 'exactest',\n",
-       " 'eggs',\n",
-       " 'tercentenary',\n",
-       " 'angelic',\n",
-       " 'relearning',\n",
-       " 'ardors',\n",
-       " 'imprints',\n",
-       " 'chamoix',\n",
-       " 'governance',\n",
-       " 'rampart',\n",
-       " 'estuary',\n",
-       " 'poltroons',\n",
-       " 'expect',\n",
-       " 'restaurant',\n",
-       " 'ashrams',\n",
-       " 'illuminates',\n",
-       " 'reprises',\n",
-       " 'seismology',\n",
-       " 'announce',\n",
-       " 'tomorrows',\n",
-       " 'carcinogenics',\n",
-       " 'duplex',\n",
-       " 'transmitters',\n",
-       " 'prosier',\n",
-       " 'anther',\n",
-       " 'masticates',\n",
-       " 'raunchy',\n",
-       " 'briefs',\n",
-       " 'poniard',\n",
-       " 'daunted',\n",
-       " 'topmasts',\n",
-       " 'mynas']"
-      ]
-     },
-     "execution_count": 135,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "ds = decoys(padded, ws, ws_words)\n",
-    "ds"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 108,
-   "metadata": {
-    "collapsed": false,
-    "scrolled": true
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "thralled (True, 2, 2, <Direction.right: 2>)\n",
-      "slung (True, 9, 4, <Direction.up: 3>)\n",
-      "freighted (True, 8, 12, <Direction.down: 4>)\n",
-      "townhouse (True, 18, 2, <Direction.upright: 6>)\n",
-      "salute (True, 12, 11, <Direction.left: 1>)\n",
-      "phoebes (True, 10, 6, <Direction.up: 3>)\n",
-      "faltered (True, 18, 19, <Direction.left: 1>)\n",
-      "laywomen (True, 19, 12, <Direction.upleft: 5>)\n",
-      "squeaked (True, 8, 17, <Direction.up: 3>)\n",
-      "perforating (True, 15, 15, <Direction.up: 3>)\n",
-      "iodise (True, 4, 7, <Direction.down: 4>)\n",
-      "lacier (True, 8, 10, <Direction.downleft: 7>)\n",
-      "autoimmune (True, 0, 3, <Direction.right: 2>)\n",
-      "tinging (True, 16, 1, <Direction.up: 3>)\n",
-      "snagged (True, 1, 10, <Direction.down: 4>)\n",
-      "splendidest (True, 8, 0, <Direction.down: 4>)\n",
-      "roughed (True, 10, 9, <Direction.upright: 6>)\n",
-      "crevasse (True, 11, 18, <Direction.up: 3>)\n",
-      "lone (True, 15, 17, <Direction.up: 3>)\n",
-      "ecologists (True, 12, 16, <Direction.up: 3>)\n",
-      "sponge (True, 13, 13, <Direction.up: 3>)\n",
-      "magnetising (True, 1, 14, <Direction.down: 4>)\n",
-      "sneezing (True, 3, 7, <Direction.left: 1>)\n",
-      "virulent (True, 13, 19, <Direction.up: 3>)\n",
-      "flight (True, 19, 3, <Direction.right: 2>)\n",
-      "sirup (True, 4, 3, <Direction.down: 4>)\n",
-      "yacht (True, 13, 18, <Direction.down: 4>)\n",
-      "random (True, 13, 15, <Direction.downleft: 7>)\n",
-      "accusations (True, 7, 2, <Direction.down: 4>)\n",
-      "wiled (True, 3, 13, <Direction.downleft: 7>)\n",
-      "paved (True, 8, 3, <Direction.down: 4>)\n",
-      "majorly (True, 1, 0, <Direction.right: 2>)\n",
-      "miser (True, 4, 1, <Direction.down: 4>)\n",
-      "memoir (True, 11, 5, <Direction.up: 3>)\n",
-      "emends (True, 14, 5, <Direction.downright: 8>)\n",
-      "slurs (True, 17, 12, <Direction.right: 2>)\n",
-      "clunk (True, 6, 11, <Direction.down: 4>)\n",
-      "erases (True, 1, 7, <Direction.right: 2>)\n",
-      "quasi (True, 19, 15, <Direction.right: 2>)\n",
-      "leakiest (False, 0, 0, <Direction.left: 1>)\n",
-      "lumpiest (False, 0, 0, <Direction.left: 1>)\n",
-      "bastion (False, 0, 0, <Direction.left: 1>)\n",
-      "steamier (False, 0, 0, <Direction.left: 1>)\n",
-      "elegant (False, 0, 0, <Direction.left: 1>)\n",
-      "slogging (False, 0, 0, <Direction.left: 1>)\n",
-      "rejects (False, 0, 0, <Direction.left: 1>)\n",
-      "gaze (False, 0, 0, <Direction.left: 1>)\n",
-      "swopping (False, 0, 0, <Direction.left: 1>)\n",
-      "resonances (False, 0, 0, <Direction.left: 1>)\n",
-      "treasonous (False, 0, 0, <Direction.left: 1>)\n",
-      "corm (False, 0, 0, <Direction.left: 1>)\n",
-      "abuses (False, 0, 0, <Direction.left: 1>)\n",
-      "toga (False, 0, 0, <Direction.left: 1>)\n",
-      "upcountry (False, 0, 0, <Direction.left: 1>)\n",
-      "scrawled (False, 0, 0, <Direction.left: 1>)\n",
-      "cellar (False, 0, 0, <Direction.left: 1>)\n",
-      "skinflint (False, 0, 0, <Direction.left: 1>)\n",
-      "wasteland (False, 0, 0, <Direction.left: 1>)\n",
-      "madman (False, 0, 0, <Direction.left: 1>)\n",
-      "lash (False, 0, 0, <Direction.left: 1>)\n"
-     ]
-    }
-   ],
-   "source": [
-    "for w in ws + ds:\n",
-    "    print(w, present(padded, w))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 142,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      ".strigger.essegassum\n",
-      "acselacs.tapri..pgcr\n",
-      "moeclienterr.em.uaie\n",
-      "apisearsclmo.kvpmntp\n",
-      "lebpg..ohlucfaeaespe\n",
-      "ifbi.ev.aafeesr.urol\n",
-      "riae.el.iwfse.o.oqss\n",
-      "evcsr...n..sd.dv..r.\n",
-      "pestdewels..e.aw.ut.\n",
-      "mrlimmersionrl.ob.e.\n",
-      "iyllatnemadnufwls.nl\n",
-      "..sdboomovulesivl.ri\n",
-      ".eiepsreggij.tdeljif\n",
-      "dkwn.atread..oereiat\n",
-      "uais..efile..pnihlhi\n",
-      "rhkripelyt.illsnst.n\n",
-      "iweekendunotablete.g\n",
-      "nfondlyrytsenohsuo..\n",
-      "g.mriffa....naysnp..\n",
-      ".meatspoodle.within.\n",
-      "cstriggerpessegassum\n",
-      "acselacsytapriijpgcr\n",
-      "moeclienterrtemnuaie\n",
-      "apisearsclmookvpmntp\n",
-      "lebpgatohlucfaeaespe\n",
-      "ifbisevxaafeesrlurol\n",
-      "riaehelciwfseioioqss\n",
-      "evcsrkuynpasdfdvetrq\n",
-      "pestdewelsniegawkutd\n",
-      "mrlimmersionrloobuel\n",
-      "iyllatnemadnufwlsanl\n",
-      "dwsdboomovulesivlyri\n",
-      "oeiepsreggijntdeljif\n",
-      "dkwnkatreadvnoereiat\n",
-      "uaiscuefilehapnihlhi\n",
-      "rhkripelytqillsnsten\n",
-      "iweekendunotabletetg\n",
-      "nfondlyrytsenohsuocc\n",
-      "gemriffanternaysnpef\n",
-      "bmeatspoodleswithing\n",
-      "62 words added;  8 directions\n",
-      "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",
-      "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"
-     ]
-    }
-   ],
-   "source": [
-    "g, ws = interesting_grid()\n",
-    "p = pad_grid(g)\n",
-    "ds = decoys(p, ws, ws_words)\n",
-    "print(show_grid(g))\n",
-    "print(show_grid(p))\n",
-    "print(len(ws), 'words added; ', len(set(present(g, w)[3] for w in ws)), 'directions')\n",
-    "print('Present:', wcat(sorted(ws)))\n",
-    "print('Decoys:', wcat(sorted(ds)))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 143,
-   "metadata": {
-    "collapsed": false,
-    "scrolled": true
-   },
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "0\n",
-      "1\n",
-      "2\n",
-      "3\n",
-      "4\n",
-      "5\n",
-      "6\n",
-      "7\n",
-      "8\n",
-      "9\n",
-      "10\n",
-      "11\n",
-      "12\n",
-      "13\n",
-      "14\n",
-      "15\n",
-      "16\n",
-      "17\n",
-      "18\n",
-      "19\n",
-      "20\n",
-      "21\n",
-      "22\n",
-      "23\n",
-      "24\n",
-      "25\n",
-      "26\n",
-      "27\n",
-      "28\n",
-      "29\n",
-      "30\n",
-      "31\n",
-      "32\n",
-      "33\n",
-      "34\n",
-      "35\n",
-      "36\n",
-      "37\n",
-      "38\n",
-      "39\n",
-      "40\n",
-      "41\n",
-      "42\n",
-      "43\n",
-      "44\n",
-      "45\n",
-      "46\n",
-      "47\n",
-      "48\n",
-      "49\n",
-      "50\n",
-      "51\n",
-      "52\n",
-      "53\n",
-      "54\n",
-      "55\n",
-      "56\n",
-      "57\n",
-      "58\n",
-      "59\n",
-      "60\n",
-      "61\n",
-      "62\n",
-      "63\n",
-      "64\n",
-      "65\n",
-      "66\n",
-      "67\n",
-      "68\n",
-      "69\n",
-      "70\n",
-      "71\n",
-      "72\n",
-      "73\n",
-      "74\n",
-      "75\n",
-      "76\n",
-      "77\n",
-      "78\n",
-      "79\n",
-      "80\n",
-      "81\n",
-      "82\n",
-      "83\n",
-      "84\n",
-      "85\n",
-      "86\n",
-      "87\n",
-      "88\n",
-      "89\n",
-      "90\n",
-      "91\n",
-      "92\n",
-      "93\n",
-      "94\n",
-      "95\n",
-      "96\n",
-      "97\n",
-      "98\n",
-      "99\n"
-     ]
-    }
-   ],
-   "source": [
-    "for i in range(100):\n",
-    "    print(i)\n",
-    "    g, ws = interesting_grid()\n",
-    "    p = pad_grid(g)\n",
-    "    ds = decoys(p, ws, ws_words)\n",
-    "    with open('wordsearch{:02}.txt'.format(i), 'w') as f:\n",
-    "        f.write('20x20\\n')\n",
-    "        f.write(show_grid(p))\n",
-    "        f.write('\\n')\n",
-    "        f.write(lcat(sorted(ws + ds)))\n",
-    "    with open('wordsearch-solution{:02}.txt'.format(i), 'w') as f:\n",
-    "        f.write('20x20\\n')\n",
-    "        f.write(show_grid(g))\n",
-    "        f.write('\\n')\n",
-    "        f.write(lcat(sorted(ws)) + '\\n\\n')\n",
-    "        f.write(lcat(sorted(ds)))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": null,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": []
-  }
- ],
- "metadata": {
-  "kernelspec": {
-   "display_name": "Python 3",
-   "language": "python",
-   "name": "python3"
-  },
-  "language_info": {
-   "codemirror_mode": {
-    "name": "ipython",
-    "version": 3
-   },
-   "file_extension": ".py",
-   "mimetype": "text/x-python",
-   "name": "python",
-   "nbconvert_exporter": "python",
-   "pygments_lexer": "ipython3",
-   "version": "3.5.2"
-  }
- },
- "nbformat": 4,
- "nbformat_minor": 0
-}