{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wordsearch\n",
    "Given a text file, consisting of three parts (a grid size, a grid, and a list of words), find:\n",
    "* the words present in the grid, \n",
    "* the longest word present in the grid, \n",
    "* the number of words not present in the grid, \n",
    "* the longest word not present that can be formed from the leftover letters\n",
    "\n",
    "The only words that need be considered are the ones given in the list in the puzzle input.\n",
    "\n",
    "The puzzle consists of:\n",
    "1. A line consisting of _w_`x`_h_, where _w_ and _h_ are integers giving the width and height of the grid.\n",
    "2. The grid itself, consisting of _h_ lines each of _w_ letters.\n",
    "3. A list of words, one word per line, of arbitrary length. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "\n",
    "`...p.mown.\n",
    ".sdse..ee.\n",
    ".e.elad.cr\n",
    "pi.dtir.ah\n",
    "rzsiwovspu\n",
    "oawh.kieab\n",
    "brow.c.rda\n",
    "ecnotops.r\n",
    "d.kc.d...b\n",
    ".staple...`\n",
    "\n",
    "```\n",
    "fhjpamownq\n",
    "wsdseuqeev\n",
    "ieaeladhcr\n",
    "piedtiriah\n",
    "rzsiwovspu\n",
    "oawhakieab\n",
    "browpcfrda\n",
    "ecnotopssr\n",
    "dikchdnpnb\n",
    "bstapleokr\n",
    "```\n",
    "\n",
    "14 words added;  6 directions\n",
    "\n",
    "Present: apace cowhides crazies dock knows lived mown pears probed rhubarb rioted staple tops wide\n",
    "\n",
    "Decoys: adapting bombing boor brick cackles carnal casino chaplets chump coaster coccyxes coddle collies creels crumbled cunt curds curled curlier deepen demeanor dicier dowses ensuing faddish fest fickler foaming gambol garoting gliding gristle grunts guts ibex impugns instants kielbasy lanyard loamier lugs market meanly minuend misprint mitts molested moonshot mucking oaks olives orgasmic pastrami perfect proceed puckered quashed refined regards retraces revel ridges ringlet scoff shinier siren solaria sprain sunder sunup tamped tapes thirds throw tiller times trains tranquil transfix typesets uric wariness welts whimsy winced winced\n",
    "\n",
    "Decoys: fickler, adapting, chump, foaming, molested, carnal, crumbled, guts, minuend, bombing, winced, coccyxes, solaria, shinier, cackles\n",
    "\n",
    "All words: adapting, apace, bombing, cackles, carnal, chump, coccyxes, cowhides, crazies, crumbled, dock, fickler, foaming, guts, knows, lived, minuend, molested, mown, pears, probed, rhubarb, rioted, shinier, solaria, staple, tops, wide, winced\n",
    "\n",
    "Directions:  [('probed', '`(True, 3, 0, <Direction.down: 4>)`'), ('staple', '`(True, 9, 1, <Direction.right: 2>)`'), ('rioted', '`(True, 6, 7, <Direction.upleft: 5>)`'), ('cowhides', '`(True, 8, 3, <Direction.up: 3>)`'), ('tops', '`(True, 7, 4, <Direction.right: 2>)`'), ('knows', '`(True, 8, 2, <Direction.up: 3>)`'), ('lived', '`(True, 2, 4, <Direction.downright: 8>)`'), ('rhubarb', '`(True, 2, 9, <Direction.down: 4>)`'), ('crazies', '`(True, 7, 1, <Direction.up: 3>)`'), ('dock', '`(True, 8, 5, <Direction.up: 3>)`'), ('apace', '`(True, 5, 8, <Direction.up: 3>)`'), ('mown', '`(True, 0, 5, <Direction.right: 2>)`'), ('pears', '`(True, 0, 3, <Direction.downright: 8>)`'), ('wide', '`(True, 4, 4, <Direction.upright: 6>)`')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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": 2,
   "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": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def show_grid(grid):\n",
    "    return lcat(cat(r) for r in grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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": 5,
   "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": 6,
   "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": 7,
   "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": 8,
   "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": "markdown",
   "metadata": {},
   "source": [
    "# All wordsearch puzzles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "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": "markdown",
   "metadata": {},
   "source": [
    "## Huge wordsearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(100, 100)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "puzzle = read_wordsearch('10-wordsearch.txt')\n",
    "puzzle[:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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))\n",
    "\n",
    "def total_found_words_length(puzzles):\n",
    "    return sum(found_words_length(p) for p in puzzles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8092"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "found_words_length(puzzle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 31.3 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "found_words_length(puzzle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1149"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "width, height, grid, words = puzzle\n",
    "len(present_many(grid, words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "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": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def unused_letters(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",
    "    return used_words, unused_letter_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def unused_vowels(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_vowel_count = sum(1 for l in unused_grid for c in l if c in 'aeiou')\n",
    "    return unused_vowel_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def total_max_unfound_word_length(puzzles):\n",
    "    return sum(max_unfound_word_length(p) for p in puzzles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "594"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unused_vowels(puzzle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 31.4 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "unused_vowels(puzzle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# max_unfound_word_length(puzzle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# %%timeit\n",
    "# max_unfound_word_length(puzzle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2217"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uw, unlc = unused_letters(puzzle)\n",
    "sum(unlc[l] for l in unlc)"
   ]
  },
  {
   "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
}