X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=04-08-amidakuji%2Famidakuji-solution-1-slow.ipynb;fp=04-08-amidakuji%2Famidakuji-solution-1-slow.ipynb;h=345321daa12de45880fa71827fb01305186f3017;hb=787b6246ddfd5d1eaa228cdd11c537096362eb2f;hp=0000000000000000000000000000000000000000;hpb=b39e05e955bfcbc82abd31571d4cff37021b5942;p=ou-summer-of-code-2017.git diff --git a/04-08-amidakuji/amidakuji-solution-1-slow.ipynb b/04-08-amidakuji/amidakuji-solution-1-slow.ipynb new file mode 100644 index 0000000..345321d --- /dev/null +++ b/04-08-amidakuji/amidakuji-solution-1-slow.ipynb @@ -0,0 +1,1881 @@ +{ + "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 +}