04-08-amidakuji/amidakuji-solution-2.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\n",
  14     "import re"
  15    ]
  16   },
  17   {
  18    "cell_type": "code",
  19    "execution_count": 2,
  20    "metadata": {
  21     "collapsed": true
  22    },
  23    "outputs": [],
  24    "source": [
  25     "Link = collections.namedtuple('Link', 'height left right')"
  26    ]
  27   },
  28   {
  29    "cell_type": "code",
  30    "execution_count": 3,
  31    "metadata": {
  32     "collapsed": true
  33    },
  34    "outputs": [],
  35    "source": [
  36     "def extract_pairs(net_string):\n",
  37     "    return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
  38    ]
  39   },
  40   {
  41    "cell_type": "code",
  42    "execution_count": 4,
  43    "metadata": {
  44     "collapsed": true
  45    },
  46    "outputs": [],
  47    "source": [
  48     "def read_net_string(net_string):\n",
  49     "    return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
  50    ]
  51   },
  52   {
  53    "cell_type": "code",
  54    "execution_count": 5,
  55    "metadata": {
  56     "collapsed": true
  57    },
  58    "outputs": [],
  59    "source": [
  60     "def read_net(filename):\n",
  61     "    with open(filename) as f:\n",
  62     "        pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
  63     "        lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
  64     "        return [Link(h, l, r) \n",
  65     "                for h, (l, r) in enumerate(lrs)]"
  66    ]
  67   },
  68   {
  69    "cell_type": "code",
  70    "execution_count": 6,
  71    "metadata": {},
  72    "outputs": [
  73     {
  74      "data": {
  75       "text/plain": [
  76        "[Link(height=0, left=2, right=5),\n",
  77        " Link(height=1, left=1, right=4),\n",
  78        " Link(height=2, left=0, right=3),\n",
  79        " Link(height=3, left=0, right=3),\n",
  80        " Link(height=4, left=0, right=5),\n",
  81        " Link(height=5, left=3, right=5),\n",
  82        " Link(height=6, left=0, right=2),\n",
  83        " Link(height=7, left=3, right=4),\n",
  84        " Link(height=8, left=2, right=4),\n",
  85        " Link(height=9, left=1, right=2),\n",
  86        " Link(height=10, left=0, right=4),\n",
  87        " Link(height=11, left=1, right=2),\n",
  88        " Link(height=12, left=2, right=4),\n",
  89        " Link(height=13, left=0, right=4),\n",
  90        " Link(height=14, left=1, right=4)]"
  91       ]
  92      },
  93      "execution_count": 6,
  94      "metadata": {},
  95      "output_type": "execute_result"
  96     }
  97    ],
  98    "source": [
  99     "small_net = read_net('04-small.txt')\n",
 100     "small_net"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 7,
 106    "metadata": {},
 107    "outputs": [
 108     {
 109      "data": {
 110       "text/plain": [
 111        "10135"
 112       ]
 113      },
 114      "execution_count": 7,
 115      "metadata": {},
 116      "output_type": "execute_result"
 117     }
 118    ],
 119    "source": [
 120     "net = read_net('04-lines.txt')\n",
 121     "len(net)"
 122    ]
 123   },
 124   {
 125    "cell_type": "code",
 126    "execution_count": 8,
 127    "metadata": {
 128     "collapsed": true
 129    },
 130    "outputs": [],
 131    "source": [
 132     "def show_net(links, pair_sep=', '):\n",
 133     "    return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 9,
 139    "metadata": {
 140     "collapsed": true
 141    },
 142    "outputs": [],
 143    "source": [
 144     "def link_ends(link):\n",
 145     "    return set((link.left, link.right))"
 146    ]
 147   },
 148   {
 149    "cell_type": "code",
 150    "execution_count": 10,
 151    "metadata": {
 152     "collapsed": true
 153    },
 154    "outputs": [],
 155    "source": [
 156     "def follow(initial_line, links):\n",
 157     "    line = initial_line\n",
 158     "    heights = sorted(set(l.height for l in links))\n",
 159     "    for h in heights:\n",
 160     "        for l in [l for l in links if l.height == h]:\n",
 161     "            if line in link_ends(l):\n",
 162     "                line = [e for e in link_ends(l) if e != line][0]\n",
 163     "#                 print(l, line)\n",
 164     "    return line"
 165    ]
 166   },
 167   {
 168    "cell_type": "code",
 169    "execution_count": 11,
 170    "metadata": {
 171     "collapsed": true
 172    },
 173    "outputs": [],
 174    "source": [
 175     "def pack(net):\n",
 176     "    packed_links = []\n",
 177     "    line_heights = collections.defaultdict(lambda: -1)\n",
 178     "    for link in sorted(net):\n",
 179     "        link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
 180     "        line_heights[link.left] = link_height\n",
 181     "        line_heights[link.right] = link_height\n",
 182     "        packed_links += [Link(link_height, link.left, link.right)]\n",
 183     "    return sorted(packed_links)"
 184    ]
 185   },
 186   {
 187    "cell_type": "code",
 188    "execution_count": 12,
 189    "metadata": {},
 190    "outputs": [
 191     {
 192      "data": {
 193       "text/plain": [
 194        "14"
 195       ]
 196      },
 197      "execution_count": 12,
 198      "metadata": {},
 199      "output_type": "execute_result"
 200     }
 201    ],
 202    "source": [
 203     "max(l.height for l in small_net)"
 204    ]
 205   },
 206   {
 207    "cell_type": "code",
 208    "execution_count": 13,
 209    "metadata": {},
 210    "outputs": [
 211     {
 212      "data": {
 213       "text/plain": [
 214        "10"
 215       ]
 216      },
 217      "execution_count": 13,
 218      "metadata": {},
 219      "output_type": "execute_result"
 220     }
 221    ],
 222    "source": [
 223     "max(l.height for l in pack(small_net))"
 224    ]
 225   },
 226   {
 227    "cell_type": "code",
 228    "execution_count": 14,
 229    "metadata": {},
 230    "outputs": [
 231     {
 232      "data": {
 233       "text/plain": [
 234        "10134"
 235       ]
 236      },
 237      "execution_count": 14,
 238      "metadata": {},
 239      "output_type": "execute_result"
 240     }
 241    ],
 242    "source": [
 243     "max(l.height for l in net)"
 244    ]
 245   },
 246   {
 247    "cell_type": "code",
 248    "execution_count": 15,
 249    "metadata": {},
 250    "outputs": [
 251     {
 252      "data": {
 253       "text/plain": [
 254        "2286"
 255       ]
 256      },
 257      "execution_count": 15,
 258      "metadata": {},
 259      "output_type": "execute_result"
 260     }
 261    ],
 262    "source": [
 263     "max(l.height for l in pack(net))"
 264    ]
 265   },
 266   {
 267    "cell_type": "code",
 268    "execution_count": 16,
 269    "metadata": {
 270     "collapsed": true
 271    },
 272    "outputs": [],
 273    "source": [
 274     "def height_groups(net):\n",
 275     "    return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
 276    ]
 277   },
 278   {
 279    "cell_type": "code",
 280    "execution_count": 17,
 281    "metadata": {
 282     "collapsed": true
 283    },
 284    "outputs": [],
 285    "source": [
 286     "def follow_many(in_sequence, net):\n",
 287     "    hgs = height_groups(net)\n",
 288     "    seq = list(in_sequence)\n",
 289     "    for h in hgs:\n",
 290     "        for link in hgs[h]:\n",
 291     "            seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
 292     "    return seq"
 293    ]
 294   },
 295   {
 296    "cell_type": "code",
 297    "execution_count": 18,
 298    "metadata": {},
 299    "outputs": [
 300     {
 301      "data": {
 302       "text/plain": [
 303        "'acfbedghij'"
 304       ]
 305      },
 306      "execution_count": 18,
 307      "metadata": {},
 308      "output_type": "execute_result"
 309     }
 310    ],
 311    "source": [
 312     "''.join(follow_many('abcdefghij', small_net))"
 313    ]
 314   },
 315   {
 316    "cell_type": "code",
 317    "execution_count": 19,
 318    "metadata": {},
 319    "outputs": [
 320     {
 321      "name": "stdout",
 322      "output_type": "stream",
 323      "text": [
 324       "10000 loops, best of 3: 38.1 µs per loop\n"
 325      ]
 326     }
 327    ],
 328    "source": [
 329     "%%timeit\n",
 330     "follow_many('abcdefghij', small_net)"
 331    ]
 332   },
 333   {
 334    "cell_type": "code",
 335    "execution_count": 20,
 336    "metadata": {},
 337    "outputs": [
 338     {
 339      "data": {
 340       "text/plain": [
 341        "'doqzmbishkwunvltpcexyjgfra'"
 342       ]
 343      },
 344      "execution_count": 20,
 345      "metadata": {},
 346      "output_type": "execute_result"
 347     }
 348    ],
 349    "source": [
 350     "''.join(follow_many(string.ascii_lowercase, net))"
 351    ]
 352   },
 353   {
 354    "cell_type": "code",
 355    "execution_count": 21,
 356    "metadata": {},
 357    "outputs": [
 358     {
 359      "name": "stdout",
 360      "output_type": "stream",
 361      "text": [
 362       "100 loops, best of 3: 19 ms per loop\n"
 363      ]
 364     }
 365    ],
 366    "source": [
 367     "%%timeit\n",
 368     "follow_many(string.ascii_lowercase, net)"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 22,
 374    "metadata": {
 375     "collapsed": true
 376    },
 377    "outputs": [],
 378    "source": [
 379     "pnet = pack(net)"
 380    ]
 381   },
 382   {
 383    "cell_type": "code",
 384    "execution_count": 23,
 385    "metadata": {
 386     "collapsed": true
 387    },
 388    "outputs": [],
 389    "source": [
 390     "def eliminable_pairs(net):\n",
 391     "    hgs = height_groups(net)\n",
 392     "    eps = []\n",
 393     "    for h in range(1, max(hgs.keys())):\n",
 394     "        for l in hgs[h]:\n",
 395     "            o = Link(l.height - 1, l.left, l.right)\n",
 396     "            if o in hgs[h-1]:\n",
 397     "                eps += [(l, o)]\n",
 398     "    return eps"
 399    ]
 400   },
 401   {
 402    "cell_type": "code",
 403    "execution_count": 24,
 404    "metadata": {
 405     "scrolled": true
 406    },
 407    "outputs": [
 408     {
 409      "data": {
 410       "text/plain": [
 411        "[(Link(height=115, left=2, right=23), Link(height=114, left=2, right=23)),\n",
 412        " (Link(height=149, left=15, right=23), Link(height=148, left=15, right=23)),\n",
 413        " (Link(height=201, left=0, right=7), Link(height=200, left=0, right=7)),\n",
 414        " (Link(height=207, left=22, right=23), Link(height=206, left=22, right=23)),\n",
 415        " (Link(height=210, left=17, right=23), Link(height=209, left=17, right=23)),\n",
 416        " (Link(height=247, left=16, right=20), Link(height=246, left=16, right=20)),\n",
 417        " (Link(height=418, left=19, right=24), Link(height=417, left=19, right=24)),\n",
 418        " (Link(height=424, left=9, right=21), Link(height=423, left=9, right=21)),\n",
 419        " (Link(height=453, left=3, right=16), Link(height=452, left=3, right=16)),\n",
 420        " (Link(height=456, left=2, right=22), Link(height=455, left=2, right=22)),\n",
 421        " (Link(height=465, left=18, right=20), Link(height=464, left=18, right=20)),\n",
 422        " (Link(height=491, left=14, right=18), Link(height=490, left=14, right=18)),\n",
 423        " (Link(height=552, left=16, right=17), Link(height=551, left=16, right=17)),\n",
 424        " (Link(height=772, left=0, right=7), Link(height=771, left=0, right=7)),\n",
 425        " (Link(height=848, left=1, right=2), Link(height=847, left=1, right=2)),\n",
 426        " (Link(height=895, left=6, right=21), Link(height=894, left=6, right=21)),\n",
 427        " (Link(height=930, left=11, right=13), Link(height=929, left=11, right=13)),\n",
 428        " (Link(height=987, left=8, right=17), Link(height=986, left=8, right=17)),\n",
 429        " (Link(height=988, left=8, right=17), Link(height=987, left=8, right=17)),\n",
 430        " (Link(height=1030, left=9, right=24), Link(height=1029, left=9, right=24)),\n",
 431        " (Link(height=1134, left=4, right=23), Link(height=1133, left=4, right=23)),\n",
 432        " (Link(height=1163, left=14, right=15), Link(height=1162, left=14, right=15)),\n",
 433        " (Link(height=1164, left=14, right=15), Link(height=1163, left=14, right=15)),\n",
 434        " (Link(height=1170, left=2, right=21), Link(height=1169, left=2, right=21)),\n",
 435        " (Link(height=1232, left=6, right=22), Link(height=1231, left=6, right=22)),\n",
 436        " (Link(height=1254, left=13, right=15), Link(height=1253, left=13, right=15)),\n",
 437        " (Link(height=1255, left=1, right=24), Link(height=1254, left=1, right=24)),\n",
 438        " (Link(height=1324, left=3, right=22), Link(height=1323, left=3, right=22)),\n",
 439        " (Link(height=1370, left=15, right=19), Link(height=1369, left=15, right=19)),\n",
 440        " (Link(height=1441, left=0, right=14), Link(height=1440, left=0, right=14)),\n",
 441        " (Link(height=1441, left=11, right=24), Link(height=1440, left=11, right=24)),\n",
 442        " (Link(height=1547, left=11, right=13), Link(height=1546, left=11, right=13)),\n",
 443        " (Link(height=1578, left=14, right=23), Link(height=1577, left=14, right=23)),\n",
 444        " (Link(height=1616, left=7, right=14), Link(height=1615, left=7, right=14)),\n",
 445        " (Link(height=1671, left=8, right=20), Link(height=1670, left=8, right=20)),\n",
 446        " (Link(height=1684, left=14, right=18), Link(height=1683, left=14, right=18)),\n",
 447        " (Link(height=1717, left=0, right=17), Link(height=1716, left=0, right=17)),\n",
 448        " (Link(height=1727, left=7, right=8), Link(height=1726, left=7, right=8)),\n",
 449        " (Link(height=1866, left=8, right=16), Link(height=1865, left=8, right=16)),\n",
 450        " (Link(height=1911, left=1, right=12), Link(height=1910, left=1, right=12)),\n",
 451        " (Link(height=1966, left=20, right=23), Link(height=1965, left=20, right=23)),\n",
 452        " (Link(height=1974, left=5, right=23), Link(height=1973, left=5, right=23)),\n",
 453        " (Link(height=1994, left=18, right=19), Link(height=1993, left=18, right=19)),\n",
 454        " (Link(height=2005, left=2, right=19), Link(height=2004, left=2, right=19)),\n",
 455        " (Link(height=2031, left=12, right=17), Link(height=2030, left=12, right=17)),\n",
 456        " (Link(height=2108, left=7, right=12), Link(height=2107, left=7, right=12)),\n",
 457        " (Link(height=2137, left=7, right=16), Link(height=2136, left=7, right=16)),\n",
 458        " (Link(height=2138, left=7, right=16), Link(height=2137, left=7, right=16)),\n",
 459        " (Link(height=2229, left=10, right=11), Link(height=2228, left=10, right=11)),\n",
 460        " (Link(height=2239, left=16, right=24), Link(height=2238, left=16, right=24)),\n",
 461        " (Link(height=2240, left=16, right=24), Link(height=2239, left=16, right=24)),\n",
 462        " (Link(height=2246, left=4, right=13), Link(height=2245, left=4, right=13)),\n",
 463        " (Link(height=2247, left=4, right=13), Link(height=2246, left=4, right=13)),\n",
 464        " (Link(height=2276, left=19, right=24), Link(height=2275, left=19, right=24)),\n",
 465        " (Link(height=2277, left=4, right=18), Link(height=2276, left=4, right=18))]"
 466       ]
 467      },
 468      "execution_count": 24,
 469      "metadata": {},
 470      "output_type": "execute_result"
 471     }
 472    ],
 473    "source": [
 474     "eliminable_pairs(pnet)"
 475    ]
 476   },
 477   {
 478    "cell_type": "code",
 479    "execution_count": 25,
 480    "metadata": {},
 481    "outputs": [
 482     {
 483      "name": "stdout",
 484      "output_type": "stream",
 485      "text": [
 486       "10 loops, best of 3: 23.5 ms per loop\n"
 487      ]
 488     }
 489    ],
 490    "source": [
 491     "%%timeit\n",
 492     "eliminable_pairs(pnet)"
 493    ]
 494   },
 495   {
 496    "cell_type": "code",
 497    "execution_count": 26,
 498    "metadata": {
 499     "collapsed": true
 500    },
 501    "outputs": [],
 502    "source": [
 503     "def eliminable_pair(hgs):\n",
 504     "    for h in range(1, max(hgs.keys())):\n",
 505     "        for l in hgs[h]:\n",
 506     "            o = Link(l.height - 1, l.left, l.right)\n",
 507     "            if o in hgs[h-1]:\n",
 508     "                return l, o\n",
 509     "    return None"
 510    ]
 511   },
 512   {
 513    "cell_type": "code",
 514    "execution_count": 27,
 515    "metadata": {
 516     "collapsed": true
 517    },
 518    "outputs": [],
 519    "source": [
 520     "def eliminate_pairs(net):\n",
 521     "    hgs = height_groups(pack(net))\n",
 522     "    eliminable_links = eliminable_pair(hgs)\n",
 523     "    while eliminable_links:\n",
 524     "        net = pack(l for l in net if l not in eliminable_links)\n",
 525     "        hgs = height_groups(pack(net))\n",
 526     "        eliminable_links = eliminable_pair(hgs)\n",
 527     "    return net"
 528    ]
 529   },
 530   {
 531    "cell_type": "code",
 532    "execution_count": 28,
 533    "metadata": {
 534     "collapsed": true
 535    },
 536    "outputs": [],
 537    "source": [
 538     "enet = eliminate_pairs(pnet)"
 539    ]
 540   },
 541   {
 542    "cell_type": "code",
 543    "execution_count": 29,
 544    "metadata": {
 545     "collapsed": true
 546    },
 547    "outputs": [],
 548    "source": [
 549     "assert follow_many(string.ascii_lowercase,  net) == follow_many(string.ascii_lowercase, enet)\n",
 550     "assert follow_many(string.ascii_lowercase, pnet) == follow_many(string.ascii_lowercase, enet)"
 551    ]
 552   },
 553   {
 554    "cell_type": "code",
 555    "execution_count": 30,
 556    "metadata": {},
 557    "outputs": [
 558     {
 559      "name": "stdout",
 560      "output_type": "stream",
 561      "text": [
 562       "1 loop, best of 3: 2.35 s per loop\n"
 563      ]
 564     }
 565    ],
 566    "source": [
 567     "%%timeit\n",
 568     "eliminate_pairs(pnet)"
 569    ]
 570   },
 571   {
 572    "cell_type": "code",
 573    "execution_count": 31,
 574    "metadata": {
 575     "collapsed": true
 576    },
 577    "outputs": [],
 578    "source": [
 579     "def triple_pair(height_groups, debug=False):\n",
 580     "    ts = []\n",
 581     "    for h in range(3, max(height_groups.keys())):\n",
 582     "        for d in height_groups[h]:\n",
 583     "            if debug: print('d:', d)\n",
 584     "            ch = h - 1\n",
 585     "            cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
 586     "            if debug: print('cs:', cs)\n",
 587     "            while ch > 2 and not cs:\n",
 588     "                ch -= 1\n",
 589     "                cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
 590     "                if debug: print('cs:', cs)\n",
 591     "            if len(cs) == 1:\n",
 592     "                c = cs[0]\n",
 593     "                lines = set((d.left, d.right, c.left, c.right))\n",
 594     "                if debug: print('c:', '; lines:', lines)\n",
 595     "                bs = [l for l in height_groups[ch-1] if link_ends(l) & lines]\n",
 596     "                b = Link(ch - 1, d.left, d.right)\n",
 597     "                if debug: print('b:', b, '; bs:', bs)\n",
 598     "                if len(bs) == 1 and b in bs:\n",
 599     "                    ah = b.height - 1\n",
 600     "                    als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
 601     "                    if debug: print('ah:', ah, '; als:', als)\n",
 602     "                    while ah > 0 and not als:\n",
 603     "                        ah -= 1\n",
 604     "                        als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
 605     "                        if debug: print('ah:', ah, '; als:', als)\n",
 606     "                    a = Link(ah, c.left, c.right)\n",
 607     "                    if debug: print('a:', a)\n",
 608     "                    if a in als:\n",
 609     "                        if debug: print('adding:', a, b, c, d)\n",
 610     "                        ts += [(a, b, c, d)]\n",
 611     "    return ts"
 612    ]
 613   },
 614   {
 615    "cell_type": "code",
 616    "execution_count": 32,
 617    "metadata": {
 618     "collapsed": true
 619    },
 620    "outputs": [],
 621    "source": [
 622     "def eliminate_a_triple_pair(net, debug=False):\n",
 623     "    hgs = height_groups(net)\n",
 624     "\n",
 625     "    tps = triple_pair(hgs)\n",
 626     "    if debug: print('eatp', tps)\n",
 627     "    if tps:\n",
 628     "        a, b, c, d = tps[0]\n",
 629     "        x = Link(b.height - 0.5, b.left, b.right)\n",
 630     "        y = Link(b.height, a.left, a.right)\n",
 631     "        if debug: print('removing', a, b, c, d, '; adding', x, y)\n",
 632     "        return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
 633     "    return None"
 634    ]
 635   },
 636   {
 637    "cell_type": "code",
 638    "execution_count": 33,
 639    "metadata": {},
 640    "outputs": [
 641     {
 642      "data": {
 643       "text/plain": [
 644        "[(Link(height=8, left=1, right=5),\n",
 645        "  Link(height=9, left=1, right=21),\n",
 646        "  Link(height=10, left=1, right=5),\n",
 647        "  Link(height=11, left=1, right=21)),\n",
 648        " (Link(height=40, left=16, right=23),\n",
 649        "  Link(height=41, left=16, right=19),\n",
 650        "  Link(height=42, left=16, right=23),\n",
 651        "  Link(height=43, left=16, right=19)),\n",
 652        " (Link(height=62, left=0, right=10),\n",
 653        "  Link(height=63, left=10, right=13),\n",
 654        "  Link(height=64, left=0, right=10),\n",
 655        "  Link(height=65, left=10, right=13)),\n",
 656        " (Link(height=137, left=23, right=24),\n",
 657        "  Link(height=139, left=0, right=24),\n",
 658        "  Link(height=140, left=23, right=24),\n",
 659        "  Link(height=141, left=0, right=24)),\n",
 660        " (Link(height=138, left=10, right=21),\n",
 661        "  Link(height=139, left=2, right=10),\n",
 662        "  Link(height=140, left=10, right=21),\n",
 663        "  Link(height=141, left=2, right=10)),\n",
 664        " (Link(height=139, left=2, right=10),\n",
 665        "  Link(height=140, left=10, right=21),\n",
 666        "  Link(height=141, left=2, right=10),\n",
 667        "  Link(height=142, left=10, right=21)),\n",
 668        " (Link(height=156, left=6, right=11),\n",
 669        "  Link(height=157, left=3, right=6),\n",
 670        "  Link(height=158, left=6, right=11),\n",
 671        "  Link(height=159, left=3, right=6)),\n",
 672        " (Link(height=184, left=2, right=21),\n",
 673        "  Link(height=185, left=5, right=21),\n",
 674        "  Link(height=186, left=2, right=21),\n",
 675        "  Link(height=187, left=5, right=21)),\n",
 676        " (Link(height=272, left=7, right=13),\n",
 677        "  Link(height=273, left=7, right=11),\n",
 678        "  Link(height=274, left=7, right=13),\n",
 679        "  Link(height=275, left=7, right=11)),\n",
 680        " (Link(height=290, left=14, right=15),\n",
 681        "  Link(height=291, left=5, right=15),\n",
 682        "  Link(height=292, left=14, right=15),\n",
 683        "  Link(height=293, left=5, right=15)),\n",
 684        " (Link(height=387, left=1, right=8),\n",
 685        "  Link(height=389, left=8, right=15),\n",
 686        "  Link(height=390, left=1, right=8),\n",
 687        "  Link(height=391, left=8, right=15)),\n",
 688        " (Link(height=420, left=14, right=22),\n",
 689        "  Link(height=422, left=14, right=18),\n",
 690        "  Link(height=423, left=14, right=22),\n",
 691        "  Link(height=424, left=14, right=18)),\n",
 692        " (Link(height=432, left=5, right=19),\n",
 693        "  Link(height=433, left=1, right=19),\n",
 694        "  Link(height=434, left=5, right=19),\n",
 695        "  Link(height=435, left=1, right=19)),\n",
 696        " (Link(height=454, left=0, right=15),\n",
 697        "  Link(height=455, left=14, right=15),\n",
 698        "  Link(height=456, left=0, right=15),\n",
 699        "  Link(height=457, left=14, right=15)),\n",
 700        " (Link(height=546, left=13, right=21),\n",
 701        "  Link(height=547, left=6, right=21),\n",
 702        "  Link(height=548, left=13, right=21),\n",
 703        "  Link(height=549, left=6, right=21)),\n",
 704        " (Link(height=620, left=17, right=23),\n",
 705        "  Link(height=621, left=1, right=23),\n",
 706        "  Link(height=622, left=17, right=23),\n",
 707        "  Link(height=623, left=1, right=23)),\n",
 708        " (Link(height=699, left=8, right=15),\n",
 709        "  Link(height=700, left=3, right=15),\n",
 710        "  Link(height=701, left=8, right=15),\n",
 711        "  Link(height=702, left=3, right=15)),\n",
 712        " (Link(height=789, left=7, right=24),\n",
 713        "  Link(height=790, left=8, right=24),\n",
 714        "  Link(height=791, left=7, right=24),\n",
 715        "  Link(height=792, left=8, right=24)),\n",
 716        " (Link(height=795, left=8, right=13),\n",
 717        "  Link(height=796, left=4, right=8),\n",
 718        "  Link(height=797, left=8, right=13),\n",
 719        "  Link(height=798, left=4, right=8)),\n",
 720        " (Link(height=809, left=16, right=17),\n",
 721        "  Link(height=810, left=3, right=16),\n",
 722        "  Link(height=811, left=16, right=17),\n",
 723        "  Link(height=812, left=3, right=16)),\n",
 724        " (Link(height=900, left=2, right=15),\n",
 725        "  Link(height=901, left=13, right=15),\n",
 726        "  Link(height=902, left=2, right=15),\n",
 727        "  Link(height=903, left=13, right=15)),\n",
 728        " (Link(height=921, left=2, right=15),\n",
 729        "  Link(height=922, left=15, right=16),\n",
 730        "  Link(height=923, left=2, right=15),\n",
 731        "  Link(height=924, left=15, right=16)),\n",
 732        " (Link(height=961, left=2, right=15),\n",
 733        "  Link(height=962, left=2, right=14),\n",
 734        "  Link(height=963, left=2, right=15),\n",
 735        "  Link(height=964, left=2, right=14)),\n",
 736        " (Link(height=976, left=13, right=18),\n",
 737        "  Link(height=979, left=18, right=19),\n",
 738        "  Link(height=980, left=13, right=18),\n",
 739        "  Link(height=981, left=18, right=19)),\n",
 740        " (Link(height=985, left=5, right=16),\n",
 741        "  Link(height=986, left=2, right=5),\n",
 742        "  Link(height=987, left=5, right=16),\n",
 743        "  Link(height=988, left=2, right=5)),\n",
 744        " (Link(height=1050, left=9, right=24),\n",
 745        "  Link(height=1054, left=9, right=18),\n",
 746        "  Link(height=1055, left=9, right=24),\n",
 747        "  Link(height=1056, left=9, right=18)),\n",
 748        " (Link(height=1159, left=11, right=21),\n",
 749        "  Link(height=1160, left=11, right=14),\n",
 750        "  Link(height=1161, left=11, right=21),\n",
 751        "  Link(height=1162, left=11, right=14)),\n",
 752        " (Link(height=1284, left=0, right=11),\n",
 753        "  Link(height=1285, left=0, right=14),\n",
 754        "  Link(height=1286, left=0, right=11),\n",
 755        "  Link(height=1287, left=0, right=14)),\n",
 756        " (Link(height=1331, left=4, right=9),\n",
 757        "  Link(height=1333, left=4, right=10),\n",
 758        "  Link(height=1334, left=4, right=9),\n",
 759        "  Link(height=1335, left=4, right=10)),\n",
 760        " (Link(height=1332, left=12, right=18),\n",
 761        "  Link(height=1333, left=12, right=24),\n",
 762        "  Link(height=1334, left=12, right=18),\n",
 763        "  Link(height=1335, left=12, right=24)),\n",
 764        " (Link(height=1343, left=0, right=17),\n",
 765        "  Link(height=1344, left=0, right=23),\n",
 766        "  Link(height=1345, left=0, right=17),\n",
 767        "  Link(height=1346, left=0, right=23)),\n",
 768        " (Link(height=1357, left=4, right=16),\n",
 769        "  Link(height=1358, left=16, right=17),\n",
 770        "  Link(height=1359, left=4, right=16),\n",
 771        "  Link(height=1360, left=16, right=17)),\n",
 772        " (Link(height=1441, left=6, right=20),\n",
 773        "  Link(height=1443, left=16, right=20),\n",
 774        "  Link(height=1444, left=6, right=20),\n",
 775        "  Link(height=1445, left=16, right=20)),\n",
 776        " (Link(height=1464, left=17, right=23),\n",
 777        "  Link(height=1465, left=3, right=17),\n",
 778        "  Link(height=1466, left=17, right=23),\n",
 779        "  Link(height=1467, left=3, right=17)),\n",
 780        " (Link(height=1540, left=8, right=23),\n",
 781        "  Link(height=1541, left=7, right=23),\n",
 782        "  Link(height=1542, left=8, right=23),\n",
 783        "  Link(height=1543, left=7, right=23)),\n",
 784        " (Link(height=1570, left=0, right=1),\n",
 785        "  Link(height=1571, left=1, right=21),\n",
 786        "  Link(height=1572, left=0, right=1),\n",
 787        "  Link(height=1573, left=1, right=21)),\n",
 788        " (Link(height=1600, left=15, right=22),\n",
 789        "  Link(height=1603, left=7, right=15),\n",
 790        "  Link(height=1604, left=15, right=22),\n",
 791        "  Link(height=1605, left=7, right=15)),\n",
 792        " (Link(height=1632, left=12, right=18),\n",
 793        "  Link(height=1634, left=12, right=20),\n",
 794        "  Link(height=1635, left=12, right=18),\n",
 795        "  Link(height=1636, left=12, right=20)),\n",
 796        " (Link(height=1702, left=13, right=24),\n",
 797        "  Link(height=1705, left=14, right=24),\n",
 798        "  Link(height=1706, left=13, right=24),\n",
 799        "  Link(height=1707, left=14, right=24)),\n",
 800        " (Link(height=1721, left=3, right=24),\n",
 801        "  Link(height=1722, left=3, right=21),\n",
 802        "  Link(height=1723, left=3, right=24),\n",
 803        "  Link(height=1724, left=3, right=21)),\n",
 804        " (Link(height=1722, left=3, right=21),\n",
 805        "  Link(height=1723, left=3, right=24),\n",
 806        "  Link(height=1724, left=3, right=21),\n",
 807        "  Link(height=1725, left=3, right=24)),\n",
 808        " (Link(height=1762, left=0, right=21),\n",
 809        "  Link(height=1763, left=13, right=21),\n",
 810        "  Link(height=1764, left=0, right=21),\n",
 811        "  Link(height=1765, left=13, right=21)),\n",
 812        " (Link(height=1769, left=7, right=9),\n",
 813        "  Link(height=1770, left=7, right=12),\n",
 814        "  Link(height=1771, left=7, right=9),\n",
 815        "  Link(height=1772, left=7, right=12)),\n",
 816        " (Link(height=1914, left=10, right=24),\n",
 817        "  Link(height=1915, left=8, right=24),\n",
 818        "  Link(height=1916, left=10, right=24),\n",
 819        "  Link(height=1917, left=8, right=24)),\n",
 820        " (Link(height=1920, left=4, right=23),\n",
 821        "  Link(height=1921, left=3, right=4),\n",
 822        "  Link(height=1922, left=4, right=23),\n",
 823        "  Link(height=1923, left=3, right=4)),\n",
 824        " (Link(height=2023, left=4, right=7),\n",
 825        "  Link(height=2024, left=7, right=15),\n",
 826        "  Link(height=2025, left=4, right=7),\n",
 827        "  Link(height=2026, left=7, right=15)),\n",
 828        " (Link(height=2025, left=8, right=19),\n",
 829        "  Link(height=2031, left=8, right=15),\n",
 830        "  Link(height=2032, left=8, right=19),\n",
 831        "  Link(height=2033, left=8, right=15)),\n",
 832        " (Link(height=2152, left=10, right=15),\n",
 833        "  Link(height=2153, left=10, right=16),\n",
 834        "  Link(height=2154, left=10, right=15),\n",
 835        "  Link(height=2155, left=10, right=16)),\n",
 836        " (Link(height=2194, left=22, right=24),\n",
 837        "  Link(height=2195, left=7, right=22),\n",
 838        "  Link(height=2196, left=22, right=24),\n",
 839        "  Link(height=2197, left=7, right=22)),\n",
 840        " (Link(height=2211, left=5, right=6),\n",
 841        "  Link(height=2212, left=6, right=14),\n",
 842        "  Link(height=2213, left=5, right=6),\n",
 843        "  Link(height=2214, left=6, right=14))]"
 844       ]
 845      },
 846      "execution_count": 33,
 847      "metadata": {},
 848      "output_type": "execute_result"
 849     }
 850    ],
 851    "source": [
 852     "hgs = height_groups(enet)\n",
 853     "triple_pair(hgs)"
 854    ]
 855   },
 856   {
 857    "cell_type": "code",
 858    "execution_count": 34,
 859    "metadata": {
 860     "collapsed": true
 861    },
 862    "outputs": [],
 863    "source": [
 864     "etnet = eliminate_a_triple_pair(enet)"
 865    ]
 866   },
 867   {
 868    "cell_type": "code",
 869    "execution_count": 35,
 870    "metadata": {
 871     "collapsed": true
 872    },
 873    "outputs": [],
 874    "source": [
 875     "assert follow_many(string.ascii_lowercase, etnet) == follow_many(string.ascii_lowercase, enet)"
 876    ]
 877   },
 878   {
 879    "cell_type": "code",
 880    "execution_count": 36,
 881    "metadata": {
 882     "collapsed": true
 883    },
 884    "outputs": [],
 885    "source": [
 886     "def eliminate_triple_pairs(net):\n",
 887     "    print(len(net))\n",
 888     "    new_net = eliminate_a_triple_pair(net)\n",
 889     "    while new_net:\n",
 890     "        print(len(net))\n",
 891     "        net = new_net\n",
 892     "        new_net = eliminate_a_triple_pair(net)\n",
 893     "    return net"
 894    ]
 895   },
 896   {
 897    "cell_type": "code",
 898    "execution_count": 37,
 899    "metadata": {
 900     "scrolled": true
 901    },
 902    "outputs": [
 903     {
 904      "name": "stdout",
 905      "output_type": "stream",
 906      "text": [
 907       "10033\n",
 908       "10033\n",
 909       "10031\n",
 910       "10029\n",
 911       "10027\n",
 912       "10025\n",
 913       "10023\n",
 914       "10021\n",
 915       "10019\n",
 916       "10017\n",
 917       "10015\n",
 918       "10013\n",
 919       "10011\n",
 920       "10009\n",
 921       "10007\n",
 922       "10005\n",
 923       "10003\n",
 924       "10001\n",
 925       "9999\n",
 926       "9997\n",
 927       "9995\n",
 928       "9993\n",
 929       "9991\n",
 930       "9989\n",
 931       "9987\n",
 932       "9985\n",
 933       "9983\n",
 934       "9981\n",
 935       "9979\n",
 936       "9977\n",
 937       "9975\n",
 938       "9973\n",
 939       "9971\n",
 940       "9969\n",
 941       "9967\n",
 942       "9965\n",
 943       "9963\n",
 944       "9961\n",
 945       "9959\n",
 946       "9957\n",
 947       "9955\n",
 948       "9953\n",
 949       "9951\n",
 950       "9949\n",
 951       "9947\n",
 952       "9945\n",
 953       "9943\n",
 954       "9941\n",
 955       "9939\n"
 956      ]
 957     }
 958    ],
 959    "source": [
 960     "setnet = eliminate_triple_pairs(enet)"
 961    ]
 962   },
 963   {
 964    "cell_type": "code",
 965    "execution_count": 38,
 966    "metadata": {},
 967    "outputs": [
 968     {
 969      "data": {
 970       "text/plain": [
 971        "9937"
 972       ]
 973      },
 974      "execution_count": 38,
 975      "metadata": {},
 976      "output_type": "execute_result"
 977     }
 978    ],
 979    "source": [
 980     "len(setnet)"
 981    ]
 982   },
 983   {
 984    "cell_type": "code",
 985    "execution_count": 39,
 986    "metadata": {
 987     "collapsed": true
 988    },
 989    "outputs": [],
 990    "source": [
 991     "assert follow_many(string.ascii_lowercase, etnet) == follow_many(string.ascii_lowercase, enet)"
 992    ]
 993   },
 994   {
 995    "cell_type": "code",
 996    "execution_count": 40,
 997    "metadata": {},
 998    "outputs": [
 999     {
1000      "data": {
1001       "text/plain": [
1002        "'doqzmbishkwunvltpcexyjgfra'"
1003       ]
1004      },
1005      "execution_count": 40,
1006      "metadata": {},
1007      "output_type": "execute_result"
1008     }
1009    ],
1010    "source": [
1011     "''.join(follow_many(string.ascii_lowercase, etnet))"
1012    ]
1013   },
1014   {
1015    "cell_type": "code",
1016    "execution_count": 41,
1017    "metadata": {},
1018    "outputs": [
1019     {
1020      "data": {
1021       "text/plain": [
1022        "'doqzmbishkwunvltpcexyjgfra'"
1023       ]
1024      },
1025      "execution_count": 41,
1026      "metadata": {},
1027      "output_type": "execute_result"
1028     }
1029    ],
1030    "source": [
1031     "''.join(follow_many(string.ascii_lowercase, setnet))"
1032    ]
1033   },
1034   {
1035    "cell_type": "code",
1036    "execution_count": 42,
1037    "metadata": {},
1038    "outputs": [
1039     {
1040      "data": {
1041       "text/plain": [
1042        "'doqzmbishkwunvltpcexyjgfra'"
1043       ]
1044      },
1045      "execution_count": 42,
1046      "metadata": {},
1047      "output_type": "execute_result"
1048     }
1049    ],
1050    "source": [
1051     "''.join(follow_many(string.ascii_lowercase, enet))"
1052    ]
1053   },
1054   {
1055    "cell_type": "code",
1056    "execution_count": 43,
1057    "metadata": {},
1058    "outputs": [
1059     {
1060      "data": {
1061       "text/plain": [
1062        "'doqzmbishkwunvltpcexyjgfra'"
1063       ]
1064      },
1065      "execution_count": 43,
1066      "metadata": {},
1067      "output_type": "execute_result"
1068     }
1069    ],
1070    "source": [
1071     "''.join(follow_many(string.ascii_lowercase, net))"
1072    ]
1073   },
1074   {
1075    "cell_type": "code",
1076    "execution_count": 44,
1077    "metadata": {},
1078    "outputs": [
1079     {
1080      "data": {
1081       "text/plain": [
1082        "[]"
1083       ]
1084      },
1085      "execution_count": 44,
1086      "metadata": {},
1087      "output_type": "execute_result"
1088     }
1089    ],
1090    "source": [
1091     "eliminable_pairs(etnet)"
1092    ]
1093   },
1094   {
1095    "cell_type": "code",
1096    "execution_count": 45,
1097    "metadata": {},
1098    "outputs": [
1099     {
1100      "data": {
1101       "text/plain": [
1102        "(10135, 10031)"
1103       ]
1104      },
1105      "execution_count": 45,
1106      "metadata": {},
1107      "output_type": "execute_result"
1108     }
1109    ],
1110    "source": [
1111     "len(net), len(etnet)"
1112    ]
1113   },
1114   {
1115    "cell_type": "code",
1116    "execution_count": 46,
1117    "metadata": {
1118     "collapsed": true
1119    },
1120    "outputs": [],
1121    "source": [
1122     "def simplify(net0):\n",
1123     "    netp = eliminate_pairs(net0)\n",
1124     "    new_net = eliminate_a_triple_pair(netp)\n",
1125     "    while new_net:\n",
1126     "#         print('sipl', len(net0), len(netp), len(new_net))\n",
1127     "        netp = eliminate_pairs(new_net)\n",
1128     "        new_net = eliminate_a_triple_pair(netp)\n",
1129     "    return netp"
1130    ]
1131   },
1132   {
1133    "cell_type": "code",
1134    "execution_count": 47,
1135    "metadata": {
1136     "collapsed": true
1137    },
1138    "outputs": [],
1139    "source": [
1140     "simple_net = simplify(pnet)"
1141    ]
1142   },
1143   {
1144    "cell_type": "code",
1145    "execution_count": 48,
1146    "metadata": {},
1147    "outputs": [
1148     {
1149      "data": {
1150       "text/plain": [
1151        "True"
1152       ]
1153      },
1154      "execution_count": 48,
1155      "metadata": {},
1156      "output_type": "execute_result"
1157     }
1158    ],
1159    "source": [
1160     "''.join(follow_many(string.ascii_lowercase, simple_net)) == ''.join(follow_many(string.ascii_lowercase, net))"
1161    ]
1162   },
1163   {
1164    "cell_type": "code",
1165    "execution_count": 49,
1166    "metadata": {},
1167    "outputs": [
1168     {
1169      "data": {
1170       "text/plain": [
1171        "'doqzmbishkwunvltpcexyjgfra'"
1172       ]
1173      },
1174      "execution_count": 49,
1175      "metadata": {},
1176      "output_type": "execute_result"
1177     }
1178    ],
1179    "source": [
1180     "''.join(follow_many(string.ascii_lowercase, simple_net))"
1181    ]
1182   },
1183   {
1184    "cell_type": "code",
1185    "execution_count": 50,
1186    "metadata": {},
1187    "outputs": [
1188     {
1189      "data": {
1190       "text/plain": [
1191        "'doqzmbishkwunvltpcexyjgfra'"
1192       ]
1193      },
1194      "execution_count": 50,
1195      "metadata": {},
1196      "output_type": "execute_result"
1197     }
1198    ],
1199    "source": [
1200     "''.join(follow_many(string.ascii_lowercase, net))"
1201    ]
1202   },
1203   {
1204    "cell_type": "code",
1205    "execution_count": 51,
1206    "metadata": {},
1207    "outputs": [
1208     {
1209      "data": {
1210       "text/plain": [
1211        "9931"
1212       ]
1213      },
1214      "execution_count": 51,
1215      "metadata": {},
1216      "output_type": "execute_result"
1217     }
1218    ],
1219    "source": [
1220     "len(simple_net)"
1221    ]
1222   },
1223   {
1224    "cell_type": "code",
1225    "execution_count": 52,
1226    "metadata": {
1227     "collapsed": true
1228    },
1229    "outputs": [],
1230    "source": [
1231     "def simplify_with_checks(net0):\n",
1232     "    netp = eliminate_pairs(net0)\n",
1233     "    if follow_many(string.ascii_lowercase, net0) != follow_many(string.ascii_lowercase, netp):\n",
1234     "        print('pairs', eliminable_pairs(net0))\n",
1235     "        return net0\n",
1236     "    else:\n",
1237     "        print('pairs ok')\n",
1238     "    new_net = eliminate_a_triple_pair(netp)\n",
1239     "    if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
1240     "        hg = find_height_groups(netp)\n",
1241     "        print('triple', triple_pair_hg(hg))\n",
1242     "        return netp\n",
1243     "    else:\n",
1244     "        print('triple ok')\n",
1245     "    while new_net:\n",
1246     "#         print('sipl', len(net0), len(netp), len(new_net))\n",
1247     "        netp = eliminate_pairs(new_net)\n",
1248     "        if follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
1249     "            print('pairs', eliminable_pairs(new_net))\n",
1250     "            return new_net\n",
1251     "        else:\n",
1252     "            print('pairs ok')\n",
1253     "        new_net = eliminate_a_triple_pair(netp)\n",
1254     "        if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
1255     "            hg = find_height_groups(netp)\n",
1256     "            print('triple', triple_pair_hg(hg))\n",
1257     "            return netp\n",
1258     "        else:\n",
1259     "            print('triple ok')\n",
1260     "    print('** done')\n",
1261     "    return netp"
1262    ]
1263   },
1264   {
1265    "cell_type": "code",
1266    "execution_count": 53,
1267    "metadata": {
1268     "scrolled": true
1269    },
1270    "outputs": [
1271     {
1272      "name": "stdout",
1273      "output_type": "stream",
1274      "text": [
1275       "pairs ok\n",
1276       "triple ok\n",
1277       "pairs ok\n",
1278       "triple ok\n",
1279       "pairs ok\n",
1280       "triple ok\n",
1281       "pairs ok\n",
1282       "triple ok\n",
1283       "pairs ok\n",
1284       "triple ok\n",
1285       "pairs ok\n",
1286       "triple ok\n",
1287       "pairs ok\n",
1288       "triple ok\n",
1289       "pairs ok\n",
1290       "triple ok\n",
1291       "pairs ok\n",
1292       "triple ok\n",
1293       "pairs ok\n",
1294       "triple ok\n",
1295       "pairs ok\n",
1296       "triple ok\n",
1297       "pairs ok\n",
1298       "triple ok\n",
1299       "pairs ok\n",
1300       "triple ok\n",
1301       "pairs ok\n",
1302       "triple ok\n",
1303       "pairs ok\n",
1304       "triple ok\n",
1305       "pairs ok\n",
1306       "triple ok\n",
1307       "pairs ok\n",
1308       "triple ok\n",
1309       "pairs ok\n",
1310       "triple ok\n",
1311       "pairs ok\n",
1312       "triple ok\n",
1313       "pairs ok\n",
1314       "triple ok\n",
1315       "pairs ok\n",
1316       "triple ok\n",
1317       "pairs ok\n",
1318       "triple ok\n",
1319       "pairs ok\n",
1320       "triple ok\n",
1321       "pairs ok\n",
1322       "triple ok\n",
1323       "pairs ok\n",
1324       "triple ok\n",
1325       "pairs ok\n",
1326       "triple ok\n",
1327       "pairs ok\n",
1328       "triple ok\n",
1329       "pairs ok\n",
1330       "triple ok\n",
1331       "pairs ok\n",
1332       "triple ok\n",
1333       "pairs ok\n",
1334       "triple ok\n",
1335       "pairs ok\n",
1336       "triple ok\n",
1337       "pairs ok\n",
1338       "triple ok\n",
1339       "pairs ok\n",
1340       "triple ok\n",
1341       "pairs ok\n",
1342       "triple ok\n",
1343       "pairs ok\n",
1344       "triple ok\n",
1345       "pairs ok\n",
1346       "triple ok\n",
1347       "pairs ok\n",
1348       "triple ok\n",
1349       "pairs ok\n",
1350       "triple ok\n",
1351       "pairs ok\n",
1352       "triple ok\n",
1353       "pairs ok\n",
1354       "triple ok\n",
1355       "pairs ok\n",
1356       "triple ok\n",
1357       "pairs ok\n",
1358       "triple ok\n",
1359       "pairs ok\n",
1360       "triple ok\n",
1361       "pairs ok\n",
1362       "triple ok\n",
1363       "pairs ok\n",
1364       "triple ok\n",
1365       "pairs ok\n",
1366       "triple ok\n",
1367       "pairs ok\n",
1368       "triple ok\n",
1369       "pairs ok\n",
1370       "triple ok\n",
1371       "pairs ok\n",
1372       "triple ok\n",
1373       "** done\n"
1374      ]
1375     }
1376    ],
1377    "source": [
1378     "spnet = simplify_with_checks(pnet)"
1379    ]
1380   },
1381   {
1382    "cell_type": "code",
1383    "execution_count": 54,
1384    "metadata": {},
1385    "outputs": [
1386     {
1387      "data": {
1388       "text/plain": [
1389        "True"
1390       ]
1391      },
1392      "execution_count": 54,
1393      "metadata": {},
1394      "output_type": "execute_result"
1395     }
1396    ],
1397    "source": [
1398     "''.join(follow_many(string.ascii_lowercase, spnet)) == ''.join(follow_many(string.ascii_lowercase, net))"
1399    ]
1400   },
1401   {
1402    "cell_type": "code",
1403    "execution_count": 55,
1404    "metadata": {},
1405    "outputs": [
1406     {
1407      "data": {
1408       "text/plain": [
1409        "9931"
1410       ]
1411      },
1412      "execution_count": 55,
1413      "metadata": {},
1414      "output_type": "execute_result"
1415     }
1416    ],
1417    "source": [
1418     "len(spnet)"
1419    ]
1420   },
1421   {
1422    "cell_type": "code",
1423    "execution_count": null,
1424    "metadata": {
1425     "collapsed": true
1426    },
1427    "outputs": [],
1428    "source": []
1429   }
1430  ],
1431  "metadata": {
1432   "kernelspec": {
1433    "display_name": "Python 3",
1434    "language": "python",
1435    "name": "python3"
1436   },
1437   "language_info": {
1438    "codemirror_mode": {
1439     "name": "ipython",
1440     "version": 3
1441    },
1442    "file_extension": ".py",
1443    "mimetype": "text/x-python",
1444    "name": "python",
1445    "nbconvert_exporter": "python",
1446    "pygments_lexer": "ipython3",
1447    "version": "3.5.2+"
1448   }
1449  },
1450  "nbformat": 4,
1451  "nbformat_minor": 2
1452 }