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