06-tour-shapes/tour-shapes-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "Given a sequence of {F|L|R}, each of which is \"move forward one step\", \"turn left, then move forward one step\", \"turn right, then move forward one step\":\n",
   8     "1. which tours are closed?\n",
   9     "2. what is the area enclosed by the tour?"
  10    ]
  11   },
  12   {
  13    "cell_type": "code",
  14    "execution_count": 2,
  15    "metadata": {
  16     "collapsed": true
  17    },
  18    "outputs": [],
  19    "source": [
  20     "import collections\n",
  21     "import enum\n",
  22     "import random\n",
  23     "import os\n",
  24     "\n",
  25     "import matplotlib.pyplot as plt\n",
  26     "%matplotlib inline\n"
  27    ]
  28   },
  29   {
  30    "cell_type": "code",
  31    "execution_count": 3,
  32    "metadata": {
  33     "collapsed": true
  34    },
  35    "outputs": [],
  36    "source": [
  37     "class Direction(enum.Enum):\n",
  38     "    UP = 1\n",
  39     "    RIGHT = 2\n",
  40     "    DOWN = 3\n",
  41     "    LEFT = 4\n",
  42     "    \n",
  43     "turn_lefts = {Direction.UP: Direction.LEFT, Direction.LEFT: Direction.DOWN,\n",
  44     "              Direction.DOWN: Direction.RIGHT, Direction.RIGHT: Direction.UP}\n",
  45     "\n",
  46     "turn_rights = {Direction.UP: Direction.RIGHT, Direction.RIGHT: Direction.DOWN,\n",
  47     "               Direction.DOWN: Direction.LEFT, Direction.LEFT: Direction.UP}\n",
  48     "\n",
  49     "def turn_left(d):\n",
  50     "    return turn_lefts[d]\n",
  51     "\n",
  52     "def turn_right(d):\n",
  53     "    return turn_rights[d]\n"
  54    ]
  55   },
  56   {
  57    "cell_type": "code",
  58    "execution_count": 4,
  59    "metadata": {
  60     "collapsed": true
  61    },
  62    "outputs": [],
  63    "source": [
  64     "Step = collections.namedtuple('Step', ['x', 'y', 'dir'])\n",
  65     "Mistake = collections.namedtuple('Mistake', ['i', 'step'])"
  66    ]
  67   },
  68   {
  69    "cell_type": "code",
  70    "execution_count": 5,
  71    "metadata": {
  72     "collapsed": true
  73    },
  74    "outputs": [],
  75    "source": [
  76     "def advance(step, d):\n",
  77     "    if d == Direction.UP:\n",
  78     "        return Step(step.x, step.y+1, d)\n",
  79     "    elif d == Direction.DOWN:\n",
  80     "        return Step(step.x, step.y-1, d)\n",
  81     "    elif d == Direction.LEFT:\n",
  82     "        return Step(step.x-1, step.y, d)\n",
  83     "    elif d == Direction.RIGHT:\n",
  84     "        return Step(step.x+1, step.y, d)"
  85    ]
  86   },
  87   {
  88    "cell_type": "code",
  89    "execution_count": 6,
  90    "metadata": {
  91     "collapsed": true
  92    },
  93    "outputs": [],
  94    "source": [
  95     "def step(s, current):\n",
  96     "    if s == 'F':\n",
  97     "        return advance(current, current.dir)\n",
  98     "    elif s == 'L':\n",
  99     "        return advance(current, turn_left(current.dir))\n",
 100     "    elif s == 'R':\n",
 101     "        return advance(current, turn_right(current.dir))\n",
 102     "    else:\n",
 103     "        raise ValueError"
 104    ]
 105   },
 106   {
 107    "cell_type": "code",
 108    "execution_count": 7,
 109    "metadata": {
 110     "collapsed": true
 111    },
 112    "outputs": [],
 113    "source": [
 114     "def trace_tour(tour, startx=0, starty=0, startdir=Direction.RIGHT):\n",
 115     "    current = Step(startx, starty, startdir)\n",
 116     "    trace = [current]\n",
 117     "    for s in tour:\n",
 118     "        current = step(s, current)\n",
 119     "        trace += [current]\n",
 120     "    return trace    "
 121    ]
 122   },
 123   {
 124    "cell_type": "code",
 125    "execution_count": 8,
 126    "metadata": {
 127     "collapsed": true
 128    },
 129    "outputs": [],
 130    "source": [
 131     "def positions(trace):\n",
 132     "    return [(s.x, s.y) for s in trace]"
 133    ]
 134   },
 135   {
 136    "cell_type": "code",
 137    "execution_count": 9,
 138    "metadata": {
 139     "collapsed": true
 140    },
 141    "outputs": [],
 142    "source": [
 143     "def valid(trace):\n",
 144     "    return (trace[-1].x == 0 \n",
 145     "            and trace[-1].y == 0 \n",
 146     "            and len(set(positions(trace))) + 1 == len(trace))"
 147    ]
 148   },
 149   {
 150    "cell_type": "code",
 151    "execution_count": 10,
 152    "metadata": {
 153     "collapsed": true
 154    },
 155    "outputs": [],
 156    "source": [
 157     "def valid_prefix(tour):\n",
 158     "    current = Step(0, 0, Direction.RIGHT)\n",
 159     "    prefix = []\n",
 160     "    posns = []\n",
 161     "    for s in tour:\n",
 162     "        current = step(s, current)\n",
 163     "        prefix += [s]\n",
 164     "        if (current.x, current.y) in posns:\n",
 165     "            return ''\n",
 166     "        elif current.x == 0 and current.y == 0: \n",
 167     "            return ''.join(prefix)\n",
 168     "        posns += [(current.x, current.y)]\n",
 169     "    if current.x == 0 and current.y == 0:\n",
 170     "        return ''.join(prefix)\n",
 171     "    else:\n",
 172     "        return ''"
 173    ]
 174   },
 175   {
 176    "cell_type": "code",
 177    "execution_count": 11,
 178    "metadata": {
 179     "collapsed": true
 180    },
 181    "outputs": [],
 182    "source": [
 183     "def mistake_positions(trace, debug=False):\n",
 184     "    mistakes = []\n",
 185     "    current = trace[0]\n",
 186     "    posns = [(0, 0)]\n",
 187     "    for i, current in enumerate(trace[1:]):\n",
 188     "        if (current.x, current.y) in posns:\n",
 189     "            if debug: print(i, current)\n",
 190     "            mistakes += [Mistake(i+1, current)]\n",
 191     "        posns += [(current.x, current.y)]\n",
 192     "    if (current.x, current.y) == (0, 0):\n",
 193     "        return mistakes[:-1]\n",
 194     "    else:\n",
 195     "        return mistakes + [Mistake(len(trace)+1, current)]"
 196    ]
 197   },
 198   {
 199    "cell_type": "code",
 200    "execution_count": 12,
 201    "metadata": {
 202     "collapsed": true
 203    },
 204    "outputs": [],
 205    "source": [
 206     "def returns_to_origin(mistake_positions):\n",
 207     "    return [i for i, m in mistake_positions\n",
 208     "           if (m.x, m.y) == (0, 0)]"
 209    ]
 210   },
 211   {
 212    "cell_type": "code",
 213    "execution_count": 13,
 214    "metadata": {
 215     "collapsed": true
 216    },
 217    "outputs": [],
 218    "source": [
 219     "sample_tours = ['FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL']"
 220    ]
 221   },
 222   {
 223    "cell_type": "code",
 224    "execution_count": 14,
 225    "metadata": {
 226     "collapsed": true
 227    },
 228    "outputs": [],
 229    "source": [
 230     "def bounds(trace):\n",
 231     "    return (max(s.x for s in trace),\n",
 232     "            max(s.y for s in trace),\n",
 233     "            min(s.x for s in trace),\n",
 234     "            min(s.y for s in trace))"
 235    ]
 236   },
 237   {
 238    "cell_type": "code",
 239    "execution_count": 15,
 240    "metadata": {
 241     "collapsed": true
 242    },
 243    "outputs": [],
 244    "source": [
 245     "plot_wh = {Direction.UP: (0, 1), Direction.LEFT: (-1, 0),\n",
 246     "           Direction.DOWN: (0, -1), Direction.RIGHT: (1, 0)}"
 247    ]
 248   },
 249   {
 250    "cell_type": "code",
 251    "execution_count": 16,
 252    "metadata": {
 253     "collapsed": true
 254    },
 255    "outputs": [],
 256    "source": [
 257     "def chunks(items, n=2):\n",
 258     "    return [items[i:i+n] for i in range(len(items) - n + 1)]"
 259    ]
 260   },
 261   {
 262    "cell_type": "code",
 263    "execution_count": 17,
 264    "metadata": {
 265     "collapsed": true
 266    },
 267    "outputs": [],
 268    "source": [
 269     "def plot_trace(trace, colour='k', xybounds=None, fig=None, subplot_details=None, filename=None):\n",
 270     "    plt.axis('on')\n",
 271     "    plt.axes().set_aspect('equal')\n",
 272     "    for s, t in chunks(trace, 2):\n",
 273     "        w, h = plot_wh[t.dir]\n",
 274     "        plt.arrow(s.x, s.y, w, h, head_width=0.1, head_length=0.1, fc=colour, ec=colour, length_includes_head=True)\n",
 275     "    xh, yh, xl, yl = bounds(trace)\n",
 276     "    if xybounds is not None:    \n",
 277     "        bxh, byh, bxl, byl = xybounds\n",
 278     "        plt.xlim([min(xl, bxl)-1, max(xh, bxh)+1])\n",
 279     "        plt.ylim([min(yl, byl)-1, max(yh, byh)+1])\n",
 280     "    else:\n",
 281     "        plt.xlim([xl-1, xh+1])\n",
 282     "        plt.ylim([yl-1, yh+1])\n",
 283     "    if filename:\n",
 284     "        plt.savefig(filename)"
 285    ]
 286   },
 287   {
 288    "cell_type": "markdown",
 289    "metadata": {},
 290    "source": [
 291     "# Part 1"
 292    ]
 293   },
 294   {
 295    "cell_type": "code",
 296    "execution_count": 18,
 297    "metadata": {},
 298    "outputs": [
 299     {
 300      "data": {
 301       "text/plain": [
 302        "226"
 303       ]
 304      },
 305      "execution_count": 18,
 306      "metadata": {},
 307      "output_type": "execute_result"
 308     }
 309    ],
 310    "source": [
 311     "with open('06-tours.txt') as f:\n",
 312     "    tours = [t.strip() for t in f.readlines()]\n",
 313     "len(tours)"
 314    ]
 315   },
 316   {
 317    "cell_type": "code",
 318    "execution_count": 19,
 319    "metadata": {},
 320    "outputs": [
 321     {
 322      "data": {
 323       "text/plain": [
 324        "61762"
 325       ]
 326      },
 327      "execution_count": 19,
 328      "metadata": {},
 329      "output_type": "execute_result"
 330     }
 331    ],
 332    "source": [
 333     "sum(len(t) for t in tours if valid(trace_tour(t)))"
 334    ]
 335   },
 336   {
 337    "cell_type": "code",
 338    "execution_count": 31,
 339    "metadata": {},
 340    "outputs": [
 341     {
 342      "data": {
 343       "text/plain": [
 344        "100"
 345       ]
 346      },
 347      "execution_count": 31,
 348      "metadata": {},
 349      "output_type": "execute_result"
 350     }
 351    ],
 352    "source": [
 353     "sum(1 for t in tours if valid(trace_tour(t)))"
 354    ]
 355   },
 356   {
 357    "cell_type": "code",
 358    "execution_count": 20,
 359    "metadata": {},
 360    "outputs": [
 361     {
 362      "data": {
 363       "text/plain": [
 364        "123845"
 365       ]
 366      },
 367      "execution_count": 20,
 368      "metadata": {},
 369      "output_type": "execute_result"
 370     }
 371    ],
 372    "source": [
 373     "sum(len(t) for t in tours)"
 374    ]
 375   },
 376   {
 377    "cell_type": "code",
 378    "execution_count": 21,
 379    "metadata": {},
 380    "outputs": [
 381     {
 382      "name": "stdout",
 383      "output_type": "stream",
 384      "text": [
 385       "1 loop, best of 3: 211 ms per loop\n"
 386      ]
 387     }
 388    ],
 389    "source": [
 390     "%%timeit\n",
 391     "sum(len(t) for t in tours if valid(trace_tour(t)))"
 392    ]
 393   },
 394   {
 395    "cell_type": "markdown",
 396    "metadata": {},
 397    "source": [
 398     "# Part 2"
 399    ]
 400   },
 401   {
 402    "cell_type": "code",
 403    "execution_count": 23,
 404    "metadata": {},
 405    "outputs": [],
 406    "source": [
 407     "# %%timeit\n",
 408     "# [(i, j) \n",
 409     "#  for i, pi in enumerate(tours) \n",
 410     "#  for j, pj in enumerate(tours)\n",
 411     "#  if i != j\n",
 412     "#  if not valid(trace_tour(pi))\n",
 413     "#  if not valid(trace_tour(pj))\n",
 414     "#  if valid(trace_tour(pi + pj))]"
 415    ]
 416   },
 417   {
 418    "cell_type": "code",
 419    "execution_count": null,
 420    "metadata": {},
 421    "outputs": [],
 422    "source": [
 423     "# [(i, j) \n",
 424     "#  for i, pi in enumerate(tours) \n",
 425     "#  for j, pj in enumerate(tours)\n",
 426     "#  if i != j\n",
 427     "#  if not valid(trace_tour(pi))\n",
 428     "#  if not valid(trace_tour(pj))\n",
 429     "#  if valid(trace_tour(pi + pj))]"
 430    ]
 431   },
 432   {
 433    "cell_type": "code",
 434    "execution_count": null,
 435    "metadata": {},
 436    "outputs": [],
 437    "source": [
 438     "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 439     "#     +\n",
 440     "#     sum(len(pi + pj) \n",
 441     "#      for i, pi in enumerate(tours) \n",
 442     "#      for j, pj in enumerate(tours)\n",
 443     "#      if i != j\n",
 444     "#      if not valid(trace_tour(pi))\n",
 445     "#      if not valid(trace_tour(pj))\n",
 446     "#      if valid(trace_tour(pi + pj)))\n",
 447     "# )"
 448    ]
 449   },
 450   {
 451    "cell_type": "code",
 452    "execution_count": 24,
 453    "metadata": {},
 454    "outputs": [
 455     {
 456      "name": "stdout",
 457      "output_type": "stream",
 458      "text": [
 459       "1 1\n",
 460       "2 1\n",
 461       "3 4\n",
 462       "4 5\n",
 463       "5 7\n",
 464       "6 3\n",
 465       "7 1\n",
 466       "8 2\n",
 467       "9 2\n",
 468       "11 2\n",
 469       "18 1\n",
 470       "19 1\n"
 471      ]
 472     }
 473    ],
 474    "source": [
 475     "l1s = {}\n",
 476     "for t in tours:\n",
 477     "    tr = trace_tour(t)\n",
 478     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 479     "    if l1 > 0:\n",
 480     "        if l1 not in l1s:\n",
 481     "            l1s[l1] = []\n",
 482     "        l1s[l1] += [t]\n",
 483     "\n",
 484     "for l1 in l1s:\n",
 485     "    if l1 < 20:\n",
 486     "        print(l1, len(l1s[l1]))"
 487    ]
 488   },
 489   {
 490    "cell_type": "code",
 491    "execution_count": 25,
 492    "metadata": {},
 493    "outputs": [
 494     {
 495      "data": {
 496       "text/plain": [
 497        "[(1, 1),\n",
 498        " (2, 1),\n",
 499        " (3, 4),\n",
 500        " (4, 5),\n",
 501        " (5, 7),\n",
 502        " (6, 3),\n",
 503        " (7, 1),\n",
 504        " (8, 2),\n",
 505        " (9, 2),\n",
 506        " (11, 2),\n",
 507        " (18, 1),\n",
 508        " (19, 1)]"
 509       ]
 510      },
 511      "execution_count": 25,
 512      "metadata": {},
 513      "output_type": "execute_result"
 514     }
 515    ],
 516    "source": [
 517     "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
 518    ]
 519   },
 520   {
 521    "cell_type": "code",
 522    "execution_count": 27,
 523    "metadata": {},
 524    "outputs": [],
 525    "source": [
 526     "# %%timeit\n",
 527     "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 528     "#     +\n",
 529     "#     sum(len(pi + pj) \n",
 530     "#      for i, pi in enumerate(tours) \n",
 531     "#      for j, pj in enumerate(tours)\n",
 532     "#      if i != j\n",
 533     "#      if not valid(trace_tour(pi))\n",
 534     "#      if not valid(trace_tour(pj))\n",
 535     "#      if valid(trace_tour(pi + pj)))\n",
 536     "# )"
 537    ]
 538   },
 539   {
 540    "cell_type": "code",
 541    "execution_count": 28,
 542    "metadata": {
 543     "collapsed": true
 544    },
 545    "outputs": [],
 546    "source": [
 547     "good_is = []\n",
 548     "goods = []\n",
 549     "tried = []\n",
 550     "for l1 in l1s:\n",
 551     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 552     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 553     "    for t1 in candidates:\n",
 554     "        for t2 in candidates:\n",
 555     "            if t1 != t2:\n",
 556     "                t12 = t1 + t2\n",
 557     "                if (t12) not in tried:\n",
 558     "                    tried += [(t12)]\n",
 559     "                    if valid(trace_tour(t12)):\n",
 560     "                        good_is += [(tours.index(t1), tours.index(t2))]\n",
 561     "                        goods += [t12]"
 562    ]
 563   },
 564   {
 565    "cell_type": "code",
 566    "execution_count": 29,
 567    "metadata": {},
 568    "outputs": [
 569     {
 570      "data": {
 571       "text/plain": [
 572        "80622"
 573       ]
 574      },
 575      "execution_count": 29,
 576      "metadata": {},
 577      "output_type": "execute_result"
 578     }
 579    ],
 580    "source": [
 581     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 582     "    +\n",
 583     "    sum(len(t12) for t12 in goods)\n",
 584     ")"
 585    ]
 586   },
 587   {
 588    "cell_type": "code",
 589    "execution_count": 32,
 590    "metadata": {},
 591    "outputs": [
 592     {
 593      "name": "stdout",
 594      "output_type": "stream",
 595      "text": [
 596       "1 loop, best of 3: 1.27 s per loop\n"
 597      ]
 598     }
 599    ],
 600    "source": [
 601     "%%timeit\n",
 602     "\n",
 603     "l1s = {}\n",
 604     "for t in tours:\n",
 605     "    tr = trace_tour(t)\n",
 606     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 607     "    if l1 > 0:\n",
 608     "        if l1 not in l1s:\n",
 609     "            l1s[l1] = []\n",
 610     "        l1s[l1] += [t]\n",
 611     "\n",
 612     "goods = []\n",
 613     "tried = []\n",
 614     "for l1 in l1s:\n",
 615     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 616     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 617     "    for t1 in candidates:\n",
 618     "        for t2 in candidates:\n",
 619     "            if t1 != t2:\n",
 620     "                t12 = t1 + t2\n",
 621     "                if (t12) not in tried:\n",
 622     "                    tried += [(t12)]\n",
 623     "                    if valid(trace_tour(t12)):\n",
 624     "                        goods += [t12]\n",
 625     "\n",
 626     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 627     "    +\n",
 628     "    sum(len(t12) for t12 in goods)\n",
 629     ")"
 630    ]
 631   },
 632   {
 633    "cell_type": "code",
 634    "execution_count": 33,
 635    "metadata": {},
 636    "outputs": [
 637     {
 638      "data": {
 639       "text/plain": [
 640        "13"
 641       ]
 642      },
 643      "execution_count": 33,
 644      "metadata": {},
 645      "output_type": "execute_result"
 646     }
 647    ],
 648    "source": [
 649     "len(goods)"
 650    ]
 651   },
 652   {
 653    "cell_type": "code",
 654    "execution_count": 37,
 655    "metadata": {},
 656    "outputs": [
 657     {
 658      "data": {
 659       "text/plain": [
 660        "[(16, 125),\n",
 661        " (70, 48),\n",
 662        " (91, 128),\n",
 663        " (110, 134),\n",
 664        " (116, 194),\n",
 665        " (123, 51),\n",
 666        " (136, 9),\n",
 667        " (142, 193),\n",
 668        " (152, 63),\n",
 669        " (168, 150),\n",
 670        " (201, 83),\n",
 671        " (208, 204),\n",
 672        " (212, 113)]"
 673       ]
 674      },
 675      "execution_count": 37,
 676      "metadata": {},
 677      "output_type": "execute_result"
 678     }
 679    ],
 680    "source": [
 681     "sorted(good_is)"
 682    ]
 683   },
 684   {
 685    "cell_type": "code",
 686    "execution_count": 38,
 687    "metadata": {},
 688    "outputs": [
 689     {
 690      "data": {
 691       "text/plain": [
 692        "[(136, 9),\n",
 693        " (70, 48),\n",
 694        " (123, 51),\n",
 695        " (152, 63),\n",
 696        " (201, 83),\n",
 697        " (212, 113),\n",
 698        " (16, 125),\n",
 699        " (91, 128),\n",
 700        " (110, 134),\n",
 701        " (168, 150),\n",
 702        " (142, 193),\n",
 703        " (116, 194),\n",
 704        " (208, 204)]"
 705       ]
 706      },
 707      "execution_count": 38,
 708      "metadata": {},
 709      "output_type": "execute_result"
 710     }
 711    ],
 712    "source": [
 713     "sorted(good_is, key=lambda p: p[1])"
 714    ]
 715   },
 716   {
 717    "cell_type": "code",
 718    "execution_count": null,
 719    "metadata": {
 720     "collapsed": true
 721    },
 722    "outputs": [],
 723    "source": []
 724   }
 725  ],
 726  "metadata": {
 727   "kernelspec": {
 728    "display_name": "Python 3",
 729    "language": "python",
 730    "name": "python3"
 731   },
 732   "language_info": {
 733    "codemirror_mode": {
 734     "name": "ipython",
 735     "version": 3
 736    },
 737    "file_extension": ".py",
 738    "mimetype": "text/x-python",
 739    "name": "python",
 740    "nbconvert_exporter": "python",
 741    "pygments_lexer": "ipython3",
 742    "version": "3.5.2+"
 743   }
 744  },
 745  "nbformat": 4,
 746  "nbformat_minor": 2
 747 }