{ "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, )`'), ('staple', '`(True, 9, 1, )`'), ('rioted', '`(True, 6, 7, )`'), ('cowhides', '`(True, 8, 3, )`'), ('tops', '`(True, 7, 4, )`'), ('knows', '`(True, 8, 2, )`'), ('lived', '`(True, 2, 4, )`'), ('rhubarb', '`(True, 2, 9, )`'), ('crazies', '`(True, 7, 1, )`'), ('dock', '`(True, 8, 5, )`'), ('apace', '`(True, 5, 8, )`'), ('mown', '`(True, 0, 5, )`'), ('pears', '`(True, 0, 3, )`'), ('wide', '`(True, 4, 4, )`')]" ] }, { "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, )\n", "adorable (True, 11, 4, )\n", "aeon (True, 11, 4, )\n", "alias (True, 15, 15, )\n", "ancestor (False, 0, 0, )\n", "baritone (False, 0, 0, )\n", "bemusing (False, 0, 0, )\n", "blonds (False, 0, 0, )\n", "bran (True, 1, 9, )\n", "calcite (True, 19, 9, )\n", "candor (True, 17, 12, )\n", "conciseness (False, 0, 0, )\n", "consequent (False, 0, 0, )\n", "cuddle (False, 0, 0, )\n", "damming (True, 17, 2, )\n", "dashboards (False, 0, 0, )\n", "despairing (False, 0, 0, )\n", "dint (False, 0, 0, )\n", "dullard (True, 8, 2, )\n", "dynasty (True, 3, 4, )\n", "employer (False, 0, 0, )\n", "exhorts (True, 0, 8, )\n", "feted (True, 5, 10, )\n", "fill (True, 9, 14, )\n", "flattens (True, 10, 10, )\n", "foghorn (True, 10, 11, )\n", "fortification (True, 19, 16, )\n", "freakish (False, 0, 0, )\n", "frolics (True, 16, 16, )\n", "gall (False, 0, 0, )\n", "gees (True, 17, 0, )\n", "genies (True, 5, 7, )\n", "gets (True, 6, 4, )\n", "hastening (True, 14, 13, )\n", "hits (True, 2, 0, )\n", "hopelessness (False, 0, 0, )\n", "hurlers (True, 18, 0, )\n", "impales (False, 0, 0, )\n", "infix (False, 0, 0, )\n", "inflow (False, 0, 0, )\n", "innumerable (False, 0, 0, )\n", "intentional (False, 0, 0, )\n", "jerkin (False, 0, 0, )\n", "justification (False, 0, 0, )\n", "kitty (True, 8, 15, )\n", "knuckles (True, 17, 19, )\n", "leaving (False, 0, 0, )\n", "like (True, 3, 11, )\n", "limitation (True, 8, 3, )\n", "locoweeds (False, 0, 0, )\n", "loot (True, 3, 19, )\n", "lucking (True, 7, 10, )\n", "lumps (True, 0, 17, )\n", "mercerising (True, 15, 17, )\n", "monickers (False, 0, 0, )\n", "motionless (True, 13, 1, )\n", "naturally (True, 9, 16, )\n", "nighest (True, 15, 4, )\n", "notion (True, 17, 18, )\n", "ogled (True, 1, 18, )\n", "originality (False, 0, 0, )\n", "outings (False, 0, 0, )\n", "pendulous (False, 0, 0, )\n", "piled (True, 1, 10, )\n", "pins (True, 7, 4, )\n", "pithier (False, 0, 0, )\n", "prep (True, 10, 4, )\n", "randomness (False, 0, 0, )\n", "rectors (False, 0, 0, )\n", "redrew (False, 0, 0, )\n", "reformulated (False, 0, 0, )\n", "remoteness (False, 0, 0, )\n", "retaking (True, 6, 0, )\n", "rethink (False, 0, 0, )\n", "rope (True, 9, 4, )\n", "rubier (True, 0, 4, )\n", "sailors (True, 7, 15, )\n", "scowls (False, 0, 0, )\n", "scum (True, 16, 11, )\n", "sepals (True, 6, 10, )\n", "sequencers (False, 0, 0, )\n", "serf (False, 0, 0, )\n", "shoaled (True, 11, 18, )\n", "shook (False, 0, 0, )\n", "sonic (True, 18, 18, )\n", "spottiest (False, 0, 0, )\n", "stag (True, 7, 8, )\n", "stood (False, 0, 0, )\n", "stratum (True, 2, 13, )\n", "strong (True, 4, 19, )\n", "studying (True, 0, 16, )\n", "surtaxing (False, 0, 0, )\n", "tailing (True, 13, 6, )\n", "tears (True, 13, 3, )\n", "teazles (True, 4, 10, )\n", "vans (True, 18, 8, )\n", "wardrobes (False, 0, 0, )\n", "wooded (True, 12, 5, )\n", "worsts (True, 1, 0, )\n", "zings (True, 10, 14, )\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, )\n", "adorable (True, 11, 4, )\n", "aeon (True, 11, 4, )\n", "alias (True, 15, 15, )\n", "ancestor (False, 0, 0, )\n", "baritone (False, 0, 0, )\n", "bemusing (False, 0, 0, )\n", "blonds (False, 0, 0, )\n", "bran (True, 1, 9, )\n", "calcite (True, 19, 9, )\n", "candor (True, 17, 12, )\n", "conciseness (False, 0, 0, )\n", "consequent (False, 0, 0, )\n", "cuddle (False, 0, 0, )\n", "damming (True, 17, 2, )\n", "dashboards (False, 0, 0, )\n", "despairing (False, 0, 0, )\n", "dint (False, 0, 0, )\n", "dullard (True, 8, 2, )\n", "dynasty (True, 3, 4, )\n", "employer (False, 0, 0, )\n", "exhorts (True, 0, 8, )\n", "feted (True, 5, 10, )\n", "fill (True, 9, 14, )\n", "flattens (True, 10, 10, )\n", "foghorn (True, 10, 11, )\n", "fortification (True, 19, 16, )\n", "freakish (False, 0, 0, )\n", "frolics (True, 16, 16, )\n", "gall (False, 0, 0, )\n", "gees (True, 17, 0, )\n", "genies (True, 5, 7, )\n", "gets (True, 6, 4, )\n", "hastening (True, 14, 13, )\n", "hits (True, 2, 0, )\n", "hopelessness (False, 0, 0, )\n", "hurlers (True, 18, 0, )\n", "impales (False, 0, 0, )\n", "infix (False, 0, 0, )\n", "inflow (False, 0, 0, )\n", "innumerable (False, 0, 0, )\n", "intentional (False, 0, 0, )\n", "jerkin (False, 0, 0, )\n", "justification (False, 0, 0, )\n", "kitty (True, 8, 15, )\n", "knuckles (True, 17, 19, )\n", "leaving (False, 0, 0, )\n", "like (True, 3, 11, )\n", "limitation (True, 8, 3, )\n", "locoweeds (False, 0, 0, )\n", "loot (True, 3, 19, )\n", "lucking (True, 7, 10, )\n", "lumps (True, 0, 17, )\n", "mercerising (True, 15, 17, )\n", "monickers (False, 0, 0, )\n", "motionless (True, 13, 1, )\n", "naturally (True, 9, 16, )\n", "nighest (True, 15, 4, )\n", "notion (True, 17, 18, )\n", "ogled (True, 1, 18, )\n", "originality (False, 0, 0, )\n", "outings (False, 0, 0, )\n", "pendulous (False, 0, 0, )\n", "piled (True, 1, 10, )\n", "pins (True, 7, 4, )\n", "pithier (False, 0, 0, )\n", "prep (True, 10, 4, )\n", "randomness (False, 0, 0, )\n", "rectors (False, 0, 0, )\n", "redrew (False, 0, 0, )\n", "reformulated (False, 0, 0, )\n", "remoteness (False, 0, 0, )\n", "retaking (True, 6, 0, )\n", "rethink (False, 0, 0, )\n", "rope (True, 9, 4, )\n", "rubier (True, 0, 4, )\n", "sailors (True, 7, 15, )\n", "scowls (False, 0, 0, )\n", "scum (True, 16, 11, )\n", "sepals (True, 6, 10, )\n", "sequencers (False, 0, 0, )\n", "serf (False, 0, 0, )\n", "shoaled (True, 11, 18, )\n", "shook (False, 0, 0, )\n", "sonic (True, 18, 18, )\n", "spottiest (False, 0, 0, )\n", "stag (True, 7, 8, )\n", "stood (False, 0, 0, )\n", "stratum (True, 2, 13, )\n", "strong (True, 4, 19, )\n", "studying (True, 0, 16, )\n", "surtaxing (False, 0, 0, )\n", "tailing (True, 13, 6, )\n", "tears (True, 13, 3, )\n", "teazles (True, 4, 10, )\n", "vans (True, 18, 8, )\n", "wardrobes (False, 0, 0, )\n", "wooded (True, 12, 5, )\n", "worsts (True, 1, 0, )\n", "zings (True, 10, 14, )\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, ),\n", " ('dogged', 7, 45, ),\n", " ('activist', 51, 35, )]" ] }, "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 }