04-08-amidakuji/amidakuji-creation.ipynb

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