+++ /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": "code",
- "execution_count": 13,
- "metadata": {
- "collapsed": false
- },
- "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": 14,
- "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": 15,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def show_grid(grid):\n",
- " return lcat(cat(r) for r in grid)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 16,
- "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": 17,
- "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": 18,
- "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": 20,
- "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": 22,
- "metadata": {
- "collapsed": false
- },
- "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": 50,
- "metadata": {
- "collapsed": false,
- "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": 50,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "width, height, g, ws = read_wordsearch('wordsearch04.txt')\n",
- "g, ws"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 51,
- "metadata": {
- "collapsed": false,
- "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": 52,
- "metadata": {
- "collapsed": false,
- "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": 52,
- "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": 53,
- "metadata": {
- "collapsed": false
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "'fortification'"
- ]
- },
- "execution_count": 53,
- "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": 54,
- "metadata": {
- "collapsed": false
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "'justification'"
- ]
- },
- "execution_count": 54,
- "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": 55,
- "metadata": {
- "collapsed": false
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "57"
- ]
- },
- "execution_count": 55,
- "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": 56,
- "metadata": {
- "collapsed": false,
- "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": 56,
- "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": 57,
- "metadata": {
- "collapsed": false,
- "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": 57,
- "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": 59,
- "metadata": {
- "collapsed": false,
- "scrolled": true
- },
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "ancestor Counter({'c': 1, 'a': 1, 's': 1, 't': 1, 'n': 1, 'r': 1, 'o': 1, 'e': 1})\n",
- "baritone Counter({'a': 1, 'i': 1, 'r': 1, 't': 1, 'b': 1, 'n': 1, 'o': 1, 'e': 1})\n",
- "bemusing Counter({'g': 1, 'u': 1, 'i': 1, 's': 1, 'n': 1, 'm': 1, 'b': 1, 'e': 1})\n",
- "blonds Counter({'s': 1, 'd': 1, 'n': 1, 'b': 1, 'o': 1, 'l': 1})\n",
- "conciseness Counter({'s': 3, 'c': 2, 'n': 2, 'e': 2, 'i': 1, 'o': 1})\n",
- "consequent Counter({'n': 2, 'e': 2, 'u': 1, 'c': 1, 's': 1, 't': 1, 'q': 1, 'o': 1})\n",
- "cuddle Counter({'d': 2, 'u': 1, 'e': 1, 'c': 1, 'l': 1})\n",
- "dashboards Counter({'a': 2, 's': 2, 'd': 2, 'o': 1, 'r': 1, 'b': 1, 'h': 1})\n",
- "*despairing Counter({'i': 2, 'g': 1, 'a': 1, 's': 1, 'r': 1, 'd': 1, 'n': 1, 'p': 1, 'e': 1})\n",
- "dint Counter({'d': 1, 'n': 1, 'i': 1, 't': 1})\n",
- "employer Counter({'e': 2, 'y': 1, 'r': 1, 'm': 1, 'p': 1, 'o': 1, 'l': 1})\n",
- "freakish Counter({'k': 1, 'a': 1, 'i': 1, 'r': 1, 'f': 1, 's': 1, 'h': 1, 'e': 1})\n",
- "*gall Counter({'l': 2, 'g': 1, 'a': 1})\n",
- "hopelessness Counter({'s': 4, 'e': 3, 'h': 1, 'n': 1, 'p': 1, 'o': 1, 'l': 1})\n",
- "*impales Counter({'s': 1, 'a': 1, 'i': 1, 'm': 1, 'e': 1, 'p': 1, 'l': 1})\n",
- "infix Counter({'i': 2, 'f': 1, 'n': 1, 'x': 1})\n",
- "inflow Counter({'i': 1, 'w': 1, 'f': 1, 'n': 1, 'o': 1, 'l': 1})\n",
- "innumerable Counter({'n': 2, 'e': 2, 'u': 1, 'l': 1, 'a': 1, 'i': 1, 'r': 1, 'm': 1, 'b': 1})\n",
- "intentional Counter({'n': 3, 'i': 2, 't': 2, 'a': 1, 'l': 1, 'o': 1, 'e': 1})\n",
- "*jerkin Counter({'k': 1, 'i': 1, 'r': 1, 'n': 1, 'j': 1, 'e': 1})\n",
- "justification Counter({'i': 3, 't': 2, 'u': 1, 'c': 1, 's': 1, 'n': 1, 'f': 1, 'j': 1, 'o': 1, 'a': 1})\n",
- "leaving Counter({'g': 1, 'l': 1, 'a': 1, 'i': 1, 'n': 1, 'v': 1, 'e': 1})\n",
- "locoweeds Counter({'o': 2, 'e': 2, 'c': 1, 's': 1, 'd': 1, 'w': 1, 'l': 1})\n",
- "monickers Counter({'k': 1, 'c': 1, 's': 1, 'i': 1, 'r': 1, 'n': 1, 'm': 1, 'o': 1, 'e': 1})\n",
- "originality Counter({'i': 3, 'g': 1, 'a': 1, 'r': 1, 't': 1, 'n': 1, 'y': 1, 'o': 1, 'l': 1})\n",
- "outings Counter({'g': 1, 'u': 1, 's': 1, 'i': 1, 't': 1, 'n': 1, 'o': 1})\n",
- "pendulous Counter({'u': 2, 's': 1, 'd': 1, 'n': 1, 'l': 1, 'p': 1, 'o': 1, 'e': 1})\n",
- "pithier Counter({'i': 2, 'r': 1, 't': 1, 'p': 1, 'h': 1, 'e': 1})\n",
- "randomness Counter({'s': 2, 'n': 2, 'a': 1, 'r': 1, 'd': 1, 'm': 1, 'o': 1, 'e': 1})\n",
- "rectors Counter({'r': 2, 'c': 1, 's': 1, 't': 1, 'o': 1, 'e': 1})\n",
- "redrew Counter({'e': 2, 'r': 2, 'd': 1, 'w': 1})\n",
- "reformulated Counter({'r': 2, 'e': 2, 'u': 1, 'a': 1, 'f': 1, 't': 1, 'm': 1, 'l': 1, 'd': 1, 'o': 1})\n",
- "remoteness Counter({'e': 3, 's': 2, 'r': 1, 't': 1, 'm': 1, 'n': 1, 'o': 1})\n",
- "rethink Counter({'k': 1, 'i': 1, 'r': 1, 't': 1, 'n': 1, 'h': 1, 'e': 1})\n",
- "scowls Counter({'s': 2, 'w': 1, 'c': 1, 'o': 1, 'l': 1})\n",
- "sequencers Counter({'e': 3, 's': 2, 'u': 1, 'c': 1, 'r': 1, 'n': 1, 'q': 1})\n",
- "serf Counter({'f': 1, 'r': 1, 's': 1, 'e': 1})\n",
- "shook Counter({'o': 2, 'k': 1, 'h': 1, 's': 1})\n",
- "spottiest Counter({'t': 3, 's': 2, 'i': 1, 'p': 1, 'o': 1, 'e': 1})\n",
- "stood Counter({'o': 2, 'd': 1, 't': 1, 's': 1})\n",
- "surtaxing Counter({'i': 1, 'u': 1, 'x': 1, 'g': 1, 'a': 1, 's': 1, 'r': 1, 't': 1, 'n': 1})\n",
- "wardrobes Counter({'r': 2, 'a': 1, 's': 1, 'd': 1, 'w': 1, 'b': 1, 'o': 1, 'e': 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": 48,
- "metadata": {
- "collapsed": false
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "10"
- ]
- },
- "execution_count": 48,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "max(len(w) for w in makeable_words)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 49,
- "metadata": {
- "collapsed": false
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "'despairing'"
- ]
- },
- "execution_count": 49,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "sorted(makeable_words, key=len)[-1]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 74,
- "metadata": {
- "collapsed": false
- },
- "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": 75,
- "metadata": {
- "collapsed": false
- },
- "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": 70,
- "metadata": {
- "collapsed": false
- },
- "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": 76,
- "metadata": {
- "collapsed": false,
- "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": 38,
- "metadata": {
- "collapsed": false
- },
- "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": "code",
- "execution_count": null,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": []
- }
- ],
- "metadata": {
- "kernelspec": {
- "display_name": "Python 3",
- "language": "python",
- "name": "python3"
- },
- "language_info": {
- "codemirror_mode": {
- "name": "ipython",
- "version": 3
- },
- "file_extension": ".py",
- "mimetype": "text/x-python",
- "name": "python",
- "nbconvert_exporter": "python",
- "pygments_lexer": "ipython3",
- "version": "3.5.2"
- }
- },
- "nbformat": 4,
- "nbformat_minor": 0
-}