{ "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", "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": 6, "metadata": {}, "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": 7, "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": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def show_grid(grid):\n", " return lcat(cat(r) for r in grid)" ] }, { "cell_type": "code", "execution_count": 9, "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": 10, "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": 11, "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": 12, "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": 13, "metadata": {}, "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": 14, "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": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "width, height, g, ws = read_wordsearch('wordsearch04.txt')\n", "g, ws" ] }, { "cell_type": "code", "execution_count": 15, "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": 16, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "['absolved',\n", " 'adorable',\n", " 'aeon',\n", " 'alias',\n", " 'bran',\n", " 'calcite',\n", " 'candor',\n", " 'damming',\n", " 'dullard',\n", " 'dynasty',\n", " 'exhorts',\n", " 'feted',\n", " 'fill',\n", " 'flattens',\n", " 'foghorn',\n", " 'fortification',\n", " 'frolics',\n", " 'gees',\n", " 'genies',\n", " 'gets',\n", " 'hastening',\n", " 'hits',\n", " 'hurlers',\n", " 'kitty',\n", " 'knuckles',\n", " 'like',\n", " 'limitation',\n", " 'loot',\n", " 'lucking',\n", " 'lumps',\n", " 'mercerising',\n", " 'motionless',\n", " 'naturally',\n", " 'nighest',\n", " 'notion',\n", " 'ogled',\n", " 'piled',\n", " 'pins',\n", " 'prep',\n", " 'retaking',\n", " 'rope',\n", " 'rubier',\n", " 'sailors',\n", " 'scum',\n", " 'sepals',\n", " 'shoaled',\n", " 'sonic',\n", " 'stag',\n", " 'stratum',\n", " 'strong',\n", " 'studying',\n", " 'tailing',\n", " 'tears',\n", " 'teazles',\n", " 'vans',\n", " 'wooded',\n", " 'worsts',\n", " 'zings']" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[w for w in ws if present(g, w)[0]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What is the longest word that is present?" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'fortification'" ] }, "execution_count": 17, "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": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'justification'" ] }, "execution_count": 18, "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": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "57" ] }, "execution_count": 19, "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": 20, "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": 20, "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": 21, "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": 21, "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": 22, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ancestor Counter({'c': 1, 'a': 1, 't': 1, 's': 1, 'r': 1, 'n': 1, 'e': 1, 'o': 1})\n", "baritone Counter({'a': 1, 'r': 1, 'i': 1, 'b': 1, 't': 1, 'e': 1, 'o': 1, 'n': 1})\n", "bemusing Counter({'g': 1, 'i': 1, 's': 1, 'u': 1, 'b': 1, 'm': 1, 'n': 1, 'e': 1})\n", "blonds Counter({'d': 1, 's': 1, 'b': 1, 'n': 1, 'l': 1, 'o': 1})\n", "conciseness Counter({'s': 3, 'c': 2, 'n': 2, 'e': 2, 'i': 1, 'o': 1})\n", "consequent Counter({'n': 2, 'e': 2, 'c': 1, 't': 1, 's': 1, 'u': 1, 'q': 1, 'o': 1})\n", "cuddle Counter({'d': 2, 'c': 1, 'e': 1, 'l': 1, 'u': 1})\n", "dashboards Counter({'a': 2, 's': 2, 'd': 2, 'r': 1, 'h': 1, 'b': 1, 'o': 1})\n", "*despairing Counter({'i': 2, 'g': 1, 'a': 1, 'r': 1, 's': 1, 'p': 1, 'd': 1, 'e': 1, 'n': 1})\n", "dint Counter({'d': 1, 'i': 1, 't': 1, 'n': 1})\n", "employer Counter({'e': 2, 'r': 1, 'm': 1, 'p': 1, 'l': 1, 'y': 1, 'o': 1})\n", "freakish Counter({'s': 1, 'a': 1, 'i': 1, 'r': 1, 'k': 1, 'h': 1, 'f': 1, 'e': 1})\n", "*gall Counter({'l': 2, 'g': 1, 'a': 1})\n", "hopelessness Counter({'s': 4, 'e': 3, 'h': 1, 'p': 1, 'n': 1, 'l': 1, 'o': 1})\n", "*impales Counter({'s': 1, 'a': 1, 'm': 1, 'p': 1, 'i': 1, 'l': 1, 'e': 1})\n", "infix Counter({'i': 2, 'f': 1, 'n': 1, 'x': 1})\n", "inflow Counter({'i': 1, 'w': 1, 'l': 1, 'n': 1, 'f': 1, 'o': 1})\n", "innumerable Counter({'n': 2, 'e': 2, 'a': 1, 'l': 1, 'r': 1, 'm': 1, 'u': 1, 'b': 1, 'i': 1})\n", "intentional Counter({'n': 3, 't': 2, 'i': 2, 'a': 1, 'l': 1, 'e': 1, 'o': 1})\n", "*jerkin Counter({'r': 1, 'i': 1, 'j': 1, 'n': 1, 'e': 1, 'k': 1})\n", "justification Counter({'i': 3, 't': 2, 'c': 1, 'a': 1, 'j': 1, 's': 1, 'u': 1, 'f': 1, 'o': 1, 'n': 1})\n", "leaving Counter({'g': 1, 'a': 1, 'v': 1, 'i': 1, 'l': 1, 'n': 1, 'e': 1})\n", "locoweeds Counter({'e': 2, 'o': 2, 'c': 1, 's': 1, 'w': 1, 'l': 1, 'd': 1})\n", "monickers Counter({'c': 1, 'r': 1, 'i': 1, 's': 1, 'm': 1, 'n': 1, 'e': 1, 'o': 1, 'k': 1})\n", "originality Counter({'i': 3, 'g': 1, 'a': 1, 'r': 1, 't': 1, 'n': 1, 'l': 1, 'y': 1, 'o': 1})\n", "outings Counter({'g': 1, 'n': 1, 'i': 1, 'u': 1, 's': 1, 't': 1, 'o': 1})\n", "pendulous Counter({'u': 2, 'd': 1, 's': 1, 'p': 1, 'l': 1, 'n': 1, 'e': 1, 'o': 1})\n", "pithier Counter({'i': 2, 'r': 1, 'h': 1, 'p': 1, 't': 1, 'e': 1})\n", "randomness Counter({'s': 2, 'n': 2, 'a': 1, 'r': 1, 'm': 1, 'd': 1, 'e': 1, 'o': 1})\n", "rectors Counter({'r': 2, 'c': 1, 's': 1, 't': 1, 'e': 1, 'o': 1})\n", "redrew Counter({'r': 2, 'e': 2, 'd': 1, 'w': 1})\n", "reformulated Counter({'r': 2, 'e': 2, 'a': 1, 'l': 1, 'm': 1, 'u': 1, 't': 1, 'f': 1, 'd': 1, 'o': 1})\n", "remoteness Counter({'e': 3, 's': 2, 'r': 1, 'm': 1, 't': 1, 'o': 1, 'n': 1})\n", "rethink Counter({'r': 1, 'i': 1, 'h': 1, 'k': 1, 't': 1, 'e': 1, 'n': 1})\n", "scowls Counter({'s': 2, 'c': 1, 'l': 1, 'o': 1, 'w': 1})\n", "sequencers Counter({'e': 3, 's': 2, 'c': 1, 'r': 1, 'u': 1, 'q': 1, 'n': 1})\n", "serf Counter({'e': 1, 'f': 1, 'r': 1, 's': 1})\n", "shook Counter({'o': 2, 'k': 1, 's': 1, 'h': 1})\n", "spottiest Counter({'t': 3, 's': 2, 'i': 1, 'p': 1, 'e': 1, 'o': 1})\n", "stood Counter({'o': 2, 't': 1, 's': 1, 'd': 1})\n", "surtaxing Counter({'g': 1, 'a': 1, 'i': 1, 'r': 1, 's': 1, 'u': 1, 'x': 1, 't': 1, 'n': 1})\n", "wardrobes Counter({'r': 2, 'a': 1, 'b': 1, 's': 1, 'w': 1, 'd': 1, 'e': 1, 'o': 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": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(len(w) for w in makeable_words)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'despairing'" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sorted(makeable_words, key=len)[-1]" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "def do_wordsearch_tasks(fn, show_anyway=False):\n", " width, height, grid, words = read_wordsearch(fn)\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", " lwps = [w for w in used_words if len(w) == len(lwp)]\n", " lwa = sorted(unused_words, key=len)[-1]\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))" ] }, { "cell_type": "code", "execution_count": 26, "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" ] } ], "source": [ "do_wordsearch_tasks('wordsearch04.txt', show_anyway=True)" ] }, { "cell_type": "code", "execution_count": 27, "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": 28, "metadata": { "scrolled": true }, "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", "\n", "wordsearch17.txt\n", "58 words present\n", "Longest word present: complementing, 13 letters (['complementing'])\n", "Longest word absent: upholstering, 12 letters (['domestically', 'upholstering'])\n", "56 unused letters\n", "Longest makeable word: plunderer, 9 (['plunderer'])\n", "\n", "wordsearch32.txt\n", "60 words present\n", "Longest word present: reciprocating, 13 letters (['reciprocating'])\n", "Longest word absent: parenthesise, 12 letters (['collectibles', 'frontrunners', 'parenthesise'])\n", "65 unused letters\n", "Longest makeable word: sultanas, 8 (['sultanas'])\n", "\n", "wordsearch52.txt\n", "51 words present\n", "Longest word present: prefabricated, 13 letters (['prefabricated'])\n", "Longest word absent: catastrophic, 12 letters (['capitalistic', 'catastrophic'])\n", "86 unused letters\n", "Longest makeable word: unimpressed, 11 (['bloodstream', 'brainstorms', 'reassembles', 'rhapsodises', 'synergistic', 'unimpressed'])\n", "\n", "wordsearch62.txt\n", "58 words present\n", "Longest word present: diametrically, 13 letters (['diametrically'])\n", "Longest word absent: streetlights, 12 letters (['harmonically', 'skyrocketing', 'streetlights'])\n", "59 unused letters\n", "Longest makeable word: tabernacle, 10 (['falterings', 'tabernacle'])\n", "\n", "wordsearch76.txt\n", "60 words present\n", "Longest word present: bloodthirstier, 14 letters (['bloodthirstier'])\n", "Longest word absent: incriminating, 13 letters (['incriminating'])\n", "59 unused letters\n", "Longest makeable word: stubbornly, 10 (['leafletted', 'stubbornly'])\n", "\n", "wordsearch94.txt\n", "59 words present\n", "Longest word present: unforgettable, 13 letters (['unforgettable'])\n", "Longest word absent: accommodated, 12 letters (['accommodated'])\n", "69 unused letters\n", "Longest makeable word: respectably, 11 (['predictions', 'respectably'])\n" ] } ], "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": 29, "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": 59, "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": 41, "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": 41, "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": 42, "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": 45, "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": 63, "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": 54, "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": 64, "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": 65, "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" ] } ], "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))" ] }, { "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 }