04-08-amidakuji/amidakuji-creation.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {
   7     "collapsed": true
   8    },
   9    "outputs": [],
  10    "source": [
  11     "import collections\n",
  12     "import random\n",
  13     "import string\n",
  14     "import itertools"
  15    ]
  16   },
  17   {
  18    "cell_type": "code",
  19    "execution_count": 2,
  20    "metadata": {
  21     "collapsed": true
  22    },
  23    "outputs": [],
  24    "source": [
  25     "Link = collections.namedtuple('Link', 'height left right')"
  26    ]
  27   },
  28   {
  29    "cell_type": "code",
  30    "execution_count": 3,
  31    "metadata": {
  32     "collapsed": true
  33    },
  34    "outputs": [],
  35    "source": [
  36     "def link_ends(link):\n",
  37     "    return set((link.left, link.right))"
  38    ]
  39   },
  40   {
  41    "cell_type": "code",
  42    "execution_count": 4,
  43    "metadata": {
  44     "collapsed": true
  45    },
  46    "outputs": [],
  47    "source": [
  48     "def can_add(link, links):\n",
  49     "    ends = link_ends(link)\n",
  50     "    same_height_links = [l for l in links if l.height == link.height]\n",
  51     "    return all(ends.isdisjoint(link_ends(l)) for l in same_height_links)"
  52    ]
  53   },
  54   {
  55    "cell_type": "code",
  56    "execution_count": 5,
  57    "metadata": {
  58     "collapsed": true
  59    },
  60    "outputs": [],
  61    "source": [
  62     "def make_net(num_links, lines=10, height=50):\n",
  63     "    links = set()\n",
  64     "    while len(links) < num_links:\n",
  65     "        a = random.randrange(lines)\n",
  66     "        b = random.randrange(lines)\n",
  67     "        if a != b:\n",
  68     "            l = min(a, b)\n",
  69     "            r = max(a, b)\n",
  70     "            h = random.randrange(height)\n",
  71     "            link = Link(h, l, r)\n",
  72     "            if can_add(link, links):\n",
  73     "                links.add(link)\n",
  74     "    return links"
  75    ]
  76   },
  77   {
  78    "cell_type": "code",
  79    "execution_count": 6,
  80    "metadata": {},
  81    "outputs": [
  82     {
  83      "data": {
  84       "text/plain": [
  85        "{Link(height=2, left=0, right=3),\n",
  86        " Link(height=2, left=1, right=7),\n",
  87        " Link(height=3, left=1, right=8),\n",
  88        " Link(height=9, left=6, right=9),\n",
  89        " Link(height=15, left=0, right=4),\n",
  90        " Link(height=20, left=0, right=8),\n",
  91        " Link(height=23, left=3, right=4),\n",
  92        " Link(height=24, left=3, right=6),\n",
  93        " Link(height=28, left=1, right=8),\n",
  94        " Link(height=28, left=5, right=6),\n",
  95        " Link(height=32, left=1, right=7),\n",
  96        " Link(height=34, left=1, right=9),\n",
  97        " Link(height=36, left=0, right=4),\n",
  98        " Link(height=38, left=5, right=6),\n",
  99        " Link(height=40, left=0, right=2),\n",
 100        " Link(height=41, left=3, right=7),\n",
 101        " Link(height=43, left=2, right=4),\n",
 102        " Link(height=43, left=6, right=8),\n",
 103        " Link(height=44, left=0, right=6),\n",
 104        " Link(height=46, left=7, right=8)}"
 105       ]
 106      },
 107      "execution_count": 6,
 108      "metadata": {},
 109      "output_type": "execute_result"
 110     }
 111    ],
 112    "source": [
 113     "net = make_net(20)\n",
 114     "net"
 115    ]
 116   },
 117   {
 118    "cell_type": "code",
 119    "execution_count": 7,
 120    "metadata": {
 121     "collapsed": true
 122    },
 123    "outputs": [],
 124    "source": [
 125     "def follow(initial_line, links):\n",
 126     "    line = initial_line\n",
 127     "    heights = sorted(set(l.height for l in links))\n",
 128     "    for h in heights:\n",
 129     "        for l in [l for l in links if l.height == h]:\n",
 130     "            if line in link_ends(l):\n",
 131     "                line = [e for e in link_ends(l) if e != line][0]\n",
 132     "#                 print(l, line)\n",
 133     "    return line"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 8,
 139    "metadata": {},
 140    "outputs": [
 141     {
 142      "data": {
 143       "text/plain": [
 144        "3"
 145       ]
 146      },
 147      "execution_count": 8,
 148      "metadata": {},
 149      "output_type": "execute_result"
 150     }
 151    ],
 152    "source": [
 153     "follow(4, net)"
 154    ]
 155   },
 156   {
 157    "cell_type": "code",
 158    "execution_count": 9,
 159    "metadata": {
 160     "collapsed": true
 161    },
 162    "outputs": [],
 163    "source": [
 164     "def pack(net):\n",
 165     "    packed_links = []\n",
 166     "    line_heights = collections.defaultdict(lambda: -1)\n",
 167     "    for link in sorted(net):\n",
 168     "        link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
 169     "        line_heights[link.left] = link_height\n",
 170     "        line_heights[link.right] = link_height\n",
 171     "        packed_links += [Link(link_height, link.left, link.right)]\n",
 172     "    return sorted(packed_links)"
 173    ]
 174   },
 175   {
 176    "cell_type": "code",
 177    "execution_count": 10,
 178    "metadata": {
 179     "collapsed": true
 180    },
 181    "outputs": [],
 182    "source": [
 183     "def follow_many_slow(in_sequence, links):\n",
 184     "    out_sequence = [(follow(i, links), term) \n",
 185     "                    for i, term in enumerate(in_sequence)]\n",
 186     "    return [term for i, term in sorted(out_sequence)]"
 187    ]
 188   },
 189   {
 190    "cell_type": "code",
 191    "execution_count": 11,
 192    "metadata": {
 193     "collapsed": true
 194    },
 195    "outputs": [],
 196    "source": [
 197     "def follow_many(in_sequence, net):\n",
 198     "    height_groups = [list(g) for _, g in itertools.groupby(pack(net), lambda l: l.height)]\n",
 199     "    seq = list(in_sequence)\n",
 200     "    for links in height_groups:\n",
 201     "        for link in links:\n",
 202     "#             l = seq[link.left]\n",
 203     "#             r = seq[link.right]\n",
 204     "#             seq[link.right] = l\n",
 205     "#             seq[link.left] = r\n",
 206     "            seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
 207     "    return seq"
 208    ]
 209   },
 210   {
 211    "cell_type": "code",
 212    "execution_count": 12,
 213    "metadata": {},
 214    "outputs": [
 215     {
 216      "name": "stdout",
 217      "output_type": "stream",
 218      "text": [
 219       "10000 loops, best of 3: 45.7 µs per loop\n"
 220      ]
 221     }
 222    ],
 223    "source": [
 224     "%%timeit\n",
 225     "follow_many('abcdefghij', net)"
 226    ]
 227   },
 228   {
 229    "cell_type": "code",
 230    "execution_count": 13,
 231    "metadata": {
 232     "collapsed": true
 233    },
 234    "outputs": [],
 235    "source": [
 236     "# %%timeit\n",
 237     "# follow_many_slow('abcdefghij', net)"
 238    ]
 239   },
 240   {
 241    "cell_type": "code",
 242    "execution_count": 104,
 243    "metadata": {
 244     "collapsed": true
 245    },
 246    "outputs": [],
 247    "source": [
 248     "def show_net(links, randomise=False, pair_sep=', '):\n",
 249     "    if randomise:\n",
 250     "        output = []\n",
 251     "        heights = sorted(set(l.height for l in links))\n",
 252     "        for h in heights:\n",
 253     "            ls = [l for l in links if l.height == h]\n",
 254     "            random.shuffle(ls)\n",
 255     "            output += ['({}, {})'.format(l.left, l.right) for l in ls]\n",
 256     "        return pair_sep.join(output)\n",
 257     "    return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
 258    ]
 259   },
 260   {
 261    "cell_type": "code",
 262    "execution_count": 105,
 263    "metadata": {},
 264    "outputs": [
 265     {
 266      "data": {
 267       "text/plain": [
 268        "'(0, 3), (1, 7), (1, 8), (6, 9), (0, 4), (0, 8), (3, 4), (3, 6), (1, 8), (5, 6), (1, 7), (1, 9), (0, 4), (5, 6), (0, 2), (3, 7), (2, 4), (6, 8), (0, 6), (7, 8)'"
 269       ]
 270      },
 271      "execution_count": 105,
 272      "metadata": {},
 273      "output_type": "execute_result"
 274     }
 275    ],
 276    "source": [
 277     "show_net(net)"
 278    ]
 279   },
 280   {
 281    "cell_type": "code",
 282    "execution_count": 106,
 283    "metadata": {},
 284    "outputs": [
 285     {
 286      "data": {
 287       "text/plain": [
 288        "'(1, 7), (0, 3), (1, 8), (6, 9), (0, 4), (0, 8), (3, 4), (3, 6), (5, 6), (1, 8), (1, 7), (1, 9), (0, 4), (5, 6), (0, 2), (3, 7), (6, 8), (2, 4), (0, 6), (7, 8)'"
 289       ]
 290      },
 291      "execution_count": 106,
 292      "metadata": {},
 293      "output_type": "execute_result"
 294     }
 295    ],
 296    "source": [
 297     "show_net(net, randomise=True)"
 298    ]
 299   },
 300   {
 301    "cell_type": "code",
 302    "execution_count": 110,
 303    "metadata": {},
 304    "outputs": [
 305     {
 306      "data": {
 307       "text/plain": [
 308        "'(0, 3) : (1, 7) : (1, 8) : (6, 9) : (0, 4) : (0, 8) : (3, 4) : (3, 6) : (1, 8) : (5, 6) : (1, 7) : (1, 9) : (0, 4) : (5, 6) : (0, 2) : (3, 7) : (2, 4) : (6, 8) : (0, 6) : (7, 8)'"
 309       ]
 310      },
 311      "execution_count": 110,
 312      "metadata": {},
 313      "output_type": "execute_result"
 314     }
 315    ],
 316    "source": [
 317     "show_net(net, pair_sep=' : ')"
 318    ]
 319   },
 320   {
 321    "cell_type": "code",
 322    "execution_count": 111,
 323    "metadata": {},
 324    "outputs": [
 325     {
 326      "data": {
 327       "text/plain": [
 328        "'(0, 3)\\n(1, 7)\\n(1, 8)\\n(6, 9)\\n(0, 4)\\n(0, 8)\\n(3, 4)\\n(3, 6)\\n(1, 8)\\n(5, 6)\\n(1, 7)\\n(1, 9)\\n(0, 4)\\n(5, 6)\\n(0, 2)\\n(3, 7)\\n(2, 4)\\n(6, 8)\\n(0, 6)\\n(7, 8)'"
 329       ]
 330      },
 331      "execution_count": 111,
 332      "metadata": {},
 333      "output_type": "execute_result"
 334     }
 335    ],
 336    "source": [
 337     "show_net(net, pair_sep='\\n')"
 338    ]
 339   },
 340   {
 341    "cell_type": "code",
 342    "execution_count": 112,
 343    "metadata": {
 344     "scrolled": true
 345    },
 346    "outputs": [
 347     {
 348      "name": "stdout",
 349      "output_type": "stream",
 350      "text": [
 351       "(0, 3)\n",
 352       "(1, 7)\n",
 353       "(1, 8)\n",
 354       "(6, 9)\n",
 355       "(0, 4)\n",
 356       "(0, 8)\n",
 357       "(3, 4)\n",
 358       "(3, 6)\n",
 359       "(1, 8)\n",
 360       "(5, 6)\n",
 361       "(1, 7)\n",
 362       "(1, 9)\n",
 363       "(0, 4)\n",
 364       "(5, 6)\n",
 365       "(0, 2)\n",
 366       "(3, 7)\n",
 367       "(2, 4)\n",
 368       "(6, 8)\n",
 369       "(0, 6)\n",
 370       "(7, 8)\n"
 371      ]
 372     }
 373    ],
 374    "source": [
 375     "print(show_net(net, pair_sep='\\n'))"
 376    ]
 377   },
 378   {
 379    "cell_type": "code",
 380    "execution_count": 108,
 381    "metadata": {},
 382    "outputs": [
 383     {
 384      "data": {
 385       "text/plain": [
 386        "'(0, 3), (1, 7), (1, 8), (6, 9), (0, 4), (0, 8), (3, 4), (3, 6), (1, 8), (5, 6), (1, 7), (1, 9), (0, 4), (5, 6), (0, 2), (3, 7), (2, 4), (6, 8), (0, 6), (7, 8)'"
 387       ]
 388      },
 389      "execution_count": 108,
 390      "metadata": {},
 391      "output_type": "execute_result"
 392     }
 393    ],
 394    "source": [
 395     "show_net(net)"
 396    ]
 397   },
 398   {
 399    "cell_type": "code",
 400    "execution_count": 17,
 401    "metadata": {},
 402    "outputs": [
 403     {
 404      "data": {
 405       "text/plain": [
 406        "[]"
 407       ]
 408      },
 409      "execution_count": 17,
 410      "metadata": {},
 411      "output_type": "execute_result"
 412     }
 413    ],
 414    "source": [
 415     "ls = [l for l in net if l.height == 1]\n",
 416     "ls"
 417    ]
 418   },
 419   {
 420    "cell_type": "code",
 421    "execution_count": 18,
 422    "metadata": {
 423     "collapsed": true
 424    },
 425    "outputs": [],
 426    "source": [
 427     "random.shuffle(ls)"
 428    ]
 429   },
 430   {
 431    "cell_type": "code",
 432    "execution_count": 19,
 433    "metadata": {
 434     "collapsed": true
 435    },
 436    "outputs": [],
 437    "source": [
 438     "def read_net(net_string):\n",
 439     "    return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
 440    ]
 441   },
 442   {
 443    "cell_type": "code",
 444    "execution_count": 20,
 445    "metadata": {
 446     "collapsed": true
 447    },
 448    "outputs": [],
 449    "source": [
 450     "def extract_pairs(net_string):\n",
 451     "    return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
 452    ]
 453   },
 454   {
 455    "cell_type": "code",
 456    "execution_count": 21,
 457    "metadata": {},
 458    "outputs": [
 459     {
 460      "data": {
 461       "text/plain": [
 462        "[Link(height=0, left=0, right=3),\n",
 463        " Link(height=1, left=1, right=7),\n",
 464        " Link(height=2, left=1, right=8),\n",
 465        " Link(height=3, left=6, right=9),\n",
 466        " Link(height=4, left=0, right=4),\n",
 467        " Link(height=5, left=0, right=8),\n",
 468        " Link(height=6, left=3, right=4),\n",
 469        " Link(height=7, left=3, right=6),\n",
 470        " Link(height=8, left=1, right=8),\n",
 471        " Link(height=9, left=5, right=6),\n",
 472        " Link(height=10, left=1, right=7),\n",
 473        " Link(height=11, left=1, right=9),\n",
 474        " Link(height=12, left=0, right=4),\n",
 475        " Link(height=13, left=5, right=6),\n",
 476        " Link(height=14, left=0, right=2),\n",
 477        " Link(height=15, left=3, right=7),\n",
 478        " Link(height=16, left=2, right=4),\n",
 479        " Link(height=17, left=6, right=8),\n",
 480        " Link(height=18, left=0, right=6),\n",
 481        " Link(height=19, left=7, right=8)]"
 482       ]
 483      },
 484      "execution_count": 21,
 485      "metadata": {},
 486      "output_type": "execute_result"
 487     }
 488    ],
 489    "source": [
 490     "read_net(show_net(net))"
 491    ]
 492   },
 493   {
 494    "cell_type": "code",
 495    "execution_count": 22,
 496    "metadata": {},
 497    "outputs": [
 498     {
 499      "data": {
 500       "text/plain": [
 501        "[Link(height=0, left=0, right=3),\n",
 502        " Link(height=0, left=1, right=7),\n",
 503        " Link(height=0, left=6, right=9),\n",
 504        " Link(height=1, left=0, right=4),\n",
 505        " Link(height=1, left=1, right=8),\n",
 506        " Link(height=2, left=0, right=8),\n",
 507        " Link(height=2, left=3, right=4),\n",
 508        " Link(height=3, left=0, right=4),\n",
 509        " Link(height=3, left=1, right=8),\n",
 510        " Link(height=3, left=3, right=6),\n",
 511        " Link(height=4, left=0, right=2),\n",
 512        " Link(height=4, left=1, right=7),\n",
 513        " Link(height=4, left=5, right=6),\n",
 514        " Link(height=5, left=1, right=9),\n",
 515        " Link(height=5, left=2, right=4),\n",
 516        " Link(height=5, left=3, right=7),\n",
 517        " Link(height=5, left=5, right=6),\n",
 518        " Link(height=6, left=6, right=8),\n",
 519        " Link(height=7, left=0, right=6),\n",
 520        " Link(height=7, left=7, right=8)]"
 521       ]
 522      },
 523      "execution_count": 22,
 524      "metadata": {},
 525      "output_type": "execute_result"
 526     }
 527    ],
 528    "source": [
 529     "pack(net)"
 530    ]
 531   },
 532   {
 533    "cell_type": "code",
 534    "execution_count": 23,
 535    "metadata": {},
 536    "outputs": [
 537     {
 538      "data": {
 539       "text/plain": [
 540        "[Link(height=0, left=0, right=3),\n",
 541        " Link(height=0, left=1, right=7),\n",
 542        " Link(height=0, left=6, right=9),\n",
 543        " Link(height=1, left=0, right=4),\n",
 544        " Link(height=1, left=1, right=8),\n",
 545        " Link(height=2, left=0, right=8),\n",
 546        " Link(height=2, left=3, right=4),\n",
 547        " Link(height=3, left=0, right=4),\n",
 548        " Link(height=3, left=1, right=8),\n",
 549        " Link(height=3, left=3, right=6),\n",
 550        " Link(height=4, left=0, right=2),\n",
 551        " Link(height=4, left=1, right=7),\n",
 552        " Link(height=4, left=5, right=6),\n",
 553        " Link(height=5, left=1, right=9),\n",
 554        " Link(height=5, left=2, right=4),\n",
 555        " Link(height=5, left=3, right=7),\n",
 556        " Link(height=5, left=5, right=6),\n",
 557        " Link(height=6, left=6, right=8),\n",
 558        " Link(height=7, left=0, right=6),\n",
 559        " Link(height=7, left=7, right=8)]"
 560       ]
 561      },
 562      "execution_count": 23,
 563      "metadata": {},
 564      "output_type": "execute_result"
 565     }
 566    ],
 567    "source": [
 568     "pack(read_net(show_net(net)))"
 569    ]
 570   },
 571   {
 572    "cell_type": "code",
 573    "execution_count": 24,
 574    "metadata": {},
 575    "outputs": [
 576     {
 577      "data": {
 578       "text/plain": [
 579        "(False, True)"
 580       ]
 581      },
 582      "execution_count": 24,
 583      "metadata": {},
 584      "output_type": "execute_result"
 585     }
 586    ],
 587    "source": [
 588     "pnet = pack(net)\n",
 589     "rrnet = read_net(show_net(net, randomise=True))\n",
 590     "rnet = read_net(show_net(net))\n",
 591     "rnet == rrnet, pack(rrnet) == pnet"
 592    ]
 593   },
 594   {
 595    "cell_type": "code",
 596    "execution_count": 25,
 597    "metadata": {
 598     "collapsed": true
 599    },
 600    "outputs": [],
 601    "source": [
 602     "lnet = make_net(10207, 26, 100000)\n",
 603     "plnet = pack(lnet)\n",
 604     "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, plnet)\n",
 605     "# for i in range(204):\n",
 606     "#     assert follow(i, lnet) == follow(i, plnet)"
 607    ]
 608   },
 609   {
 610    "cell_type": "code",
 611    "execution_count": 26,
 612    "metadata": {
 613     "collapsed": true
 614    },
 615    "outputs": [],
 616    "source": [
 617     "rlnet = read_net(show_net(lnet))\n",
 618     "prlnet = pack(rlnet)"
 619    ]
 620   },
 621   {
 622    "cell_type": "code",
 623    "execution_count": 27,
 624    "metadata": {},
 625    "outputs": [
 626     {
 627      "data": {
 628       "text/plain": [
 629        "2224"
 630       ]
 631      },
 632      "execution_count": 27,
 633      "metadata": {},
 634      "output_type": "execute_result"
 635     }
 636    ],
 637    "source": [
 638     "max(link.height for link in plnet)"
 639    ]
 640   },
 641   {
 642    "cell_type": "code",
 643    "execution_count": 28,
 644    "metadata": {},
 645    "outputs": [
 646     {
 647      "data": {
 648       "text/plain": [
 649        "99998"
 650       ]
 651      },
 652      "execution_count": 28,
 653      "metadata": {},
 654      "output_type": "execute_result"
 655     }
 656    ],
 657    "source": [
 658     "max(link.height for link in lnet)"
 659    ]
 660   },
 661   {
 662    "cell_type": "code",
 663    "execution_count": 29,
 664    "metadata": {},
 665    "outputs": [
 666     {
 667      "data": {
 668       "text/plain": [
 669        "10206"
 670       ]
 671      },
 672      "execution_count": 29,
 673      "metadata": {},
 674      "output_type": "execute_result"
 675     }
 676    ],
 677    "source": [
 678     "max(link.height for link in rlnet)"
 679    ]
 680   },
 681   {
 682    "cell_type": "code",
 683    "execution_count": 30,
 684    "metadata": {},
 685    "outputs": [
 686     {
 687      "data": {
 688       "text/plain": [
 689        "2224"
 690       ]
 691      },
 692      "execution_count": 30,
 693      "metadata": {},
 694      "output_type": "execute_result"
 695     }
 696    ],
 697    "source": [
 698     "max(link.height for link in prlnet)"
 699    ]
 700   },
 701   {
 702    "cell_type": "code",
 703    "execution_count": 31,
 704    "metadata": {
 705     "collapsed": true
 706    },
 707    "outputs": [],
 708    "source": [
 709     "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, prlnet)"
 710    ]
 711   },
 712   {
 713    "cell_type": "code",
 714    "execution_count": 32,
 715    "metadata": {},
 716    "outputs": [
 717     {
 718      "name": "stdout",
 719      "output_type": "stream",
 720      "text": [
 721       "10 loops, best of 3: 23.4 ms per loop\n"
 722      ]
 723     }
 724    ],
 725    "source": [
 726     "%%timeit\n",
 727     "follow_many(string.ascii_lowercase, lnet)"
 728    ]
 729   },
 730   {
 731    "cell_type": "code",
 732    "execution_count": 33,
 733    "metadata": {
 734     "collapsed": true
 735    },
 736    "outputs": [],
 737    "source": [
 738     "# %%timeit\n",
 739     "# follow_many_slow(string.ascii_lowercase, lnet)"
 740    ]
 741   },
 742   {
 743    "cell_type": "code",
 744    "execution_count": 34,
 745    "metadata": {
 746     "collapsed": true
 747    },
 748    "outputs": [],
 749    "source": [
 750     "def eliminable_pairs_slow(net):\n",
 751     "    eps = []\n",
 752     "    for l in net:\n",
 753     "        o = Link(l.height + 1, l.left, l.right)\n",
 754     "        if o in net:\n",
 755     "            eps += [(l, o)]\n",
 756     "    return eps    "
 757    ]
 758   },
 759   {
 760    "cell_type": "code",
 761    "execution_count": 35,
 762    "metadata": {
 763     "collapsed": true
 764    },
 765    "outputs": [],
 766    "source": [
 767     "def eliminable_pairs(net):\n",
 768     "    height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
 769     "    eps = []\n",
 770     "    for h in range(1, max(height_groups.keys())):\n",
 771     "        for l in height_groups[h]:\n",
 772     "            o = Link(l.height - 1, l.left, l.right)\n",
 773     "            if o in height_groups[h-1]:\n",
 774     "                eps += [(l, o)]\n",
 775     "    return eps"
 776    ]
 777   },
 778   {
 779    "cell_type": "code",
 780    "execution_count": 36,
 781    "metadata": {},
 782    "outputs": [
 783     {
 784      "name": "stdout",
 785      "output_type": "stream",
 786      "text": [
 787       "10 loops, best of 3: 23.5 ms per loop\n"
 788      ]
 789     }
 790    ],
 791    "source": [
 792     "%%timeit\n",
 793     "eliminable_pairs(plnet)"
 794    ]
 795   },
 796   {
 797    "cell_type": "code",
 798    "execution_count": 37,
 799    "metadata": {
 800     "collapsed": true
 801    },
 802    "outputs": [],
 803    "source": [
 804     "def eliminable_pair(net):\n",
 805     "    for l in net:\n",
 806     "        o = Link(l.height + 1, l.left, l.right)\n",
 807     "        if o in net:\n",
 808     "            return l, o\n",
 809     "    return None"
 810    ]
 811   },
 812   {
 813    "cell_type": "code",
 814    "execution_count": 38,
 815    "metadata": {
 816     "collapsed": true
 817    },
 818    "outputs": [],
 819    "source": [
 820     "def eliminable_pair_hg(height_groups):\n",
 821     "    for h in range(1, max(height_groups.keys())):\n",
 822     "        for l in height_groups[h]:\n",
 823     "            o = Link(l.height - 1, l.left, l.right)\n",
 824     "            if o in height_groups[h-1]:\n",
 825     "                return l, o\n",
 826     "    return None"
 827    ]
 828   },
 829   {
 830    "cell_type": "code",
 831    "execution_count": 39,
 832    "metadata": {
 833     "collapsed": true
 834    },
 835    "outputs": [],
 836    "source": [
 837     "def eliminate_pairs_slow(net):\n",
 838     "    eliminable_links = eliminable_pair(net)\n",
 839     "    while eliminable_links:\n",
 840     "        net = pack(l for l in net if l not in eliminable_links)\n",
 841     "        eliminable_links = eliminable_pair(net)\n",
 842     "    return net"
 843    ]
 844   },
 845   {
 846    "cell_type": "code",
 847    "execution_count": 40,
 848    "metadata": {
 849     "collapsed": true
 850    },
 851    "outputs": [],
 852    "source": [
 853     "def eliminate_pairs(net):\n",
 854     "    height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
 855     "    eliminable_links = eliminable_pair_hg(height_groups)\n",
 856     "    while eliminable_links:\n",
 857     "        net = pack(l for l in net if l not in eliminable_links)\n",
 858     "        height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
 859     "        eliminable_links = eliminable_pair_hg(height_groups)\n",
 860     "    return net"
 861    ]
 862   },
 863   {
 864    "cell_type": "code",
 865    "execution_count": 41,
 866    "metadata": {},
 867    "outputs": [
 868     {
 869      "name": "stdout",
 870      "output_type": "stream",
 871      "text": [
 872       "10207\n"
 873      ]
 874     },
 875     {
 876      "data": {
 877       "text/plain": [
 878        "(10207, 9839)"
 879       ]
 880      },
 881      "execution_count": 41,
 882      "metadata": {},
 883      "output_type": "execute_result"
 884     }
 885    ],
 886    "source": [
 887     "print(len(plnet))\n",
 888     "elnet = eliminate_pairs(plnet)\n",
 889     "len(plnet), len(elnet)"
 890    ]
 891   },
 892   {
 893    "cell_type": "code",
 894    "execution_count": 42,
 895    "metadata": {},
 896    "outputs": [
 897     {
 898      "data": {
 899       "text/plain": [
 900        "[]"
 901       ]
 902      },
 903      "execution_count": 42,
 904      "metadata": {},
 905      "output_type": "execute_result"
 906     }
 907    ],
 908    "source": [
 909     "eliminable_pairs(elnet)"
 910    ]
 911   },
 912   {
 913    "cell_type": "code",
 914    "execution_count": 43,
 915    "metadata": {
 916     "collapsed": true
 917    },
 918    "outputs": [],
 919    "source": [
 920     "assert follow_many(string.ascii_lowercase,  lnet) == follow_many(string.ascii_lowercase, elnet)\n",
 921     "assert follow_many(string.ascii_lowercase, plnet) == follow_many(string.ascii_lowercase, elnet)"
 922    ]
 923   },
 924   {
 925    "cell_type": "code",
 926    "execution_count": 44,
 927    "metadata": {},
 928    "outputs": [
 929     {
 930      "name": "stdout",
 931      "output_type": "stream",
 932      "text": [
 933       "1 loop, best of 3: 5.77 s per loop\n"
 934      ]
 935     }
 936    ],
 937    "source": [
 938     "%%timeit\n",
 939     "elnet = eliminate_pairs(plnet)"
 940    ]
 941   },
 942   {
 943    "cell_type": "code",
 944    "execution_count": 45,
 945    "metadata": {
 946     "collapsed": true
 947    },
 948    "outputs": [],
 949    "source": [
 950     "# for i in range(26):\n",
 951     "#     assert follow(i, plnet) == follow(i, elnet)\n",
 952     "#     assert follow(i,  lnet) == follow(i, elnet)"
 953    ]
 954   },
 955   {
 956    "cell_type": "code",
 957    "execution_count": 46,
 958    "metadata": {
 959     "collapsed": true
 960    },
 961    "outputs": [],
 962    "source": [
 963     "# follow(0, plnet), follow(0, elnet), follow(0, lnet)"
 964    ]
 965   },
 966   {
 967    "cell_type": "code",
 968    "execution_count": 47,
 969    "metadata": {
 970     "collapsed": true
 971    },
 972    "outputs": [],
 973    "source": [
 974     "def triple_slow(net):\n",
 975     "    x = None\n",
 976     "    y = None\n",
 977     "    ts = []\n",
 978     "    for a in net:\n",
 979     "        bs = [l for l in net if l.height == a.height + 1 \n",
 980     "              if l.left == a.right or l.right == a.left]\n",
 981     "        for b in bs:\n",
 982     "            c = Link(a.height + 2, a.left, a.right)\n",
 983     "            if c in net:\n",
 984     "                ts += [(a, b, c)]\n",
 985     "    return ts"
 986    ]
 987   },
 988   {
 989    "cell_type": "code",
 990    "execution_count": 48,
 991    "metadata": {
 992     "collapsed": true
 993    },
 994    "outputs": [],
 995    "source": [
 996     "def triple_pair_slow(net):\n",
 997     "    ts = []\n",
 998     "    for a in net:\n",
 999     "        a_ends = link_ends(a)\n",
1000     "        bs = [l for l in net if l.height == a.height + 1 \n",
1001     "              if link_ends(l) & a_ends]\n",
1002     "        if len(bs) == 1:\n",
1003     "            b = bs[0]\n",
1004     "            lines = set((a.left, a.right, b.left, b.right))\n",
1005     "            cs = [l for l in net \n",
1006     "                  if l.height == a.height + 2\n",
1007     "                  if link_ends(l) & lines]\n",
1008     "            if len(cs) == 1:\n",
1009     "                c = Link(a.height + 2, a.left, a.right)\n",
1010     "                if c in cs:\n",
1011     "                    ds = [l for l in net \n",
1012     "                          if l.height == a.height + 3\n",
1013     "                          if link_ends(l) & lines]\n",
1014     "                    d = Link(a.height + 3, b.left, b.right)\n",
1015     "                    if d in ds:\n",
1016     "                        ts += [(a, b, c, d)]\n",
1017     "    return ts"
1018    ]
1019   },
1020   {
1021    "cell_type": "code",
1022    "execution_count": 49,
1023    "metadata": {
1024     "collapsed": true
1025    },
1026    "outputs": [],
1027    "source": [
1028     "def find_height_groups(net):\n",
1029     "    return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
1030    ]
1031   },
1032   {
1033    "cell_type": "code",
1034    "execution_count": 50,
1035    "metadata": {},
1036    "outputs": [],
1037    "source": [
1038     "def triple_pair_hg(height_groups, debug=False):\n",
1039     "    ts = []\n",
1040     "    for h in range(3, max(height_groups.keys())):\n",
1041     "        for d in height_groups[h]:\n",
1042     "            if debug: print('d:', d)\n",
1043     "            ch = h - 1\n",
1044     "            cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
1045     "            if debug: print('cs:', cs)\n",
1046     "            while ch > 2 and not cs:\n",
1047     "                ch -= 1\n",
1048     "                cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
1049     "                if debug: print('cs:', cs)\n",
1050     "            if len(cs) == 1:\n",
1051     "                c = cs[0]\n",
1052     "                lines = set((d.left, d.right, c.left, c.right))\n",
1053     "                if debug: print('c:', '; lines:', lines)\n",
1054     "                bs = [l for l in height_groups[ch-1] if link_ends(l) & lines]\n",
1055     "                b = Link(ch - 1, d.left, d.right)\n",
1056     "                if debug: print('b:', b, '; bs:', bs)\n",
1057     "                if len(bs) == 1 and b in bs:\n",
1058     "                    ah = b.height - 1\n",
1059     "                    als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
1060     "                    if debug: print('ah:', ah, '; als:', als)\n",
1061     "                    while ah > 0 and not als:\n",
1062     "                        ah -= 1\n",
1063     "                        als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
1064     "                        if debug: print('ah:', ah, '; als:', als)\n",
1065     "                    a = Link(ah, c.left, c.right)\n",
1066     "                    if debug: print('a:', a)\n",
1067     "                    if a in als:\n",
1068     "                        if debug: print('adding:', a, b, c, d)\n",
1069     "                        ts += [(a, b, c, d)]\n",
1070     "    return ts"
1071    ]
1072   },
1073   {
1074    "cell_type": "code",
1075    "execution_count": 51,
1076    "metadata": {
1077     "collapsed": true
1078    },
1079    "outputs": [],
1080    "source": [
1081     "def eliminate_a_triple_pair_slow(net, debug=False):\n",
1082     "    tps = triple_pair_slow(net)\n",
1083     "    if debug: print('eatp', tps)\n",
1084     "\n",
1085     "    if tps:\n",
1086     "        a, b, c, d = tps[0]\n",
1087     "#         x = Link(a.height, b.left, b.right)\n",
1088     "#         y = Link(b.height, a.left, a.right)\n",
1089     "        x = Link(b.height - 0.5, b.left, b.right)\n",
1090     "        y = Link(b.height, a.left, a.right)\n",
1091     "        if debug: print('removing', a, b, c, d, '; adding', x, y)\n",
1092     "        return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
1093     "    return None"
1094    ]
1095   },
1096   {
1097    "cell_type": "code",
1098    "execution_count": 52,
1099    "metadata": {
1100     "collapsed": true
1101    },
1102    "outputs": [],
1103    "source": [
1104     "def eliminate_a_triple_pair(net, debug=False):\n",
1105     "    height_groups = find_height_groups(net)\n",
1106     "\n",
1107     "    tps = triple_pair_hg(height_groups)\n",
1108     "    if debug: print('eatp', tps)\n",
1109     "    if tps:\n",
1110     "        a, b, c, d = tps[0]\n",
1111     "        x = Link(b.height - 0.5, b.left, b.right)\n",
1112     "        y = Link(b.height, a.left, a.right)\n",
1113     "        if debug: print('removing', a, b, c, d, '; adding', x, y)\n",
1114     "        return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
1115     "    return None"
1116    ]
1117   },
1118   {
1119    "cell_type": "code",
1120    "execution_count": 53,
1121    "metadata": {},
1122    "outputs": [
1123     {
1124      "data": {
1125       "text/plain": [
1126        "[(Link(height=831, left=8, right=16),\n",
1127        "  Link(height=832, left=8, right=25),\n",
1128        "  Link(height=833, left=8, right=16),\n",
1129        "  Link(height=834, left=8, right=25)),\n",
1130        " (Link(height=1657, left=1, right=13),\n",
1131        "  Link(height=1658, left=1, right=12),\n",
1132        "  Link(height=1659, left=1, right=13),\n",
1133        "  Link(height=1660, left=1, right=12))]"
1134       ]
1135      },
1136      "execution_count": 53,
1137      "metadata": {},
1138      "output_type": "execute_result"
1139     }
1140    ],
1141    "source": [
1142     "height_groups = find_height_groups(elnet)\n",
1143     "triple_pair_hg(height_groups)"
1144    ]
1145   },
1146   {
1147    "cell_type": "code",
1148    "execution_count": 54,
1149    "metadata": {},
1150    "outputs": [
1151     {
1152      "name": "stdout",
1153      "output_type": "stream",
1154      "text": [
1155       "10 loops, best of 3: 99.4 ms per loop\n"
1156      ]
1157     }
1158    ],
1159    "source": [
1160     "%%timeit\n",
1161     "height_groups = find_height_groups(elnet)\n",
1162     "triple_pair_hg(height_groups)"
1163    ]
1164   },
1165   {
1166    "cell_type": "code",
1167    "execution_count": 55,
1168    "metadata": {
1169     "collapsed": true
1170    },
1171    "outputs": [],
1172    "source": [
1173     "def eliminate_triple_pairs_slow(net):\n",
1174     "    print(len(net))\n",
1175     "    new_net = eliminate_a_triple_pair_slow(net)\n",
1176     "    while new_net:\n",
1177     "        print(len(net))\n",
1178     "        net = new_net\n",
1179     "        new_net = eliminate_a_triple_pair_slow(net)\n",
1180     "    return net"
1181    ]
1182   },
1183   {
1184    "cell_type": "code",
1185    "execution_count": 56,
1186    "metadata": {
1187     "collapsed": true
1188    },
1189    "outputs": [],
1190    "source": [
1191     "def eliminate_triple_pairs(net):\n",
1192     "    print(len(net))\n",
1193     "    new_net = eliminate_a_triple_pair(net)\n",
1194     "    while new_net:\n",
1195     "        print(len(net))\n",
1196     "        net = new_net\n",
1197     "        new_net = eliminate_a_triple_pair(net)\n",
1198     "    return net"
1199    ]
1200   },
1201   {
1202    "cell_type": "code",
1203    "execution_count": 57,
1204    "metadata": {},
1205    "outputs": [],
1206    "source": [
1207     "etlnet = eliminate_a_triple_pair(elnet)"
1208    ]
1209   },
1210   {
1211    "cell_type": "code",
1212    "execution_count": 58,
1213    "metadata": {},
1214    "outputs": [],
1215    "source": [
1216     "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
1217    ]
1218   },
1219   {
1220    "cell_type": "code",
1221    "execution_count": 59,
1222    "metadata": {},
1223    "outputs": [
1224     {
1225      "name": "stdout",
1226      "output_type": "stream",
1227      "text": [
1228       "9839\n",
1229       "9839\n",
1230       "9837\n"
1231      ]
1232     }
1233    ],
1234    "source": [
1235     "setlnet = eliminate_triple_pairs(elnet)"
1236    ]
1237   },
1238   {
1239    "cell_type": "code",
1240    "execution_count": 60,
1241    "metadata": {},
1242    "outputs": [
1243     {
1244      "data": {
1245       "text/plain": [
1246        "9835"
1247       ]
1248      },
1249      "execution_count": 60,
1250      "metadata": {},
1251      "output_type": "execute_result"
1252     }
1253    ],
1254    "source": [
1255     "len(setlnet)"
1256    ]
1257   },
1258   {
1259    "cell_type": "code",
1260    "execution_count": 61,
1261    "metadata": {},
1262    "outputs": [],
1263    "source": [
1264     "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
1265    ]
1266   },
1267   {
1268    "cell_type": "code",
1269    "execution_count": 62,
1270    "metadata": {},
1271    "outputs": [
1272     {
1273      "data": {
1274       "text/plain": [
1275        "'buxphgtzqykfawvomcjresnldi'"
1276       ]
1277      },
1278      "execution_count": 62,
1279      "metadata": {},
1280      "output_type": "execute_result"
1281     }
1282    ],
1283    "source": [
1284     "''.join(follow_many(string.ascii_lowercase, etlnet))"
1285    ]
1286   },
1287   {
1288    "cell_type": "code",
1289    "execution_count": 63,
1290    "metadata": {},
1291    "outputs": [
1292     {
1293      "data": {
1294       "text/plain": [
1295        "'buxphgtzqykfawvomcjresnldi'"
1296       ]
1297      },
1298      "execution_count": 63,
1299      "metadata": {},
1300      "output_type": "execute_result"
1301     }
1302    ],
1303    "source": [
1304     "''.join(follow_many(string.ascii_lowercase, setlnet))"
1305    ]
1306   },
1307   {
1308    "cell_type": "code",
1309    "execution_count": 64,
1310    "metadata": {},
1311    "outputs": [
1312     {
1313      "data": {
1314       "text/plain": [
1315        "'buxphgtzqykfawvomcjresnldi'"
1316       ]
1317      },
1318      "execution_count": 64,
1319      "metadata": {},
1320      "output_type": "execute_result"
1321     }
1322    ],
1323    "source": [
1324     "''.join(follow_many(string.ascii_lowercase, elnet))"
1325    ]
1326   },
1327   {
1328    "cell_type": "code",
1329    "execution_count": 65,
1330    "metadata": {},
1331    "outputs": [
1332     {
1333      "data": {
1334       "text/plain": [
1335        "'buxphgtzqykfawvomcjresnldi'"
1336       ]
1337      },
1338      "execution_count": 65,
1339      "metadata": {},
1340      "output_type": "execute_result"
1341     }
1342    ],
1343    "source": [
1344     "''.join(follow_many(string.ascii_lowercase, lnet))"
1345    ]
1346   },
1347   {
1348    "cell_type": "code",
1349    "execution_count": 66,
1350    "metadata": {},
1351    "outputs": [
1352     {
1353      "data": {
1354       "text/plain": [
1355        "[]"
1356       ]
1357      },
1358      "execution_count": 66,
1359      "metadata": {},
1360      "output_type": "execute_result"
1361     }
1362    ],
1363    "source": [
1364     "eliminable_pairs(etlnet)"
1365    ]
1366   },
1367   {
1368    "cell_type": "code",
1369    "execution_count": 67,
1370    "metadata": {},
1371    "outputs": [
1372     {
1373      "data": {
1374       "text/plain": [
1375        "(10207, 9837)"
1376       ]
1377      },
1378      "execution_count": 67,
1379      "metadata": {},
1380      "output_type": "execute_result"
1381     }
1382    ],
1383    "source": [
1384     "len(lnet), len(etlnet)"
1385    ]
1386   },
1387   {
1388    "cell_type": "code",
1389    "execution_count": 68,
1390    "metadata": {
1391     "collapsed": true
1392    },
1393    "outputs": [],
1394    "source": [
1395     "def simplify(net0):\n",
1396     "    netp = eliminate_pairs(net0)\n",
1397     "    new_net = eliminate_a_triple_pair(netp)\n",
1398     "    while new_net:\n",
1399     "#         print('sipl', len(net0), len(netp), len(new_net))\n",
1400     "        netp = eliminate_pairs(new_net)\n",
1401     "        new_net = eliminate_a_triple_pair(netp)\n",
1402     "    return netp"
1403    ]
1404   },
1405   {
1406    "cell_type": "code",
1407    "execution_count": 69,
1408    "metadata": {},
1409    "outputs": [],
1410    "source": [
1411     "simple_lnet = simplify(plnet)"
1412    ]
1413   },
1414   {
1415    "cell_type": "code",
1416    "execution_count": 70,
1417    "metadata": {},
1418    "outputs": [
1419     {
1420      "data": {
1421       "text/plain": [
1422        "True"
1423       ]
1424      },
1425      "execution_count": 70,
1426      "metadata": {},
1427      "output_type": "execute_result"
1428     }
1429    ],
1430    "source": [
1431     "''.join(follow_many(string.ascii_lowercase, simple_lnet)) == ''.join(follow_many(string.ascii_lowercase, lnet))"
1432    ]
1433   },
1434   {
1435    "cell_type": "code",
1436    "execution_count": 71,
1437    "metadata": {},
1438    "outputs": [
1439     {
1440      "data": {
1441       "text/plain": [
1442        "'buxphgtzqykfawvomcjresnldi'"
1443       ]
1444      },
1445      "execution_count": 71,
1446      "metadata": {},
1447      "output_type": "execute_result"
1448     }
1449    ],
1450    "source": [
1451     "''.join(follow_many(string.ascii_lowercase, simple_lnet))"
1452    ]
1453   },
1454   {
1455    "cell_type": "code",
1456    "execution_count": 72,
1457    "metadata": {},
1458    "outputs": [
1459     {
1460      "data": {
1461       "text/plain": [
1462        "'buxphgtzqykfawvomcjresnldi'"
1463       ]
1464      },
1465      "execution_count": 72,
1466      "metadata": {},
1467      "output_type": "execute_result"
1468     }
1469    ],
1470    "source": [
1471     "''.join(follow_many(string.ascii_lowercase, lnet))"
1472    ]
1473   },
1474   {
1475    "cell_type": "code",
1476    "execution_count": 73,
1477    "metadata": {},
1478    "outputs": [
1479     {
1480      "data": {
1481       "text/plain": [
1482        "9835"
1483       ]
1484      },
1485      "execution_count": 73,
1486      "metadata": {},
1487      "output_type": "execute_result"
1488     }
1489    ],
1490    "source": [
1491     "len(simple_lnet)"
1492    ]
1493   },
1494   {
1495    "cell_type": "code",
1496    "execution_count": 89,
1497    "metadata": {
1498     "collapsed": true
1499    },
1500    "outputs": [],
1501    "source": [
1502     "def add_triple_pair(net, max_lines=None, trace=False):\n",
1503     "    if not max_lines:\n",
1504     "        max_lines = max(l.right for l in net)\n",
1505     "    a, b, c = 0, 0, 0\n",
1506     "    while len(set((a, b, c))) != 3:\n",
1507     "        a = random.randrange(max_lines)\n",
1508     "        b = random.randrange(max_lines)\n",
1509     "        c = random.randrange(max_lines)\n",
1510     "    tp = [(min(a, b), max(a, b)), (min(b, c), max(b, c))] * 2\n",
1511     "    \n",
1512     "    pairs = [(l.left, l.right) for l in sorted(net)]\n",
1513     "    i = random.randrange(len(pairs))\n",
1514     "    if trace: print(i, tp)\n",
1515     "    new_pairs = pairs[:i] + tp + pairs[i:]\n",
1516     "    return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)])   "
1517    ]
1518   },
1519   {
1520    "cell_type": "code",
1521    "execution_count": 90,
1522    "metadata": {
1523     "collapsed": true
1524    },
1525    "outputs": [],
1526    "source": [
1527     "def add_pair(net, max_lines=None, trace=False):\n",
1528     "    if not max_lines:\n",
1529     "        max_lines = max(l.right for l in net)\n",
1530     "\n",
1531     "    a, b = 0, 0\n",
1532     "    while a == b:\n",
1533     "        a = random.randrange(max_lines)\n",
1534     "        b = random.randrange(max_lines)\n",
1535     "    p = [(min(a, b), max(a, b))] * 2\n",
1536     "    \n",
1537     "    pairs = [(l.left, l.right) for l in sorted(net)]\n",
1538     "    i = random.randrange(len(pairs))\n",
1539     "    \n",
1540     "    if trace: print(i, p)\n",
1541     "    new_pairs = pairs[:i] + p + pairs[i:]\n",
1542     "    return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)])   "
1543    ]
1544   },
1545   {
1546    "cell_type": "code",
1547    "execution_count": 76,
1548    "metadata": {},
1549    "outputs": [
1550     {
1551      "data": {
1552       "text/plain": [
1553        "[]"
1554       ]
1555      },
1556      "execution_count": 76,
1557      "metadata": {},
1558      "output_type": "execute_result"
1559     }
1560    ],
1561    "source": [
1562     "height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
1563     "tps = triple_pair_hg(height_groups)\n",
1564     "tps"
1565    ]
1566   },
1567   {
1568    "cell_type": "code",
1569    "execution_count": 91,
1570    "metadata": {
1571     "scrolled": true
1572    },
1573    "outputs": [
1574     {
1575      "data": {
1576       "text/plain": [
1577        "[]"
1578       ]
1579      },
1580      "execution_count": 91,
1581      "metadata": {},
1582      "output_type": "execute_result"
1583     }
1584    ],
1585    "source": [
1586     "lnettp = simple_lnet\n",
1587     "for _ in range(10):\n",
1588     "    lnettp = add_pair(lnettp)\n",
1589     "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1590     "tps = triple_pair_hg(height_groups)\n",
1591     "tps"
1592    ]
1593   },
1594   {
1595    "cell_type": "code",
1596    "execution_count": 92,
1597    "metadata": {
1598     "scrolled": true
1599    },
1600    "outputs": [
1601     {
1602      "data": {
1603       "text/plain": [
1604        "[(Link(height=195, left=5, right=10),\n",
1605        "  Link(height=197, left=1, right=5),\n",
1606        "  Link(height=198, left=5, right=10),\n",
1607        "  Link(height=199, left=1, right=5)),\n",
1608        " (Link(height=359, left=6, right=16),\n",
1609        "  Link(height=360, left=16, right=20),\n",
1610        "  Link(height=361, left=6, right=16),\n",
1611        "  Link(height=362, left=16, right=20)),\n",
1612        " (Link(height=409, left=0, right=9),\n",
1613        "  Link(height=410, left=9, right=16),\n",
1614        "  Link(height=411, left=0, right=9),\n",
1615        "  Link(height=412, left=9, right=16)),\n",
1616        " (Link(height=606, left=0, right=7),\n",
1617        "  Link(height=607, left=0, right=5),\n",
1618        "  Link(height=608, left=0, right=7),\n",
1619        "  Link(height=609, left=0, right=5)),\n",
1620        " (Link(height=967, left=7, right=19),\n",
1621        "  Link(height=968, left=19, right=23),\n",
1622        "  Link(height=969, left=7, right=19),\n",
1623        "  Link(height=970, left=19, right=23)),\n",
1624        " (Link(height=973, left=9, right=18),\n",
1625        "  Link(height=975, left=9, right=15),\n",
1626        "  Link(height=976, left=9, right=18),\n",
1627        "  Link(height=977, left=9, right=15)),\n",
1628        " (Link(height=1193, left=1, right=11),\n",
1629        "  Link(height=1194, left=1, right=19),\n",
1630        "  Link(height=1195, left=1, right=11),\n",
1631        "  Link(height=1196, left=1, right=19)),\n",
1632        " (Link(height=1388, left=17, right=21),\n",
1633        "  Link(height=1389, left=6, right=17),\n",
1634        "  Link(height=1390, left=17, right=21),\n",
1635        "  Link(height=1391, left=6, right=17)),\n",
1636        " (Link(height=1700, left=5, right=24),\n",
1637        "  Link(height=1701, left=11, right=24),\n",
1638        "  Link(height=1702, left=5, right=24),\n",
1639        "  Link(height=1703, left=11, right=24)),\n",
1640        " (Link(height=1923, left=12, right=19),\n",
1641        "  Link(height=1924, left=19, right=24),\n",
1642        "  Link(height=1925, left=12, right=19),\n",
1643        "  Link(height=1926, left=19, right=24))]"
1644       ]
1645      },
1646      "execution_count": 92,
1647      "metadata": {},
1648      "output_type": "execute_result"
1649     }
1650    ],
1651    "source": [
1652     "lnettp = simple_lnet\n",
1653     "for _ in range(10):\n",
1654     "    lnettp = add_triple_pair(lnettp)\n",
1655     "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1656     "tps = triple_pair_hg(height_groups)\n",
1657     "tps"
1658    ]
1659   },
1660   {
1661    "cell_type": "code",
1662    "execution_count": 93,
1663    "metadata": {
1664     "scrolled": true
1665    },
1666    "outputs": [
1667     {
1668      "data": {
1669       "text/plain": [
1670        "[(Link(height=8, left=1, right=5),\n",
1671        "  Link(height=9, left=1, right=21),\n",
1672        "  Link(height=10, left=1, right=5),\n",
1673        "  Link(height=11, left=1, right=21)),\n",
1674        " (Link(height=40, left=16, right=23),\n",
1675        "  Link(height=41, left=16, right=19),\n",
1676        "  Link(height=42, left=16, right=23),\n",
1677        "  Link(height=43, left=16, right=19)),\n",
1678        " (Link(height=62, left=0, right=10),\n",
1679        "  Link(height=63, left=10, right=13),\n",
1680        "  Link(height=64, left=0, right=10),\n",
1681        "  Link(height=65, left=10, right=13)),\n",
1682        " (Link(height=137, left=23, right=24),\n",
1683        "  Link(height=139, left=0, right=24),\n",
1684        "  Link(height=140, left=23, right=24),\n",
1685        "  Link(height=141, left=0, right=24)),\n",
1686        " (Link(height=138, left=10, right=21),\n",
1687        "  Link(height=139, left=2, right=10),\n",
1688        "  Link(height=140, left=10, right=21),\n",
1689        "  Link(height=141, left=2, right=10)),\n",
1690        " (Link(height=139, left=2, right=10),\n",
1691        "  Link(height=140, left=10, right=21),\n",
1692        "  Link(height=141, left=2, right=10),\n",
1693        "  Link(height=142, left=10, right=21)),\n",
1694        " (Link(height=156, left=6, right=11),\n",
1695        "  Link(height=157, left=3, right=6),\n",
1696        "  Link(height=158, left=6, right=11),\n",
1697        "  Link(height=159, left=3, right=6)),\n",
1698        " (Link(height=184, left=2, right=21),\n",
1699        "  Link(height=185, left=5, right=21),\n",
1700        "  Link(height=186, left=2, right=21),\n",
1701        "  Link(height=187, left=5, right=21)),\n",
1702        " (Link(height=274, left=7, right=13),\n",
1703        "  Link(height=275, left=7, right=11),\n",
1704        "  Link(height=276, left=7, right=13),\n",
1705        "  Link(height=277, left=7, right=11)),\n",
1706        " (Link(height=292, left=14, right=15),\n",
1707        "  Link(height=293, left=5, right=15),\n",
1708        "  Link(height=294, left=14, right=15),\n",
1709        "  Link(height=295, left=5, right=15)),\n",
1710        " (Link(height=389, left=1, right=8),\n",
1711        "  Link(height=391, left=8, right=15),\n",
1712        "  Link(height=392, left=1, right=8),\n",
1713        "  Link(height=393, left=8, right=15)),\n",
1714        " (Link(height=422, left=14, right=22),\n",
1715        "  Link(height=424, left=14, right=18),\n",
1716        "  Link(height=425, left=14, right=22),\n",
1717        "  Link(height=426, left=14, right=18)),\n",
1718        " (Link(height=434, left=5, right=19),\n",
1719        "  Link(height=435, left=1, right=19),\n",
1720        "  Link(height=436, left=5, right=19),\n",
1721        "  Link(height=437, left=1, right=19)),\n",
1722        " (Link(height=456, left=0, right=15),\n",
1723        "  Link(height=457, left=14, right=15),\n",
1724        "  Link(height=458, left=0, right=15),\n",
1725        "  Link(height=459, left=14, right=15)),\n",
1726        " (Link(height=550, left=13, right=21),\n",
1727        "  Link(height=551, left=6, right=21),\n",
1728        "  Link(height=552, left=13, right=21),\n",
1729        "  Link(height=553, left=6, right=21)),\n",
1730        " (Link(height=624, left=17, right=23),\n",
1731        "  Link(height=625, left=1, right=23),\n",
1732        "  Link(height=626, left=17, right=23),\n",
1733        "  Link(height=627, left=1, right=23)),\n",
1734        " (Link(height=703, left=8, right=15),\n",
1735        "  Link(height=704, left=3, right=15),\n",
1736        "  Link(height=705, left=8, right=15),\n",
1737        "  Link(height=706, left=3, right=15)),\n",
1738        " (Link(height=794, left=7, right=24),\n",
1739        "  Link(height=795, left=8, right=24),\n",
1740        "  Link(height=796, left=7, right=24),\n",
1741        "  Link(height=797, left=8, right=24)),\n",
1742        " (Link(height=800, left=8, right=13),\n",
1743        "  Link(height=801, left=4, right=8),\n",
1744        "  Link(height=802, left=8, right=13),\n",
1745        "  Link(height=803, left=4, right=8)),\n",
1746        " (Link(height=814, left=16, right=17),\n",
1747        "  Link(height=815, left=3, right=16),\n",
1748        "  Link(height=816, left=16, right=17),\n",
1749        "  Link(height=817, left=3, right=16)),\n",
1750        " (Link(height=905, left=2, right=15),\n",
1751        "  Link(height=906, left=13, right=15),\n",
1752        "  Link(height=907, left=2, right=15),\n",
1753        "  Link(height=908, left=13, right=15)),\n",
1754        " (Link(height=926, left=2, right=15),\n",
1755        "  Link(height=927, left=15, right=16),\n",
1756        "  Link(height=928, left=2, right=15),\n",
1757        "  Link(height=929, left=15, right=16)),\n",
1758        " (Link(height=967, left=2, right=15),\n",
1759        "  Link(height=968, left=2, right=14),\n",
1760        "  Link(height=969, left=2, right=15),\n",
1761        "  Link(height=970, left=2, right=14)),\n",
1762        " (Link(height=982, left=13, right=18),\n",
1763        "  Link(height=985, left=18, right=19),\n",
1764        "  Link(height=986, left=13, right=18),\n",
1765        "  Link(height=987, left=18, right=19)),\n",
1766        " (Link(height=993, left=5, right=16),\n",
1767        "  Link(height=994, left=2, right=5),\n",
1768        "  Link(height=995, left=5, right=16),\n",
1769        "  Link(height=996, left=2, right=5)),\n",
1770        " (Link(height=1058, left=9, right=24),\n",
1771        "  Link(height=1062, left=9, right=18),\n",
1772        "  Link(height=1063, left=9, right=24),\n",
1773        "  Link(height=1064, left=9, right=18)),\n",
1774        " (Link(height=1171, left=11, right=21),\n",
1775        "  Link(height=1172, left=11, right=14),\n",
1776        "  Link(height=1173, left=11, right=21),\n",
1777        "  Link(height=1174, left=11, right=14)),\n",
1778        " (Link(height=1294, left=0, right=11),\n",
1779        "  Link(height=1295, left=0, right=14),\n",
1780        "  Link(height=1296, left=0, right=11),\n",
1781        "  Link(height=1297, left=0, right=14)),\n",
1782        " (Link(height=1341, left=4, right=9),\n",
1783        "  Link(height=1343, left=4, right=10),\n",
1784        "  Link(height=1344, left=4, right=9),\n",
1785        "  Link(height=1345, left=4, right=10)),\n",
1786        " (Link(height=1342, left=12, right=18),\n",
1787        "  Link(height=1343, left=12, right=24),\n",
1788        "  Link(height=1344, left=12, right=18),\n",
1789        "  Link(height=1345, left=12, right=24)),\n",
1790        " (Link(height=1353, left=0, right=17),\n",
1791        "  Link(height=1354, left=0, right=23),\n",
1792        "  Link(height=1355, left=0, right=17),\n",
1793        "  Link(height=1356, left=0, right=23)),\n",
1794        " (Link(height=1367, left=4, right=16),\n",
1795        "  Link(height=1368, left=16, right=17),\n",
1796        "  Link(height=1369, left=4, right=16),\n",
1797        "  Link(height=1370, left=16, right=17)),\n",
1798        " (Link(height=1441, left=11, right=24),\n",
1799        "  Link(height=1442, left=18, right=24),\n",
1800        "  Link(height=1443, left=11, right=24),\n",
1801        "  Link(height=1444, left=18, right=24)),\n",
1802        " (Link(height=1451, left=6, right=20),\n",
1803        "  Link(height=1453, left=16, right=20),\n",
1804        "  Link(height=1454, left=6, right=20),\n",
1805        "  Link(height=1455, left=16, right=20)),\n",
1806        " (Link(height=1474, left=17, right=23),\n",
1807        "  Link(height=1475, left=3, right=17),\n",
1808        "  Link(height=1476, left=17, right=23),\n",
1809        "  Link(height=1477, left=3, right=17)),\n",
1810        " (Link(height=1550, left=8, right=23),\n",
1811        "  Link(height=1551, left=7, right=23),\n",
1812        "  Link(height=1552, left=8, right=23),\n",
1813        "  Link(height=1553, left=7, right=23)),\n",
1814        " (Link(height=1574, left=4, right=14),\n",
1815        "  Link(height=1575, left=14, right=23),\n",
1816        "  Link(height=1576, left=4, right=14),\n",
1817        "  Link(height=1577, left=14, right=23)),\n",
1818        " (Link(height=1580, left=0, right=1),\n",
1819        "  Link(height=1581, left=1, right=21),\n",
1820        "  Link(height=1582, left=0, right=1),\n",
1821        "  Link(height=1583, left=1, right=21)),\n",
1822        " (Link(height=1612, left=15, right=22),\n",
1823        "  Link(height=1617, left=7, right=15),\n",
1824        "  Link(height=1618, left=15, right=22),\n",
1825        "  Link(height=1619, left=7, right=15)),\n",
1826        " (Link(height=1644, left=12, right=18),\n",
1827        "  Link(height=1646, left=12, right=20),\n",
1828        "  Link(height=1647, left=12, right=18),\n",
1829        "  Link(height=1648, left=12, right=20)),\n",
1830        " (Link(height=1716, left=13, right=24),\n",
1831        "  Link(height=1719, left=14, right=24),\n",
1832        "  Link(height=1720, left=13, right=24),\n",
1833        "  Link(height=1721, left=14, right=24)),\n",
1834        " (Link(height=1735, left=3, right=24),\n",
1835        "  Link(height=1736, left=3, right=21),\n",
1836        "  Link(height=1737, left=3, right=24),\n",
1837        "  Link(height=1738, left=3, right=21)),\n",
1838        " (Link(height=1736, left=3, right=21),\n",
1839        "  Link(height=1737, left=3, right=24),\n",
1840        "  Link(height=1738, left=3, right=21),\n",
1841        "  Link(height=1739, left=3, right=24)),\n",
1842        " (Link(height=1776, left=0, right=21),\n",
1843        "  Link(height=1777, left=13, right=21),\n",
1844        "  Link(height=1778, left=0, right=21),\n",
1845        "  Link(height=1779, left=13, right=21)),\n",
1846        " (Link(height=1783, left=7, right=9),\n",
1847        "  Link(height=1784, left=7, right=12),\n",
1848        "  Link(height=1785, left=7, right=9),\n",
1849        "  Link(height=1786, left=7, right=12)),\n",
1850        " (Link(height=1929, left=10, right=24),\n",
1851        "  Link(height=1930, left=8, right=24),\n",
1852        "  Link(height=1931, left=10, right=24),\n",
1853        "  Link(height=1932, left=8, right=24)),\n",
1854        " (Link(height=1935, left=4, right=23),\n",
1855        "  Link(height=1936, left=3, right=4),\n",
1856        "  Link(height=1937, left=4, right=23),\n",
1857        "  Link(height=1938, left=3, right=4)),\n",
1858        " (Link(height=2043, left=4, right=7),\n",
1859        "  Link(height=2044, left=7, right=15),\n",
1860        "  Link(height=2045, left=4, right=7),\n",
1861        "  Link(height=2046, left=7, right=15)),\n",
1862        " (Link(height=2045, left=8, right=19),\n",
1863        "  Link(height=2051, left=8, right=15),\n",
1864        "  Link(height=2052, left=8, right=19),\n",
1865        "  Link(height=2053, left=8, right=15)),\n",
1866        " (Link(height=2172, left=10, right=15),\n",
1867        "  Link(height=2173, left=10, right=16),\n",
1868        "  Link(height=2174, left=10, right=15),\n",
1869        "  Link(height=2175, left=10, right=16)),\n",
1870        " (Link(height=2214, left=22, right=24),\n",
1871        "  Link(height=2215, left=7, right=22),\n",
1872        "  Link(height=2216, left=22, right=24),\n",
1873        "  Link(height=2217, left=7, right=22)),\n",
1874        " (Link(height=2231, left=5, right=6),\n",
1875        "  Link(height=2232, left=6, right=14),\n",
1876        "  Link(height=2233, left=5, right=6),\n",
1877        "  Link(height=2234, left=6, right=14))]"
1878       ]
1879      },
1880      "execution_count": 93,
1881      "metadata": {},
1882      "output_type": "execute_result"
1883     }
1884    ],
1885    "source": [
1886     "lnettp = simple_lnet\n",
1887     "for _ in range(50):\n",
1888     "    lnettp = add_pair(lnettp)\n",
1889     "for _ in range(50):\n",
1890     "    lnettp = add_triple_pair(lnettp)\n",
1891     "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1892     "tps = triple_pair_hg(height_groups)\n",
1893     "tps"
1894    ]
1895   },
1896   {
1897    "cell_type": "code",
1898    "execution_count": 94,
1899    "metadata": {},
1900    "outputs": [
1901     {
1902      "data": {
1903       "text/plain": [
1904        "True"
1905       ]
1906      },
1907      "execution_count": 94,
1908      "metadata": {},
1909      "output_type": "execute_result"
1910     }
1911    ],
1912    "source": [
1913     "lnettp == pack(lnettp)"
1914    ]
1915   },
1916   {
1917    "cell_type": "code",
1918    "execution_count": 95,
1919    "metadata": {
1920     "scrolled": true
1921    },
1922    "outputs": [
1923     {
1924      "data": {
1925       "text/plain": [
1926        "9931"
1927       ]
1928      },
1929      "execution_count": 95,
1930      "metadata": {},
1931      "output_type": "execute_result"
1932     }
1933    ],
1934    "source": [
1935     "lnettps = simplify(lnettp)\n",
1936     "len(lnettps)"
1937    ]
1938   },
1939   {
1940    "cell_type": "code",
1941    "execution_count": 96,
1942    "metadata": {},
1943    "outputs": [
1944     {
1945      "data": {
1946       "text/plain": [
1947        "(9835, 10135, 9931)"
1948       ]
1949      },
1950      "execution_count": 96,
1951      "metadata": {},
1952      "output_type": "execute_result"
1953     }
1954    ],
1955    "source": [
1956     "len(simple_lnet), len(lnettp), len(lnettps)"
1957    ]
1958   },
1959   {
1960    "cell_type": "code",
1961    "execution_count": 97,
1962    "metadata": {},
1963    "outputs": [
1964     {
1965      "data": {
1966       "text/plain": [
1967        "True"
1968       ]
1969      },
1970      "execution_count": 97,
1971      "metadata": {},
1972      "output_type": "execute_result"
1973     }
1974    ],
1975    "source": [
1976     "''.join(follow_many(string.ascii_lowercase, lnet)) == ''.join(follow_many(string.ascii_lowercase, simple_lnet))"
1977    ]
1978   },
1979   {
1980    "cell_type": "code",
1981    "execution_count": 98,
1982    "metadata": {},
1983    "outputs": [
1984     {
1985      "data": {
1986       "text/plain": [
1987        "True"
1988       ]
1989      },
1990      "execution_count": 98,
1991      "metadata": {},
1992      "output_type": "execute_result"
1993     }
1994    ],
1995    "source": [
1996     "''.join(follow_many(string.ascii_lowercase, lnettps)) == ''.join(follow_many(string.ascii_lowercase, lnettp))"
1997    ]
1998   },
1999   {
2000    "cell_type": "code",
2001    "execution_count": 99,
2002    "metadata": {},
2003    "outputs": [
2004     {
2005      "data": {
2006       "text/plain": [
2007        "2286"
2008       ]
2009      },
2010      "execution_count": 99,
2011      "metadata": {},
2012      "output_type": "execute_result"
2013     }
2014    ],
2015    "source": [
2016     "max(l.height for l in lnettp)"
2017    ]
2018   },
2019   {
2020    "cell_type": "code",
2021    "execution_count": 100,
2022    "metadata": {
2023     "collapsed": true
2024    },
2025    "outputs": [],
2026    "source": [
2027     "def simplify_with_checks(net0):\n",
2028     "    netp = eliminate_pairs(net0)\n",
2029     "    if follow_many(string.ascii_lowercase, net0) != follow_many(string.ascii_lowercase, netp):\n",
2030     "        print('pairs', eliminable_pairs(net0))\n",
2031     "        return net0\n",
2032     "    else:\n",
2033     "        print('pairs ok')\n",
2034     "    new_net = eliminate_a_triple_pair(netp)\n",
2035     "    if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
2036     "        hg = find_height_groups(netp)\n",
2037     "        print('triple', triple_pair_hg(hg))\n",
2038     "        return netp\n",
2039     "    else:\n",
2040     "        print('triple ok')\n",
2041     "    while new_net:\n",
2042     "#         print('sipl', len(net0), len(netp), len(new_net))\n",
2043     "        netp = eliminate_pairs(new_net)\n",
2044     "        if follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
2045     "            print('pairs', eliminable_pairs(new_net))\n",
2046     "            return new_net\n",
2047     "        else:\n",
2048     "            print('pairs ok')\n",
2049     "        new_net = eliminate_a_triple_pair(netp)\n",
2050     "        if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
2051     "            hg = find_height_groups(netp)\n",
2052     "            print('triple', triple_pair_hg(hg))\n",
2053     "            return netp\n",
2054     "        else:\n",
2055     "            print('triple ok')\n",
2056     "    print('** done')\n",
2057     "    return netp"
2058    ]
2059   },
2060   {
2061    "cell_type": "code",
2062    "execution_count": 101,
2063    "metadata": {
2064     "scrolled": true
2065    },
2066    "outputs": [
2067     {
2068      "name": "stdout",
2069      "output_type": "stream",
2070      "text": [
2071       "pairs ok\n",
2072       "triple ok\n",
2073       "pairs ok\n",
2074       "triple ok\n",
2075       "pairs ok\n",
2076       "triple ok\n",
2077       "pairs ok\n",
2078       "triple ok\n",
2079       "pairs ok\n",
2080       "triple ok\n",
2081       "pairs ok\n",
2082       "triple ok\n",
2083       "pairs ok\n",
2084       "triple ok\n",
2085       "pairs ok\n",
2086       "triple ok\n",
2087       "pairs ok\n",
2088       "triple ok\n",
2089       "pairs ok\n",
2090       "triple ok\n",
2091       "pairs ok\n",
2092       "triple ok\n",
2093       "pairs ok\n",
2094       "triple ok\n",
2095       "pairs ok\n",
2096       "triple ok\n",
2097       "pairs ok\n",
2098       "triple ok\n",
2099       "pairs ok\n",
2100       "triple ok\n",
2101       "pairs ok\n",
2102       "triple ok\n",
2103       "pairs ok\n",
2104       "triple ok\n",
2105       "pairs ok\n",
2106       "triple ok\n",
2107       "pairs ok\n",
2108       "triple ok\n",
2109       "pairs ok\n",
2110       "triple ok\n",
2111       "pairs ok\n",
2112       "triple ok\n",
2113       "pairs ok\n",
2114       "triple ok\n",
2115       "pairs ok\n",
2116       "triple ok\n",
2117       "pairs ok\n",
2118       "triple ok\n",
2119       "pairs ok\n",
2120       "triple ok\n",
2121       "pairs ok\n",
2122       "triple ok\n",
2123       "pairs ok\n",
2124       "triple ok\n",
2125       "pairs ok\n",
2126       "triple ok\n",
2127       "pairs ok\n",
2128       "triple ok\n",
2129       "pairs ok\n",
2130       "triple ok\n",
2131       "pairs ok\n",
2132       "triple ok\n",
2133       "pairs ok\n",
2134       "triple ok\n",
2135       "pairs ok\n",
2136       "triple ok\n",
2137       "pairs ok\n",
2138       "triple ok\n",
2139       "pairs ok\n",
2140       "triple ok\n",
2141       "pairs ok\n",
2142       "triple ok\n",
2143       "pairs ok\n",
2144       "triple ok\n",
2145       "pairs ok\n",
2146       "triple ok\n",
2147       "pairs ok\n",
2148       "triple ok\n",
2149       "pairs ok\n",
2150       "triple ok\n",
2151       "pairs ok\n",
2152       "triple ok\n",
2153       "pairs ok\n",
2154       "triple ok\n",
2155       "pairs ok\n",
2156       "triple ok\n",
2157       "pairs ok\n",
2158       "triple ok\n",
2159       "pairs ok\n",
2160       "triple ok\n",
2161       "pairs ok\n",
2162       "triple ok\n",
2163       "pairs ok\n",
2164       "triple ok\n",
2165       "pairs ok\n",
2166       "triple ok\n",
2167       "pairs ok\n",
2168       "triple ok\n",
2169       "** done\n"
2170      ]
2171     }
2172    ],
2173    "source": [
2174     "lnettps = simplify_with_checks(lnettp)"
2175    ]
2176   },
2177   {
2178    "cell_type": "code",
2179    "execution_count": 102,
2180    "metadata": {},
2181    "outputs": [
2182     {
2183      "data": {
2184       "text/plain": [
2185        "True"
2186       ]
2187      },
2188      "execution_count": 102,
2189      "metadata": {},
2190      "output_type": "execute_result"
2191     }
2192    ],
2193    "source": [
2194     "''.join(follow_many(string.ascii_lowercase, lnettps)) == ''.join(follow_many(string.ascii_lowercase, lnettp))"
2195    ]
2196   },
2197   {
2198    "cell_type": "code",
2199    "execution_count": 103,
2200    "metadata": {},
2201    "outputs": [
2202     {
2203      "data": {
2204       "text/plain": [
2205        "10135"
2206       ]
2207      },
2208      "execution_count": 103,
2209      "metadata": {},
2210      "output_type": "execute_result"
2211     }
2212    ],
2213    "source": [
2214     "len(lnettp)"
2215    ]
2216   },
2217   {
2218    "cell_type": "code",
2219    "execution_count": 113,
2220    "metadata": {},
2221    "outputs": [
2222     {
2223      "data": {
2224       "text/plain": [
2225        "83459"
2226       ]
2227      },
2228      "execution_count": 113,
2229      "metadata": {},
2230      "output_type": "execute_result"
2231     }
2232    ],
2233    "source": [
2234     "open('04-lines.txt', 'w').write(show_net(lnettp, randomise=True, pair_sep='\\n'))"
2235    ]
2236   },
2237   {
2238    "cell_type": "code",
2239    "execution_count": 114,
2240    "metadata": {},
2241    "outputs": [
2242     {
2243      "data": {
2244       "text/plain": [
2245        "139"
2246       ]
2247      },
2248      "execution_count": 114,
2249      "metadata": {},
2250      "output_type": "execute_result"
2251     }
2252    ],
2253    "source": [
2254     "open('04-small.txt', 'w').write(show_net(make_net(20), randomise=True, pair_sep='\\n'))"
2255    ]
2256   },
2257   {
2258    "cell_type": "code",
2259    "execution_count": null,
2260    "metadata": {
2261     "collapsed": true
2262    },
2263    "outputs": [],
2264    "source": []
2265   }
2266  ],
2267  "metadata": {
2268   "kernelspec": {
2269    "display_name": "Python 3",
2270    "language": "python",
2271    "name": "python3"
2272   },
2273   "language_info": {
2274    "codemirror_mode": {
2275     "name": "ipython",
2276     "version": 3
2277    },
2278    "file_extension": ".py",
2279    "mimetype": "text/x-python",
2280    "name": "python",
2281    "nbconvert_exporter": "python",
2282    "pygments_lexer": "ipython3",
2283    "version": "3.5.2+"
2284   }
2285  },
2286  "nbformat": 4,
2287  "nbformat_minor": 2
2288 }