X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=04-08-amidakuji%2Famidakuji-creation.ipynb;fp=04-08-amidakuji%2Famidakuji-creation.ipynb;h=0000000000000000000000000000000000000000;hb=55f602f3ca4d1297233e471706caaad9c7a99b5e;hp=65d9751162ae8e913af95c2d7dff399baa088120;hpb=c1f001553a729b73032babaeb7b900a63704c436;p=ou-summer-of-code-2017.git diff --git a/04-08-amidakuji/amidakuji-creation.ipynb b/04-08-amidakuji/amidakuji-creation.ipynb deleted file mode 100644 index 65d9751..0000000 --- a/04-08-amidakuji/amidakuji-creation.ipynb +++ /dev/null @@ -1,2514 +0,0 @@ -{ - "cells": [ - { - "cell_type": "code", - "execution_count": 36, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "import collections\n", - "import random\n", - "import string\n", - "import itertools" - ] - }, - { - "cell_type": "code", - "execution_count": 37, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "Link = collections.namedtuple('Link', 'height left right')" - ] - }, - { - "cell_type": "code", - "execution_count": 38, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "def link_ends(link):\n", - " return set((link.left, link.right))" - ] - }, - { - "cell_type": "code", - "execution_count": 39, - "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": 40, - "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": 41, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "{Link(height=4, left=0, right=3),\n", - " Link(height=8, left=1, right=5),\n", - " Link(height=16, left=0, right=4),\n", - " Link(height=17, left=1, right=5),\n", - " Link(height=18, left=3, right=5),\n", - " Link(height=20, left=0, right=1),\n", - " Link(height=25, left=0, right=3),\n", - " Link(height=30, left=1, right=4),\n", - " Link(height=33, left=0, right=4),\n", - " Link(height=34, left=4, right=5),\n", - " Link(height=35, left=0, right=3),\n", - " Link(height=36, left=1, right=4),\n", - " Link(height=37, left=2, right=5),\n", - " Link(height=45, left=4, right=5),\n", - " Link(height=46, left=2, right=5)}" - ] - }, - "execution_count": 41, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "net = make_net(15, lines=6)\n", - "net" - ] - }, - { - "cell_type": "code", - "execution_count": 42, - "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": 43, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "3" - ] - }, - "execution_count": 43, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "follow(4, net)" - ] - }, - { - "cell_type": "code", - "execution_count": 44, - "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": 45, - "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": 46, - "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": 47, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "10000 loops, best of 3: 39.2 µs per loop\n" - ] - } - ], - "source": [ - "%%timeit\n", - "follow_many('abcdef', net)" - ] - }, - { - "cell_type": "code", - "execution_count": 48, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "# %%timeit\n", - "# follow_many_slow('abcdefghij', net)" - ] - }, - { - "cell_type": "code", - "execution_count": 49, - "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": 50, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'(0, 3), (1, 5), (0, 4), (1, 5), (3, 5), (0, 1), (0, 3), (1, 4), (0, 4), (4, 5), (0, 3), (1, 4), (2, 5), (4, 5), (2, 5)'" - ] - }, - "execution_count": 50, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "show_net(net)" - ] - }, - { - "cell_type": "code", - "execution_count": 51, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'(0, 3), (1, 5), (0, 4), (1, 5), (3, 5), (0, 1), (0, 3), (1, 4), (0, 4), (4, 5), (0, 3), (1, 4), (2, 5), (4, 5), (2, 5)'" - ] - }, - "execution_count": 51, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "show_net(net, randomise=True)" - ] - }, - { - "cell_type": "code", - "execution_count": 52, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'(0, 3) : (1, 5) : (0, 4) : (1, 5) : (3, 5) : (0, 1) : (0, 3) : (1, 4) : (0, 4) : (4, 5) : (0, 3) : (1, 4) : (2, 5) : (4, 5) : (2, 5)'" - ] - }, - "execution_count": 52, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "show_net(net, pair_sep=' : ')" - ] - }, - { - "cell_type": "code", - "execution_count": 53, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'(0, 3)\\n(1, 5)\\n(0, 4)\\n(1, 5)\\n(3, 5)\\n(0, 1)\\n(0, 3)\\n(1, 4)\\n(0, 4)\\n(4, 5)\\n(0, 3)\\n(1, 4)\\n(2, 5)\\n(4, 5)\\n(2, 5)'" - ] - }, - "execution_count": 53, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "show_net(net, pair_sep='\\n')" - ] - }, - { - "cell_type": "code", - "execution_count": 54, - "metadata": { - "scrolled": true - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "(0, 3)\n", - "(1, 5)\n", - "(0, 4)\n", - "(1, 5)\n", - "(3, 5)\n", - "(0, 1)\n", - "(0, 3)\n", - "(1, 4)\n", - "(0, 4)\n", - "(4, 5)\n", - "(0, 3)\n", - "(1, 4)\n", - "(2, 5)\n", - "(4, 5)\n", - "(2, 5)\n" - ] - } - ], - "source": [ - "print(show_net(net, pair_sep='\\n'))" - ] - }, - { - "cell_type": "code", - "execution_count": 55, - "metadata": {}, - "outputs": [], - "source": [ - "# open('04-small.txt', 'w').write(show_net(net))" - ] - }, - { - "cell_type": "code", - "execution_count": 56, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'(0, 3), (1, 5), (0, 4), (1, 5), (3, 5), (0, 1), (0, 3), (1, 4), (0, 4), (4, 5), (0, 3), (1, 4), (2, 5), (4, 5), (2, 5)'" - ] - }, - "execution_count": 56, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "show_net(net)" - ] - }, - { - "cell_type": "code", - "execution_count": 57, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[]" - ] - }, - "execution_count": 57, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "ls = [l for l in net if l.height == 1]\n", - "ls" - ] - }, - { - "cell_type": "code", - "execution_count": 58, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "random.shuffle(ls)" - ] - }, - { - "cell_type": "code", - "execution_count": 59, - "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": 60, - "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": 61, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "net = read_net('(1, 5), (2, 4), (0, 2), (0, 4), (0, 1), (0, 2), (1, 5), (0, 3), (1, 2), (4, 5), (0, 5), (3, 5), (1, 4), (0, 1), (2, 3)')" - ] - }, - { - "cell_type": "code", - "execution_count": 62, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[Link(height=0, left=1, right=5),\n", - " Link(height=1, left=2, right=4),\n", - " Link(height=2, left=0, right=2),\n", - " Link(height=3, left=0, right=4),\n", - " Link(height=4, left=0, right=1),\n", - " Link(height=5, left=0, right=2),\n", - " Link(height=6, left=1, right=5),\n", - " Link(height=7, left=0, right=3),\n", - " Link(height=8, left=1, right=2),\n", - " Link(height=9, left=4, right=5),\n", - " Link(height=10, left=0, right=5),\n", - " Link(height=11, left=3, right=5),\n", - " Link(height=12, left=1, right=4),\n", - " Link(height=13, left=0, right=1),\n", - " Link(height=14, left=2, right=3)]" - ] - }, - "execution_count": 62, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "read_net(show_net(net))" - ] - }, - { - "cell_type": "code", - "execution_count": 63, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[Link(height=0, left=1, right=5),\n", - " Link(height=0, left=2, right=4),\n", - " Link(height=1, left=0, right=2),\n", - " Link(height=2, left=0, right=4),\n", - " Link(height=3, left=0, right=1),\n", - " Link(height=4, left=0, right=2),\n", - " Link(height=4, left=1, right=5),\n", - " Link(height=5, left=0, right=3),\n", - " Link(height=5, left=1, right=2),\n", - " Link(height=5, left=4, right=5),\n", - " Link(height=6, left=0, right=5),\n", - " Link(height=6, left=1, right=4),\n", - " Link(height=7, left=0, right=1),\n", - " Link(height=7, left=3, right=5),\n", - " Link(height=8, left=2, right=3)]" - ] - }, - "execution_count": 63, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "pack(net)" - ] - }, - { - "cell_type": "code", - "execution_count": 64, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[Link(height=0, left=1, right=5),\n", - " Link(height=0, left=2, right=4),\n", - " Link(height=1, left=0, right=2),\n", - " Link(height=2, left=0, right=4),\n", - " Link(height=3, left=0, right=1),\n", - " Link(height=4, left=0, right=2),\n", - " Link(height=4, left=1, right=5),\n", - " Link(height=5, left=0, right=3),\n", - " Link(height=5, left=1, right=2),\n", - " Link(height=5, left=4, right=5),\n", - " Link(height=6, left=0, right=5),\n", - " Link(height=6, left=1, right=4),\n", - " Link(height=7, left=0, right=1),\n", - " Link(height=7, left=3, right=5),\n", - " Link(height=8, left=2, right=3)]" - ] - }, - "execution_count": 64, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "pack(read_net(show_net(net)))" - ] - }, - { - "cell_type": "code", - "execution_count": 65, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "(True, True)" - ] - }, - "execution_count": 65, - "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": 66, - "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": 67, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "rlnet = read_net(show_net(lnet))\n", - "prlnet = pack(rlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 68, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "2239" - ] - }, - "execution_count": 68, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "max(link.height for link in plnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 69, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "99989" - ] - }, - "execution_count": 69, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "max(link.height for link in lnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 70, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "10206" - ] - }, - "execution_count": 70, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "max(link.height for link in rlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 71, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "2239" - ] - }, - "execution_count": 71, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "max(link.height for link in prlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 72, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, prlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 73, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "10 loops, best of 3: 25.9 ms per loop\n" - ] - } - ], - "source": [ - "%%timeit\n", - "follow_many(string.ascii_lowercase, lnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 74, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "# %%timeit\n", - "# follow_many_slow(string.ascii_lowercase, lnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 75, - "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": 76, - "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": 77, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "10 loops, best of 3: 24.1 ms per loop\n" - ] - } - ], - "source": [ - "%%timeit\n", - "eliminable_pairs(plnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 78, - "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": 79, - "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": 80, - "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": 81, - "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": 82, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "10207\n" - ] - }, - { - "data": { - "text/plain": [ - "(10207, 9813)" - ] - }, - "execution_count": 82, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "print(len(plnet))\n", - "elnet = eliminate_pairs(plnet)\n", - "len(plnet), len(elnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 83, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[]" - ] - }, - "execution_count": 83, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "eliminable_pairs(elnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 84, - "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": 85, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "1 loop, best of 3: 6.08 s per loop\n" - ] - } - ], - "source": [ - "%%timeit\n", - "elnet = eliminate_pairs(plnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 86, - "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": 87, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "# follow(0, plnet), follow(0, elnet), follow(0, lnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 88, - "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": 89, - "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": 90, - "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": 91, - "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": 92, - "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": 93, - "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": 94, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[(Link(height=1126, left=8, right=17),\n", - " Link(height=1127, left=1, right=8),\n", - " Link(height=1128, left=8, right=17),\n", - " Link(height=1129, left=1, right=8)),\n", - " (Link(height=1952, left=12, right=25),\n", - " Link(height=1953, left=10, right=12),\n", - " Link(height=1954, left=12, right=25),\n", - " Link(height=1955, left=10, right=12))]" - ] - }, - "execution_count": 94, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "height_groups = find_height_groups(elnet)\n", - "triple_pair_hg(height_groups)" - ] - }, - { - "cell_type": "code", - "execution_count": 95, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "10 loops, best of 3: 98.7 ms per loop\n" - ] - } - ], - "source": [ - "%%timeit\n", - "height_groups = find_height_groups(elnet)\n", - "triple_pair_hg(height_groups)" - ] - }, - { - "cell_type": "code", - "execution_count": 96, - "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": 97, - "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": 98, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "etlnet = eliminate_a_triple_pair(elnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 99, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 100, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "9813\n", - "9813\n", - "9811\n" - ] - } - ], - "source": [ - "setlnet = eliminate_triple_pairs(elnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 101, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "9809" - ] - }, - "execution_count": 101, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "len(setlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 102, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 103, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'ypetfugkzdsacbvwjohqlnirmx'" - ] - }, - "execution_count": 103, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, etlnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 104, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'ypetfugkzdsacbvwjohqlnirmx'" - ] - }, - "execution_count": 104, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, setlnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 105, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'ypetfugkzdsacbvwjohqlnirmx'" - ] - }, - "execution_count": 105, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, elnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 106, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'ypetfugkzdsacbvwjohqlnirmx'" - ] - }, - "execution_count": 106, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, lnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 107, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[]" - ] - }, - "execution_count": 107, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "eliminable_pairs(etlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 108, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "(10207, 9811)" - ] - }, - "execution_count": 108, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "len(lnet), len(etlnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 109, - "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": 110, - "metadata": { - "collapsed": true - }, - "outputs": [], - "source": [ - "simple_lnet = simplify(plnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 111, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "True" - ] - }, - "execution_count": 111, - "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": 112, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'ypetfugkzdsacbvwjohqlnirmx'" - ] - }, - "execution_count": 112, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, simple_lnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 113, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'ypetfugkzdsacbvwjohqlnirmx'" - ] - }, - "execution_count": 113, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, lnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 114, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "9809" - ] - }, - "execution_count": 114, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "len(simple_lnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 115, - "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": 116, - "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": 117, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[]" - ] - }, - "execution_count": 117, - "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": 118, - "metadata": { - "scrolled": true - }, - "outputs": [ - { - "data": { - "text/plain": [ - "[]" - ] - }, - "execution_count": 118, - "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": 119, - "metadata": { - "scrolled": true - }, - "outputs": [ - { - "data": { - "text/plain": [ - "[(Link(height=301, left=7, right=23),\n", - " Link(height=302, left=16, right=23),\n", - " Link(height=303, left=7, right=23),\n", - " Link(height=304, left=16, right=23)),\n", - " (Link(height=362, left=11, right=23),\n", - " Link(height=363, left=3, right=23),\n", - " Link(height=364, left=11, right=23),\n", - " Link(height=365, left=3, right=23)),\n", - " (Link(height=363, left=3, right=23),\n", - " Link(height=364, left=11, right=23),\n", - " Link(height=365, left=3, right=23),\n", - " Link(height=366, left=11, right=23)),\n", - " (Link(height=595, left=12, right=15),\n", - " Link(height=596, left=10, right=15),\n", - " Link(height=597, left=12, right=15),\n", - " Link(height=598, left=10, right=15)),\n", - " (Link(height=796, left=12, right=21),\n", - " Link(height=797, left=4, right=12),\n", - " Link(height=798, left=12, right=21),\n", - " Link(height=799, left=4, right=12)),\n", - " (Link(height=879, left=0, right=18),\n", - " Link(height=880, left=0, right=8),\n", - " Link(height=881, left=0, right=18),\n", - " Link(height=882, left=0, right=8)),\n", - " (Link(height=930, left=3, right=17),\n", - " Link(height=931, left=3, right=21),\n", - " Link(height=932, left=3, right=17),\n", - " Link(height=933, left=3, right=21)),\n", - " (Link(height=1120, left=5, right=19),\n", - " Link(height=1121, left=18, right=19),\n", - " Link(height=1122, left=5, right=19),\n", - " Link(height=1123, left=18, right=19)),\n", - " (Link(height=2040, left=9, right=21),\n", - " Link(height=2041, left=9, right=15),\n", - " Link(height=2042, left=9, right=21),\n", - " Link(height=2043, left=9, right=15)),\n", - " (Link(height=2110, left=13, right=21),\n", - " Link(height=2111, left=13, right=24),\n", - " Link(height=2112, left=13, right=21),\n", - " Link(height=2113, left=13, right=24))]" - ] - }, - "execution_count": 119, - "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": 120, - "metadata": { - "scrolled": true - }, - "outputs": [ - { - "data": { - "text/plain": [ - "[(Link(height=49, left=10, right=20),\n", - " Link(height=50, left=2, right=20),\n", - " Link(height=51, left=10, right=20),\n", - " Link(height=52, left=2, right=20)),\n", - " (Link(height=54, left=2, right=24),\n", - " Link(height=55, left=3, right=24),\n", - " Link(height=56, left=2, right=24),\n", - " Link(height=57, left=3, right=24)),\n", - " (Link(height=62, left=2, right=15),\n", - " Link(height=63, left=0, right=15),\n", - " Link(height=64, left=2, right=15),\n", - " Link(height=65, left=0, right=15)),\n", - " (Link(height=114, left=14, right=18),\n", - " Link(height=115, left=3, right=18),\n", - " Link(height=116, left=14, right=18),\n", - " Link(height=117, left=3, right=18)),\n", - " (Link(height=138, left=13, right=19),\n", - " Link(height=139, left=8, right=19),\n", - " Link(height=140, left=13, right=19),\n", - " Link(height=141, left=8, right=19)),\n", - " (Link(height=160, left=12, right=13),\n", - " Link(height=161, left=4, right=12),\n", - " Link(height=162, left=12, right=13),\n", - " Link(height=163, left=4, right=12)),\n", - " (Link(height=315, left=23, right=24),\n", - " Link(height=320, left=20, right=23),\n", - " Link(height=321, left=23, right=24),\n", - " Link(height=322, left=20, right=23)),\n", - " (Link(height=324, left=3, right=18),\n", - " Link(height=325, left=16, right=18),\n", - " Link(height=326, left=3, right=18),\n", - " Link(height=327, left=16, right=18)),\n", - " (Link(height=342, left=21, right=22),\n", - " Link(height=345, left=1, right=22),\n", - " Link(height=346, left=21, right=22),\n", - " Link(height=347, left=1, right=22)),\n", - " (Link(height=405, left=8, right=19),\n", - " Link(height=406, left=4, right=8),\n", - " Link(height=407, left=8, right=19),\n", - " Link(height=408, left=4, right=8)),\n", - " (Link(height=468, left=11, right=22),\n", - " Link(height=469, left=15, right=22),\n", - " Link(height=470, left=11, right=22),\n", - " Link(height=471, left=15, right=22)),\n", - " (Link(height=549, left=1, right=2),\n", - " Link(height=550, left=1, right=6),\n", - " Link(height=551, left=1, right=2),\n", - " Link(height=552, left=1, right=6)),\n", - " (Link(height=568, left=16, right=21),\n", - " Link(height=569, left=11, right=21),\n", - " Link(height=570, left=16, right=21),\n", - " Link(height=571, left=11, right=21)),\n", - " (Link(height=608, left=17, right=20),\n", - " Link(height=609, left=2, right=17),\n", - " Link(height=610, left=17, right=20),\n", - " Link(height=611, left=2, right=17)),\n", - " (Link(height=613, left=18, right=21),\n", - " Link(height=618, left=18, right=19),\n", - " Link(height=619, left=18, right=21),\n", - " Link(height=620, left=18, right=19)),\n", - " (Link(height=635, left=2, right=4),\n", - " Link(height=636, left=4, right=20),\n", - " Link(height=637, left=2, right=4),\n", - " Link(height=638, left=4, right=20)),\n", - " (Link(height=681, left=7, right=20),\n", - " Link(height=682, left=20, right=22),\n", - " Link(height=683, left=7, right=20),\n", - " Link(height=684, left=20, right=22)),\n", - " (Link(height=750, left=23, right=24),\n", - " Link(height=751, left=18, right=24),\n", - " Link(height=752, left=23, right=24),\n", - " Link(height=753, left=18, right=24)),\n", - " (Link(height=760, left=12, right=18),\n", - " Link(height=761, left=17, right=18),\n", - " Link(height=762, left=12, right=18),\n", - " Link(height=763, left=17, right=18)),\n", - " (Link(height=765, left=0, right=9),\n", - " Link(height=766, left=0, right=14),\n", - " Link(height=767, left=0, right=9),\n", - " Link(height=768, left=0, right=14)),\n", - " (Link(height=805, left=16, right=22),\n", - " Link(height=806, left=0, right=16),\n", - " Link(height=807, left=16, right=22),\n", - " Link(height=808, left=0, right=16)),\n", - " (Link(height=834, left=1, right=6),\n", - " Link(height=835, left=3, right=6),\n", - " Link(height=836, left=1, right=6),\n", - " Link(height=837, left=3, right=6)),\n", - " (Link(height=881, left=2, right=12),\n", - " Link(height=882, left=2, right=23),\n", - " Link(height=883, left=2, right=12),\n", - " Link(height=884, left=2, right=23)),\n", - " (Link(height=904, left=12, right=23),\n", - " Link(height=905, left=12, right=14),\n", - " Link(height=906, left=12, right=23),\n", - " Link(height=907, left=12, right=14)),\n", - " (Link(height=936, left=7, right=17),\n", - " Link(height=937, left=15, right=17),\n", - " Link(height=938, left=7, right=17),\n", - " Link(height=939, left=15, right=17)),\n", - " (Link(height=1010, left=4, right=6),\n", - " Link(height=1011, left=6, right=17),\n", - " Link(height=1012, left=4, right=6),\n", - " Link(height=1013, left=6, right=17)),\n", - " (Link(height=1030, left=1, right=12),\n", - " Link(height=1031, left=1, right=20),\n", - " Link(height=1032, left=1, right=12),\n", - " Link(height=1033, left=1, right=20)),\n", - " (Link(height=1197, left=2, right=9),\n", - " Link(height=1198, left=9, right=22),\n", - " Link(height=1199, left=2, right=9),\n", - " Link(height=1200, left=9, right=22)),\n", - " (Link(height=1222, left=2, right=3),\n", - " Link(height=1223, left=2, right=5),\n", - " Link(height=1224, left=2, right=3),\n", - " Link(height=1225, left=2, right=5)),\n", - " (Link(height=1318, left=12, right=23),\n", - " Link(height=1319, left=4, right=12),\n", - " Link(height=1320, left=12, right=23),\n", - " Link(height=1321, left=4, right=12)),\n", - " (Link(height=1341, left=17, right=22),\n", - " Link(height=1342, left=11, right=17),\n", - " Link(height=1343, left=17, right=22),\n", - " Link(height=1344, left=11, right=17)),\n", - " (Link(height=1396, left=4, right=9),\n", - " Link(height=1397, left=3, right=9),\n", - " Link(height=1398, left=4, right=9),\n", - " Link(height=1399, left=3, right=9)),\n", - " (Link(height=1426, left=18, right=24),\n", - " Link(height=1427, left=17, right=18),\n", - " Link(height=1428, left=18, right=24),\n", - " Link(height=1429, left=17, right=18)),\n", - " (Link(height=1456, left=2, right=15),\n", - " Link(height=1457, left=3, right=15),\n", - " Link(height=1458, left=2, right=15),\n", - " Link(height=1459, left=3, right=15)),\n", - " (Link(height=1505, left=13, right=18),\n", - " Link(height=1506, left=13, right=21),\n", - " Link(height=1507, left=13, right=18),\n", - " Link(height=1508, left=13, right=21)),\n", - " (Link(height=1551, left=10, right=12),\n", - " Link(height=1552, left=4, right=12),\n", - " Link(height=1553, left=10, right=12),\n", - " Link(height=1554, left=4, right=12)),\n", - " (Link(height=1622, left=4, right=11),\n", - " Link(height=1623, left=11, right=16),\n", - " Link(height=1624, left=4, right=11),\n", - " Link(height=1625, left=11, right=16)),\n", - " (Link(height=1653, left=8, right=24),\n", - " Link(height=1654, left=4, right=8),\n", - " Link(height=1655, left=8, right=24),\n", - " Link(height=1656, left=4, right=8)),\n", - " (Link(height=1688, left=0, right=5),\n", - " Link(height=1689, left=0, right=23),\n", - " Link(height=1690, left=0, right=5),\n", - " Link(height=1691, left=0, right=23)),\n", - " (Link(height=1724, left=10, right=23),\n", - " Link(height=1725, left=10, right=11),\n", - " Link(height=1726, left=10, right=23),\n", - " Link(height=1727, left=10, right=11)),\n", - " (Link(height=1863, left=1, right=12),\n", - " Link(height=1864, left=1, right=13),\n", - " Link(height=1865, left=1, right=12),\n", - " Link(height=1866, left=1, right=13)),\n", - " (Link(height=1873, left=10, right=22),\n", - " Link(height=1874, left=10, right=15),\n", - " Link(height=1875, left=10, right=22),\n", - " Link(height=1876, left=10, right=15)),\n", - " (Link(height=1879, left=18, right=20),\n", - " Link(height=1880, left=17, right=20),\n", - " Link(height=1881, left=18, right=20),\n", - " Link(height=1882, left=17, right=20)),\n", - " (Link(height=1916, left=18, right=19),\n", - " Link(height=1917, left=7, right=18),\n", - " Link(height=1918, left=18, right=19),\n", - " Link(height=1919, left=7, right=18)),\n", - " (Link(height=1961, left=11, right=20),\n", - " Link(height=1962, left=7, right=20),\n", - " Link(height=1963, left=11, right=20),\n", - " Link(height=1964, left=7, right=20)),\n", - " (Link(height=1962, left=9, right=18),\n", - " Link(height=1963, left=18, right=19),\n", - " Link(height=1964, left=9, right=18),\n", - " Link(height=1965, left=18, right=19)),\n", - " (Link(height=2031, left=3, right=6),\n", - " Link(height=2032, left=3, right=4),\n", - " Link(height=2033, left=3, right=6),\n", - " Link(height=2034, left=3, right=4)),\n", - " (Link(height=2077, left=2, right=9),\n", - " Link(height=2078, left=2, right=23),\n", - " Link(height=2079, left=2, right=9),\n", - " Link(height=2080, left=2, right=23)),\n", - " (Link(height=2165, left=1, right=8),\n", - " Link(height=2166, left=4, right=8),\n", - " Link(height=2167, left=1, right=8),\n", - " Link(height=2168, left=4, right=8)),\n", - " (Link(height=2185, left=6, right=21),\n", - " Link(height=2186, left=11, right=21),\n", - " Link(height=2187, left=6, right=21),\n", - " Link(height=2188, left=11, right=21))]" - ] - }, - "execution_count": 120, - "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": 121, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "True" - ] - }, - "execution_count": 121, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "lnettp == pack(lnettp)" - ] - }, - { - "cell_type": "code", - "execution_count": 122, - "metadata": { - "scrolled": true - }, - "outputs": [ - { - "data": { - "text/plain": [ - "9909" - ] - }, - "execution_count": 122, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "lnettps = simplify(lnettp)\n", - "len(lnettps)" - ] - }, - { - "cell_type": "code", - "execution_count": 123, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "(9809, 10109, 9909)" - ] - }, - "execution_count": 123, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "len(simple_lnet), len(lnettp), len(lnettps)" - ] - }, - { - "cell_type": "code", - "execution_count": 124, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "True" - ] - }, - "execution_count": 124, - "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": 125, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "True" - ] - }, - "execution_count": 125, - "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": 126, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "2285" - ] - }, - "execution_count": 126, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "max(l.height for l in lnettp)" - ] - }, - { - "cell_type": "code", - "execution_count": 127, - "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": 128, - "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", - "** done\n" - ] - } - ], - "source": [ - "lnettps = simplify_with_checks(lnettp)" - ] - }, - { - "cell_type": "code", - "execution_count": 129, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "True" - ] - }, - "execution_count": 129, - "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": 130, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "10109" - ] - }, - "execution_count": 130, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "len(lnettp)" - ] - }, - { - "cell_type": "code", - "execution_count": 131, - "metadata": {}, - "outputs": [], - "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": 143, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "8 [(2, 4), (0, 4), (2, 4), (0, 4)]\n", - "10 [(1, 2), (1, 2)]\n" - ] - }, - { - "data": { - "text/plain": [ - "[Link(height=0, left=2, right=5),\n", - " Link(height=1, left=1, right=4),\n", - " Link(height=2, left=0, right=3),\n", - " Link(height=3, left=0, right=3),\n", - " Link(height=4, left=0, right=5),\n", - " Link(height=5, left=3, right=5),\n", - " Link(height=6, left=0, right=2),\n", - " Link(height=7, left=3, right=4),\n", - " Link(height=8, left=2, right=4),\n", - " Link(height=9, left=1, right=2),\n", - " Link(height=10, left=0, right=4),\n", - " Link(height=11, left=1, right=2),\n", - " Link(height=12, left=2, right=4),\n", - " Link(height=13, left=1, right=2),\n", - " Link(height=14, left=0, right=4),\n", - " Link(height=15, left=1, right=4)]" - ] - }, - "execution_count": 143, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "net = make_net(10, lines=6)\n", - "net = add_triple_pair(net, trace=True)\n", - "net = add_pair(net, trace=True)\n", - "net = read_net(show_net(net, randomise=True))\n", - "net" - ] - }, - { - "cell_type": "code", - "execution_count": 147, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "'(2, 5), (1, 4), (0, 3), (0, 3), (0, 5), (3, 5), (0, 2), (3, 4), (2, 4), (1, 2), (0, 4), (1, 2), (2, 4), (1, 2), (0, 4), (1, 4)'" - ] - }, - "execution_count": 147, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "show_net(net)" - ] - }, - { - "cell_type": "code", - "execution_count": 149, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[Link(height=0, left=2, right=5),\n", - " Link(height=1, left=1, right=4),\n", - " Link(height=2, left=0, right=3),\n", - " Link(height=3, left=0, right=3),\n", - " Link(height=4, left=0, right=5),\n", - " Link(height=5, left=3, right=5),\n", - " Link(height=6, left=0, right=2),\n", - " Link(height=7, left=3, right=4),\n", - " Link(height=8, left=2, right=4),\n", - " Link(height=9, left=1, right=2),\n", - " Link(height=10, left=0, right=4),\n", - " Link(height=11, left=1, right=2),\n", - " Link(height=12, left=2, right=4),\n", - " Link(height=13, left=0, right=4),\n", - " Link(height=14, left=1, right=4)]" - ] - }, - "execution_count": 149, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "net = read_net('(2, 5), (1, 4), (0, 3), (0, 3), (0, 5), (3, 5), (0, 2), (3, 4), (2, 4), (1, 2), (0, 4), (1, 2), (2, 4), (0, 4), (1, 4)')\n", - "net" - ] - }, - { - "cell_type": "code", - "execution_count": 150, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[Link(height=0, left=0, right=3),\n", - " Link(height=0, left=1, right=4),\n", - " Link(height=0, left=2, right=5),\n", - " Link(height=1, left=0, right=3),\n", - " Link(height=2, left=0, right=5),\n", - " Link(height=3, left=0, right=2),\n", - " Link(height=3, left=3, right=5),\n", - " Link(height=4, left=3, right=4),\n", - " Link(height=5, left=2, right=4),\n", - " Link(height=6, left=0, right=4),\n", - " Link(height=6, left=1, right=2),\n", - " Link(height=7, left=1, right=2),\n", - " Link(height=8, left=2, right=4),\n", - " Link(height=9, left=0, right=4),\n", - " Link(height=10, left=1, right=4)]" - ] - }, - "execution_count": 150, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "pack(net)" - ] - }, - { - "cell_type": "code", - "execution_count": 151, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "[Link(height=0, left=1, right=4),\n", - " Link(height=0, left=2, right=5),\n", - " Link(height=1, left=0, right=5),\n", - " Link(height=2, left=0, right=2),\n", - " Link(height=2, left=3, right=5),\n", - " Link(height=3, left=3, right=4),\n", - " Link(height=4, left=2, right=4),\n", - " Link(height=5, left=0, right=4),\n", - " Link(height=6, left=2, right=4),\n", - " Link(height=7, left=0, right=4),\n", - " Link(height=8, left=1, right=4)]" - ] - }, - "execution_count": 151, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "epnet = eliminate_pairs(net)\n", - "pack(epnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 152, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "11\n", - "11\n" - ] - }, - { - "data": { - "text/plain": [ - "[Link(height=0, left=1, right=4),\n", - " Link(height=0, left=2, right=5),\n", - " Link(height=1, left=0, right=5),\n", - " Link(height=2, left=0, right=2),\n", - " Link(height=2, left=3, right=5),\n", - " Link(height=3, left=3, right=4),\n", - " Link(height=4, left=0, right=4),\n", - " Link(height=5, left=2, right=4),\n", - " Link(height=6, left=1, right=4)]" - ] - }, - "execution_count": 152, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "eptnet = eliminate_triple_pairs(epnet)\n", - "pack(eptnet)" - ] - }, - { - "cell_type": "code", - "execution_count": 153, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "True" - ] - }, - "execution_count": 153, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "''.join(follow_many(string.ascii_lowercase, net)) == ''.join(follow_many(string.ascii_lowercase, eptnet))" - ] - }, - { - "cell_type": "code", - "execution_count": 155, - "metadata": {}, - "outputs": [ - { - "data": { - "text/plain": [ - "104" - ] - }, - "execution_count": 155, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "open('04-small.txt', 'w').write(show_net(net, 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 -}