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": 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": 17,
 297    "metadata": {},
 298    "outputs": [
 299     {
 300      "data": {
 301       "text/plain": [
 302        "226"
 303       ]
 304      },
 305      "execution_count": 17,
 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": 18,
 319    "metadata": {},
 320    "outputs": [
 321     {
 322      "data": {
 323       "text/plain": [
 324        "61762"
 325       ]
 326      },
 327      "execution_count": 18,
 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": 19,
 339    "metadata": {},
 340    "outputs": [
 341     {
 342      "data": {
 343       "text/plain": [
 344        "100"
 345       ]
 346      },
 347      "execution_count": 19,
 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: 213 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": 22,
 404    "metadata": {
 405     "collapsed": true
 406    },
 407    "outputs": [],
 408    "source": [
 409     "# %%timeit\n",
 410     "# [(i, j) \n",
 411     "#  for i, pi in enumerate(tours) \n",
 412     "#  for j, pj in enumerate(tours)\n",
 413     "#  if i != j\n",
 414     "#  if not valid(trace_tour(pi))\n",
 415     "#  if not valid(trace_tour(pj))\n",
 416     "#  if valid(trace_tour(pi + pj))]"
 417    ]
 418   },
 419   {
 420    "cell_type": "code",
 421    "execution_count": 23,
 422    "metadata": {
 423     "collapsed": true
 424    },
 425    "outputs": [],
 426    "source": [
 427     "# [(i, j) \n",
 428     "#  for i, pi in enumerate(tours) \n",
 429     "#  for j, pj in enumerate(tours)\n",
 430     "#  if i != j\n",
 431     "#  if not valid(trace_tour(pi))\n",
 432     "#  if not valid(trace_tour(pj))\n",
 433     "#  if valid(trace_tour(pi + pj))]"
 434    ]
 435   },
 436   {
 437    "cell_type": "code",
 438    "execution_count": 24,
 439    "metadata": {
 440     "collapsed": true
 441    },
 442    "outputs": [],
 443    "source": [
 444     "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 445     "#     +\n",
 446     "#     sum(len(pi + pj) \n",
 447     "#      for i, pi in enumerate(tours) \n",
 448     "#      for j, pj in enumerate(tours)\n",
 449     "#      if i != j\n",
 450     "#      if not valid(trace_tour(pi))\n",
 451     "#      if not valid(trace_tour(pj))\n",
 452     "#      if valid(trace_tour(pi + pj)))\n",
 453     "# )"
 454    ]
 455   },
 456   {
 457    "cell_type": "code",
 458    "execution_count": 25,
 459    "metadata": {},
 460    "outputs": [
 461     {
 462      "name": "stdout",
 463      "output_type": "stream",
 464      "text": [
 465       "1 1\n",
 466       "2 1\n",
 467       "3 4\n",
 468       "4 5\n",
 469       "5 7\n",
 470       "6 3\n",
 471       "7 1\n",
 472       "8 2\n",
 473       "9 2\n",
 474       "11 2\n",
 475       "18 1\n",
 476       "19 1\n"
 477      ]
 478     }
 479    ],
 480    "source": [
 481     "l1s = {}\n",
 482     "for t in tours:\n",
 483     "    tr = trace_tour(t)\n",
 484     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 485     "    if l1 > 0:\n",
 486     "        if l1 not in l1s:\n",
 487     "            l1s[l1] = []\n",
 488     "        l1s[l1] += [t]\n",
 489     "\n",
 490     "for l1 in l1s:\n",
 491     "    if l1 < 20:\n",
 492     "        print(l1, len(l1s[l1]))"
 493    ]
 494   },
 495   {
 496    "cell_type": "code",
 497    "execution_count": 26,
 498    "metadata": {},
 499    "outputs": [
 500     {
 501      "data": {
 502       "text/plain": [
 503        "[(1, 1),\n",
 504        " (2, 1),\n",
 505        " (3, 4),\n",
 506        " (4, 5),\n",
 507        " (5, 7),\n",
 508        " (6, 3),\n",
 509        " (7, 1),\n",
 510        " (8, 2),\n",
 511        " (9, 2),\n",
 512        " (11, 2),\n",
 513        " (18, 1),\n",
 514        " (19, 1)]"
 515       ]
 516      },
 517      "execution_count": 26,
 518      "metadata": {},
 519      "output_type": "execute_result"
 520     }
 521    ],
 522    "source": [
 523     "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
 524    ]
 525   },
 526   {
 527    "cell_type": "code",
 528    "execution_count": 27,
 529    "metadata": {
 530     "collapsed": true
 531    },
 532    "outputs": [],
 533    "source": [
 534     "# %%timeit\n",
 535     "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 536     "#     +\n",
 537     "#     sum(len(pi + pj) \n",
 538     "#      for i, pi in enumerate(tours) \n",
 539     "#      for j, pj in enumerate(tours)\n",
 540     "#      if i != j\n",
 541     "#      if not valid(trace_tour(pi))\n",
 542     "#      if not valid(trace_tour(pj))\n",
 543     "#      if valid(trace_tour(pi + pj)))\n",
 544     "# )"
 545    ]
 546   },
 547   {
 548    "cell_type": "code",
 549    "execution_count": 28,
 550    "metadata": {
 551     "collapsed": true
 552    },
 553    "outputs": [],
 554    "source": [
 555     "good_is = []\n",
 556     "goods = []\n",
 557     "tried = []\n",
 558     "for l1 in l1s:\n",
 559     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 560     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 561     "    for t1 in candidates:\n",
 562     "        for t2 in candidates:\n",
 563     "            if t1 != t2:\n",
 564     "                t12 = t1 + t2\n",
 565     "                if (t12) not in tried:\n",
 566     "                    tried += [(t12)]\n",
 567     "                    if valid(trace_tour(t12)):\n",
 568     "                        good_is += [(tours.index(t1), tours.index(t2))]\n",
 569     "                        goods += [t12]"
 570    ]
 571   },
 572   {
 573    "cell_type": "code",
 574    "execution_count": 29,
 575    "metadata": {},
 576    "outputs": [
 577     {
 578      "data": {
 579       "text/plain": [
 580        "80622"
 581       ]
 582      },
 583      "execution_count": 29,
 584      "metadata": {},
 585      "output_type": "execute_result"
 586     }
 587    ],
 588    "source": [
 589     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 590     "    +\n",
 591     "    sum(len(t12) for t12 in goods)\n",
 592     ")"
 593    ]
 594   },
 595   {
 596    "cell_type": "code",
 597    "execution_count": 30,
 598    "metadata": {},
 599    "outputs": [
 600     {
 601      "name": "stdout",
 602      "output_type": "stream",
 603      "text": [
 604       "1 loop, best of 3: 1.29 s per loop\n"
 605      ]
 606     }
 607    ],
 608    "source": [
 609     "%%timeit\n",
 610     "\n",
 611     "l1s = {}\n",
 612     "for t in tours:\n",
 613     "    tr = trace_tour(t)\n",
 614     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 615     "    if l1 > 0:\n",
 616     "        if l1 not in l1s:\n",
 617     "            l1s[l1] = []\n",
 618     "        l1s[l1] += [t]\n",
 619     "\n",
 620     "goods = []\n",
 621     "tried = []\n",
 622     "for l1 in l1s:\n",
 623     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 624     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 625     "    for t1 in candidates:\n",
 626     "        for t2 in candidates:\n",
 627     "            if t1 != t2:\n",
 628     "                t12 = t1 + t2\n",
 629     "                if (t12) not in tried:\n",
 630     "                    tried += [(t12)]\n",
 631     "                    if valid(trace_tour(t12)):\n",
 632     "                        goods += [t12]\n",
 633     "\n",
 634     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 635     "    +\n",
 636     "    sum(len(t12) for t12 in goods)\n",
 637     ")"
 638    ]
 639   },
 640   {
 641    "cell_type": "code",
 642    "execution_count": 31,
 643    "metadata": {},
 644    "outputs": [
 645     {
 646      "data": {
 647       "text/plain": [
 648        "13"
 649       ]
 650      },
 651      "execution_count": 31,
 652      "metadata": {},
 653      "output_type": "execute_result"
 654     }
 655    ],
 656    "source": [
 657     "len(goods)"
 658    ]
 659   },
 660   {
 661    "cell_type": "code",
 662    "execution_count": 32,
 663    "metadata": {},
 664    "outputs": [
 665     {
 666      "data": {
 667       "text/plain": [
 668        "[(16, 125),\n",
 669        " (70, 48),\n",
 670        " (91, 128),\n",
 671        " (110, 134),\n",
 672        " (116, 194),\n",
 673        " (123, 51),\n",
 674        " (136, 9),\n",
 675        " (142, 193),\n",
 676        " (152, 63),\n",
 677        " (168, 150),\n",
 678        " (201, 83),\n",
 679        " (208, 204),\n",
 680        " (212, 113)]"
 681       ]
 682      },
 683      "execution_count": 32,
 684      "metadata": {},
 685      "output_type": "execute_result"
 686     }
 687    ],
 688    "source": [
 689     "sorted(good_is)"
 690    ]
 691   },
 692   {
 693    "cell_type": "code",
 694    "execution_count": 33,
 695    "metadata": {},
 696    "outputs": [
 697     {
 698      "data": {
 699       "text/plain": [
 700        "[(136, 9),\n",
 701        " (70, 48),\n",
 702        " (123, 51),\n",
 703        " (152, 63),\n",
 704        " (201, 83),\n",
 705        " (212, 113),\n",
 706        " (16, 125),\n",
 707        " (91, 128),\n",
 708        " (110, 134),\n",
 709        " (168, 150),\n",
 710        " (142, 193),\n",
 711        " (116, 194),\n",
 712        " (208, 204)]"
 713       ]
 714      },
 715      "execution_count": 33,
 716      "metadata": {},
 717      "output_type": "execute_result"
 718     }
 719    ],
 720    "source": [
 721     "sorted(good_is, key=lambda p: p[1])"
 722    ]
 723   },
 724   {
 725    "cell_type": "code",
 726    "execution_count": 34,
 727    "metadata": {},
 728    "outputs": [
 729     {
 730      "data": {
 731       "text/plain": [
 732        "[(1, 1),\n",
 733        " (2, 1),\n",
 734        " (3, 4),\n",
 735        " (4, 5),\n",
 736        " (5, 7),\n",
 737        " (6, 3),\n",
 738        " (7, 1),\n",
 739        " (8, 2),\n",
 740        " (9, 2),\n",
 741        " (11, 2),\n",
 742        " (18, 1),\n",
 743        " (19, 1),\n",
 744        " (21, 1),\n",
 745        " (24, 1),\n",
 746        " (132, 2),\n",
 747        " (26, 2),\n",
 748        " (28, 1),\n",
 749        " (29, 1),\n",
 750        " (34, 2),\n",
 751        " (36, 1),\n",
 752        " (37, 3),\n",
 753        " (166, 2),\n",
 754        " (40, 2),\n",
 755        " (41, 2),\n",
 756        " (44, 3),\n",
 757        " (46, 1),\n",
 758        " (48, 2),\n",
 759        " (50, 3),\n",
 760        " (52, 2),\n",
 761        " (53, 1),\n",
 762        " (54, 1),\n",
 763        " (56, 2),\n",
 764        " (57, 3),\n",
 765        " (58, 1),\n",
 766        " (59, 2),\n",
 767        " (61, 1),\n",
 768        " (64, 1),\n",
 769        " (66, 2),\n",
 770        " (68, 1),\n",
 771        " (70, 1),\n",
 772        " (74, 1),\n",
 773        " (75, 1),\n",
 774        " (76, 3),\n",
 775        " (77, 1),\n",
 776        " (81, 1),\n",
 777        " (82, 2),\n",
 778        " (86, 1),\n",
 779        " (88, 1),\n",
 780        " (90, 1),\n",
 781        " (94, 1),\n",
 782        " (97, 1),\n",
 783        " (98, 1),\n",
 784        " (101, 2),\n",
 785        " (106, 1),\n",
 786        " (107, 1),\n",
 787        " (114, 2),\n",
 788        " (117, 3),\n",
 789        " (127, 1)]"
 790       ]
 791      },
 792      "execution_count": 34,
 793      "metadata": {},
 794      "output_type": "execute_result"
 795     }
 796    ],
 797    "source": [
 798     "[(l, len(l1s[l])) for l in l1s.keys()]"
 799    ]
 800   },
 801   {
 802    "cell_type": "code",
 803    "execution_count": null,
 804    "metadata": {
 805     "collapsed": true
 806    },
 807    "outputs": [],
 808    "source": []
 809   }
 810  ],
 811  "metadata": {
 812   "kernelspec": {
 813    "display_name": "Python 3",
 814    "language": "python",
 815    "name": "python3"
 816   },
 817   "language_info": {
 818    "codemirror_mode": {
 819     "name": "ipython",
 820     "version": 3
 821    },
 822    "file_extension": ".py",
 823    "mimetype": "text/x-python",
 824    "name": "python",
 825    "nbconvert_exporter": "python",
 826    "pygments_lexer": "ipython3",
 827    "version": "3.5.2+"
 828   }
 829  },
 830  "nbformat": 4,
 831  "nbformat_minor": 2
 832 }