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