{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import collections\n",
"import random\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": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def can_add(link, links):\n",
" ends = link_ends(link)\n",
" same_height_links = [l for l in links if l.height == link.height]\n",
" return all(ends.isdisjoint(link_ends(l)) for l in same_height_links)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def make_net(num_links, lines=10, height=50):\n",
" links = set()\n",
" while len(links) < num_links:\n",
" a = random.randrange(lines)\n",
" b = random.randrange(lines)\n",
" if a != b:\n",
" l = min(a, b)\n",
" r = max(a, b)\n",
" h = random.randrange(height)\n",
" link = Link(h, l, r)\n",
" if can_add(link, links):\n",
" links.add(link)\n",
" return links"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{Link(height=2, left=0, right=3),\n",
" Link(height=2, left=1, right=7),\n",
" Link(height=3, left=1, right=8),\n",
" Link(height=9, left=6, right=9),\n",
" Link(height=15, left=0, right=4),\n",
" Link(height=20, left=0, right=8),\n",
" Link(height=23, left=3, right=4),\n",
" Link(height=24, left=3, right=6),\n",
" Link(height=28, left=1, right=8),\n",
" Link(height=28, left=5, right=6),\n",
" Link(height=32, left=1, right=7),\n",
" Link(height=34, left=1, right=9),\n",
" Link(height=36, left=0, right=4),\n",
" Link(height=38, left=5, right=6),\n",
" Link(height=40, left=0, right=2),\n",
" Link(height=41, left=3, right=7),\n",
" Link(height=43, left=2, right=4),\n",
" Link(height=43, left=6, right=8),\n",
" Link(height=44, left=0, right=6),\n",
" Link(height=46, left=7, right=8)}"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"net = make_net(20)\n",
"net"
]
},
{
"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": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"follow(4, net)"
]
},
{
"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",
"# l = seq[link.left]\n",
"# r = seq[link.right]\n",
"# seq[link.right] = l\n",
"# seq[link.left] = r\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: 45.7 µ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": 104,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def show_net(links, randomise=False, pair_sep=', '):\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 pair_sep.join(output)\n",
" return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
]
},
{
"cell_type": "code",
"execution_count": 105,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(0, 3), (1, 7), (1, 8), (6, 9), (0, 4), (0, 8), (3, 4), (3, 6), (1, 8), (5, 6), (1, 7), (1, 9), (0, 4), (5, 6), (0, 2), (3, 7), (2, 4), (6, 8), (0, 6), (7, 8)'"
]
},
"execution_count": 105,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"show_net(net)"
]
},
{
"cell_type": "code",
"execution_count": 106,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(1, 7), (0, 3), (1, 8), (6, 9), (0, 4), (0, 8), (3, 4), (3, 6), (5, 6), (1, 8), (1, 7), (1, 9), (0, 4), (5, 6), (0, 2), (3, 7), (6, 8), (2, 4), (0, 6), (7, 8)'"
]
},
"execution_count": 106,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"show_net(net, randomise=True)"
]
},
{
"cell_type": "code",
"execution_count": 110,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(0, 3) : (1, 7) : (1, 8) : (6, 9) : (0, 4) : (0, 8) : (3, 4) : (3, 6) : (1, 8) : (5, 6) : (1, 7) : (1, 9) : (0, 4) : (5, 6) : (0, 2) : (3, 7) : (2, 4) : (6, 8) : (0, 6) : (7, 8)'"
]
},
"execution_count": 110,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"show_net(net, pair_sep=' : ')"
]
},
{
"cell_type": "code",
"execution_count": 111,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(0, 3)\\n(1, 7)\\n(1, 8)\\n(6, 9)\\n(0, 4)\\n(0, 8)\\n(3, 4)\\n(3, 6)\\n(1, 8)\\n(5, 6)\\n(1, 7)\\n(1, 9)\\n(0, 4)\\n(5, 6)\\n(0, 2)\\n(3, 7)\\n(2, 4)\\n(6, 8)\\n(0, 6)\\n(7, 8)'"
]
},
"execution_count": 111,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"show_net(net, pair_sep='\\n')"
]
},
{
"cell_type": "code",
"execution_count": 112,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(0, 3)\n",
"(1, 7)\n",
"(1, 8)\n",
"(6, 9)\n",
"(0, 4)\n",
"(0, 8)\n",
"(3, 4)\n",
"(3, 6)\n",
"(1, 8)\n",
"(5, 6)\n",
"(1, 7)\n",
"(1, 9)\n",
"(0, 4)\n",
"(5, 6)\n",
"(0, 2)\n",
"(3, 7)\n",
"(2, 4)\n",
"(6, 8)\n",
"(0, 6)\n",
"(7, 8)\n"
]
}
],
"source": [
"print(show_net(net, pair_sep='\\n'))"
]
},
{
"cell_type": "code",
"execution_count": 108,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(0, 3), (1, 7), (1, 8), (6, 9), (0, 4), (0, 8), (3, 4), (3, 6), (1, 8), (5, 6), (1, 7), (1, 9), (0, 4), (5, 6), (0, 2), (3, 7), (2, 4), (6, 8), (0, 6), (7, 8)'"
]
},
"execution_count": 108,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"show_net(net)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ls = [l for l in net if l.height == 1]\n",
"ls"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"random.shuffle(ls)"
]
},
{
"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": 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": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Link(height=0, left=0, right=3),\n",
" Link(height=1, left=1, right=7),\n",
" Link(height=2, left=1, right=8),\n",
" Link(height=3, left=6, right=9),\n",
" Link(height=4, left=0, right=4),\n",
" Link(height=5, left=0, right=8),\n",
" Link(height=6, left=3, right=4),\n",
" Link(height=7, left=3, right=6),\n",
" Link(height=8, left=1, right=8),\n",
" Link(height=9, left=5, right=6),\n",
" Link(height=10, left=1, right=7),\n",
" Link(height=11, left=1, right=9),\n",
" Link(height=12, left=0, right=4),\n",
" Link(height=13, left=5, right=6),\n",
" Link(height=14, left=0, right=2),\n",
" Link(height=15, left=3, right=7),\n",
" Link(height=16, left=2, right=4),\n",
" Link(height=17, left=6, right=8),\n",
" Link(height=18, left=0, right=6),\n",
" Link(height=19, left=7, right=8)]"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"read_net(show_net(net))"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Link(height=0, left=0, right=3),\n",
" Link(height=0, left=1, right=7),\n",
" Link(height=0, left=6, right=9),\n",
" Link(height=1, left=0, right=4),\n",
" Link(height=1, left=1, right=8),\n",
" Link(height=2, left=0, right=8),\n",
" Link(height=2, left=3, right=4),\n",
" Link(height=3, left=0, right=4),\n",
" Link(height=3, left=1, right=8),\n",
" Link(height=3, left=3, right=6),\n",
" Link(height=4, left=0, right=2),\n",
" Link(height=4, left=1, right=7),\n",
" Link(height=4, left=5, right=6),\n",
" Link(height=5, left=1, right=9),\n",
" Link(height=5, left=2, right=4),\n",
" Link(height=5, left=3, right=7),\n",
" Link(height=5, left=5, right=6),\n",
" Link(height=6, left=6, right=8),\n",
" Link(height=7, left=0, right=6),\n",
" Link(height=7, left=7, right=8)]"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pack(net)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Link(height=0, left=0, right=3),\n",
" Link(height=0, left=1, right=7),\n",
" Link(height=0, left=6, right=9),\n",
" Link(height=1, left=0, right=4),\n",
" Link(height=1, left=1, right=8),\n",
" Link(height=2, left=0, right=8),\n",
" Link(height=2, left=3, right=4),\n",
" Link(height=3, left=0, right=4),\n",
" Link(height=3, left=1, right=8),\n",
" Link(height=3, left=3, right=6),\n",
" Link(height=4, left=0, right=2),\n",
" Link(height=4, left=1, right=7),\n",
" Link(height=4, left=5, right=6),\n",
" Link(height=5, left=1, right=9),\n",
" Link(height=5, left=2, right=4),\n",
" Link(height=5, left=3, right=7),\n",
" Link(height=5, left=5, right=6),\n",
" Link(height=6, left=6, right=8),\n",
" Link(height=7, left=0, right=6),\n",
" Link(height=7, left=7, right=8)]"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pack(read_net(show_net(net)))"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(False, True)"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pnet = pack(net)\n",
"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": 25,
"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": 26,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"rlnet = read_net(show_net(lnet))\n",
"prlnet = pack(rlnet)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2224"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(link.height for link in plnet)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"99998"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(link.height for link in lnet)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10206"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(link.height for link in rlnet)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2224"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(link.height for link in prlnet)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, prlnet)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10 loops, best of 3: 23.4 ms per loop\n"
]
}
],
"source": [
"%%timeit\n",
"follow_many(string.ascii_lowercase, lnet)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# %%timeit\n",
"# follow_many_slow(string.ascii_lowercase, lnet)"
]
},
{
"cell_type": "code",
"execution_count": 34,
"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": 35,
"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": 36,
"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": 37,
"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": 38,
"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": 39,
"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": 40,
"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": 41,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10207\n"
]
},
{
"data": {
"text/plain": [
"(10207, 9839)"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print(len(plnet))\n",
"elnet = eliminate_pairs(plnet)\n",
"len(plnet), len(elnet)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eliminable_pairs(elnet)"
]
},
{
"cell_type": "code",
"execution_count": 43,
"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": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 loop, best of 3: 5.77 s per loop\n"
]
}
],
"source": [
"%%timeit\n",
"elnet = eliminate_pairs(plnet)"
]
},
{
"cell_type": "code",
"execution_count": 45,
"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": 46,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# follow(0, plnet), follow(0, elnet), follow(0, lnet)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def triple_slow(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": 48,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def triple_pair_slow(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": 49,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def find_height_groups(net):\n",
" return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"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": 51,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def eliminate_a_triple_pair_slow(net, debug=False):\n",
" tps = triple_pair_slow(net)\n",
" if debug: 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(b.height - 0.5, b.left, b.right)\n",
" y = Link(b.height, a.left, a.right)\n",
" if debug: 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": 52,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def eliminate_a_triple_pair(net, debug=False):\n",
" height_groups = find_height_groups(net)\n",
"\n",
" tps = triple_pair_hg(height_groups)\n",
" if debug: print('eatp', tps)\n",
" if tps:\n",
" a, b, c, d = tps[0]\n",
" x = Link(b.height - 0.5, b.left, b.right)\n",
" y = Link(b.height, a.left, a.right)\n",
" if debug: 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": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(Link(height=831, left=8, right=16),\n",
" Link(height=832, left=8, right=25),\n",
" Link(height=833, left=8, right=16),\n",
" Link(height=834, left=8, right=25)),\n",
" (Link(height=1657, left=1, right=13),\n",
" Link(height=1658, left=1, right=12),\n",
" Link(height=1659, left=1, right=13),\n",
" Link(height=1660, left=1, right=12))]"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"height_groups = find_height_groups(elnet)\n",
"triple_pair_hg(height_groups)"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10 loops, best of 3: 99.4 ms per loop\n"
]
}
],
"source": [
"%%timeit\n",
"height_groups = find_height_groups(elnet)\n",
"triple_pair_hg(height_groups)"
]
},
{
"cell_type": "code",
"execution_count": 55,
"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": 56,
"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": 57,
"metadata": {},
"outputs": [],
"source": [
"etlnet = eliminate_a_triple_pair(elnet)"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [],
"source": [
"assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"9839\n",
"9839\n",
"9837\n"
]
}
],
"source": [
"setlnet = eliminate_triple_pairs(elnet)"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9835"
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(setlnet)"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [],
"source": [
"assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'buxphgtzqykfawvomcjresnldi'"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, etlnet))"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'buxphgtzqykfawvomcjresnldi'"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, setlnet))"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'buxphgtzqykfawvomcjresnldi'"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, elnet))"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'buxphgtzqykfawvomcjresnldi'"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, lnet))"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eliminable_pairs(etlnet)"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(10207, 9837)"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(lnet), len(etlnet)"
]
},
{
"cell_type": "code",
"execution_count": 68,
"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": 69,
"metadata": {},
"outputs": [],
"source": [
"simple_lnet = simplify(plnet)"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 70,
"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": 71,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'buxphgtzqykfawvomcjresnldi'"
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, simple_lnet))"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'buxphgtzqykfawvomcjresnldi'"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, lnet))"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9835"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(simple_lnet)"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def add_triple_pair(net, max_lines=None, trace=False):\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",
" if trace: 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": 90,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def add_pair(net, max_lines=None, trace=False):\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",
" if trace: 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": 76,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 76,
"metadata": {},
"output_type": "execute_result"
}
],
"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": 91,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 91,
"metadata": {},
"output_type": "execute_result"
}
],
"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": 92,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"[(Link(height=195, left=5, right=10),\n",
" Link(height=197, left=1, right=5),\n",
" Link(height=198, left=5, right=10),\n",
" Link(height=199, left=1, right=5)),\n",
" (Link(height=359, left=6, right=16),\n",
" Link(height=360, left=16, right=20),\n",
" Link(height=361, left=6, right=16),\n",
" Link(height=362, left=16, right=20)),\n",
" (Link(height=409, left=0, right=9),\n",
" Link(height=410, left=9, right=16),\n",
" Link(height=411, left=0, right=9),\n",
" Link(height=412, left=9, right=16)),\n",
" (Link(height=606, left=0, right=7),\n",
" Link(height=607, left=0, right=5),\n",
" Link(height=608, left=0, right=7),\n",
" Link(height=609, left=0, right=5)),\n",
" (Link(height=967, left=7, right=19),\n",
" Link(height=968, left=19, right=23),\n",
" Link(height=969, left=7, right=19),\n",
" Link(height=970, left=19, right=23)),\n",
" (Link(height=973, left=9, right=18),\n",
" Link(height=975, left=9, right=15),\n",
" Link(height=976, left=9, right=18),\n",
" Link(height=977, left=9, right=15)),\n",
" (Link(height=1193, left=1, right=11),\n",
" Link(height=1194, left=1, right=19),\n",
" Link(height=1195, left=1, right=11),\n",
" Link(height=1196, left=1, right=19)),\n",
" (Link(height=1388, left=17, right=21),\n",
" Link(height=1389, left=6, right=17),\n",
" Link(height=1390, left=17, right=21),\n",
" Link(height=1391, left=6, right=17)),\n",
" (Link(height=1700, left=5, right=24),\n",
" Link(height=1701, left=11, right=24),\n",
" Link(height=1702, left=5, right=24),\n",
" Link(height=1703, left=11, right=24)),\n",
" (Link(height=1923, left=12, right=19),\n",
" Link(height=1924, left=19, right=24),\n",
" Link(height=1925, left=12, right=19),\n",
" Link(height=1926, left=19, right=24))]"
]
},
"execution_count": 92,
"metadata": {},
"output_type": "execute_result"
}
],
"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": 93,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"[(Link(height=8, left=1, right=5),\n",
" Link(height=9, left=1, right=21),\n",
" Link(height=10, left=1, right=5),\n",
" Link(height=11, left=1, right=21)),\n",
" (Link(height=40, left=16, right=23),\n",
" Link(height=41, left=16, right=19),\n",
" Link(height=42, left=16, right=23),\n",
" Link(height=43, left=16, right=19)),\n",
" (Link(height=62, left=0, right=10),\n",
" Link(height=63, left=10, right=13),\n",
" Link(height=64, left=0, right=10),\n",
" Link(height=65, left=10, right=13)),\n",
" (Link(height=137, left=23, right=24),\n",
" Link(height=139, left=0, right=24),\n",
" Link(height=140, left=23, right=24),\n",
" Link(height=141, left=0, right=24)),\n",
" (Link(height=138, left=10, right=21),\n",
" Link(height=139, left=2, right=10),\n",
" Link(height=140, left=10, right=21),\n",
" Link(height=141, left=2, right=10)),\n",
" (Link(height=139, left=2, right=10),\n",
" Link(height=140, left=10, right=21),\n",
" Link(height=141, left=2, right=10),\n",
" Link(height=142, left=10, right=21)),\n",
" (Link(height=156, left=6, right=11),\n",
" Link(height=157, left=3, right=6),\n",
" Link(height=158, left=6, right=11),\n",
" Link(height=159, left=3, right=6)),\n",
" (Link(height=184, left=2, right=21),\n",
" Link(height=185, left=5, right=21),\n",
" Link(height=186, left=2, right=21),\n",
" Link(height=187, left=5, right=21)),\n",
" (Link(height=274, left=7, right=13),\n",
" Link(height=275, left=7, right=11),\n",
" Link(height=276, left=7, right=13),\n",
" Link(height=277, left=7, right=11)),\n",
" (Link(height=292, left=14, right=15),\n",
" Link(height=293, left=5, right=15),\n",
" Link(height=294, left=14, right=15),\n",
" Link(height=295, left=5, right=15)),\n",
" (Link(height=389, left=1, right=8),\n",
" Link(height=391, left=8, right=15),\n",
" Link(height=392, left=1, right=8),\n",
" Link(height=393, left=8, right=15)),\n",
" (Link(height=422, left=14, right=22),\n",
" Link(height=424, left=14, right=18),\n",
" Link(height=425, left=14, right=22),\n",
" Link(height=426, left=14, right=18)),\n",
" (Link(height=434, left=5, right=19),\n",
" Link(height=435, left=1, right=19),\n",
" Link(height=436, left=5, right=19),\n",
" Link(height=437, left=1, right=19)),\n",
" (Link(height=456, left=0, right=15),\n",
" Link(height=457, left=14, right=15),\n",
" Link(height=458, left=0, right=15),\n",
" Link(height=459, left=14, right=15)),\n",
" (Link(height=550, left=13, right=21),\n",
" Link(height=551, left=6, right=21),\n",
" Link(height=552, left=13, right=21),\n",
" Link(height=553, left=6, right=21)),\n",
" (Link(height=624, left=17, right=23),\n",
" Link(height=625, left=1, right=23),\n",
" Link(height=626, left=17, right=23),\n",
" Link(height=627, left=1, right=23)),\n",
" (Link(height=703, left=8, right=15),\n",
" Link(height=704, left=3, right=15),\n",
" Link(height=705, left=8, right=15),\n",
" Link(height=706, left=3, right=15)),\n",
" (Link(height=794, left=7, right=24),\n",
" Link(height=795, left=8, right=24),\n",
" Link(height=796, left=7, right=24),\n",
" Link(height=797, left=8, right=24)),\n",
" (Link(height=800, left=8, right=13),\n",
" Link(height=801, left=4, right=8),\n",
" Link(height=802, left=8, right=13),\n",
" Link(height=803, left=4, right=8)),\n",
" (Link(height=814, left=16, right=17),\n",
" Link(height=815, left=3, right=16),\n",
" Link(height=816, left=16, right=17),\n",
" Link(height=817, left=3, right=16)),\n",
" (Link(height=905, left=2, right=15),\n",
" Link(height=906, left=13, right=15),\n",
" Link(height=907, left=2, right=15),\n",
" Link(height=908, left=13, right=15)),\n",
" (Link(height=926, left=2, right=15),\n",
" Link(height=927, left=15, right=16),\n",
" Link(height=928, left=2, right=15),\n",
" Link(height=929, left=15, right=16)),\n",
" (Link(height=967, left=2, right=15),\n",
" Link(height=968, left=2, right=14),\n",
" Link(height=969, left=2, right=15),\n",
" Link(height=970, left=2, right=14)),\n",
" (Link(height=982, left=13, right=18),\n",
" Link(height=985, left=18, right=19),\n",
" Link(height=986, left=13, right=18),\n",
" Link(height=987, left=18, right=19)),\n",
" (Link(height=993, left=5, right=16),\n",
" Link(height=994, left=2, right=5),\n",
" Link(height=995, left=5, right=16),\n",
" Link(height=996, left=2, right=5)),\n",
" (Link(height=1058, left=9, right=24),\n",
" Link(height=1062, left=9, right=18),\n",
" Link(height=1063, left=9, right=24),\n",
" Link(height=1064, left=9, right=18)),\n",
" (Link(height=1171, left=11, right=21),\n",
" Link(height=1172, left=11, right=14),\n",
" Link(height=1173, left=11, right=21),\n",
" Link(height=1174, left=11, right=14)),\n",
" (Link(height=1294, left=0, right=11),\n",
" Link(height=1295, left=0, right=14),\n",
" Link(height=1296, left=0, right=11),\n",
" Link(height=1297, left=0, right=14)),\n",
" (Link(height=1341, left=4, right=9),\n",
" Link(height=1343, left=4, right=10),\n",
" Link(height=1344, left=4, right=9),\n",
" Link(height=1345, left=4, right=10)),\n",
" (Link(height=1342, left=12, right=18),\n",
" Link(height=1343, left=12, right=24),\n",
" Link(height=1344, left=12, right=18),\n",
" Link(height=1345, left=12, right=24)),\n",
" (Link(height=1353, left=0, right=17),\n",
" Link(height=1354, left=0, right=23),\n",
" Link(height=1355, left=0, right=17),\n",
" Link(height=1356, left=0, right=23)),\n",
" (Link(height=1367, left=4, right=16),\n",
" Link(height=1368, left=16, right=17),\n",
" Link(height=1369, left=4, right=16),\n",
" Link(height=1370, left=16, right=17)),\n",
" (Link(height=1441, left=11, right=24),\n",
" Link(height=1442, left=18, right=24),\n",
" Link(height=1443, left=11, right=24),\n",
" Link(height=1444, left=18, right=24)),\n",
" (Link(height=1451, left=6, right=20),\n",
" Link(height=1453, left=16, right=20),\n",
" Link(height=1454, left=6, right=20),\n",
" Link(height=1455, left=16, right=20)),\n",
" (Link(height=1474, left=17, right=23),\n",
" Link(height=1475, left=3, right=17),\n",
" Link(height=1476, left=17, right=23),\n",
" Link(height=1477, left=3, right=17)),\n",
" (Link(height=1550, left=8, right=23),\n",
" Link(height=1551, left=7, right=23),\n",
" Link(height=1552, left=8, right=23),\n",
" Link(height=1553, left=7, right=23)),\n",
" (Link(height=1574, left=4, right=14),\n",
" Link(height=1575, left=14, right=23),\n",
" Link(height=1576, left=4, right=14),\n",
" Link(height=1577, left=14, right=23)),\n",
" (Link(height=1580, left=0, right=1),\n",
" Link(height=1581, left=1, right=21),\n",
" Link(height=1582, left=0, right=1),\n",
" Link(height=1583, left=1, right=21)),\n",
" (Link(height=1612, left=15, right=22),\n",
" Link(height=1617, left=7, right=15),\n",
" Link(height=1618, left=15, right=22),\n",
" Link(height=1619, left=7, right=15)),\n",
" (Link(height=1644, left=12, right=18),\n",
" Link(height=1646, left=12, right=20),\n",
" Link(height=1647, left=12, right=18),\n",
" Link(height=1648, left=12, right=20)),\n",
" (Link(height=1716, left=13, right=24),\n",
" Link(height=1719, left=14, right=24),\n",
" Link(height=1720, left=13, right=24),\n",
" Link(height=1721, left=14, right=24)),\n",
" (Link(height=1735, left=3, right=24),\n",
" Link(height=1736, left=3, right=21),\n",
" Link(height=1737, left=3, right=24),\n",
" Link(height=1738, left=3, right=21)),\n",
" (Link(height=1736, left=3, right=21),\n",
" Link(height=1737, left=3, right=24),\n",
" Link(height=1738, left=3, right=21),\n",
" Link(height=1739, left=3, right=24)),\n",
" (Link(height=1776, left=0, right=21),\n",
" Link(height=1777, left=13, right=21),\n",
" Link(height=1778, left=0, right=21),\n",
" Link(height=1779, left=13, right=21)),\n",
" (Link(height=1783, left=7, right=9),\n",
" Link(height=1784, left=7, right=12),\n",
" Link(height=1785, left=7, right=9),\n",
" Link(height=1786, left=7, right=12)),\n",
" (Link(height=1929, left=10, right=24),\n",
" Link(height=1930, left=8, right=24),\n",
" Link(height=1931, left=10, right=24),\n",
" Link(height=1932, left=8, right=24)),\n",
" (Link(height=1935, left=4, right=23),\n",
" Link(height=1936, left=3, right=4),\n",
" Link(height=1937, left=4, right=23),\n",
" Link(height=1938, left=3, right=4)),\n",
" (Link(height=2043, left=4, right=7),\n",
" Link(height=2044, left=7, right=15),\n",
" Link(height=2045, left=4, right=7),\n",
" Link(height=2046, left=7, right=15)),\n",
" (Link(height=2045, left=8, right=19),\n",
" Link(height=2051, left=8, right=15),\n",
" Link(height=2052, left=8, right=19),\n",
" Link(height=2053, left=8, right=15)),\n",
" (Link(height=2172, left=10, right=15),\n",
" Link(height=2173, left=10, right=16),\n",
" Link(height=2174, left=10, right=15),\n",
" Link(height=2175, left=10, right=16)),\n",
" (Link(height=2214, left=22, right=24),\n",
" Link(height=2215, left=7, right=22),\n",
" Link(height=2216, left=22, right=24),\n",
" Link(height=2217, left=7, right=22)),\n",
" (Link(height=2231, left=5, right=6),\n",
" Link(height=2232, left=6, right=14),\n",
" Link(height=2233, left=5, right=6),\n",
" Link(height=2234, left=6, right=14))]"
]
},
"execution_count": 93,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lnettp = simple_lnet\n",
"for _ in range(50):\n",
" lnettp = add_pair(lnettp)\n",
"for _ in range(50):\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": 94,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 94,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lnettp == pack(lnettp)"
]
},
{
"cell_type": "code",
"execution_count": 95,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"9931"
]
},
"execution_count": 95,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lnettps = simplify(lnettp)\n",
"len(lnettps)"
]
},
{
"cell_type": "code",
"execution_count": 96,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(9835, 10135, 9931)"
]
},
"execution_count": 96,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(simple_lnet), len(lnettp), len(lnettps)"
]
},
{
"cell_type": "code",
"execution_count": 97,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 97,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, lnet)) == ''.join(follow_many(string.ascii_lowercase, simple_lnet))"
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 98,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, lnettps)) == ''.join(follow_many(string.ascii_lowercase, lnettp))"
]
},
{
"cell_type": "code",
"execution_count": 99,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2286"
]
},
"execution_count": 99,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(l.height for l in lnettp)"
]
},
{
"cell_type": "code",
"execution_count": 100,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def simplify_with_checks(net0):\n",
" netp = eliminate_pairs(net0)\n",
" if follow_many(string.ascii_lowercase, net0) != follow_many(string.ascii_lowercase, netp):\n",
" print('pairs', eliminable_pairs(net0))\n",
" return net0\n",
" else:\n",
" print('pairs ok')\n",
" new_net = eliminate_a_triple_pair(netp)\n",
" if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
" hg = find_height_groups(netp)\n",
" print('triple', triple_pair_hg(hg))\n",
" return netp\n",
" else:\n",
" print('triple ok')\n",
" while new_net:\n",
"# print('sipl', len(net0), len(netp), len(new_net))\n",
" netp = eliminate_pairs(new_net)\n",
" if follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
" print('pairs', eliminable_pairs(new_net))\n",
" return new_net\n",
" else:\n",
" print('pairs ok')\n",
" new_net = eliminate_a_triple_pair(netp)\n",
" if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
" hg = find_height_groups(netp)\n",
" print('triple', triple_pair_hg(hg))\n",
" return netp\n",
" else:\n",
" print('triple ok')\n",
" print('** done')\n",
" return netp"
]
},
{
"cell_type": "code",
"execution_count": 101,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"pairs ok\n",
"triple ok\n",
"** done\n"
]
}
],
"source": [
"lnettps = simplify_with_checks(lnettp)"
]
},
{
"cell_type": "code",
"execution_count": 102,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 102,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, lnettps)) == ''.join(follow_many(string.ascii_lowercase, lnettp))"
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10135"
]
},
"execution_count": 103,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(lnettp)"
]
},
{
"cell_type": "code",
"execution_count": 113,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"83459"
]
},
"execution_count": 113,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"open('04-lines.txt', 'w').write(show_net(lnettp, randomise=True, pair_sep='\\n'))"
]
},
{
"cell_type": "code",
"execution_count": 114,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"139"
]
},
"execution_count": 114,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"open('04-small.txt', 'w').write(show_net(make_net(20), randomise=True, pair_sep='\\n'))"
]
},
{
"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
}