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": 1,
  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": 2,
  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": 3,
  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": 4,
  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": 5,
  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": 6,
 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": 7,
 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": 8,
 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": 9,
 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": 10,
 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": 11,
 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": 12,
 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": 13,
 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": 14,
 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": 15,
 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": 16,
 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": 23,
 297    "metadata": {},
 298    "outputs": [
 299     {
 300      "data": {
 301       "text/plain": [
 302        "226"
 303       ]
 304      },
 305      "execution_count": 23,
 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": 24,
 319    "metadata": {},
 320    "outputs": [
 321     {
 322      "data": {
 323       "text/plain": [
 324        "61762"
 325       ]
 326      },
 327      "execution_count": 24,
 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": 45,
 339    "metadata": {},
 340    "outputs": [
 341     {
 342      "name": "stdout",
 343      "output_type": "stream",
 344      "text": [
 345       "1 loop, best of 3: 209 ms per loop\n"
 346      ]
 347     }
 348    ],
 349    "source": [
 350     "%%timeit\n",
 351     "sum(len(t) for t in tours if valid(trace_tour(t)))"
 352    ]
 353   },
 354   {
 355    "cell_type": "markdown",
 356    "metadata": {},
 357    "source": [
 358     "# Part 2"
 359    ]
 360   },
 361   {
 362    "cell_type": "code",
 363    "execution_count": 25,
 364    "metadata": {},
 365    "outputs": [
 366     {
 367      "name": "stdout",
 368      "output_type": "stream",
 369      "text": [
 370       "1 loop, best of 3: 1min 29s per loop\n"
 371      ]
 372     }
 373    ],
 374    "source": [
 375     "%%timeit\n",
 376     "[(i, j) \n",
 377     " for i, pi in enumerate(tours) \n",
 378     " for j, pj in enumerate(tours)\n",
 379     " if i != j\n",
 380     " if not valid(trace_tour(pi))\n",
 381     " if not valid(trace_tour(pj))\n",
 382     " if valid(trace_tour(pi + pj))]"
 383    ]
 384   },
 385   {
 386    "cell_type": "code",
 387    "execution_count": 31,
 388    "metadata": {},
 389    "outputs": [
 390     {
 391      "data": {
 392       "text/plain": [
 393        "[(16, 125),\n",
 394        " (70, 48),\n",
 395        " (91, 128),\n",
 396        " (110, 134),\n",
 397        " (116, 194),\n",
 398        " (123, 51),\n",
 399        " (136, 9),\n",
 400        " (142, 193),\n",
 401        " (152, 63),\n",
 402        " (168, 150),\n",
 403        " (201, 83),\n",
 404        " (208, 204),\n",
 405        " (212, 113)]"
 406       ]
 407      },
 408      "execution_count": 31,
 409      "metadata": {},
 410      "output_type": "execute_result"
 411     }
 412    ],
 413    "source": [
 414     "[(i, j) \n",
 415     " for i, pi in enumerate(tours) \n",
 416     " for j, pj in enumerate(tours)\n",
 417     " if i != j\n",
 418     " if not valid(trace_tour(pi))\n",
 419     " if not valid(trace_tour(pj))\n",
 420     " if valid(trace_tour(pi + pj))]"
 421    ]
 422   },
 423   {
 424    "cell_type": "code",
 425    "execution_count": 42,
 426    "metadata": {},
 427    "outputs": [
 428     {
 429      "data": {
 430       "text/plain": [
 431        "80622"
 432       ]
 433      },
 434      "execution_count": 42,
 435      "metadata": {},
 436      "output_type": "execute_result"
 437     }
 438    ],
 439    "source": [
 440     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 441     "    +\n",
 442     "    sum(len(pi + pj) \n",
 443     "     for i, pi in enumerate(tours) \n",
 444     "     for j, pj in enumerate(tours)\n",
 445     "     if i != j\n",
 446     "     if not valid(trace_tour(pi))\n",
 447     "     if not valid(trace_tour(pj))\n",
 448     "     if valid(trace_tour(pi + pj)))\n",
 449     ")"
 450    ]
 451   },
 452   {
 453    "cell_type": "code",
 454    "execution_count": 34,
 455    "metadata": {},
 456    "outputs": [
 457     {
 458      "name": "stdout",
 459      "output_type": "stream",
 460      "text": [
 461       "1 1\n",
 462       "2 1\n",
 463       "3 4\n",
 464       "4 5\n",
 465       "5 7\n",
 466       "6 3\n",
 467       "7 1\n",
 468       "8 2\n",
 469       "9 2\n",
 470       "11 2\n",
 471       "18 1\n",
 472       "19 1\n"
 473      ]
 474     }
 475    ],
 476    "source": [
 477     "l1s = {}\n",
 478     "for t in tours:\n",
 479     "    tr = trace_tour(t)\n",
 480     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 481     "    if l1 > 0:\n",
 482     "        if l1 not in l1s:\n",
 483     "            l1s[l1] = []\n",
 484     "        l1s[l1] += [t]\n",
 485     "\n",
 486     "for l1 in l1s:\n",
 487     "    if l1 < 20:\n",
 488     "        print(l1, len(l1s[l1]))"
 489    ]
 490   },
 491   {
 492    "cell_type": "code",
 493    "execution_count": 30,
 494    "metadata": {},
 495    "outputs": [
 496     {
 497      "data": {
 498       "text/plain": [
 499        "[(0, 124),\n",
 500        " (1, 1),\n",
 501        " (2, 1),\n",
 502        " (3, 4),\n",
 503        " (4, 5),\n",
 504        " (5, 7),\n",
 505        " (6, 3),\n",
 506        " (7, 1),\n",
 507        " (8, 2),\n",
 508        " (9, 2),\n",
 509        " (11, 2),\n",
 510        " (18, 1),\n",
 511        " (19, 1)]"
 512       ]
 513      },
 514      "execution_count": 30,
 515      "metadata": {},
 516      "output_type": "execute_result"
 517     }
 518    ],
 519    "source": [
 520     "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
 521    ]
 522   },
 523   {
 524    "cell_type": "code",
 525    "execution_count": 27,
 526    "metadata": {},
 527    "outputs": [
 528     {
 529      "name": "stdout",
 530      "output_type": "stream",
 531      "text": [
 532       "1 loop, best of 3: 1min 28s per loop\n"
 533      ]
 534     }
 535    ],
 536    "source": [
 537     "%%timeit\n",
 538     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 539     "    +\n",
 540     "    sum(len(pi + pj) \n",
 541     "     for i, pi in enumerate(tours) \n",
 542     "     for j, pj in enumerate(tours)\n",
 543     "     if i != j\n",
 544     "     if not valid(trace_tour(pi))\n",
 545     "     if not valid(trace_tour(pj))\n",
 546     "     if valid(trace_tour(pi + pj)))\n",
 547     ")"
 548    ]
 549   },
 550   {
 551    "cell_type": "code",
 552    "execution_count": 50,
 553    "metadata": {
 554     "collapsed": true
 555    },
 556    "outputs": [],
 557    "source": [
 558     "good_is = []\n",
 559     "goods = []\n",
 560     "tried = []\n",
 561     "for l1 in l1s:\n",
 562     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 563     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 564     "    for t1 in candidates:\n",
 565     "        for t2 in candidates:\n",
 566     "            if t1 != t2:\n",
 567     "                t12 = t1 + t2\n",
 568     "                if (t12) not in tried:\n",
 569     "                    tried += [(t12)]\n",
 570     "                    if valid(trace_tour(t12)):\n",
 571     "                        good_is += [(tours.index(t1), tours.index(t2))]\n",
 572     "                        goods += [t12]"
 573    ]
 574   },
 575   {
 576    "cell_type": "code",
 577    "execution_count": 51,
 578    "metadata": {},
 579    "outputs": [
 580     {
 581      "data": {
 582       "text/plain": [
 583        "80622"
 584       ]
 585      },
 586      "execution_count": 51,
 587      "metadata": {},
 588      "output_type": "execute_result"
 589     }
 590    ],
 591    "source": [
 592     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 593     "    +\n",
 594     "    sum(len(t12) for t12 in goods)\n",
 595     ")"
 596    ]
 597   },
 598   {
 599    "cell_type": "code",
 600    "execution_count": 52,
 601    "metadata": {},
 602    "outputs": [
 603     {
 604      "name": "stdout",
 605      "output_type": "stream",
 606      "text": [
 607       "1 loop, best of 3: 1.16 s per loop\n"
 608      ]
 609     }
 610    ],
 611    "source": [
 612     "%%timeit\n",
 613     "\n",
 614     "l1s = {}\n",
 615     "for t in tours:\n",
 616     "    tr = trace_tour(t)\n",
 617     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 618     "    if l1 > 0:\n",
 619     "        if l1 not in l1s:\n",
 620     "            l1s[l1] = []\n",
 621     "        l1s[l1] += [t]\n",
 622     "\n",
 623     "goods = []\n",
 624     "tried = []\n",
 625     "for l1 in l1s:\n",
 626     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 627     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 628     "    for t1 in candidates:\n",
 629     "        for t2 in candidates:\n",
 630     "            if t1 != t2:\n",
 631     "                t12 = t1 + t2\n",
 632     "                if (t12) not in tried:\n",
 633     "                    tried += [(t12)]\n",
 634     "                    if valid(trace_tour(t12)):\n",
 635     "                        goods += [t12]\n",
 636     "\n",
 637     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 638     "    +\n",
 639     "    sum(len(t12) for t12 in goods)\n",
 640     ")"
 641    ]
 642   },
 643   {
 644    "cell_type": "code",
 645    "execution_count": null,
 646    "metadata": {
 647     "collapsed": true
 648    },
 649    "outputs": [],
 650    "source": []
 651   }
 652  ],
 653  "metadata": {
 654   "kernelspec": {
 655    "display_name": "Python 3",
 656    "language": "python",
 657    "name": "python3"
 658   },
 659   "language_info": {
 660    "codemirror_mode": {
 661     "name": "ipython",
 662     "version": 3
 663    },
 664    "file_extension": ".py",
 665    "mimetype": "text/x-python",
 666    "name": "python",
 667    "nbconvert_exporter": "python",
 668    "pygments_lexer": "ipython3",
 669    "version": "3.5.2+"
 670   }
 671  },
 672  "nbformat": 4,
 673  "nbformat_minor": 2
 674 }