--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Wordsearch\n",
+ "Given a text file, consisting of three parts (a grid size, a grid, and a list of words), find:\n",
+ "* the words present in the grid, \n",
+ "* the longest word present in the grid, \n",
+ "* the number of words not present in the grid, \n",
+ "* the longest word not present that can be formed from the leftover letters\n",
+ "\n",
+ "The only words that need be considered are the ones given in the list in the puzzle input.\n",
+ "\n",
+ "The puzzle consists of:\n",
+ "1. A line consisting of _w_`x`_h_, where _w_ and _h_ are integers giving the width and height of the grid.\n",
+ "2. The grid itself, consisting of _h_ lines each of _w_ letters.\n",
+ "3. A list of words, one word per line, of arbitrary length. "
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example\n",
+ "\n",
+ "\n",
+ "`...p.mown.\n",
+ ".sdse..ee.\n",
+ ".e.elad.cr\n",
+ "pi.dtir.ah\n",
+ "rzsiwovspu\n",
+ "oawh.kieab\n",
+ "brow.c.rda\n",
+ "ecnotops.r\n",
+ "d.kc.d...b\n",
+ ".staple...`\n",
+ "\n",
+ "```\n",
+ "fhjpamownq\n",
+ "wsdseuqeev\n",
+ "ieaeladhcr\n",
+ "piedtiriah\n",
+ "rzsiwovspu\n",
+ "oawhakieab\n",
+ "browpcfrda\n",
+ "ecnotopssr\n",
+ "dikchdnpnb\n",
+ "bstapleokr\n",
+ "```\n",
+ "\n",
+ "14 words added; 6 directions\n",
+ "\n",
+ "Present: apace cowhides crazies dock knows lived mown pears probed rhubarb rioted staple tops wide\n",
+ "\n",
+ "Decoys: adapting bombing boor brick cackles carnal casino chaplets chump coaster coccyxes coddle collies creels crumbled cunt curds curled curlier deepen demeanor dicier dowses ensuing faddish fest fickler foaming gambol garoting gliding gristle grunts guts ibex impugns instants kielbasy lanyard loamier lugs market meanly minuend misprint mitts molested moonshot mucking oaks olives orgasmic pastrami perfect proceed puckered quashed refined regards retraces revel ridges ringlet scoff shinier siren solaria sprain sunder sunup tamped tapes thirds throw tiller times trains tranquil transfix typesets uric wariness welts whimsy winced winced\n",
+ "\n",
+ "Decoys: fickler, adapting, chump, foaming, molested, carnal, crumbled, guts, minuend, bombing, winced, coccyxes, solaria, shinier, cackles\n",
+ "\n",
+ "All words: adapting, apace, bombing, cackles, carnal, chump, coccyxes, cowhides, crazies, crumbled, dock, fickler, foaming, guts, knows, lived, minuend, molested, mown, pears, probed, rhubarb, rioted, shinier, solaria, staple, tops, wide, winced\n",
+ "\n",
+ "Directions: [('probed', '`(True, 3, 0, <Direction.down: 4>)`'), ('staple', '`(True, 9, 1, <Direction.right: 2>)`'), ('rioted', '`(True, 6, 7, <Direction.upleft: 5>)`'), ('cowhides', '`(True, 8, 3, <Direction.up: 3>)`'), ('tops', '`(True, 7, 4, <Direction.right: 2>)`'), ('knows', '`(True, 8, 2, <Direction.up: 3>)`'), ('lived', '`(True, 2, 4, <Direction.downright: 8>)`'), ('rhubarb', '`(True, 2, 9, <Direction.down: 4>)`'), ('crazies', '`(True, 7, 1, <Direction.up: 3>)`'), ('dock', '`(True, 8, 5, <Direction.up: 3>)`'), ('apace', '`(True, 5, 8, <Direction.up: 3>)`'), ('mown', '`(True, 0, 5, <Direction.right: 2>)`'), ('pears', '`(True, 0, 3, <Direction.downright: 8>)`'), ('wide', '`(True, 4, 4, <Direction.upright: 6>)`')]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import string\n",
+ "import re\n",
+ "import collections\n",
+ "import copy\n",
+ "import os\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": 5,
+ "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": 6,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def show_grid(grid):\n",
+ " return lcat(cat(r) for r in grid)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "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": 8,
+ "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": 9,
+ "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": 10,
+ "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": 158,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def present_many(grid, words):\n",
+ " w = len(grid[0])\n",
+ " h = len(grid)\n",
+ " wordlens = set(len(w) for w in words)\n",
+ " presences = []\n",
+ " for r in range(h):\n",
+ " for c in range(w):\n",
+ " for d in Direction:\n",
+ " for wordlen in wordlens:\n",
+ " word = cat(gslice(grid, r, c, wordlen, d))\n",
+ " if word in words:\n",
+ " presences += [(word, r, c, d)]\n",
+ " return set(presences)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 141,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# def present_many(grid, words):\n",
+ "# w = len(grid[0])\n",
+ "# h = len(grid)\n",
+ "# wordlens = set(len(w) for w in words)\n",
+ "# presences = set()\n",
+ "# for r in range(h):\n",
+ "# for c in range(w):\n",
+ "# for d in Direction:\n",
+ "# for wordlen in wordlens:\n",
+ "# word = cat(gslice(grid, r, c, wordlen, d))\n",
+ "# if word in words:\n",
+ "# presences.add((word, r, c, d))\n",
+ "# return presences"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def read_wordsearch(fn):\n",
+ " lines = [l.strip() for l in open(fn).readlines()]\n",
+ " w, h = [int(s) for s in lines[0].split('x')]\n",
+ " grid = lines[1:h+1]\n",
+ " words = lines[h+1:]\n",
+ " return w, h, grid, words"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(['pistrohxegniydutslxt',\n",
+ " 'wmregunarbpiledsyuoo',\n",
+ " 'hojminbmutartslrlmgo',\n",
+ " 'isrsdniiekildabolpll',\n",
+ " 'tstsnyekentypkalases',\n",
+ " 'ssnetengcrfetedirgdt',\n",
+ " 'religstasuslatxauner',\n",
+ " 'elgcpgatsklglzistilo',\n",
+ " 'tndlimitationilkasan',\n",
+ " 'aousropedlygiifeniog',\n",
+ " 'kilrprepszffsyzqsrhs',\n",
+ " 'itlaadorableorpccese',\n",
+ " 'noaeewoodedpngmqicnl',\n",
+ " 'gmrtoitailingchelrok',\n",
+ " 'jadsngninetsahtooeic',\n",
+ " 'xeernighestsailarmtu',\n",
+ " 'aeabsolvednscumdfnon',\n",
+ " 'gydammingawlcandornk',\n",
+ " 'hurlerslvkaccxcinosw',\n",
+ " 'iqnanoitacifitrofqqi'],\n",
+ " ['absolved',\n",
+ " 'adorable',\n",
+ " 'aeon',\n",
+ " 'alias',\n",
+ " 'ancestor',\n",
+ " 'baritone',\n",
+ " 'bemusing',\n",
+ " 'blonds',\n",
+ " 'bran',\n",
+ " 'calcite',\n",
+ " 'candor',\n",
+ " 'conciseness',\n",
+ " 'consequent',\n",
+ " 'cuddle',\n",
+ " 'damming',\n",
+ " 'dashboards',\n",
+ " 'despairing',\n",
+ " 'dint',\n",
+ " 'dullard',\n",
+ " 'dynasty',\n",
+ " 'employer',\n",
+ " 'exhorts',\n",
+ " 'feted',\n",
+ " 'fill',\n",
+ " 'flattens',\n",
+ " 'foghorn',\n",
+ " 'fortification',\n",
+ " 'freakish',\n",
+ " 'frolics',\n",
+ " 'gall',\n",
+ " 'gees',\n",
+ " 'genies',\n",
+ " 'gets',\n",
+ " 'hastening',\n",
+ " 'hits',\n",
+ " 'hopelessness',\n",
+ " 'hurlers',\n",
+ " 'impales',\n",
+ " 'infix',\n",
+ " 'inflow',\n",
+ " 'innumerable',\n",
+ " 'intentional',\n",
+ " 'jerkin',\n",
+ " 'justification',\n",
+ " 'kitty',\n",
+ " 'knuckles',\n",
+ " 'leaving',\n",
+ " 'like',\n",
+ " 'limitation',\n",
+ " 'locoweeds',\n",
+ " 'loot',\n",
+ " 'lucking',\n",
+ " 'lumps',\n",
+ " 'mercerising',\n",
+ " 'monickers',\n",
+ " 'motionless',\n",
+ " 'naturally',\n",
+ " 'nighest',\n",
+ " 'notion',\n",
+ " 'ogled',\n",
+ " 'originality',\n",
+ " 'outings',\n",
+ " 'pendulous',\n",
+ " 'piled',\n",
+ " 'pins',\n",
+ " 'pithier',\n",
+ " 'prep',\n",
+ " 'randomness',\n",
+ " 'rectors',\n",
+ " 'redrew',\n",
+ " 'reformulated',\n",
+ " 'remoteness',\n",
+ " 'retaking',\n",
+ " 'rethink',\n",
+ " 'rope',\n",
+ " 'rubier',\n",
+ " 'sailors',\n",
+ " 'scowls',\n",
+ " 'scum',\n",
+ " 'sepals',\n",
+ " 'sequencers',\n",
+ " 'serf',\n",
+ " 'shoaled',\n",
+ " 'shook',\n",
+ " 'sonic',\n",
+ " 'spottiest',\n",
+ " 'stag',\n",
+ " 'stood',\n",
+ " 'stratum',\n",
+ " 'strong',\n",
+ " 'studying',\n",
+ " 'surtaxing',\n",
+ " 'tailing',\n",
+ " 'tears',\n",
+ " 'teazles',\n",
+ " 'vans',\n",
+ " 'wardrobes',\n",
+ " 'wooded',\n",
+ " 'worsts',\n",
+ " 'zings'])"
+ ]
+ },
+ "execution_count": 49,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "width, height, g, ws = read_wordsearch('wordsearch04.txt')\n",
+ "g, ws"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "absolved (True, 16, 2, <Direction.right: 2>)\n",
+ "adorable (True, 11, 4, <Direction.right: 2>)\n",
+ "aeon (True, 11, 4, <Direction.down: 4>)\n",
+ "alias (True, 15, 15, <Direction.left: 1>)\n",
+ "ancestor (False, 0, 0, <Direction.left: 1>)\n",
+ "baritone (False, 0, 0, <Direction.left: 1>)\n",
+ "bemusing (False, 0, 0, <Direction.left: 1>)\n",
+ "blonds (False, 0, 0, <Direction.left: 1>)\n",
+ "bran (True, 1, 9, <Direction.left: 1>)\n",
+ "calcite (True, 19, 9, <Direction.upright: 6>)\n",
+ "candor (True, 17, 12, <Direction.right: 2>)\n",
+ "conciseness (False, 0, 0, <Direction.left: 1>)\n",
+ "consequent (False, 0, 0, <Direction.left: 1>)\n",
+ "cuddle (False, 0, 0, <Direction.left: 1>)\n",
+ "damming (True, 17, 2, <Direction.right: 2>)\n",
+ "dashboards (False, 0, 0, <Direction.left: 1>)\n",
+ "despairing (False, 0, 0, <Direction.left: 1>)\n",
+ "dint (False, 0, 0, <Direction.left: 1>)\n",
+ "dullard (True, 8, 2, <Direction.down: 4>)\n",
+ "dynasty (True, 3, 4, <Direction.downright: 8>)\n",
+ "employer (False, 0, 0, <Direction.left: 1>)\n",
+ "exhorts (True, 0, 8, <Direction.left: 1>)\n",
+ "feted (True, 5, 10, <Direction.right: 2>)\n",
+ "fill (True, 9, 14, <Direction.upleft: 5>)\n",
+ "flattens (True, 10, 10, <Direction.upleft: 5>)\n",
+ "foghorn (True, 10, 11, <Direction.downright: 8>)\n",
+ "fortification (True, 19, 16, <Direction.left: 1>)\n",
+ "freakish (False, 0, 0, <Direction.left: 1>)\n",
+ "frolics (True, 16, 16, <Direction.up: 3>)\n",
+ "gall (False, 0, 0, <Direction.left: 1>)\n",
+ "gees (True, 17, 0, <Direction.upright: 6>)\n",
+ "genies (True, 5, 7, <Direction.upleft: 5>)\n",
+ "gets (True, 6, 4, <Direction.upleft: 5>)\n",
+ "hastening (True, 14, 13, <Direction.left: 1>)\n",
+ "hits (True, 2, 0, <Direction.down: 4>)\n",
+ "hopelessness (False, 0, 0, <Direction.left: 1>)\n",
+ "hurlers (True, 18, 0, <Direction.right: 2>)\n",
+ "impales (False, 0, 0, <Direction.left: 1>)\n",
+ "infix (False, 0, 0, <Direction.left: 1>)\n",
+ "inflow (False, 0, 0, <Direction.left: 1>)\n",
+ "innumerable (False, 0, 0, <Direction.left: 1>)\n",
+ "intentional (False, 0, 0, <Direction.left: 1>)\n",
+ "jerkin (False, 0, 0, <Direction.left: 1>)\n",
+ "justification (False, 0, 0, <Direction.left: 1>)\n",
+ "kitty (True, 8, 15, <Direction.upleft: 5>)\n",
+ "knuckles (True, 17, 19, <Direction.up: 3>)\n",
+ "leaving (False, 0, 0, <Direction.left: 1>)\n",
+ "like (True, 3, 11, <Direction.left: 1>)\n",
+ "limitation (True, 8, 3, <Direction.right: 2>)\n",
+ "locoweeds (False, 0, 0, <Direction.left: 1>)\n",
+ "loot (True, 3, 19, <Direction.up: 3>)\n",
+ "lucking (True, 7, 10, <Direction.upleft: 5>)\n",
+ "lumps (True, 0, 17, <Direction.down: 4>)\n",
+ "mercerising (True, 15, 17, <Direction.up: 3>)\n",
+ "monickers (False, 0, 0, <Direction.left: 1>)\n",
+ "motionless (True, 13, 1, <Direction.up: 3>)\n",
+ "naturally (True, 9, 16, <Direction.up: 3>)\n",
+ "nighest (True, 15, 4, <Direction.right: 2>)\n",
+ "notion (True, 17, 18, <Direction.up: 3>)\n",
+ "ogled (True, 1, 18, <Direction.down: 4>)\n",
+ "originality (False, 0, 0, <Direction.left: 1>)\n",
+ "outings (False, 0, 0, <Direction.left: 1>)\n",
+ "pendulous (False, 0, 0, <Direction.left: 1>)\n",
+ "piled (True, 1, 10, <Direction.right: 2>)\n",
+ "pins (True, 7, 4, <Direction.upleft: 5>)\n",
+ "pithier (False, 0, 0, <Direction.left: 1>)\n",
+ "prep (True, 10, 4, <Direction.right: 2>)\n",
+ "randomness (False, 0, 0, <Direction.left: 1>)\n",
+ "rectors (False, 0, 0, <Direction.left: 1>)\n",
+ "redrew (False, 0, 0, <Direction.left: 1>)\n",
+ "reformulated (False, 0, 0, <Direction.left: 1>)\n",
+ "remoteness (False, 0, 0, <Direction.left: 1>)\n",
+ "retaking (True, 6, 0, <Direction.down: 4>)\n",
+ "rethink (False, 0, 0, <Direction.left: 1>)\n",
+ "rope (True, 9, 4, <Direction.right: 2>)\n",
+ "rubier (True, 0, 4, <Direction.downright: 8>)\n",
+ "sailors (True, 7, 15, <Direction.up: 3>)\n",
+ "scowls (False, 0, 0, <Direction.left: 1>)\n",
+ "scum (True, 16, 11, <Direction.right: 2>)\n",
+ "sepals (True, 6, 10, <Direction.upright: 6>)\n",
+ "sequencers (False, 0, 0, <Direction.left: 1>)\n",
+ "serf (False, 0, 0, <Direction.left: 1>)\n",
+ "shoaled (True, 11, 18, <Direction.up: 3>)\n",
+ "shook (False, 0, 0, <Direction.left: 1>)\n",
+ "sonic (True, 18, 18, <Direction.left: 1>)\n",
+ "spottiest (False, 0, 0, <Direction.left: 1>)\n",
+ "stag (True, 7, 8, <Direction.left: 1>)\n",
+ "stood (False, 0, 0, <Direction.left: 1>)\n",
+ "stratum (True, 2, 13, <Direction.left: 1>)\n",
+ "strong (True, 4, 19, <Direction.down: 4>)\n",
+ "studying (True, 0, 16, <Direction.left: 1>)\n",
+ "surtaxing (False, 0, 0, <Direction.left: 1>)\n",
+ "tailing (True, 13, 6, <Direction.right: 2>)\n",
+ "tears (True, 13, 3, <Direction.up: 3>)\n",
+ "teazles (True, 4, 10, <Direction.downright: 8>)\n",
+ "vans (True, 18, 8, <Direction.upright: 6>)\n",
+ "wardrobes (False, 0, 0, <Direction.left: 1>)\n",
+ "wooded (True, 12, 5, <Direction.right: 2>)\n",
+ "worsts (True, 1, 0, <Direction.downright: 8>)\n",
+ "zings (True, 10, 14, <Direction.upleft: 5>)\n"
+ ]
+ }
+ ],
+ "source": [
+ "for w in ws:\n",
+ " print(w, present(g, w))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Which words are present?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 69,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1.28 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "[w for w in ws if present(g, w)[0]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 70,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 215 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "[p[0] for p in present_many(g, ws)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 61,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['absolved',\n",
+ " 'adorable',\n",
+ " 'aeon',\n",
+ " 'alias',\n",
+ " 'ancestor',\n",
+ " 'baritone',\n",
+ " 'bemusing',\n",
+ " 'blonds',\n",
+ " 'bran',\n",
+ " 'calcite',\n",
+ " 'candor',\n",
+ " 'conciseness',\n",
+ " 'consequent',\n",
+ " 'cuddle',\n",
+ " 'damming',\n",
+ " 'dashboards',\n",
+ " 'despairing',\n",
+ " 'dint',\n",
+ " 'dullard',\n",
+ " 'dynasty',\n",
+ " 'employer',\n",
+ " 'exhorts',\n",
+ " 'feted',\n",
+ " 'fill',\n",
+ " 'flattens',\n",
+ " 'foghorn',\n",
+ " 'fortification',\n",
+ " 'freakish',\n",
+ " 'frolics',\n",
+ " 'gall',\n",
+ " 'gees',\n",
+ " 'genies',\n",
+ " 'gets',\n",
+ " 'hastening',\n",
+ " 'hits',\n",
+ " 'hopelessness',\n",
+ " 'hurlers',\n",
+ " 'impales',\n",
+ " 'infix',\n",
+ " 'inflow',\n",
+ " 'innumerable',\n",
+ " 'intentional',\n",
+ " 'jerkin',\n",
+ " 'justification',\n",
+ " 'kitty',\n",
+ " 'knuckles',\n",
+ " 'leaving',\n",
+ " 'like',\n",
+ " 'limitation',\n",
+ " 'locoweeds',\n",
+ " 'loot',\n",
+ " 'lucking',\n",
+ " 'lumps',\n",
+ " 'mercerising',\n",
+ " 'monickers',\n",
+ " 'motionless',\n",
+ " 'naturally',\n",
+ " 'nighest',\n",
+ " 'notion',\n",
+ " 'ogled',\n",
+ " 'originality',\n",
+ " 'outings',\n",
+ " 'pendulous',\n",
+ " 'piled',\n",
+ " 'pins',\n",
+ " 'pithier',\n",
+ " 'prep',\n",
+ " 'randomness',\n",
+ " 'rectors',\n",
+ " 'redrew',\n",
+ " 'reformulated',\n",
+ " 'remoteness',\n",
+ " 'retaking',\n",
+ " 'rethink',\n",
+ " 'rope',\n",
+ " 'rubier',\n",
+ " 'sailors',\n",
+ " 'scowls',\n",
+ " 'scum',\n",
+ " 'sepals',\n",
+ " 'sequencers',\n",
+ " 'serf',\n",
+ " 'shoaled',\n",
+ " 'shook',\n",
+ " 'sonic',\n",
+ " 'spottiest',\n",
+ " 'stag',\n",
+ " 'stood',\n",
+ " 'stratum',\n",
+ " 'strong',\n",
+ " 'studying',\n",
+ " 'surtaxing',\n",
+ " 'tailing',\n",
+ " 'tears',\n",
+ " 'teazles',\n",
+ " 'vans',\n",
+ " 'wardrobes',\n",
+ " 'wooded',\n",
+ " 'worsts',\n",
+ " 'zings']"
+ ]
+ },
+ "execution_count": 61,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "ws"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "What is the longest word that is present?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'fortification'"
+ ]
+ },
+ "execution_count": 15,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sorted([w for w in ws if present(g, w)[0]], key=len)[-1]"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "What is the longest word that is absent?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'justification'"
+ ]
+ },
+ "execution_count": 16,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sorted([w for w in ws if not present(g, w)[0]], key=len)[-1]"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "How many letters are unused?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "57"
+ ]
+ },
+ "execution_count": 17,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "g0 = empty_grid(width, height)\n",
+ "for w in ws:\n",
+ " p, r, c, d = present(g, w)\n",
+ " if p:\n",
+ " set_grid(g0, r, c, d, w)\n",
+ "len([c for c in cat(cat(l) for l in g0) if c == '.'])"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "What is the longest word you can make form the leftover letters?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "Counter({'a': 4,\n",
+ " 'b': 1,\n",
+ " 'c': 5,\n",
+ " 'd': 3,\n",
+ " 'e': 1,\n",
+ " 'g': 2,\n",
+ " 'i': 5,\n",
+ " 'j': 2,\n",
+ " 'k': 3,\n",
+ " 'l': 2,\n",
+ " 'm': 3,\n",
+ " 'n': 3,\n",
+ " 'p': 3,\n",
+ " 'q': 5,\n",
+ " 'r': 3,\n",
+ " 's': 3,\n",
+ " 'w': 2,\n",
+ " 'x': 4,\n",
+ " 'y': 2,\n",
+ " 'z': 1})"
+ ]
+ },
+ "execution_count": 18,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "unused_letters = [l for l, u in zip((c for c in cat(cat(l) for l in g)), (c for c in cat(cat(l) for l in g0)))\n",
+ " if u == '.']\n",
+ "unused_letter_count = collections.Counter(unused_letters)\n",
+ "unused_letter_count"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['ancestor',\n",
+ " 'baritone',\n",
+ " 'bemusing',\n",
+ " 'blonds',\n",
+ " 'conciseness',\n",
+ " 'consequent',\n",
+ " 'cuddle',\n",
+ " 'dashboards',\n",
+ " 'despairing',\n",
+ " 'dint',\n",
+ " 'employer',\n",
+ " 'freakish',\n",
+ " 'gall',\n",
+ " 'hopelessness',\n",
+ " 'impales',\n",
+ " 'infix',\n",
+ " 'inflow',\n",
+ " 'innumerable',\n",
+ " 'intentional',\n",
+ " 'jerkin',\n",
+ " 'justification',\n",
+ " 'leaving',\n",
+ " 'locoweeds',\n",
+ " 'monickers',\n",
+ " 'originality',\n",
+ " 'outings',\n",
+ " 'pendulous',\n",
+ " 'pithier',\n",
+ " 'randomness',\n",
+ " 'rectors',\n",
+ " 'redrew',\n",
+ " 'reformulated',\n",
+ " 'remoteness',\n",
+ " 'rethink',\n",
+ " 'scowls',\n",
+ " 'sequencers',\n",
+ " 'serf',\n",
+ " 'shook',\n",
+ " 'spottiest',\n",
+ " 'stood',\n",
+ " 'surtaxing',\n",
+ " 'wardrobes']"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "unused_words = [w for w in ws if not present(g, w)[0]]\n",
+ "unused_words"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "ancestor Counter({'t': 1, 'r': 1, 'a': 1, 'e': 1, 'o': 1, 's': 1, 'n': 1, 'c': 1})\n",
+ "baritone Counter({'t': 1, 'i': 1, 'a': 1, 'e': 1, 'n': 1, 'o': 1, 'r': 1, 'b': 1})\n",
+ "bemusing Counter({'m': 1, 'i': 1, 'n': 1, 'g': 1, 'e': 1, 's': 1, 'u': 1, 'b': 1})\n",
+ "blonds Counter({'n': 1, 's': 1, 'd': 1, 'l': 1, 'o': 1, 'b': 1})\n",
+ "conciseness Counter({'s': 3, 'n': 2, 'e': 2, 'c': 2, 'i': 1, 'o': 1})\n",
+ "consequent Counter({'n': 2, 'e': 2, 't': 1, 'q': 1, 's': 1, 'u': 1, 'o': 1, 'c': 1})\n",
+ "cuddle Counter({'d': 2, 'l': 1, 'u': 1, 'e': 1, 'c': 1})\n",
+ "dashboards Counter({'a': 2, 'd': 2, 's': 2, 'r': 1, 'h': 1, 'o': 1, 'b': 1})\n",
+ "*despairing Counter({'i': 2, 'a': 1, 'g': 1, 'e': 1, 'n': 1, 'r': 1, 'd': 1, 'p': 1, 's': 1})\n",
+ "dint Counter({'t': 1, 'i': 1, 'd': 1, 'n': 1})\n",
+ "employer Counter({'e': 2, 'm': 1, 'r': 1, 'p': 1, 'o': 1, 'l': 1, 'y': 1})\n",
+ "freakish Counter({'i': 1, 'a': 1, 'h': 1, 'e': 1, 's': 1, 'r': 1, 'f': 1, 'k': 1})\n",
+ "*gall Counter({'l': 2, 'a': 1, 'g': 1})\n",
+ "hopelessness Counter({'s': 4, 'e': 3, 'n': 1, 'h': 1, 'l': 1, 'o': 1, 'p': 1})\n",
+ "*impales Counter({'m': 1, 'i': 1, 'a': 1, 'e': 1, 'p': 1, 's': 1, 'l': 1})\n",
+ "infix Counter({'i': 2, 'x': 1, 'n': 1, 'f': 1})\n",
+ "inflow Counter({'i': 1, 'n': 1, 'w': 1, 'o': 1, 'f': 1, 'l': 1})\n",
+ "innumerable Counter({'n': 2, 'e': 2, 'm': 1, 'i': 1, 'l': 1, 'r': 1, 'u': 1, 'a': 1, 'b': 1})\n",
+ "intentional Counter({'n': 3, 't': 2, 'i': 2, 'e': 1, 'o': 1, 'l': 1, 'a': 1})\n",
+ "*jerkin Counter({'i': 1, 'n': 1, 'e': 1, 'r': 1, 'j': 1, 'k': 1})\n",
+ "justification Counter({'i': 3, 't': 2, 'a': 1, 'n': 1, 'j': 1, 's': 1, 'f': 1, 'u': 1, 'o': 1, 'c': 1})\n",
+ "leaving Counter({'i': 1, 'a': 1, 'v': 1, 'e': 1, 'l': 1, 'n': 1, 'g': 1})\n",
+ "locoweeds Counter({'e': 2, 'o': 2, 's': 1, 'w': 1, 'l': 1, 'd': 1, 'c': 1})\n",
+ "monickers Counter({'m': 1, 'i': 1, 'n': 1, 'e': 1, 's': 1, 'r': 1, 'o': 1, 'k': 1, 'c': 1})\n",
+ "originality Counter({'i': 3, 't': 1, 'n': 1, 'g': 1, 'y': 1, 'o': 1, 'a': 1, 'l': 1, 'r': 1})\n",
+ "outings Counter({'t': 1, 'i': 1, 'n': 1, 'g': 1, 'o': 1, 'u': 1, 's': 1})\n",
+ "pendulous Counter({'u': 2, 'n': 1, 'l': 1, 'e': 1, 's': 1, 'p': 1, 'd': 1, 'o': 1})\n",
+ "pithier Counter({'i': 2, 't': 1, 'h': 1, 'e': 1, 'r': 1, 'p': 1})\n",
+ "randomness Counter({'n': 2, 's': 2, 'm': 1, 'a': 1, 'e': 1, 'r': 1, 'o': 1, 'd': 1})\n",
+ "rectors Counter({'r': 2, 't': 1, 'e': 1, 's': 1, 'o': 1, 'c': 1})\n",
+ "redrew Counter({'r': 2, 'e': 2, 'w': 1, 'd': 1})\n",
+ "reformulated Counter({'e': 2, 'r': 2, 'm': 1, 't': 1, 'a': 1, 'd': 1, 'l': 1, 'f': 1, 'u': 1, 'o': 1})\n",
+ "remoteness Counter({'e': 3, 's': 2, 'm': 1, 't': 1, 'n': 1, 'r': 1, 'o': 1})\n",
+ "rethink Counter({'t': 1, 'i': 1, 'n': 1, 'h': 1, 'e': 1, 'r': 1, 'k': 1})\n",
+ "scowls Counter({'s': 2, 'w': 1, 'l': 1, 'o': 1, 'c': 1})\n",
+ "sequencers Counter({'e': 3, 's': 2, 'n': 1, 'q': 1, 'u': 1, 'r': 1, 'c': 1})\n",
+ "serf Counter({'s': 1, 'f': 1, 'r': 1, 'e': 1})\n",
+ "shook Counter({'o': 2, 'k': 1, 's': 1, 'h': 1})\n",
+ "spottiest Counter({'t': 3, 's': 2, 'i': 1, 'e': 1, 'p': 1, 'o': 1})\n",
+ "stood Counter({'o': 2, 't': 1, 'd': 1, 's': 1})\n",
+ "surtaxing Counter({'t': 1, 'x': 1, 'a': 1, 'g': 1, 'i': 1, 'n': 1, 's': 1, 'u': 1, 'r': 1})\n",
+ "wardrobes Counter({'r': 2, 'o': 1, 'a': 1, 'e': 1, 's': 1, 'w': 1, 'd': 1, 'b': 1})\n"
+ ]
+ }
+ ],
+ "source": [
+ "makeable_words = []\n",
+ "for w in unused_words:\n",
+ " unused_word_count = collections.Counter(w)\n",
+ " if all(unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
+ " makeable_words += [w]\n",
+ " print('*', end='')\n",
+ " print(w, unused_word_count)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "10"
+ ]
+ },
+ "execution_count": 21,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(len(w) for w in makeable_words)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'despairing'"
+ ]
+ },
+ "execution_count": 22,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sorted(makeable_words, key=len)[-1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 78,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def do_wordsearch_tasks_old(fn, show_anyway=False):\n",
+ " width, height, grid, words = read_wordsearch(fn)\n",
+ "\n",
+ " used_words = [w for w in words if present(grid, w)[0]]\n",
+ " unused_words = [w for w in words if not present(grid, w)[0]]\n",
+ " lwp = sorted([w for w in words if present(grid, w)[0]], key=len)[-1]\n",
+ " lwa = sorted(unused_words, key=len)[-1]\n",
+ "\n",
+ " lwps = [w for w in used_words if len(w) == len(lwp)]\n",
+ " lwas = [w for w in unused_words if len(w) == len(lwa)]\n",
+ " g0 = empty_grid(width, height)\n",
+ " for w in words:\n",
+ " p, r, c, d = present(grid, w)\n",
+ " if p:\n",
+ " set_grid(g0, r, c, d, w) \n",
+ " unused_letters = [l for l, u in zip((c for c in cat(cat(l) for l in grid)), (c for c in cat(cat(l) for l in g0)))\n",
+ " if u == '.']\n",
+ " unused_letter_count = collections.Counter(unused_letters)\n",
+ " makeable_words = []\n",
+ " for w in unused_words:\n",
+ " unused_word_count = collections.Counter(w)\n",
+ " if all(unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
+ " makeable_words += [w]\n",
+ " lwm = sorted(makeable_words, key=len)[-1]\n",
+ " lwms = [w for w in makeable_words if len(w) == len(lwm)]\n",
+ " if show_anyway or len(set((len(lwp),len(lwa),len(lwm)))) == 3:\n",
+ " print('\\n{}'.format(fn))\n",
+ " print('{} words present'.format(len(words) - len(unused_words)))\n",
+ " print('Longest word present: {}, {} letters ({})'.format(lwp, len(lwp), lwps))\n",
+ " print('Longest word absent: {}, {} letters ({})'.format(lwa, len(lwa), lwas))\n",
+ " print('{} unused letters'.format(len([c for c in cat(cat(l) for l in g0) if c == '.'])))\n",
+ " print('Longest makeable word: {}, {} ({})'.format(lwm, len(lwm), lwms))\n",
+ " print('All makeable words: {}'.format(makeable_words))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 152,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def do_wordsearch_tasks(fn, show_anyway=False, show_all_makeable=False):\n",
+ " width, height, grid, words = read_wordsearch(fn)\n",
+ " used_words = [p[0] for p in present_many(grid, words)]\n",
+ " unused_words = [w for w in words if w not in used_words]\n",
+ " lwp = max(used_words, key=len)\n",
+ " lwps = [w for w in used_words if len(w) == len(lwp)]\n",
+ "\n",
+ " if unused_words:\n",
+ " lwa = max(unused_words, key=len)\n",
+ " \n",
+ " lwas = [w for w in unused_words if len(w) == len(lwa)]\n",
+ " unused_grid = [[c for c in r] for r in grid]\n",
+ " for w, r, c, d in present_many(grid, words):\n",
+ " set_grid(unused_grid, r, c, d, '.' * len(w))\n",
+ " unused_letters = [c for l in unused_grid for c in l if c != '.']\n",
+ " unused_letter_count = collections.Counter(unused_letters)\n",
+ " makeable_words = []\n",
+ " for w in unused_words:\n",
+ " unused_word_count = collections.Counter(w)\n",
+ " if all(unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
+ " makeable_words += [w]\n",
+ " lwm = sorted(makeable_words, key=len)[-1]\n",
+ " lwms = [w for w in makeable_words if len(w) == len(lwm)]\n",
+ " else:\n",
+ " lwa = ''\n",
+ " lwas = []\n",
+ " lwm = ''\n",
+ " lwms = []\n",
+ " \n",
+ " if show_anyway or len(set((len(lwp),len(lwa),len(lwm)))) == 3:\n",
+ " print('\\n{}'.format(fn))\n",
+ " print('{} words present'.format(len(words) - len(unused_words)))\n",
+ " print('Longest word present: {}, {} letters ({})'.format(lwp, len(lwp), lwps))\n",
+ " print('Longest word absent: {}, {} letters ({})'.format(lwa, len(lwa), lwas))\n",
+ " print('{} unused letters'.format(len([c for c in cat(cat(l) for l in g0) if c == '.'])))\n",
+ " print('Longest makeable word: {}, {} ({})'.format(lwm, len(lwm), lwms))\n",
+ " if show_all_makeable:\n",
+ " print('All makeable words: {}'.format(makeable_words))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 136,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\n",
+ "wordsearch04.txt\n",
+ "58 words present\n",
+ "Longest word present: fortification, 13 letters (['fortification'])\n",
+ "Longest word absent: justification, 13 letters (['justification'])\n",
+ "57 unused letters\n",
+ "Longest makeable word: despairing, 10 (['despairing'])\n",
+ "All makeable words: ['despairing', 'gall', 'impales', 'jerkin']\n"
+ ]
+ }
+ ],
+ "source": [
+ "do_wordsearch_tasks('wordsearch04.txt', show_anyway=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\n",
+ "wordsearch08.txt\n",
+ "62 words present\n",
+ "Longest word present: compassionately, 15 letters (['compassionately'])\n",
+ "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
+ "65 unused letters\n",
+ "Longest makeable word: vacationing, 11 (['vacationing'])\n"
+ ]
+ }
+ ],
+ "source": [
+ "do_wordsearch_tasks('wordsearch08.txt')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 80,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\n",
+ "04-wordsearch.txt\n",
+ "62 words present\n",
+ "Longest word present: compassionately, 15 letters (['compassionately'])\n",
+ "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
+ "65 unused letters\n",
+ "Longest makeable word: vacationing, 11 (['vacationing'])\n",
+ "All makeable words: ['albacore', 'entail', 'excreted', 'factory', 'fornicated', 'frantic', 'grease', 'grocer', 'informal', 'jockeying', 'justified', 'larynxes', 'reviewer', 'sabotage', 'unable', 'vacationing', 'widgeons']\n",
+ "\n",
+ "04-wordsearch.txt\n",
+ "62 words present\n",
+ "Longest word present: compassionately, 15 letters (['compassionately'])\n",
+ "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
+ "65 unused letters\n",
+ "Longest makeable word: vacationing, 11 (['vacationing'])\n",
+ "All makeable words: ['albacore', 'entail', 'excreted', 'factory', 'fornicated', 'frantic', 'grease', 'grocer', 'informal', 'jockeying', 'justified', 'larynxes', 'reviewer', 'sabotage', 'unable', 'vacationing', 'widgeons']\n",
+ "\n",
+ "04-wordsearch.txt\n",
+ "62 words present\n",
+ "Longest word present: compassionately, 15 letters (['compassionately'])\n",
+ "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
+ "65 unused letters\n",
+ "Longest makeable word: vacationing, 11 (['vacationing'])\n",
+ "All makeable words: ['albacore', 'entail', 'excreted', 'factory', 'fornicated', 'frantic', 'grease', 'grocer', 'informal', 'jockeying', 'justified', 'larynxes', 'reviewer', 'sabotage', 'unable', 'vacationing', 'widgeons']\n",
+ "\n",
+ "04-wordsearch.txt\n",
+ "62 words present\n",
+ "Longest word present: compassionately, 15 letters (['compassionately'])\n",
+ "Longest word absent: retrospectives, 14 letters (['retrospectives'])\n",
+ "65 unused letters\n",
+ "Longest makeable word: vacationing, 11 (['vacationing'])\n",
+ "All makeable words: ['albacore', 'entail', 'excreted', 'factory', 'fornicated', 'frantic', 'grease', 'grocer', 'informal', 'jockeying', 'justified', 'larynxes', 'reviewer', 'sabotage', 'unable', 'vacationing', 'widgeons']\n",
+ "1 loop, best of 3: 4.78 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "do_wordsearch_tasks_old('04-wordsearch.txt')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 142,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 463 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "do_wordsearch_tasks('wordsearch04.txt')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 143,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\n",
+ "example-wordsearch.txt\n",
+ "14 words present\n",
+ "Longest word present: cowhides, 8 letters (['cowhides'])\n",
+ "Longest word absent: adapting, 8 letters (['adapting', 'coccyxes', 'crumbled', 'molested'])\n",
+ "57 unused letters\n",
+ "Longest makeable word: shinier, 7 (['shinier'])\n",
+ "All makeable words: ['shinier']\n"
+ ]
+ }
+ ],
+ "source": [
+ "do_wordsearch_tasks('example-wordsearch.txt', show_anyway=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {
+ "collapsed": true,
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "# for fn in sorted(os.listdir()):\n",
+ "# if re.match('wordsearch\\d\\d\\.txt', fn):\n",
+ "# do_wordsearch_tasks(fn)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "absolved (True, 16, 2, <Direction.right: 2>)\n",
+ "adorable (True, 11, 4, <Direction.right: 2>)\n",
+ "aeon (True, 11, 4, <Direction.down: 4>)\n",
+ "alias (True, 15, 15, <Direction.left: 1>)\n",
+ "ancestor (False, 0, 0, <Direction.left: 1>)\n",
+ "baritone (False, 0, 0, <Direction.left: 1>)\n",
+ "bemusing (False, 0, 0, <Direction.left: 1>)\n",
+ "blonds (False, 0, 0, <Direction.left: 1>)\n",
+ "bran (True, 1, 9, <Direction.left: 1>)\n",
+ "calcite (True, 19, 9, <Direction.upright: 6>)\n",
+ "candor (True, 17, 12, <Direction.right: 2>)\n",
+ "conciseness (False, 0, 0, <Direction.left: 1>)\n",
+ "consequent (False, 0, 0, <Direction.left: 1>)\n",
+ "cuddle (False, 0, 0, <Direction.left: 1>)\n",
+ "damming (True, 17, 2, <Direction.right: 2>)\n",
+ "dashboards (False, 0, 0, <Direction.left: 1>)\n",
+ "despairing (False, 0, 0, <Direction.left: 1>)\n",
+ "dint (False, 0, 0, <Direction.left: 1>)\n",
+ "dullard (True, 8, 2, <Direction.down: 4>)\n",
+ "dynasty (True, 3, 4, <Direction.downright: 8>)\n",
+ "employer (False, 0, 0, <Direction.left: 1>)\n",
+ "exhorts (True, 0, 8, <Direction.left: 1>)\n",
+ "feted (True, 5, 10, <Direction.right: 2>)\n",
+ "fill (True, 9, 14, <Direction.upleft: 5>)\n",
+ "flattens (True, 10, 10, <Direction.upleft: 5>)\n",
+ "foghorn (True, 10, 11, <Direction.downright: 8>)\n",
+ "fortification (True, 19, 16, <Direction.left: 1>)\n",
+ "freakish (False, 0, 0, <Direction.left: 1>)\n",
+ "frolics (True, 16, 16, <Direction.up: 3>)\n",
+ "gall (False, 0, 0, <Direction.left: 1>)\n",
+ "gees (True, 17, 0, <Direction.upright: 6>)\n",
+ "genies (True, 5, 7, <Direction.upleft: 5>)\n",
+ "gets (True, 6, 4, <Direction.upleft: 5>)\n",
+ "hastening (True, 14, 13, <Direction.left: 1>)\n",
+ "hits (True, 2, 0, <Direction.down: 4>)\n",
+ "hopelessness (False, 0, 0, <Direction.left: 1>)\n",
+ "hurlers (True, 18, 0, <Direction.right: 2>)\n",
+ "impales (False, 0, 0, <Direction.left: 1>)\n",
+ "infix (False, 0, 0, <Direction.left: 1>)\n",
+ "inflow (False, 0, 0, <Direction.left: 1>)\n",
+ "innumerable (False, 0, 0, <Direction.left: 1>)\n",
+ "intentional (False, 0, 0, <Direction.left: 1>)\n",
+ "jerkin (False, 0, 0, <Direction.left: 1>)\n",
+ "justification (False, 0, 0, <Direction.left: 1>)\n",
+ "kitty (True, 8, 15, <Direction.upleft: 5>)\n",
+ "knuckles (True, 17, 19, <Direction.up: 3>)\n",
+ "leaving (False, 0, 0, <Direction.left: 1>)\n",
+ "like (True, 3, 11, <Direction.left: 1>)\n",
+ "limitation (True, 8, 3, <Direction.right: 2>)\n",
+ "locoweeds (False, 0, 0, <Direction.left: 1>)\n",
+ "loot (True, 3, 19, <Direction.up: 3>)\n",
+ "lucking (True, 7, 10, <Direction.upleft: 5>)\n",
+ "lumps (True, 0, 17, <Direction.down: 4>)\n",
+ "mercerising (True, 15, 17, <Direction.up: 3>)\n",
+ "monickers (False, 0, 0, <Direction.left: 1>)\n",
+ "motionless (True, 13, 1, <Direction.up: 3>)\n",
+ "naturally (True, 9, 16, <Direction.up: 3>)\n",
+ "nighest (True, 15, 4, <Direction.right: 2>)\n",
+ "notion (True, 17, 18, <Direction.up: 3>)\n",
+ "ogled (True, 1, 18, <Direction.down: 4>)\n",
+ "originality (False, 0, 0, <Direction.left: 1>)\n",
+ "outings (False, 0, 0, <Direction.left: 1>)\n",
+ "pendulous (False, 0, 0, <Direction.left: 1>)\n",
+ "piled (True, 1, 10, <Direction.right: 2>)\n",
+ "pins (True, 7, 4, <Direction.upleft: 5>)\n",
+ "pithier (False, 0, 0, <Direction.left: 1>)\n",
+ "prep (True, 10, 4, <Direction.right: 2>)\n",
+ "randomness (False, 0, 0, <Direction.left: 1>)\n",
+ "rectors (False, 0, 0, <Direction.left: 1>)\n",
+ "redrew (False, 0, 0, <Direction.left: 1>)\n",
+ "reformulated (False, 0, 0, <Direction.left: 1>)\n",
+ "remoteness (False, 0, 0, <Direction.left: 1>)\n",
+ "retaking (True, 6, 0, <Direction.down: 4>)\n",
+ "rethink (False, 0, 0, <Direction.left: 1>)\n",
+ "rope (True, 9, 4, <Direction.right: 2>)\n",
+ "rubier (True, 0, 4, <Direction.downright: 8>)\n",
+ "sailors (True, 7, 15, <Direction.up: 3>)\n",
+ "scowls (False, 0, 0, <Direction.left: 1>)\n",
+ "scum (True, 16, 11, <Direction.right: 2>)\n",
+ "sepals (True, 6, 10, <Direction.upright: 6>)\n",
+ "sequencers (False, 0, 0, <Direction.left: 1>)\n",
+ "serf (False, 0, 0, <Direction.left: 1>)\n",
+ "shoaled (True, 11, 18, <Direction.up: 3>)\n",
+ "shook (False, 0, 0, <Direction.left: 1>)\n",
+ "sonic (True, 18, 18, <Direction.left: 1>)\n",
+ "spottiest (False, 0, 0, <Direction.left: 1>)\n",
+ "stag (True, 7, 8, <Direction.left: 1>)\n",
+ "stood (False, 0, 0, <Direction.left: 1>)\n",
+ "stratum (True, 2, 13, <Direction.left: 1>)\n",
+ "strong (True, 4, 19, <Direction.down: 4>)\n",
+ "studying (True, 0, 16, <Direction.left: 1>)\n",
+ "surtaxing (False, 0, 0, <Direction.left: 1>)\n",
+ "tailing (True, 13, 6, <Direction.right: 2>)\n",
+ "tears (True, 13, 3, <Direction.up: 3>)\n",
+ "teazles (True, 4, 10, <Direction.downright: 8>)\n",
+ "vans (True, 18, 8, <Direction.upright: 6>)\n",
+ "wardrobes (False, 0, 0, <Direction.left: 1>)\n",
+ "wooded (True, 12, 5, <Direction.right: 2>)\n",
+ "worsts (True, 1, 0, <Direction.downright: 8>)\n",
+ "zings (True, 10, 14, <Direction.upleft: 5>)\n"
+ ]
+ }
+ ],
+ "source": [
+ "width, height, grid, words = read_wordsearch('wordsearch04.txt')\n",
+ "for w in words:\n",
+ " print(w, present(grid, w))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example for question text"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import copy\n",
+ "grid = [['.', '.', '.', 'p', '.', 'm', 'o', 'w', 'n', '.'], ['.', 's', 'd', 's', 'e', '.', '.', 'e', 'e', '.'], ['.', 'e', '.', 'e', 'l', 'a', 'd', '.', 'c', 'r'], ['p', 'i', '.', 'd', 't', 'i', 'r', '.', 'a', 'h'], ['r', 'z', 's', 'i', 'w', 'o', 'v', 's', 'p', 'u'], ['o', 'a', 'w', 'h', '.', 'k', 'i', 'e', 'a', 'b'], ['b', 'r', 'o', 'w', '.', 'c', '.', 'r', 'd', 'a'], ['e', 'c', 'n', 'o', 't', 'o', 'p', 's', '.', 'r'], ['d', '.', 'k', 'c', '.', 'd', '.', '.', '.', 'b'], ['.', 's', 't', 'a', 'p', 'l', 'e', '.', '.', '.']]\n",
+ "padded_grid = [['f', 'h', 'j', 'p', 'a', 'm', 'o', 'w', 'n', 'q'], ['w', 's', 'd', 's', 'e', 'u', 'q', 'e', 'e', 'v'], ['i', 'e', 'a', 'e', 'l', 'a', 'd', 'h', 'c', 'r'], ['p', 'i', 'e', 'd', 't', 'i', 'r', 'i', 'a', 'h'], ['r', 'z', 's', 'i', 'w', 'o', 'v', 's', 'p', 'u'], ['o', 'a', 'w', 'h', 'a', 'k', 'i', 'e', 'a', 'b'], ['b', 'r', 'o', 'w', 'p', 'c', 'f', 'r', 'd', 'a'], ['e', 'c', 'n', 'o', 't', 'o', 'p', 's', 's', 'r'], ['d', 'i', 'k', 'c', 'h', 'd', 'n', 'p', 'n', 'b'], ['b', 's', 't', 'a', 'p', 'l', 'e', 'o', 'k', 'r']]\n",
+ "present_words = ['probed', 'staple', 'rioted', 'cowhides', 'tops', 'knows', 'lived', 'rhubarb', 'crazies', 'dock', 'apace', 'mown', 'pears', 'wide']\n",
+ "decoy_words = ['fickler', 'adapting', 'chump', 'foaming', 'molested', 'carnal', 'crumbled', 'guts', 'minuend', 'bombing', 'winced', 'coccyxes', 'solaria', 'shinier', 'cackles']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'apace, cowhides, crazies, dock, knows, lived, mown, pears, probed, rhubarb, rioted, staple, tops, wide'"
+ ]
+ },
+ "execution_count": 29,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "', '.join(sorted(present_words))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 92,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(76, 14)"
+ ]
+ },
+ "execution_count": 92,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(len(w) for w in present_words), len(present_words)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'adapting, bombing, cackles, carnal, chump, coccyxes, crumbled, fickler, foaming, guts, minuend, molested, shinier, solaria, winced'"
+ ]
+ },
+ "execution_count": 30,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "', '.join(sorted(decoy_words))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'adapting, apace, bombing, cackles, carnal, chump, coccyxes, cowhides, crazies, crumbled, dock, fickler, foaming, guts, knows, lived, minuend, molested, mown, pears, probed, rhubarb, rioted, shinier, solaria, staple, tops, wide, winced'"
+ ]
+ },
+ "execution_count": 31,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "', '.join(sorted(present_words + decoy_words))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "probed 3 0 6 Direction.down [(3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0)]\n",
+ "staple 9 1 6 Direction.right [(9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)]\n",
+ "rioted 6 7 6 Direction.upleft [(6, 7), (5, 6), (4, 5), (3, 4), (2, 3), (1, 2)]\n",
+ "cowhides 8 3 8 Direction.up [(8, 3), (7, 3), (6, 3), (5, 3), (4, 3), (3, 3), (2, 3), (1, 3)]\n",
+ "tops 7 4 4 Direction.right [(7, 4), (7, 5), (7, 6), (7, 7)]\n",
+ "knows 8 2 5 Direction.up [(8, 2), (7, 2), (6, 2), (5, 2), (4, 2)]\n",
+ "lived 2 4 5 Direction.downright [(2, 4), (3, 5), (4, 6), (5, 7), (6, 8)]\n",
+ "rhubarb 2 9 7 Direction.down [(2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9)]\n",
+ "crazies 7 1 7 Direction.up [(7, 1), (6, 1), (5, 1), (4, 1), (3, 1), (2, 1), (1, 1)]\n",
+ "dock 8 5 4 Direction.up [(8, 5), (7, 5), (6, 5), (5, 5)]\n",
+ "apace 5 8 5 Direction.up [(5, 8), (4, 8), (3, 8), (2, 8), (1, 8)]\n",
+ "mown 0 5 4 Direction.right [(0, 5), (0, 6), (0, 7), (0, 8)]\n",
+ "pears 0 3 5 Direction.downright [(0, 3), (1, 4), (2, 5), (3, 6), (4, 7)]\n",
+ "wide 4 4 4 Direction.upright [(4, 4), (3, 5), (2, 6), (1, 7)]\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "[(7, 5), (2, 3), (3, 5)]"
+ ]
+ },
+ "execution_count": 32,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "cts = collections.Counter()\n",
+ "for w in present_words:\n",
+ " _, r, c, d = present(grid, w)\n",
+ " inds = indices(grid, r, c, len(w), d)\n",
+ " for i in inds:\n",
+ " cts[i] += 1\n",
+ " print(w, r, c, len(w), d, inds)\n",
+ "[i for i in cts if cts[i] > 1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\n",
+ "example-wordsearch.txt\n",
+ "14 words present\n",
+ "Longest word present: cowhides, 8 letters (['cowhides'])\n",
+ "Longest word absent: molested, 8 letters (['adapting', 'coccyxes', 'crumbled', 'molested'])\n",
+ "27 unused letters\n",
+ "Longest makeable word: shinier, 7 (['shinier'])\n"
+ ]
+ }
+ ],
+ "source": [
+ "do_wordsearch_tasks('example-wordsearch.txt', show_anyway=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "..........\n",
+ "..........\n",
+ "....l.....\n",
+ ".....i....\n",
+ "......v...\n",
+ ".......e..\n",
+ "........d.\n",
+ "..........\n",
+ "..........\n",
+ "..........\n"
+ ]
+ }
+ ],
+ "source": [
+ "g = empty_grid(10, 10)\n",
+ "set_grid(g, 2, 4, Direction.downright, 'lived')\n",
+ "print(show_grid(g))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "..........\n",
+ ".......e..\n",
+ "....l.d...\n",
+ ".....i....\n",
+ "....w.v...\n",
+ ".......e..\n",
+ "........d.\n",
+ "..........\n",
+ "..........\n",
+ ".staple...\n"
+ ]
+ }
+ ],
+ "source": [
+ "g = empty_grid(10, 10)\n",
+ "set_grid(g, 2, 4, Direction.downright, 'lived')\n",
+ "set_grid(g, 4, 4, Direction.upright, 'wide')\n",
+ "set_grid(g, 9, 1, Direction.right, 'staple')\n",
+ "print(show_grid(g))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "..........\n",
+ "...s......\n",
+ "...e......\n",
+ "...d......\n",
+ "...i......\n",
+ "...h......\n",
+ "...w......\n",
+ "...o......\n",
+ "...c......\n",
+ "..........\n"
+ ]
+ }
+ ],
+ "source": [
+ "g = empty_grid(10, 10)\n",
+ "set_grid(g, 8, 3, Direction.up, 'cowhides')\n",
+ "print(show_grid(g))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "..........\n",
+ "...s...e..\n",
+ "...el.d...\n",
+ "...d.i....\n",
+ "...iw.v...\n",
+ "...h...e..\n",
+ "...w....d.\n",
+ "...o......\n",
+ "...c......\n",
+ ".staple...\n"
+ ]
+ }
+ ],
+ "source": [
+ "g = empty_grid(10, 10)\n",
+ "set_grid(g, 2, 4, Direction.downright, 'lived')\n",
+ "set_grid(g, 4, 4, Direction.upright, 'wide')\n",
+ "set_grid(g, 9, 1, Direction.right, 'staple')\n",
+ "set_grid(g, 8, 3, Direction.up, 'cowhides')\n",
+ "print(show_grid(g))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "..........\n",
+ "..........\n",
+ "..........\n",
+ "..........\n",
+ "..........\n",
+ "..........\n",
+ "brow......\n",
+ "..........\n",
+ "..........\n",
+ "..........\n"
+ ]
+ }
+ ],
+ "source": [
+ "# Example of word in grid that is English but isn't in the words listed in the puzzle.\n",
+ "g = empty_grid(10, 10)\n",
+ "set_grid(g, 6, 0, Direction.right, 'brow')\n",
+ "print(show_grid(g))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "fhj.a....q\n",
+ "w....uq..v\n",
+ "i.a....h..\n",
+ "..e....i..\n",
+ "..........\n",
+ "....a.....\n",
+ "....p.f...\n",
+ "........s.\n",
+ ".i..h.npn.\n",
+ "b......okr\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "'aaabeffhhhiiijknnoppqqrsuvw'"
+ ]
+ },
+ "execution_count": 38,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "unused_grid = copy.deepcopy(padded_grid)\n",
+ "for w in present_words:\n",
+ " _, r, c, d = present(grid, w)\n",
+ " set_grid(unused_grid, r, c, d, '.' * len(w))\n",
+ "print(show_grid(unused_grid))\n",
+ "cat(sorted(c for l in unused_grid for c in l if c in string.ascii_letters))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 201,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "9"
+ ]
+ },
+ "execution_count": 201,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(sorted(c for l in unused_grid for c in l if c in 'aeiou'))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# All wordsearch puzzles"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 108,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def read_all_wordsearch(fn):\n",
+ " with open(fn) as f:\n",
+ " text = f.read().strip()\n",
+ " puzzles_text = text.split('\\n\\n')\n",
+ " puzzles = []\n",
+ " for p in puzzles_text:\n",
+ " lines = p.splitlines()\n",
+ " w, h = [int(s) for s in lines[0].split('x')]\n",
+ " grid = lines[1:h+1]\n",
+ " words = lines[h+1:]\n",
+ " puzzles += [(w, h, grid, words)]\n",
+ " return puzzles"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 109,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(20,\n",
+ " 20,\n",
+ " ['esaetarotcetorpwvnma',\n",
+ " 'dhuejswellraqzassuzn',\n",
+ " 'riopstewsidftvenlnlo',\n",
+ " 'dltnpupodiafilgeenap',\n",
+ " 'yeooooosvconsgatvenm',\n",
+ " 'tgtonrsdtpgsungsireo',\n",
+ " 'csmtnlaistdklisaeyrp',\n",
+ " 'fguuusortrewfkrfdluo',\n",
+ " 'dotcnpvoyiraicsrieht',\n",
+ " 'drtcoataksogdaekcoyy',\n",
+ " 'igoialcuneoneuasirvy',\n",
+ " 'ajnzdpacoqrbsoshmgnt',\n",
+ " 'mmsxeetcewussviipeei',\n",
+ " 'esbrevrioprivilramsr',\n",
+ " 'tsgerdvcvutesbtrrska',\n",
+ " 'eyselimisapenheettcl',\n",
+ " 'ryponacqcetsdsddiouu',\n",
+ " 'streitsaotsedalaanlg',\n",
+ " 'foretselppusdfrsleae',\n",
+ " 'utsolacebeardingpher'],\n",
+ " ['aboveboard',\n",
+ " 'accents',\n",
+ " 'applicants',\n",
+ " 'arbitrarily',\n",
+ " 'atlas',\n",
+ " 'bazillions',\n",
+ " 'bearding',\n",
+ " 'biathlon',\n",
+ " 'bivouacking',\n",
+ " 'canopy',\n",
+ " 'captivated',\n",
+ " 'chicory',\n",
+ " 'cockroach',\n",
+ " 'construct',\n",
+ " 'coups',\n",
+ " 'credit',\n",
+ " 'depreciates',\n",
+ " 'diameters',\n",
+ " 'diffuses',\n",
+ " 'douse',\n",
+ " 'downbeats',\n",
+ " 'dregs',\n",
+ " 'envy',\n",
+ " 'expects',\n",
+ " 'expurgations',\n",
+ " 'fact',\n",
+ " 'fastens',\n",
+ " 'festively',\n",
+ " 'flubbing',\n",
+ " 'fops',\n",
+ " 'fore',\n",
+ " 'gage',\n",
+ " 'gapes',\n",
+ " 'gawks',\n",
+ " 'gemstone',\n",
+ " 'grog',\n",
+ " 'grossly',\n",
+ " 'handlebar',\n",
+ " 'haranguing',\n",
+ " 'honorary',\n",
+ " 'hulls',\n",
+ " 'impartial',\n",
+ " 'insists',\n",
+ " 'lades',\n",
+ " 'lane',\n",
+ " 'levied',\n",
+ " 'loaned',\n",
+ " 'locust',\n",
+ " 'loons',\n",
+ " 'lucks',\n",
+ " 'lying',\n",
+ " 'memoir',\n",
+ " 'methods',\n",
+ " 'mutton',\n",
+ " 'nodular',\n",
+ " 'nunnery',\n",
+ " 'onlookers',\n",
+ " 'outputted',\n",
+ " 'overhearing',\n",
+ " 'panicky',\n",
+ " 'particularly',\n",
+ " 'peeving',\n",
+ " 'podia',\n",
+ " 'pompon',\n",
+ " 'presenting',\n",
+ " 'protectorate',\n",
+ " 'pummels',\n",
+ " 'ransoms',\n",
+ " 'regularity',\n",
+ " 'roof',\n",
+ " 'salvaged',\n",
+ " 'scanting',\n",
+ " 'scions',\n",
+ " 'shipping',\n",
+ " 'shirred',\n",
+ " 'silted',\n",
+ " 'similes',\n",
+ " 'smartened',\n",
+ " 'snicker',\n",
+ " 'snowdrops',\n",
+ " 'sobs',\n",
+ " 'solace',\n",
+ " 'stews',\n",
+ " 'stitches',\n",
+ " 'sulfides',\n",
+ " 'supplest',\n",
+ " 'suppositions',\n",
+ " 'swell',\n",
+ " 'theirs',\n",
+ " 'toastier',\n",
+ " 'tutorial',\n",
+ " 'unaccepted',\n",
+ " 'unionising',\n",
+ " 'vanquish',\n",
+ " 'venous',\n",
+ " 'verbs',\n",
+ " 'vitiation',\n",
+ " 'waving',\n",
+ " 'wrens',\n",
+ " 'yock'])"
+ ]
+ },
+ "execution_count": 109,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "puzzles = read_all_wordsearch('all-wordsearches.txt')\n",
+ "puzzles[3]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 110,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def found_words_length(puzzle):\n",
+ " width, height, grid, words = puzzle\n",
+ " return sum(len(p[0]) for p in present_many(grid, words))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 113,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[309,\n",
+ " 335,\n",
+ " 338,\n",
+ " 346,\n",
+ " 364,\n",
+ " 372,\n",
+ " 337,\n",
+ " 340,\n",
+ " 353,\n",
+ " 371,\n",
+ " 343,\n",
+ " 348,\n",
+ " 375,\n",
+ " 343,\n",
+ " 363,\n",
+ " 376,\n",
+ " 347,\n",
+ " 363,\n",
+ " 342,\n",
+ " 348,\n",
+ " 377,\n",
+ " 342,\n",
+ " 355,\n",
+ " 351,\n",
+ " 342,\n",
+ " 331,\n",
+ " 362,\n",
+ " 354,\n",
+ " 323,\n",
+ " 353,\n",
+ " 337,\n",
+ " 340,\n",
+ " 349,\n",
+ " 362,\n",
+ " 361,\n",
+ " 350,\n",
+ " 348,\n",
+ " 327,\n",
+ " 370,\n",
+ " 362,\n",
+ " 334,\n",
+ " 333,\n",
+ " 341,\n",
+ " 354,\n",
+ " 355,\n",
+ " 358,\n",
+ " 355,\n",
+ " 358,\n",
+ " 357,\n",
+ " 351,\n",
+ " 351,\n",
+ " 346,\n",
+ " 326,\n",
+ " 332,\n",
+ " 352,\n",
+ " 347,\n",
+ " 346,\n",
+ " 369,\n",
+ " 363,\n",
+ " 361,\n",
+ " 365,\n",
+ " 364,\n",
+ " 359,\n",
+ " 352,\n",
+ " 344,\n",
+ " 352,\n",
+ " 348,\n",
+ " 360,\n",
+ " 333,\n",
+ " 352,\n",
+ " 374,\n",
+ " 360,\n",
+ " 349,\n",
+ " 343,\n",
+ " 360,\n",
+ " 345,\n",
+ " 364,\n",
+ " 355,\n",
+ " 349,\n",
+ " 349,\n",
+ " 355,\n",
+ " 328,\n",
+ " 358,\n",
+ " 344,\n",
+ " 335,\n",
+ " 339,\n",
+ " 365,\n",
+ " 328,\n",
+ " 343,\n",
+ " 350,\n",
+ " 340,\n",
+ " 342,\n",
+ " 342,\n",
+ " 357,\n",
+ " 362,\n",
+ " 333,\n",
+ " 357,\n",
+ " 346,\n",
+ " 341,\n",
+ " 348]"
+ ]
+ },
+ "execution_count": 113,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[found_words_length(p) for p in puzzles]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 114,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "34988"
+ ]
+ },
+ "execution_count": 114,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(found_words_length(p) for p in puzzles)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 122,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def max_unfound_word_length(puzzle):\n",
+ " width, height, grid, words = puzzle\n",
+ " presences = present_many(grid, words)\n",
+ " used_words = [p[0] for p in presences]\n",
+ " unused_words = [w for w in words if w not in used_words]\n",
+ " \n",
+ " unused_grid = [[c for c in r] for r in grid]\n",
+ " for w, r, c, d in presences:\n",
+ " set_grid(unused_grid, r, c, d, '.' * len(w))\n",
+ " unused_letters = [c for l in unused_grid for c in l if c != '.']\n",
+ " unused_letter_count = collections.Counter(unused_letters)\n",
+ " \n",
+ " makeable_words = []\n",
+ " for w in unused_words:\n",
+ " unused_word_count = collections.Counter(w)\n",
+ " if all(unused_word_count[l] <= unused_letter_count[l] for l in unused_word_count):\n",
+ " makeable_words += [w]\n",
+ " lwm = max(len(w) for w in makeable_words)\n",
+ " return lwm"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 123,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[11,\n",
+ " 13,\n",
+ " 11,\n",
+ " 11,\n",
+ " 10,\n",
+ " 9,\n",
+ " 12,\n",
+ " 12,\n",
+ " 11,\n",
+ " 10,\n",
+ " 15,\n",
+ " 11,\n",
+ " 10,\n",
+ " 11,\n",
+ " 10,\n",
+ " 12,\n",
+ " 11,\n",
+ " 9,\n",
+ " 11,\n",
+ " 11,\n",
+ " 10,\n",
+ " 12,\n",
+ " 11,\n",
+ " 12,\n",
+ " 13,\n",
+ " 12,\n",
+ " 10,\n",
+ " 10,\n",
+ " 11,\n",
+ " 9,\n",
+ " 11,\n",
+ " 11,\n",
+ " 8,\n",
+ " 12,\n",
+ " 13,\n",
+ " 10,\n",
+ " 11,\n",
+ " 11,\n",
+ " 9,\n",
+ " 8,\n",
+ " 12,\n",
+ " 13,\n",
+ " 11,\n",
+ " 9,\n",
+ " 13,\n",
+ " 11,\n",
+ " 11,\n",
+ " 11,\n",
+ " 13,\n",
+ " 12,\n",
+ " 10,\n",
+ " 11,\n",
+ " 11,\n",
+ " 12,\n",
+ " 10,\n",
+ " 8,\n",
+ " 12,\n",
+ " 11,\n",
+ " 10,\n",
+ " 11,\n",
+ " 8,\n",
+ " 12,\n",
+ " 10,\n",
+ " 11,\n",
+ " 12,\n",
+ " 12,\n",
+ " 12,\n",
+ " 12,\n",
+ " 11,\n",
+ " 11,\n",
+ " 12,\n",
+ " 12,\n",
+ " 13,\n",
+ " 10,\n",
+ " 10,\n",
+ " 10,\n",
+ " 10,\n",
+ " 12,\n",
+ " 11,\n",
+ " 11,\n",
+ " 12,\n",
+ " 11,\n",
+ " 9,\n",
+ " 14,\n",
+ " 11,\n",
+ " 13,\n",
+ " 12,\n",
+ " 10,\n",
+ " 10,\n",
+ " 12,\n",
+ " 13,\n",
+ " 10,\n",
+ " 10,\n",
+ " 12,\n",
+ " 11,\n",
+ " 12,\n",
+ " 11,\n",
+ " 11,\n",
+ " 12,\n",
+ " 11]"
+ ]
+ },
+ "execution_count": 123,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[max_unfound_word_length(p) for p in puzzles]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 121,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1106"
+ ]
+ },
+ "execution_count": 121,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(max_unfound_word_length(p) for p in puzzles)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 124,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 18.8 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "sum(found_words_length(p) for p in puzzles)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 125,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 18.7 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "sum(max_unfound_word_length(p) for p in puzzles)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 190,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\n",
+ "huge-wordsearch.txt\n",
+ "1149 words present\n",
+ "Longest word present: hypersensitivities, 18 letters (['hypersensitivities'])\n",
+ "Longest word absent: rambunctiousness, 16 letters (['rambunctiousness'])\n",
+ "57 unused letters\n",
+ "Longest makeable word: rambunctiousness, 16 (['rambunctiousness'])\n"
+ ]
+ }
+ ],
+ "source": [
+ "do_wordsearch_tasks('huge-wordsearch.txt', show_anyway=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 191,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1min 4s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "do_wordsearch_tasks('huge-wordsearch.txt')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 192,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "width, height, grid, words = read_wordsearch('huge-wordsearch.txt')\n",
+ "pm = present_many(grid, words)\n",
+ "pold = [w for w in words if present(grid, w)[0]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 193,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1149"
+ ]
+ },
+ "execution_count": 193,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(pm)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 194,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1149"
+ ]
+ },
+ "execution_count": 194,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(pold)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 195,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1149"
+ ]
+ },
+ "execution_count": 195,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "pm_extra = [p for p in pm if p not in pold]\n",
+ "len(pm_extra)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 196,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[('poltroons', 62, 65, <Direction.downleft: 7>),\n",
+ " ('dogged', 7, 45, <Direction.down: 4>),\n",
+ " ('activist', 51, 35, <Direction.downright: 8>)]"
+ ]
+ },
+ "execution_count": 196,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "list(pm)[:3]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 197,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['abound', 'abstracted', 'accidents']"
+ ]
+ },
+ "execution_count": 197,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "pold[:3]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 198,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[('retreading', 1),\n",
+ " ('disavows', 1),\n",
+ " ('finals', 1),\n",
+ " ('conniver', 1),\n",
+ " ('warding', 1),\n",
+ " ('melon', 1),\n",
+ " ('paging', 1),\n",
+ " ('booties', 1),\n",
+ " ('civilises', 1),\n",
+ " ('hugged', 1)]"
+ ]
+ },
+ "execution_count": 198,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "collections.Counter(p[0] for p in pm).most_common(10)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 199,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[]"
+ ]
+ },
+ "execution_count": 199,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[p for p in pm if p[0] == 'seen']"
+ ]
+ },
+ {
+ "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": 1
+}