word-chains/word-chain-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Word chains\n",
   8     "\n",
   9     "\"Word chain\" puzzles are where you transform one word into another, by changing one letter at a time, with all the intermediate steps being valid words. \n",
  10     "\n",
  11     "For instance, you can transform 'rash' to 'jags' like this:\n",
  12     "\n",
  13     "```\n",
  14     "rash\n",
  15     "Bash\n",
  16     "basS\n",
  17     "baGs\n",
  18     "Jags\n",
  19     "```\n",
  20     "\n",
  21     "(the capital letter is the one changed in each step).\n",
  22     "\n",
  23     "## Part 1\n",
  24     "\n",
  25     "Given this [list of words](words4.txt), what is the minimum number of steps to go from `vice` to `wars`?"
  26    ]
  27   },
  28   {
  29    "cell_type": "code",
  30    "execution_count": 1,
  31    "metadata": {
  32     "collapsed": true
  33    },
  34    "outputs": [],
  35    "source": [
  36     "import string\n",
  37     "import heapq"
  38    ]
  39   },
  40   {
  41    "cell_type": "code",
  42    "execution_count": 2,
  43    "metadata": {},
  44    "outputs": [
  45     {
  46      "data": {
  47       "text/plain": [
  48        "2336"
  49       ]
  50      },
  51      "execution_count": 2,
  52      "metadata": {},
  53      "output_type": "execute_result"
  54     }
  55    ],
  56    "source": [
  57     "words = [w.strip() for w in open('words4.txt').readlines()]\n",
  58     "len(words)"
  59    ]
  60   },
  61   {
  62    "cell_type": "code",
  63    "execution_count": 3,
  64    "metadata": {
  65     "collapsed": true
  66    },
  67    "outputs": [],
  68    "source": [
  69     "def adjacents(word):\n",
  70     "    return [word[0:i] + l + word[i+1:]\n",
  71     "           for i in range(len(word))\n",
  72     "           for l in string.ascii_lowercase\n",
  73     "           if l != word[i]]"
  74    ]
  75   },
  76   {
  77    "cell_type": "code",
  78    "execution_count": 4,
  79    "metadata": {
  80     "collapsed": true
  81    },
  82    "outputs": [],
  83    "source": [
  84     "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
  85     "             for w in words}"
  86    ]
  87   },
  88   {
  89    "cell_type": "code",
  90    "execution_count": 5,
  91    "metadata": {
  92     "collapsed": true
  93    },
  94    "outputs": [],
  95    "source": [
  96     "def distance(w1, w2):\n",
  97     "    return sum(1 for i in range(len(w1))\n",
  98     "               if w1[i] != w2[i])"
  99    ]
 100   },
 101   {
 102    "cell_type": "code",
 103    "execution_count": 6,
 104    "metadata": {
 105     "collapsed": true
 106    },
 107    "outputs": [],
 108    "source": [
 109     "def extend(chain):\n",
 110     "    return [chain + [s] for s in neighbours[chain[-1]]\n",
 111     "           if s not in chain]"
 112    ]
 113   },
 114   {
 115    "cell_type": "code",
 116    "execution_count": 7,
 117    "metadata": {
 118     "collapsed": true
 119    },
 120    "outputs": [],
 121    "source": [
 122     "def bfs_search(start, target, debug=False):\n",
 123     "    return bfs([[start]], target, debug=debug)"
 124    ]
 125   },
 126   {
 127    "cell_type": "code",
 128    "execution_count": 8,
 129    "metadata": {
 130     "collapsed": true
 131    },
 132    "outputs": [],
 133    "source": [
 134     "def bfs(agenda, goal, debug=False):\n",
 135     "    finished = False\n",
 136     "    while not finished and agenda:\n",
 137     "        current = agenda[0]\n",
 138     "        if debug:\n",
 139     "            print(current)\n",
 140     "        if current[-1] == goal:\n",
 141     "            finished = True\n",
 142     "        else:\n",
 143     "            successors = extend(current)\n",
 144     "            agenda = agenda[1:] + successors\n",
 145     "    if agenda:\n",
 146     "        return current\n",
 147     "    else:\n",
 148     "        return None        "
 149    ]
 150   },
 151   {
 152    "cell_type": "code",
 153    "execution_count": 9,
 154    "metadata": {
 155     "collapsed": true
 156    },
 157    "outputs": [],
 158    "source": [
 159     "def dfs_search(start, target, debug=False):\n",
 160     "    return dfs([[start]], target, debug=debug)"
 161    ]
 162   },
 163   {
 164    "cell_type": "code",
 165    "execution_count": 10,
 166    "metadata": {
 167     "collapsed": true
 168    },
 169    "outputs": [],
 170    "source": [
 171     "def dfs(agenda, goal, debug=False):\n",
 172     "    finished = False\n",
 173     "    while not finished and agenda:\n",
 174     "        current = agenda[0]\n",
 175     "        if debug:\n",
 176     "            print(current)\n",
 177     "        if current[-1] == goal:\n",
 178     "            finished = True\n",
 179     "        else:\n",
 180     "            successors = extend(current)\n",
 181     "            agenda = successors + agenda[1:]\n",
 182     "    if agenda:\n",
 183     "        return current\n",
 184     "    else:\n",
 185     "        return None        "
 186    ]
 187   },
 188   {
 189    "cell_type": "code",
 190    "execution_count": 57,
 191    "metadata": {
 192     "collapsed": true
 193    },
 194    "outputs": [],
 195    "source": [
 196     "def astar_search(start, target, debug=False):\n",
 197     "    agenda = [(distance(start, target), [start])]\n",
 198     "    heapq.heapify(agenda)\n",
 199     "    return astar(agenda, target, debug=debug)"
 200    ]
 201   },
 202   {
 203    "cell_type": "code",
 204    "execution_count": 55,
 205    "metadata": {
 206     "collapsed": true
 207    },
 208    "outputs": [],
 209    "source": [
 210     "def astar(agenda, goal, debug=False):\n",
 211     "    finished = False\n",
 212     "    while not finished and agenda:\n",
 213     "        _, current = heapq.heappop(agenda)\n",
 214     "        if debug:\n",
 215     "            print(current)\n",
 216     "        if current[-1] == goal:\n",
 217     "            finished = True\n",
 218     "        else:\n",
 219     "            successors = extend(current)\n",
 220     "            for s in successors:\n",
 221     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 222     "    if agenda:\n",
 223     "        return current\n",
 224     "    else:\n",
 225     "        return None        "
 226    ]
 227   },
 228   {
 229    "cell_type": "code",
 230    "execution_count": 58,
 231    "metadata": {},
 232    "outputs": [
 233     {
 234      "data": {
 235       "text/plain": [
 236        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
 237       ]
 238      },
 239      "execution_count": 58,
 240      "metadata": {},
 241      "output_type": "execute_result"
 242     }
 243    ],
 244    "source": [
 245     "astar_search('vice', 'wars')"
 246    ]
 247   },
 248   {
 249    "cell_type": "code",
 250    "execution_count": 60,
 251    "metadata": {},
 252    "outputs": [
 253     {
 254      "data": {
 255       "text/plain": [
 256        "6"
 257       ]
 258      },
 259      "execution_count": 60,
 260      "metadata": {},
 261      "output_type": "execute_result"
 262     }
 263    ],
 264    "source": [
 265     "len(astar_search('vice', 'wars'))"
 266    ]
 267   },
 268   {
 269    "cell_type": "code",
 270    "execution_count": 15,
 271    "metadata": {},
 272    "outputs": [
 273     {
 274      "data": {
 275       "text/plain": [
 276        "6"
 277       ]
 278      },
 279      "execution_count": 15,
 280      "metadata": {},
 281      "output_type": "execute_result"
 282     }
 283    ],
 284    "source": [
 285     "len(bfs_search('vice', 'wars'))"
 286    ]
 287   },
 288   {
 289    "cell_type": "code",
 290    "execution_count": 16,
 291    "metadata": {},
 292    "outputs": [
 293     {
 294      "data": {
 295       "text/plain": [
 296        "793"
 297       ]
 298      },
 299      "execution_count": 16,
 300      "metadata": {},
 301      "output_type": "execute_result"
 302     }
 303    ],
 304    "source": [
 305     "len(dfs_search('vice', 'wars'))"
 306    ]
 307   },
 308   {
 309    "cell_type": "code",
 310    "execution_count": 17,
 311    "metadata": {},
 312    "outputs": [
 313     {
 314      "name": "stdout",
 315      "output_type": "stream",
 316      "text": [
 317       "10000 loops, best of 3: 154 µs per loop\n"
 318      ]
 319     }
 320    ],
 321    "source": [
 322     "%%timeit\n",
 323     "astar_search('vice', 'wars')"
 324    ]
 325   },
 326   {
 327    "cell_type": "code",
 328    "execution_count": 18,
 329    "metadata": {},
 330    "outputs": [
 331     {
 332      "name": "stdout",
 333      "output_type": "stream",
 334      "text": [
 335       "1 loop, best of 3: 1min 40s per loop\n"
 336      ]
 337     }
 338    ],
 339    "source": [
 340     "%%timeit\n",
 341     "bfs_search('vice', 'wars')"
 342    ]
 343   },
 344   {
 345    "cell_type": "code",
 346    "execution_count": 19,
 347    "metadata": {},
 348    "outputs": [
 349     {
 350      "name": "stdout",
 351      "output_type": "stream",
 352      "text": [
 353       "10 loops, best of 3: 86.3 ms per loop\n"
 354      ]
 355     }
 356    ],
 357    "source": [
 358     "%%timeit\n",
 359     "dfs_search('vice', 'wars')"
 360    ]
 361   },
 362   {
 363    "cell_type": "markdown",
 364    "metadata": {},
 365    "source": [
 366     "## Part 2\n",
 367     "\n",
 368     "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
 369     "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
 370     "\n",
 371     "There are 47 words reachable in one or two steps from `rash`. They are `base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, and `wish`.\n",
 372     "\n",
 373     "There are 180 words reachable in up to three steps from `rash`.\n",
 374     "\n",
 375     "How many words are reachable in up to ten steps from `vice`?"
 376    ]
 377   },
 378   {
 379    "cell_type": "code",
 380    "execution_count": 37,
 381    "metadata": {
 382     "collapsed": true
 383    },
 384    "outputs": [],
 385    "source": [
 386     "def reachable_in(word, n, trim_extras=False):\n",
 387     "    reachable = set()\n",
 388     "    boundary = set([word])\n",
 389     "    for i in range(n):\n",
 390     "        extras = set()\n",
 391     "        for w in boundary:\n",
 392     "            extras.update(neighbours[w])\n",
 393     "        if trim_extras:\n",
 394     "            extras.difference_update(reachable)\n",
 395     "        reachable.update(boundary)\n",
 396     "        boundary = extras.copy()\n",
 397     "    return reachable.union(extras).difference(set([word]))"
 398    ]
 399   },
 400   {
 401    "cell_type": "code",
 402    "execution_count": 38,
 403    "metadata": {
 404     "scrolled": true
 405    },
 406    "outputs": [
 407     {
 408      "data": {
 409       "text/plain": [
 410        "(11,\n",
 411        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
 412       ]
 413      },
 414      "execution_count": 38,
 415      "metadata": {},
 416      "output_type": "execute_result"
 417     }
 418    ],
 419    "source": [
 420     "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
 421    ]
 422   },
 423   {
 424    "cell_type": "code",
 425    "execution_count": 39,
 426    "metadata": {
 427     "scrolled": true
 428    },
 429    "outputs": [
 430     {
 431      "data": {
 432       "text/plain": [
 433        "(47,\n",
 434        " '`base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, `wish`')"
 435       ]
 436      },
 437      "execution_count": 39,
 438      "metadata": {},
 439      "output_type": "execute_result"
 440     }
 441    ],
 442    "source": [
 443     "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
 444    ]
 445   },
 446   {
 447    "cell_type": "code",
 448    "execution_count": 40,
 449    "metadata": {
 450     "scrolled": true
 451    },
 452    "outputs": [
 453     {
 454      "data": {
 455       "text/plain": [
 456        "180"
 457       ]
 458      },
 459      "execution_count": 40,
 460      "metadata": {},
 461      "output_type": "execute_result"
 462     }
 463    ],
 464    "source": [
 465     "len(reachable_in('rash', 3))"
 466    ]
 467   },
 468   {
 469    "cell_type": "code",
 470    "execution_count": 48,
 471    "metadata": {
 472     "scrolled": true
 473    },
 474    "outputs": [
 475     {
 476      "data": {
 477       "text/plain": [
 478        "2195"
 479       ]
 480      },
 481      "execution_count": 48,
 482      "metadata": {},
 483      "output_type": "execute_result"
 484     }
 485    ],
 486    "source": [
 487     "len(reachable_in('rash', 10))"
 488    ]
 489   },
 490   {
 491    "cell_type": "code",
 492    "execution_count": 47,
 493    "metadata": {
 494     "scrolled": true
 495    },
 496    "outputs": [
 497     {
 498      "data": {
 499       "text/plain": [
 500        "2192"
 501       ]
 502      },
 503      "execution_count": 47,
 504      "metadata": {},
 505      "output_type": "execute_result"
 506     }
 507    ],
 508    "source": [
 509     "len(reachable_in('vice', 10))"
 510    ]
 511   },
 512   {
 513    "cell_type": "code",
 514    "execution_count": 46,
 515    "metadata": {
 516     "scrolled": true
 517    },
 518    "outputs": [
 519     {
 520      "name": "stdout",
 521      "output_type": "stream",
 522      "text": [
 523       "100 loops, best of 3: 5.97 ms per loop\n"
 524      ]
 525     }
 526    ],
 527    "source": [
 528     "%%timeit\n",
 529     "len(reachable_in('rash', 10))"
 530    ]
 531   },
 532   {
 533    "cell_type": "code",
 534    "execution_count": 44,
 535    "metadata": {
 536     "scrolled": true
 537    },
 538    "outputs": [
 539     {
 540      "name": "stdout",
 541      "output_type": "stream",
 542      "text": [
 543       "100 loops, best of 3: 3.1 ms per loop\n"
 544      ]
 545     }
 546    ],
 547    "source": [
 548     "%%timeit\n",
 549     "len(reachable_in('rash', 10, trim_extras=True))"
 550    ]
 551   },
 552   {
 553    "cell_type": "code",
 554    "execution_count": null,
 555    "metadata": {
 556     "collapsed": true
 557    },
 558    "outputs": [],
 559    "source": []
 560   }
 561  ],
 562  "metadata": {
 563   "kernelspec": {
 564    "display_name": "Python 3",
 565    "language": "python",
 566    "name": "python3"
 567   },
 568   "language_info": {
 569    "codemirror_mode": {
 570     "name": "ipython",
 571     "version": 3
 572    },
 573    "file_extension": ".py",
 574    "mimetype": "text/x-python",
 575    "name": "python",
 576    "nbconvert_exporter": "python",
 577    "pygments_lexer": "ipython3",
 578    "version": "3.5.2+"
 579   }
 580  },
 581  "nbformat": 4,
 582  "nbformat_minor": 2
 583 }