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