--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import collections\n",
+ "import string\n",
+ "import itertools"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "Link = collections.namedtuple('Link', 'height left right')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def link_ends(link):\n",
+ " return set((link.left, link.right))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def read_net(net_string):\n",
+ " return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def follow(initial_line, links):\n",
+ " line = initial_line\n",
+ " heights = sorted(set(l.height for l in links))\n",
+ " for h in heights:\n",
+ " for l in [l for l in links if l.height == h]:\n",
+ " if line in link_ends(l):\n",
+ " line = [e for e in link_ends(l) if e != line][0]\n",
+ "# print(l, line)\n",
+ " return line"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def pack(net):\n",
+ " packed_links = []\n",
+ " line_heights = collections.defaultdict(lambda: -1)\n",
+ " for link in sorted(net):\n",
+ " link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
+ " line_heights[link.left] = link_height\n",
+ " line_heights[link.right] = link_height\n",
+ " packed_links += [Link(link_height, link.left, link.right)]\n",
+ " return sorted(packed_links)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def follow_many_slow(in_sequence, links):\n",
+ " out_sequence = [(follow(i, links), term) \n",
+ " for i, term in enumerate(in_sequence)]\n",
+ " return [term for i, term in sorted(out_sequence)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def follow_many(in_sequence, net):\n",
+ " height_groups = [list(g) for _, g in itertools.groupby(pack(net), lambda l: l.height)]\n",
+ " seq = list(in_sequence)\n",
+ " for links in height_groups:\n",
+ " for link in links:\n",
+ " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
+ " return seq"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10000 loops, best of 3: 47.5 µs per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "follow_many('abcdefghij', net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# %%timeit\n",
+ "# follow_many_slow('abcdefghij', net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def show_net(links, randomise=False):\n",
+ " if randomise:\n",
+ " output = []\n",
+ " heights = sorted(set(l.height for l in links))\n",
+ " for h in heights:\n",
+ " ls = [l for l in links if l.height == h]\n",
+ " random.shuffle(ls)\n",
+ " output += ['({}, {})'.format(l.left, l.right) for l in ls]\n",
+ " return ', '.join(output)\n",
+ " return ', '.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def extract_pairs(net_string):\n",
+ " return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(True, True)"
+ ]
+ },
+ "execution_count": 25,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "rrnet = read_net(show_net(net, randomise=True))\n",
+ "rnet = read_net(show_net(net))\n",
+ "rnet == rrnet, pack(rrnet) == pnet"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "lnet = make_net(10207, 26, 100000)\n",
+ "plnet = pack(lnet)\n",
+ "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, plnet)\n",
+ "# for i in range(204):\n",
+ "# assert follow(i, lnet) == follow(i, plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "rlnet = read_net(show_net(lnet))\n",
+ "prlnet = pack(rlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2251"
+ ]
+ },
+ "execution_count": 28,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(link.height for link in plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "99998"
+ ]
+ },
+ "execution_count": 29,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(link.height for link in lnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "10206"
+ ]
+ },
+ "execution_count": 30,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(link.height for link in rlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2251"
+ ]
+ },
+ "execution_count": 31,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(link.height for link in prlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, prlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10 loops, best of 3: 24.5 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "follow_many(string.ascii_lowercase, lnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# %%timeit\n",
+ "# follow_many_slow(string.ascii_lowercase, lnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminable_pairs_slow(net):\n",
+ " eps = []\n",
+ " for l in net:\n",
+ " o = Link(l.height + 1, l.left, l.right)\n",
+ " if o in net:\n",
+ " eps += [(l, o)]\n",
+ " return eps "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminable_pairs(net):\n",
+ " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
+ " eps = []\n",
+ " for h in range(1, max(height_groups.keys())):\n",
+ " for l in height_groups[h]:\n",
+ " o = Link(l.height - 1, l.left, l.right)\n",
+ " if o in height_groups[h-1]:\n",
+ " eps += [(l, o)]\n",
+ " return eps"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10 loops, best of 3: 23.5 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "eliminable_pairs(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 2.33 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "eliminable_pairs_slow(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "assert sorted(sorted(p) for p in eliminable_pairs(plnet)) == sorted(sorted(p) for p in eliminable_pairs_slow(plnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 40,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminable_pair(net):\n",
+ " for l in net:\n",
+ " o = Link(l.height + 1, l.left, l.right)\n",
+ " if o in net:\n",
+ " return l, o\n",
+ " return None"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 41,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminable_pair_hg(height_groups):\n",
+ " for h in range(1, max(height_groups.keys())):\n",
+ " for l in height_groups[h]:\n",
+ " o = Link(l.height - 1, l.left, l.right)\n",
+ " if o in height_groups[h-1]:\n",
+ " return l, o\n",
+ " return None"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminate_pairs_slow(net):\n",
+ " eliminable_links = eliminable_pair(net)\n",
+ " while eliminable_links:\n",
+ " net = pack(l for l in net if l not in eliminable_links)\n",
+ " eliminable_links = eliminable_pair(net)\n",
+ " return net"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 43,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminate_pairs(net):\n",
+ " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
+ " eliminable_links = eliminable_pair_hg(height_groups)\n",
+ " while eliminable_links:\n",
+ " net = pack(l for l in net if l not in eliminable_links)\n",
+ " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
+ " eliminable_links = eliminable_pair_hg(height_groups)\n",
+ " return net"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10207\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "(10207, 9811)"
+ ]
+ },
+ "execution_count": 44,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "print(len(plnet))\n",
+ "elnet = eliminate_pairs_slow(plnet)\n",
+ "len(plnet), len(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10207\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "(10207, 9811)"
+ ]
+ },
+ "execution_count": 45,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "print(len(plnet))\n",
+ "elnet = eliminate_pairs(plnet)\n",
+ "len(plnet), len(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 46,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[]"
+ ]
+ },
+ "execution_count": 46,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "eliminable_pairs(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 47,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "assert eliminate_pairs_slow(plnet) == eliminate_pairs(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, elnet)\n",
+ "assert follow_many(string.ascii_lowercase, plnet) == follow_many(string.ascii_lowercase, elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 3min 30s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "elnet = eliminate_pairs_slow(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 6.27 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "elnet = eliminate_pairs(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 51,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# for i in range(26):\n",
+ "# assert follow(i, plnet) == follow(i, elnet)\n",
+ "# assert follow(i, lnet) == follow(i, elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# follow(0, plnet), follow(0, elnet), follow(0, lnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 53,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def triple(net):\n",
+ " x = None\n",
+ " y = None\n",
+ " ts = []\n",
+ " for a in net:\n",
+ " bs = [l for l in net if l.height == a.height + 1 \n",
+ " if l.left == a.right or l.right == a.left]\n",
+ " for b in bs:\n",
+ " c = Link(a.height + 2, a.left, a.right)\n",
+ " if c in net:\n",
+ " ts += [(a, b, c)]\n",
+ " return ts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 54,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def triple_pair(net):\n",
+ " ts = []\n",
+ " for a in net:\n",
+ " a_ends = link_ends(a)\n",
+ " bs = [l for l in net if l.height == a.height + 1 \n",
+ " if link_ends(l) & a_ends]\n",
+ " if len(bs) == 1:\n",
+ " b = bs[0]\n",
+ " lines = set((a.left, a.right, b.left, b.right))\n",
+ " cs = [l for l in net \n",
+ " if l.height == a.height + 2\n",
+ " if link_ends(l) & lines]\n",
+ " if len(cs) == 1:\n",
+ " c = Link(a.height + 2, a.left, a.right)\n",
+ " if c in cs:\n",
+ " ds = [l for l in net \n",
+ " if l.height == a.height + 3\n",
+ " if link_ends(l) & lines]\n",
+ " d = Link(a.height + 3, b.left, b.right)\n",
+ " if d in ds:\n",
+ " ts += [(a, b, c, d)]\n",
+ " return ts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 129,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def triple_pair_hg(height_groups, debug=False):\n",
+ " ts = []\n",
+ " for h in range(3, max(height_groups.keys())):\n",
+ " for d in height_groups[h]:\n",
+ " if debug: print('d:', d)\n",
+ " ch = h - 1\n",
+ " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
+ " if debug: print('cs:', cs)\n",
+ " while ch > 2 and not cs:\n",
+ " ch -= 1\n",
+ " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
+ " if debug: print('cs:', cs)\n",
+ " if len(cs) == 1:\n",
+ " c = cs[0]\n",
+ " lines = set((d.left, d.right, c.left, c.right))\n",
+ " if debug: print('c:', '; lines:', lines)\n",
+ " bs = [l for l in height_groups[ch-1] if link_ends(l) & lines]\n",
+ " b = Link(ch - 1, d.left, d.right)\n",
+ " if debug: print('b:', b, '; bs:', bs)\n",
+ " if len(bs) == 1 and b in bs:\n",
+ " ah = b.height - 1\n",
+ " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
+ " if debug: print('ah:', ah, '; als:', als)\n",
+ " while ah > 0 and not als:\n",
+ " ah -= 1\n",
+ " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
+ " if debug: print('ah:', ah, '; als:', als)\n",
+ " a = Link(ah, c.left, c.right)\n",
+ " if debug: print('a:', a)\n",
+ " if a in als:\n",
+ " if debug: print('adding:', a, b, c, d)\n",
+ " ts += [(a, b, c, d)]\n",
+ " return ts"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 132,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminate_a_triple_pair_slow(net):\n",
+ " tps = triple_pair(net)\n",
+ " print('eatp', tps)\n",
+ "\n",
+ " if tps:\n",
+ " a, b, c, d = tps[0]\n",
+ "# x = Link(a.height, b.left, b.right)\n",
+ "# y = Link(b.height, a.left, a.right)\n",
+ " x = Link(a.height, b.left, b.right)\n",
+ " y = Link(b.height, a.left, a.right)\n",
+ " print('removing', a, b, c, d, '; adding', x, y)\n",
+ " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
+ " return None"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 133,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminate_a_triple_pair(net):\n",
+ " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
+ "\n",
+ " tps = triple_pair_hg(height_groups)\n",
+ " print('eatp', tps)\n",
+ " if tps:\n",
+ " a, b, c, d = tps[0]\n",
+ " x = Link(a.height, b.left, b.right)\n",
+ " y = Link(b.height, a.left, a.right)\n",
+ " print('removing', a, b, c, d, '; adding', x, y)\n",
+ " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
+ " return None"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 58,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(Link(height=12, left=0, right=5),\n",
+ " Link(height=13, left=5, right=11),\n",
+ " Link(height=14, left=0, right=5)),\n",
+ " (Link(height=29, left=2, right=18),\n",
+ " Link(height=30, left=1, right=2),\n",
+ " Link(height=31, left=2, right=18)),\n",
+ " (Link(height=40, left=2, right=3),\n",
+ " Link(height=41, left=3, right=18),\n",
+ " Link(height=42, left=2, right=3)),\n",
+ " (Link(height=43, left=1, right=10),\n",
+ " Link(height=44, left=10, right=20),\n",
+ " Link(height=45, left=1, right=10)),\n",
+ " (Link(height=91, left=5, right=8),\n",
+ " Link(height=92, left=3, right=5),\n",
+ " Link(height=93, left=5, right=8)),\n",
+ " (Link(height=91, left=5, right=8),\n",
+ " Link(height=92, left=8, right=18),\n",
+ " Link(height=93, left=5, right=8)),\n",
+ " (Link(height=99, left=13, right=17),\n",
+ " Link(height=100, left=4, right=13),\n",
+ " Link(height=101, left=13, right=17)),\n",
+ " (Link(height=120, left=18, right=20),\n",
+ " Link(height=121, left=9, right=18),\n",
+ " Link(height=122, left=18, right=20)),\n",
+ " (Link(height=147, left=19, right=21),\n",
+ " Link(height=148, left=7, right=19),\n",
+ " Link(height=149, left=19, right=21)),\n",
+ " (Link(height=147, left=19, right=21),\n",
+ " Link(height=148, left=21, right=23),\n",
+ " Link(height=149, left=19, right=21)),\n",
+ " (Link(height=179, left=13, right=25),\n",
+ " Link(height=180, left=12, right=13),\n",
+ " Link(height=181, left=13, right=25)),\n",
+ " (Link(height=265, left=3, right=20),\n",
+ " Link(height=266, left=20, right=23),\n",
+ " Link(height=267, left=3, right=20)),\n",
+ " (Link(height=291, left=5, right=23),\n",
+ " Link(height=292, left=2, right=5),\n",
+ " Link(height=293, left=5, right=23)),\n",
+ " (Link(height=292, left=18, right=25),\n",
+ " Link(height=293, left=0, right=18),\n",
+ " Link(height=294, left=18, right=25)),\n",
+ " (Link(height=302, left=11, right=19),\n",
+ " Link(height=303, left=6, right=11),\n",
+ " Link(height=304, left=11, right=19)),\n",
+ " (Link(height=309, left=15, right=20),\n",
+ " Link(height=310, left=20, right=25),\n",
+ " Link(height=311, left=15, right=20)),\n",
+ " (Link(height=325, left=13, right=18),\n",
+ " Link(height=326, left=11, right=13),\n",
+ " Link(height=327, left=13, right=18)),\n",
+ " (Link(height=362, left=11, right=22),\n",
+ " Link(height=363, left=22, right=24),\n",
+ " Link(height=364, left=11, right=22)),\n",
+ " (Link(height=372, left=22, right=23),\n",
+ " Link(height=373, left=1, right=22),\n",
+ " Link(height=374, left=22, right=23)),\n",
+ " (Link(height=386, left=4, right=17),\n",
+ " Link(height=387, left=17, right=21),\n",
+ " Link(height=388, left=4, right=17)),\n",
+ " (Link(height=393, left=4, right=16),\n",
+ " Link(height=394, left=0, right=4),\n",
+ " Link(height=395, left=4, right=16)),\n",
+ " (Link(height=531, left=0, right=4),\n",
+ " Link(height=532, left=4, right=15),\n",
+ " Link(height=533, left=0, right=4)),\n",
+ " (Link(height=575, left=5, right=21),\n",
+ " Link(height=576, left=1, right=5),\n",
+ " Link(height=577, left=5, right=21)),\n",
+ " (Link(height=639, left=7, right=11),\n",
+ " Link(height=640, left=11, right=17),\n",
+ " Link(height=641, left=7, right=11)),\n",
+ " (Link(height=687, left=2, right=4),\n",
+ " Link(height=688, left=4, right=15),\n",
+ " Link(height=689, left=2, right=4)),\n",
+ " (Link(height=706, left=8, right=11),\n",
+ " Link(height=707, left=11, right=22),\n",
+ " Link(height=708, left=8, right=11)),\n",
+ " (Link(height=722, left=22, right=23),\n",
+ " Link(height=723, left=21, right=22),\n",
+ " Link(height=724, left=22, right=23)),\n",
+ " (Link(height=768, left=9, right=11),\n",
+ " Link(height=769, left=11, right=17),\n",
+ " Link(height=770, left=9, right=11)),\n",
+ " (Link(height=792, left=5, right=12),\n",
+ " Link(height=793, left=12, right=17),\n",
+ " Link(height=794, left=5, right=12)),\n",
+ " (Link(height=805, left=20, right=22),\n",
+ " Link(height=806, left=19, right=20),\n",
+ " Link(height=807, left=20, right=22)),\n",
+ " (Link(height=806, left=19, right=20),\n",
+ " Link(height=807, left=18, right=19),\n",
+ " Link(height=808, left=19, right=20)),\n",
+ " (Link(height=806, left=19, right=20),\n",
+ " Link(height=807, left=20, right=22),\n",
+ " Link(height=808, left=19, right=20)),\n",
+ " (Link(height=882, left=7, right=14),\n",
+ " Link(height=883, left=14, right=22),\n",
+ " Link(height=884, left=7, right=14)),\n",
+ " (Link(height=884, left=6, right=11),\n",
+ " Link(height=885, left=11, right=19),\n",
+ " Link(height=886, left=6, right=11)),\n",
+ " (Link(height=892, left=12, right=17),\n",
+ " Link(height=893, left=10, right=12),\n",
+ " Link(height=894, left=12, right=17)),\n",
+ " (Link(height=916, left=18, right=24),\n",
+ " Link(height=917, left=16, right=18),\n",
+ " Link(height=918, left=18, right=24)),\n",
+ " (Link(height=919, left=14, right=17),\n",
+ " Link(height=920, left=6, right=14),\n",
+ " Link(height=921, left=14, right=17)),\n",
+ " (Link(height=994, left=0, right=3),\n",
+ " Link(height=995, left=3, right=24),\n",
+ " Link(height=996, left=0, right=3)),\n",
+ " (Link(height=1012, left=9, right=12),\n",
+ " Link(height=1013, left=12, right=24),\n",
+ " Link(height=1014, left=9, right=12)),\n",
+ " (Link(height=1034, left=1, right=6),\n",
+ " Link(height=1035, left=6, right=12),\n",
+ " Link(height=1036, left=1, right=6)),\n",
+ " (Link(height=1035, left=7, right=21),\n",
+ " Link(height=1036, left=4, right=7),\n",
+ " Link(height=1037, left=7, right=21)),\n",
+ " (Link(height=1047, left=3, right=10),\n",
+ " Link(height=1048, left=10, right=11),\n",
+ " Link(height=1049, left=3, right=10)),\n",
+ " (Link(height=1088, left=7, right=8),\n",
+ " Link(height=1089, left=8, right=14),\n",
+ " Link(height=1090, left=7, right=8)),\n",
+ " (Link(height=1104, left=3, right=10),\n",
+ " Link(height=1105, left=10, right=11),\n",
+ " Link(height=1106, left=3, right=10)),\n",
+ " (Link(height=1135, left=5, right=8),\n",
+ " Link(height=1136, left=8, right=19),\n",
+ " Link(height=1137, left=5, right=8)),\n",
+ " (Link(height=1138, left=1, right=3),\n",
+ " Link(height=1139, left=3, right=23),\n",
+ " Link(height=1140, left=1, right=3)),\n",
+ " (Link(height=1146, left=5, right=7),\n",
+ " Link(height=1147, left=7, right=24),\n",
+ " Link(height=1148, left=5, right=7)),\n",
+ " (Link(height=1197, left=5, right=14),\n",
+ " Link(height=1198, left=14, right=15),\n",
+ " Link(height=1199, left=5, right=14)),\n",
+ " (Link(height=1205, left=7, right=23),\n",
+ " Link(height=1206, left=3, right=7),\n",
+ " Link(height=1207, left=7, right=23)),\n",
+ " (Link(height=1276, left=18, right=25),\n",
+ " Link(height=1277, left=17, right=18),\n",
+ " Link(height=1278, left=18, right=25)),\n",
+ " (Link(height=1319, left=14, right=20),\n",
+ " Link(height=1320, left=20, right=24),\n",
+ " Link(height=1321, left=14, right=20)),\n",
+ " (Link(height=1328, left=8, right=21),\n",
+ " Link(height=1329, left=1, right=8),\n",
+ " Link(height=1330, left=8, right=21)),\n",
+ " (Link(height=1329, left=2, right=14),\n",
+ " Link(height=1330, left=14, right=25),\n",
+ " Link(height=1331, left=2, right=14)),\n",
+ " (Link(height=1385, left=10, right=14),\n",
+ " Link(height=1386, left=14, right=15),\n",
+ " Link(height=1387, left=10, right=14)),\n",
+ " (Link(height=1419, left=2, right=8),\n",
+ " Link(height=1420, left=8, right=15),\n",
+ " Link(height=1421, left=2, right=8)),\n",
+ " (Link(height=1465, left=13, right=21),\n",
+ " Link(height=1466, left=21, right=24),\n",
+ " Link(height=1467, left=13, right=21)),\n",
+ " (Link(height=1514, left=11, right=15),\n",
+ " Link(height=1515, left=15, right=21),\n",
+ " Link(height=1516, left=11, right=15)),\n",
+ " (Link(height=1545, left=3, right=11),\n",
+ " Link(height=1546, left=11, right=25),\n",
+ " Link(height=1547, left=3, right=11)),\n",
+ " (Link(height=1561, left=7, right=18),\n",
+ " Link(height=1562, left=0, right=7),\n",
+ " Link(height=1563, left=7, right=18)),\n",
+ " (Link(height=1671, left=9, right=15),\n",
+ " Link(height=1672, left=15, right=23),\n",
+ " Link(height=1673, left=9, right=15)),\n",
+ " (Link(height=1701, left=13, right=21),\n",
+ " Link(height=1702, left=4, right=13),\n",
+ " Link(height=1703, left=13, right=21)),\n",
+ " (Link(height=1706, left=5, right=13),\n",
+ " Link(height=1707, left=13, right=23),\n",
+ " Link(height=1708, left=5, right=13)),\n",
+ " (Link(height=1730, left=7, right=16),\n",
+ " Link(height=1731, left=1, right=7),\n",
+ " Link(height=1732, left=7, right=16)),\n",
+ " (Link(height=1781, left=0, right=8),\n",
+ " Link(height=1782, left=8, right=17),\n",
+ " Link(height=1783, left=0, right=8)),\n",
+ " (Link(height=1784, left=8, right=18),\n",
+ " Link(height=1785, left=1, right=8),\n",
+ " Link(height=1786, left=8, right=18)),\n",
+ " (Link(height=1804, left=19, right=24),\n",
+ " Link(height=1805, left=7, right=19),\n",
+ " Link(height=1806, left=19, right=24)),\n",
+ " (Link(height=1827, left=3, right=23),\n",
+ " Link(height=1828, left=23, right=25),\n",
+ " Link(height=1829, left=3, right=23)),\n",
+ " (Link(height=1837, left=1, right=16),\n",
+ " Link(height=1838, left=16, right=17),\n",
+ " Link(height=1839, left=1, right=16)),\n",
+ " (Link(height=1849, left=18, right=25),\n",
+ " Link(height=1850, left=4, right=18),\n",
+ " Link(height=1851, left=18, right=25)),\n",
+ " (Link(height=1856, left=6, right=13),\n",
+ " Link(height=1857, left=13, right=17),\n",
+ " Link(height=1858, left=6, right=13)),\n",
+ " (Link(height=1875, left=2, right=11),\n",
+ " Link(height=1876, left=11, right=15),\n",
+ " Link(height=1877, left=2, right=11)),\n",
+ " (Link(height=1970, left=6, right=24),\n",
+ " Link(height=1971, left=1, right=6),\n",
+ " Link(height=1972, left=6, right=24)),\n",
+ " (Link(height=2075, left=20, right=25),\n",
+ " Link(height=2076, left=5, right=20),\n",
+ " Link(height=2077, left=20, right=25)),\n",
+ " (Link(height=2081, left=4, right=19),\n",
+ " Link(height=2082, left=1, right=4),\n",
+ " Link(height=2083, left=4, right=19)),\n",
+ " (Link(height=2111, left=3, right=25),\n",
+ " Link(height=2112, left=1, right=3),\n",
+ " Link(height=2113, left=3, right=25)),\n",
+ " (Link(height=2225, left=3, right=12),\n",
+ " Link(height=2226, left=12, right=24),\n",
+ " Link(height=2227, left=3, right=12)),\n",
+ " (Link(height=2242, left=3, right=18),\n",
+ " Link(height=2243, left=18, right=23),\n",
+ " Link(height=2244, left=3, right=18))]"
+ ]
+ },
+ "execution_count": 58,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "triple(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 59,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(Link(height=316, left=8, right=17),\n",
+ " Link(height=317, left=8, right=21),\n",
+ " Link(height=318, left=8, right=17),\n",
+ " Link(height=319, left=8, right=21)),\n",
+ " (Link(height=867, left=4, right=11),\n",
+ " Link(height=868, left=5, right=11),\n",
+ " Link(height=869, left=4, right=11),\n",
+ " Link(height=870, left=5, right=11))]"
+ ]
+ },
+ "execution_count": 59,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "triple_pair(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 60,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(Link(height=316, left=8, right=17),\n",
+ " Link(height=317, left=8, right=21),\n",
+ " Link(height=318, left=8, right=17),\n",
+ " Link(height=319, left=8, right=21)),\n",
+ " (Link(height=867, left=4, right=11),\n",
+ " Link(height=868, left=5, right=11),\n",
+ " Link(height=869, left=4, right=11),\n",
+ " Link(height=870, left=5, right=11))]"
+ ]
+ },
+ "execution_count": 60,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(elnet), lambda l: l.height)}\n",
+ "triple_pair_hg(height_groups)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 61,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[Link(height=1368, left=13, right=19),\n",
+ " Link(height=1368, left=14, right=16),\n",
+ " Link(height=1369, left=3, right=6)]"
+ ]
+ },
+ "execution_count": 61,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[l for l in elnet if l.height >= 1367 if l.height <= 1370 if link_ends(l) & set((6, 16, 19))]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 62,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 21.3 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "triple_pair(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 63,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10 loops, best of 3: 105 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(elnet), lambda l: l.height)}\n",
+ "triple_pair_hg(height_groups)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 64,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(elnet), lambda l: l.height)}\n",
+ "assert triple_pair_hg(height_groups) == triple_pair(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 65,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[Link(height=242, left=8, right=9),\n",
+ " Link(height=242, left=15, right=21),\n",
+ " Link(height=243, left=1, right=9),\n",
+ " Link(height=243, left=8, right=14),\n",
+ " Link(height=243, left=11, right=15),\n",
+ " Link(height=244, left=1, right=18),\n",
+ " Link(height=244, left=6, right=8),\n",
+ " Link(height=244, left=9, right=20),\n",
+ " Link(height=244, left=15, right=25),\n",
+ " Link(height=245, left=0, right=15),\n",
+ " Link(height=245, left=1, right=16),\n",
+ " Link(height=245, left=9, right=12),\n",
+ " Link(height=245, left=18, right=21)]"
+ ]
+ },
+ "execution_count": 65,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[l for l in elnet if l.height >= 242 if l.height <= 245 ] #if l.left in [13, 17, 20] or l.right in [13, 17, 20]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 86,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminate_triple_pairs_slow(net):\n",
+ " print(len(net))\n",
+ " new_net = eliminate_a_triple_pair_slow(net)\n",
+ " while new_net:\n",
+ " print(len(net))\n",
+ " net = new_net\n",
+ " new_net = eliminate_a_triple_pair_slow(net)\n",
+ " return net"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 118,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def eliminate_triple_pairs(net):\n",
+ " print(len(net))\n",
+ " new_net = eliminate_a_triple_pair(net)\n",
+ " while new_net:\n",
+ " print(len(net))\n",
+ " net = new_net\n",
+ " new_net = eliminate_a_triple_pair(net)\n",
+ " return net"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 134,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "9811\n",
+ "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
+ "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=316, left=8, right=21) Link(height=317, left=8, right=17)\n",
+ "9811\n",
+ "eatp [(Link(height=866, left=4, right=11), Link(height=867, left=5, right=11), Link(height=868, left=4, right=11), Link(height=869, left=5, right=11))]\n",
+ "removing Link(height=866, left=4, right=11) Link(height=867, left=5, right=11) Link(height=868, left=4, right=11) Link(height=869, left=5, right=11) ; adding Link(height=866, left=5, right=11) Link(height=867, left=4, right=11)\n",
+ "9809\n",
+ "eatp []\n"
+ ]
+ }
+ ],
+ "source": [
+ "etlnet = eliminate_triple_pairs(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 112,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
+ "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=317, left=8, right=17) Link(height=318, left=8, right=21)\n"
+ ]
+ }
+ ],
+ "source": [
+ "etlnet = eliminate_a_triple_pair(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 135,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 136,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[Link(height=315, left=17, right=20),\n",
+ " Link(height=316, left=8, right=17),\n",
+ " Link(height=317, left=8, right=21),\n",
+ " Link(height=318, left=8, right=17),\n",
+ " Link(height=319, left=8, right=21),\n",
+ " Link(height=319, left=14, right=17),\n",
+ " Link(height=320, left=2, right=8),\n",
+ " Link(height=320, left=17, right=21)]"
+ ]
+ },
+ "execution_count": 136,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[l for l in elnet if l.height >= 315 if l.height <= 320 if link_ends(l) & set((8, 17, 21))] "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 137,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[Link(height=0, left=17, right=20),\n",
+ " Link(height=1, left=8, right=17),\n",
+ " Link(height=2, left=8, right=21),\n",
+ " Link(height=3, left=8, right=17),\n",
+ " Link(height=4, left=8, right=21),\n",
+ " Link(height=4, left=14, right=17),\n",
+ " Link(height=5, left=2, right=8),\n",
+ " Link(height=5, left=17, right=21)]"
+ ]
+ },
+ "execution_count": 137,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "nf = [l for l in elnet if l.height >= 315 if l.height <= 320 if link_ends(l) & set((8, 17, 21))]\n",
+ "pnf = pack(nf)\n",
+ "pnf"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 138,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "d: Link(height=3, left=8, right=17)\n",
+ "cs: [Link(height=2, left=8, right=21)]\n",
+ "c: ; lines: {8, 17, 21}\n",
+ "b: Link(height=1, left=8, right=17) ; bs: [Link(height=1, left=8, right=17)]\n",
+ "ah: 0 ; als: []\n",
+ "a: Link(height=0, left=8, right=21)\n",
+ "d: Link(height=4, left=8, right=21)\n",
+ "cs: [Link(height=3, left=8, right=17)]\n",
+ "c: ; lines: {8, 17, 21}\n",
+ "b: Link(height=2, left=8, right=21) ; bs: [Link(height=2, left=8, right=21)]\n",
+ "ah: 1 ; als: [Link(height=1, left=8, right=17)]\n",
+ "a: Link(height=1, left=8, right=17)\n",
+ "adding: Link(height=1, left=8, right=17) Link(height=2, left=8, right=21) Link(height=3, left=8, right=17) Link(height=4, left=8, right=21)\n",
+ "d: Link(height=4, left=14, right=17)\n",
+ "cs: [Link(height=3, left=8, right=17)]\n",
+ "c: ; lines: {8, 17, 14}\n",
+ "b: Link(height=2, left=14, right=17) ; bs: [Link(height=2, left=8, right=21)]\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "[(Link(height=1, left=8, right=17),\n",
+ " Link(height=2, left=8, right=21),\n",
+ " Link(height=3, left=8, right=17),\n",
+ " Link(height=4, left=8, right=21))]"
+ ]
+ },
+ "execution_count": 138,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(pnf), lambda l: l.height)}\n",
+ "triple_pair_hg(height_groups, debug=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 139,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "9811\n",
+ "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
+ "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=316, left=8, right=21) Link(height=317, left=8, right=17)\n",
+ "9811\n",
+ "eatp [(Link(height=866, left=4, right=11), Link(height=867, left=5, right=11), Link(height=868, left=4, right=11), Link(height=869, left=5, right=11))]\n",
+ "removing Link(height=866, left=4, right=11) Link(height=867, left=5, right=11) Link(height=868, left=4, right=11) Link(height=869, left=5, right=11) ; adding Link(height=866, left=5, right=11) Link(height=867, left=4, right=11)\n",
+ "9809\n",
+ "eatp []\n"
+ ]
+ }
+ ],
+ "source": [
+ "setlnet = eliminate_triple_pairs_slow(elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 140,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "9807"
+ ]
+ },
+ "execution_count": 140,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(setlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 141,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 142,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'zdunvslcfiqywjmkobhxtraegp'"
+ ]
+ },
+ "execution_count": 142,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, etlnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 143,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'zdunvslcfiqywjmkobhxtraegp'"
+ ]
+ },
+ "execution_count": 143,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, setlnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 144,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'zdunvslcfiqywjmkobhxtraegp'"
+ ]
+ },
+ "execution_count": 144,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, elnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 145,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'zdunvslcfiqywjmkobhxtraegp'"
+ ]
+ },
+ "execution_count": 145,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, lnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 146,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[]"
+ ]
+ },
+ "execution_count": 146,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "eliminable_pairs(etlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 147,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(10207, 9807)"
+ ]
+ },
+ "execution_count": 147,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(lnet), len(etlnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 148,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def simplify(net0):\n",
+ " netp = eliminate_pairs(net0)\n",
+ " new_net = eliminate_a_triple_pair(netp)\n",
+ " while new_net:\n",
+ "# print('sipl', len(net0), len(netp), len(new_net))\n",
+ " netp = eliminate_pairs(new_net)\n",
+ " new_net = eliminate_a_triple_pair(netp)\n",
+ " return netp"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 149,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
+ "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=316, left=8, right=21) Link(height=317, left=8, right=17)\n",
+ "eatp [(Link(height=866, left=4, right=11), Link(height=867, left=5, right=11), Link(height=868, left=4, right=11), Link(height=869, left=5, right=11))]\n",
+ "removing Link(height=866, left=4, right=11) Link(height=867, left=5, right=11) Link(height=868, left=4, right=11) Link(height=869, left=5, right=11) ; adding Link(height=866, left=5, right=11) Link(height=867, left=4, right=11)\n",
+ "eatp []\n"
+ ]
+ }
+ ],
+ "source": [
+ "simple_lnet = simplify(plnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 150,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "True"
+ ]
+ },
+ "execution_count": 150,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, simple_lnet)) == ''.join(follow_many(string.ascii_lowercase, lnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 151,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'zdunvslcfiqywjmkobhxtraegp'"
+ ]
+ },
+ "execution_count": 151,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, simple_lnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 152,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'zdunvslcfiqywjmkobhxtraegp'"
+ ]
+ },
+ "execution_count": 152,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, lnet))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 153,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "9807"
+ ]
+ },
+ "execution_count": 153,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(simple_lnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def add_triple_pair(net, max_lines=None):\n",
+ " if not max_lines:\n",
+ " max_lines = max(l.right for l in net)\n",
+ " a, b, c = 0, 0, 0\n",
+ " while len(set((a, b, c))) != 3:\n",
+ " a = random.randrange(max_lines)\n",
+ " b = random.randrange(max_lines)\n",
+ " c = random.randrange(max_lines)\n",
+ " tp = [(min(a, b), max(a, b)), (min(b, c), max(b, c))] * 2\n",
+ " \n",
+ " pairs = [(l.left, l.right) for l in sorted(net)]\n",
+ " i = random.randrange(len(pairs))\n",
+ " print(i, tp)\n",
+ " new_pairs = pairs[:i] + tp + pairs[i:]\n",
+ " return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)]) "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def add_pair(net, max_lines=None):\n",
+ " if not max_lines:\n",
+ " max_lines = max(l.right for l in net)\n",
+ "\n",
+ " a, b = 0, 0\n",
+ " while a == b:\n",
+ " a = random.randrange(max_lines)\n",
+ " b = random.randrange(max_lines)\n",
+ " p = [(min(a, b), max(a, b))] * 2\n",
+ " \n",
+ " pairs = [(l.left, l.right) for l in sorted(net)]\n",
+ " i = random.randrange(len(pairs))\n",
+ " \n",
+ " print(i, p)\n",
+ " new_pairs = pairs[:i] + p + pairs[i:]\n",
+ " return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)]) "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
+ "tps = triple_pair_hg(height_groups)\n",
+ "tps"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true,
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "lnettp = simple_lnet\n",
+ "for _ in range(10):\n",
+ " lnettp = add_pair(lnettp)\n",
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
+ "tps = triple_pair_hg(height_groups)\n",
+ "tps"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true,
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "lnettp = simple_lnet\n",
+ "for _ in range(10):\n",
+ " lnettp = add_triple_pair(lnettp)\n",
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
+ "tps = triple_pair_hg(height_groups)\n",
+ "tps"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true,
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "lnettp = simple_lnet\n",
+ "for _ in range(10):\n",
+ " lnettp = add_pair(lnettp)\n",
+ "for _ in range(10):\n",
+ " lnettp = add_triple_pair(lnettp)\n",
+ "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
+ "tps = triple_pair_hg(height_groups)\n",
+ "tps"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "lnettp == pack(lnettp)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "lnettps = simplify(lnettp)\n",
+ "len(lnettps)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "len(simple_lnet), len(lnettp), len(lnettps)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 3",
+ "language": "python",
+ "name": "python3"
+ },
+ "language_info": {
+ "codemirror_mode": {
+ "name": "ipython",
+ "version": 3
+ },
+ "file_extension": ".py",
+ "mimetype": "text/x-python",
+ "name": "python",
+ "nbconvert_exporter": "python",
+ "pygments_lexer": "ipython3",
+ "version": "3.5.2+"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}
projects / ou-summer-of-code-2017.git / blobdiff