10000Puzzle.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:894b957acf43fb31427008729fa75ff364b9d23359b1aa795c157b5b2381e980"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Preprocessing."
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def anagrams(word):\n",
      "    if len(word) < 2:\n",
      "        yield word\n",
      "    else:\n",
      "        for i, letter in enumerate(word):\n",
      "            if not letter in word[:i]:\n",
      "                for j in anagrams(word[:i]+word[i+1:]):\n",
      "                    yield j + letter\n",
      "\n",
      "with open('words.txt') as f:\n",
      "    wordlist = set(word.upper().rstrip() for word in f.readlines())\n",
      "\n",
      "print 'Anagrams on their own'\n",
      "anagrams_0 = set()\n",
      "for word in wordlist:\n",
      "    for a in anagrams(word):\n",
      "        if a in wordlist:\n",
      "            anagrams_0.add(word + '/n')\n",
      "            break\n",
      "with open('anagrams-0.txt', 'w') as f:\n",
      "    f.writelines(anagrams_0)\n",
      "\n",
      "print 'Anagrams with one extra char'\n",
      "anagrams_1 = set()\n",
      "for word in wordlist:\n",
      "    for i in range(ord('a'), ord('z')+1):\n",
      "        for a in anagrams(word + chr(i)):\n",
      "            if a in wordlist:\n",
      "                anagrams_1.add(word + '/n')\n",
      "                break\n",
      "with open('anagrams-1.txt', 'w') as f:\n",
      "    f.writelines(anagrams_1)\n",
      "\n",
      "print 'Anagrams with two extra chars'\n",
      "anagrams_2 = set()\n",
      "for word in wordlist:\n",
      "    for i in range(ord('a'), ord('z')+1):\n",
      "        for j in range(ord('a'), ord('z')+1):\n",
      "            for a in anagrams(word + chr(i) + chr(j)):\n",
      "                if a in wordlist:\n",
      "                    anagrams_2.add(word + '/n')\n",
      "                    break\n",
      "with open('anagrams-2.txt', 'w') as f:\n",
      "    f.writelines(anagrams_2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Anagrams on their own\n"
       ]
      },
      {
       "ename": "KeyboardInterrupt",
       "evalue": "",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-180-559a18f7a2f1>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     14\u001b[0m \u001b[0managrams_0\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mset\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mword\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mwordlist\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 16\u001b[1;33m     \u001b[1;32mfor\u001b[0m \u001b[0ma\u001b[0m \u001b[1;32min\u001b[0m \u001b[0managrams\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     17\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0ma\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mwordlist\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     18\u001b[0m             \u001b[0managrams_0\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0madd\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;34m'/n'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32m<ipython-input-180-559a18f7a2f1>\u001b[0m in \u001b[0;36managrams\u001b[1;34m(word)\u001b[0m\n\u001b[0;32m      5\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m                 \u001b[1;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32min\u001b[0m \u001b[0managrams\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m                     \u001b[1;32myield\u001b[0m \u001b[0mj\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mletter\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32m<ipython-input-180-559a18f7a2f1>\u001b[0m in \u001b[0;36managrams\u001b[1;34m(word)\u001b[0m\n\u001b[0;32m      5\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m                 \u001b[1;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32min\u001b[0m \u001b[0managrams\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m                     \u001b[1;32myield\u001b[0m \u001b[0mj\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mletter\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32m<ipython-input-180-559a18f7a2f1>\u001b[0m in \u001b[0;36managrams\u001b[1;34m(word)\u001b[0m\n\u001b[0;32m      5\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m                 \u001b[1;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32min\u001b[0m \u001b[0managrams\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m                     \u001b[1;32myield\u001b[0m \u001b[0mj\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mletter\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32m<ipython-input-180-559a18f7a2f1>\u001b[0m in \u001b[0;36managrams\u001b[1;34m(word)\u001b[0m\n\u001b[0;32m      6\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mletter\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      7\u001b[0m                 \u001b[1;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32min\u001b[0m \u001b[0managrams\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 8\u001b[1;33m                     \u001b[1;32myield\u001b[0m \u001b[0mj\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mletter\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      9\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     10\u001b[0m \u001b[1;32mwith\u001b[0m \u001b[0mopen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'words.txt'\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
       ]
      }
     ],
     "prompt_number": 180
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Main code."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from __future__ import division\n",
      "import hashlib\n",
      "import re\n",
      "\n",
      "with open('words.txt') as f:\n",
      "    wordlist = set(word.upper().rstrip() for word in f.readlines())\n",
      "m = hashlib.sha1()\n",
      "sha_words = {}\n",
      "match_wordlist_3_or_fewer = set()\n",
      "\n",
      "for word in wordlist:\n",
      "    m = hashlib.sha1(word.lower()).hexdigest()\n",
      "    sha_words[word] = m\n",
      "    if len(word) <= 3:\n",
      "        match_wordlist_3_or_fewer.add(word)\n",
      "\n",
      "anagrams_0 = set()\n",
      "anagrams_1 = set()\n",
      "anagrams_2 = set()\n",
      "with open('anagrams-0.txt') as f:\n",
      "    anagrams_0 = set(word.upper().rstrip() for word in f.readlines())\n",
      "with open('anagrams-1.txt') as f:\n",
      "    anagrams_1 = set(word.upper().rstrip() for word in f.readlines())\n",
      "with open('anagrams-2.txt') as f:\n",
      "    anagrams_2 = set(word.upper().rstrip() for word in f.readlines())\n",
      "\n",
      "have_anagrams = {True: anagrams_0, False: wordlist.difference(anagrams_0)}\n",
      "have_anagrams_with_one = {True: anagrams_1, False: wordlist.difference(anagrams_1)}\n",
      "have_anagrams_with_two = {True: anagrams_2, False: wordlist.difference(anagrams_2)}\n",
      "\n",
      "with open('country-codes.txt') as f:\n",
      "    match_country_codes = set(word.upper().rstrip() for word in f.readlines())\n",
      "with open('USPS-state-codes.txt') as f:\n",
      "    match_state_postal_codes = set(word.upper().rstrip() for word in f.readlines())\n",
      "with open('chemical-elements.txt') as f:\n",
      "    match_chemical_element_symbols = set(word.upper().rstrip() for word in f.readlines())\n",
      "\n",
      "scrabble_points = {\n",
      "    'a':  1, 'b':  3, 'c': 3, 'd': 2,\n",
      "    'e':  1, 'f':  4, 'g': 2, 'h': 4,\n",
      "    'i':  1, 'j':  8, 'k': 5, 'l': 1,\n",
      "    'm':  3, 'n':  1, 'o': 1, 'p': 3,\n",
      "    'q': 10, 'r':  1, 's': 1, 't': 1,\n",
      "    'u':  1, 'v':  4, 'w': 4, 'x': 8,\n",
      "    'y':  4, 'z': 10,\n",
      "}"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 200
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Helper functions"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def helper_bounds(bounds):\n",
      "    lower = upper = 0;\n",
      "    percentage = False\n",
      "\n",
      "    res = re.match(r'^exactly ([0-9.]+)\\%', bounds)\n",
      "    res2 = re.match(r'^between ([0-9.]+)\\% and ([0-9.]+)\\% \\(inclusive\\)', bounds)\n",
      "    if res:\n",
      "        # A percentage\n",
      "        lower = upper = float(res.group(1))\n",
      "        percentage = True\n",
      "    elif res2:\n",
      "        # Also a percentage\n",
      "        lower = float(res2.group(1))\n",
      "        upper = float(res2.group(2))\n",
      "        percentage = True\n",
      "    else:\n",
      "        # An absolute number or range\n",
      "        res = re.match(r'^([0-9]+)', bounds)\n",
      "        if res:\n",
      "            lower = upper = int(res.group(1))\n",
      "        else:\n",
      "            res = re.match(r'^between ([0-9]+) and ([0-9]+) \\(inclusive\\)', bounds)\n",
      "            if res:\n",
      "                lower = int(res.group(1))\n",
      "                upper = int(res.group(2))\n",
      "\n",
      "    return lower, upper, percentage\n",
      "\n",
      "def find_nonoverlapping(word, dataset, recurse):\n",
      "    count = 0\n",
      "    start = 0\n",
      "    first_match = -1\n",
      "    for end in range(1, len(word) + 1):\n",
      "        if word[start:end].upper() in dataset:\n",
      "            count += end - start\n",
      "            start = end\n",
      "            if first_match < 0:\n",
      "                first_match = end\n",
      "\n",
      "    if recurse and (first_match > 0):\n",
      "        for i in range(1, first_match):\n",
      "            subcount = find_nonoverlapping(word[i:], dataset, False)\n",
      "            if subcount > count:\n",
      "                count = subcount\n",
      "\n",
      "    return count"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 232
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Parsers"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def parse_contains(line):\n",
      "    res = re.match(\"^Contains: (.*)$\", line)\n",
      "    if res:\n",
      "        result = []\n",
      "        for word in wordlist:\n",
      "            include = True\n",
      "            for c in res.group(1):\n",
      "                include = include and c in word\n",
      "            if include:\n",
      "                result.append(word)\n",
      "        return result\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_anagram(line):\n",
      "    if 'anagram' in line:\n",
      "        res = re.match(r'^Has at least one anagram that is also in the word list: (.*)', line)\n",
      "        if res:\n",
      "            return have_anagrams['YES' == res.group(1)]\n",
      "\n",
      "        res = re.match(r'^Can be combined with one additional letter to produce an anagram of something in the word list: (.*)', line)\n",
      "        if res:\n",
      "            return have_anagrams_with_one['YES' == res.group(1)]\n",
      "\n",
      "        res = re.match(r'^Can be combined with two additional letters to produce an anagram of something in the word list: (.*)', line)\n",
      "        if res:\n",
      "            return have_anagrams_with_two['YES' == res.group(1)]\n",
      "\n",
      "        assert False, 'Unknown anagram: %s' % line\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_marked(line):\n",
      "    res = re.match(r'If you marked nonoverlapping (.*), you could mark at most: (.*)', line)\n",
      "    if res:\n",
      "        match_type = res.group(1)\n",
      "        if match_type == 'officially-assigned ISO 3166-1 alpha-2 country codes':\n",
      "            dataset = match_country_codes\n",
      "        elif match_type == 'US state postal abbreviations':\n",
      "            dataset = match_state_postal_codes\n",
      "        elif match_type == 'chemical element symbols (atomic number 112 or below)':\n",
      "            dataset = match_chemical_element_symbols\n",
      "        elif match_type == 'occurrences of words in the word list that are 3 or fewer letters long':\n",
      "            dataset = match_wordlist_3_or_fewer\n",
      "        else:\n",
      "            assert False, 'Unknown marking: %s' % res.group(1)\n",
      "\n",
      "        lower, upper, percentage = helper_bounds(res.group(2))\n",
      "\n",
      "        result = []\n",
      "        for word in wordlist:\n",
      "            count = find_nonoverlapping(word, dataset, True)\n",
      "            if percentage:\n",
      "                count = count/len(word)*100\n",
      "            if count >= lower and count <= upper:\n",
      "                result.append(word)\n",
      "        return result\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_scrabble(line):\n",
      "    res = re.match(r'^Base Scrabble score: (.+)', line)\n",
      "    if res:\n",
      "        lower, upper, percentage = helper_bounds(res.group(1))\n",
      "\n",
      "        result = []\n",
      "        for word in wordlist:\n",
      "            score = sum(scrabble_points[c.lower()] for c in word)\n",
      "            if score >= lower and score <= upper:\n",
      "                result.append(word)\n",
      "        return result\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_sha1(line):\n",
      "    res = re.match(\"^SHA-1 hash of lowercased word, expressed in hexadecimal, (.*)$\", line)\n",
      "    if res:\n",
      "        subres = re.match(r'^starts with: ([0-9A-F]+)', res.group(1))\n",
      "        if (subres):\n",
      "            g = subres.group(1).lower()\n",
      "            return [word for (word, h) in sha_words.iteritems() if h.startswith(g)]\n",
      "\n",
      "        subres = re.match(r'^ends with: ([0-9A-F]+)', res.group(1))\n",
      "        if (subres):\n",
      "            g = subres.group(1).lower()\n",
      "            return [word for (word, h) in sha_words.iteritems() if h.endswith(g)]\n",
      "\n",
      "        subres = re.match(r'^contains: ([0-9A-F]+)', res.group(1))\n",
      "        if (subres):\n",
      "            g = subres.group(1).lower()\n",
      "            return [word for (word, h) in sha_words.iteritems() if g in h]\n",
      "\n",
      "        assert False, 'Unknown SHA-1 matching: %s' % res.group(1)\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_sum_letters(line):\n",
      "    res = re.match(r'^Sum of letters \\(A=1, B=2, etc\\): (.+)', line)\n",
      "    if res:\n",
      "        lower, upper, percentage = helper_bounds(res.group(1))\n",
      "\n",
      "        result = []\n",
      "        for word in wordlist:\n",
      "            letter_sum = sum(ord(c) - ord('A') + 1 for c in word)\n",
      "            if letter_sum >= lower and letter_sum <= upper:\n",
      "                result.append(word)\n",
      "        return result\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_sum_letters_divisible(line):\n",
      "    res = re.match(r'^Sum of letters \\(A=1, B=2, etc\\) is divisible by ([0-9]): (.+)', line)\n",
      "    if res:\n",
      "        divisor = int(res.group(1))\n",
      "        divisible = 'YES' == res.group(2)\n",
      "\n",
      "        result = []\n",
      "        for word in wordlist:\n",
      "            letter_sum = sum(ord(c) - ord('A') + 1 for c in word)\n",
      "            if letter_sum % divisor == 0 and divisible:\n",
      "                result.append(word)\n",
      "            elif letter_sum % divisor != 0 and not divisible:\n",
      "                result.append(word)\n",
      "        return result\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "def parse_vowels(line):\n",
      "    res = re.match(r'^Vowels: (.+)', line)\n",
      "    if res:\n",
      "        lower, upper, percentage = helper_bounds(res.group(1))\n",
      "\n",
      "        result = []\n",
      "        for word in wordlist:\n",
      "            vowel_sum = sum(1 for c in word if c in 'aeiou')\n",
      "            if percentage:\n",
      "                vowel_sum = vowel_sum/len(word)*100\n",
      "            if vowel_sum >= lower and vowel_sum <= upper:\n",
      "                result.append(word)\n",
      "        return result\n",
      "    else:\n",
      "        return None\n",
      "\n",
      "all_matchers = [parse_contains,\n",
      "                parse_anagram,\n",
      "                parse_marked,\n",
      "                parse_scrabble,\n",
      "                parse_sha1,\n",
      "                parse_sum_letters,\n",
      "                parse_sum_letters_divisible,\n",
      "                parse_vowels,\n",
      "]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 234
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "File processor"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def process_file(fname):\n",
      "    with open(fname) as f:\n",
      "        lines = [line.rstrip() for line in f.readlines()]\n",
      "    words = None\n",
      "    for line in lines:\n",
      "        print line\n",
      "        matched = 0\n",
      "        for matcher in all_matchers:\n",
      "            res = matcher(line)\n",
      "            if res is None:\n",
      "                continue\n",
      "            matched = 1\n",
      "            if words is None:\n",
      "                words = set(res)\n",
      "            else:\n",
      "                if not set(res):\n",
      "                    print 'About to fail. Last set of words:'\n",
      "                    print words\n",
      "                words = words.intersection(set(res))\n",
      "            break\n",
      "        assert matched, \"Line %s not matched\" % (line,)\n",
      "    return words\n",
      "\n",
      "print process_file(\"row0/row0_col62.txt\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Contains: KER\n",
        "SHA-1 hash of lowercased word, expressed in hexadecimal, starts with: BE"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Sum of letters (A=1, B=2, etc): between 87 and 93 (inclusive)"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "set(['PARTAKER'])"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 230
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Set up pyramid."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rows=125\n",
      "cols=142\n",
      "\n",
      "pyramid = [[None]*cols for i in range(rows)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 45,
       "text": [
        "142"
       ]
      }
     ],
     "prompt_number": 45
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Load in pyramid data."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rule_types = set()\n",
      "pyramid_data = [[{}]*cols for i in range(rows)]\n",
      "\n",
      "for dirname in listdir('.'):\n",
      "    if dirname.startswith('row'):\n",
      "        row = int(dirname[3:])\n",
      "        for filename in listdir(dirname):\n",
      "            col = int(filename[(len(dirname) + 4):][:-4])\n",
      "            #with open('%s/%s' % (dirname, filename)) as f:\n",
      "                #ruleline = f.readline()\n",
      "                #ruletype, ruleval = ruleline.rsplit(':', 1)\n",
      "                #rule_types.add(ruletype)\n",
      "                #pyramid_data[row][col][ruletype] = ruleval[1:-1]\n",
      "                #if ruletype.startswith('Sum of letters'):\n",
      "                #    print ruleline\n",
      "            pyramid_data[row][col] = process_file('%s/%s' % (dirname, filename))\n",
      "\n",
      "#for rule in rule_types:\n",
      "#    print rule\n",
      "\n",
      "#for key, val in pyramid_data[1][100].iteritems():\n",
      "#    print '%s: %s' % (key, val)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Can be combined with one additional letter to produce an anagram of something in the word list: NO\n",
        "Can be combined with two additional letters to produce an anagram of something in the word list: NO\n",
        "Contains: RY"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "If you marked nonoverlapping officially-assigned ISO 3166-1 alpha-2 country codes, you could mark at most: between 47.0% and 50.0% (inclusive) of the letters"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Most common vowel(s) each appear(s): between 0 and 1 (inclusive) times"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      },
      {
       "ename": "AssertionError",
       "evalue": "Line Most common vowel(s) each appear(s): between 0 and 1 (inclusive) times not matched",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-221-304a44c4222b>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     14\u001b[0m                 \u001b[1;31m#if ruletype.startswith('Sum of letters'):\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m                 \u001b[1;31m#    print ruleline\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 16\u001b[1;33m             \u001b[0mpyramid_data\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mrow\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mcol\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mprocess_file\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'%s/%s'\u001b[0m \u001b[1;33m%\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mdirname\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfilename\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     17\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     18\u001b[0m \u001b[1;31m#for rule in rule_types:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;32m<ipython-input-220-e29febdbd1bc>\u001b[0m in \u001b[0;36mprocess_file\u001b[1;34m(fname)\u001b[0m\n\u001b[0;32m    248\u001b[0m                 \u001b[0mwords\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mwords\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mintersection\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mset\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    249\u001b[0m             \u001b[1;32mbreak\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 250\u001b[1;33m         \u001b[1;32massert\u001b[0m \u001b[0mmatched\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"Line %s not matched\"\u001b[0m \u001b[1;33m%\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mline\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    251\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mwords\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    252\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
        "\u001b[1;31mAssertionError\u001b[0m: Line Most common vowel(s) each appear(s): between 0 and 1 (inclusive) times not matched"
       ]
      }
     ],
     "prompt_number": 221
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Load in words."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "words = []\n",
      "words_by_length = {}\n",
      "sum_of_letters = {}\n",
      "\n",
      "with open('words.txt') as f:\n",
      "    for word in f:\n",
      "        word = word[:-1]\n",
      "        words.append(word)\n",
      "\n",
      "        wordlen = len(word)\n",
      "        if not words_by_length.has_key(wordlen):\n",
      "            words_by_length[wordlen] = set()\n",
      "        words_by_length[wordlen].add(word)\n",
      "\n",
      "        wordsum = sum_word_by_letters(word)\n",
      "        if not sum_of_letters.has_key(wordsum):\n",
      "            sum_of_letters[wordsum] = set()\n",
      "        sum_of_letters[wordsum].add(word)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "KeyError",
       "evalue": "1",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-189-e8fc4fa4e985>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     18\u001b[0m         \u001b[0msum_of_letters\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mwordsum\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0madd\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mword\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     19\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 20\u001b[1;33m \u001b[1;32mprint\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mwords_by_length\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
        "\u001b[1;31mKeyError\u001b[0m: 1"
       ]
      }
     ],
     "prompt_number": 189
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Load in examples."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "detailed = {}\n",
      "normal = {}\n",
      "\n",
      "for filename in listdir('examples'):\n",
      "    with open('examples/%s' % filename) as f:\n",
      "        wordline = f.readline()\n",
      "        word = wordline.rsplit(' ', 1)[1][:-2]\n",
      "        if filename.startswith('detailed'):\n",
      "            detailed[word] = []\n",
      "        elif filename.startswith('normal'):\n",
      "            normal[word] = []\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 34
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}