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