X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=04-08-amidakuji%2Famidakuji-solution-2.ipynb;fp=04-08-amidakuji%2Famidakuji-solution-2.ipynb;h=8fc722f25341bd1a5bae61c89d43616206936e1a;hb=787b6246ddfd5d1eaa228cdd11c537096362eb2f;hp=0000000000000000000000000000000000000000;hpb=b39e05e955bfcbc82abd31571d4cff37021b5942;p=ou-summer-of-code-2017.git diff --git a/04-08-amidakuji/amidakuji-solution-2.ipynb b/04-08-amidakuji/amidakuji-solution-2.ipynb new file mode 100644 index 0000000..8fc722f --- /dev/null +++ b/04-08-amidakuji/amidakuji-solution-2.ipynb @@ -0,0 +1,1457 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "import collections\n", + "import string\n", + "import itertools\n", + "import re" + ] + }, + { + "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 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": 4, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def read_net_string(net_string):\n", + " return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def read_net(filename):\n", + " with open(filename) as f:\n", + " pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n", + " lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n", + " return [Link(h, l, r) \n", + " for h, (l, r) in enumerate(lrs)]" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[Link(height=0, left=2, right=3),\n", + " Link(height=1, left=2, right=6),\n", + " Link(height=2, left=3, right=7),\n", + " Link(height=3, left=5, right=6),\n", + " Link(height=4, left=0, right=1),\n", + " Link(height=5, left=0, right=1),\n", + " Link(height=6, left=6, right=7),\n", + " Link(height=7, left=2, right=5),\n", + " Link(height=8, left=6, right=9),\n", + " Link(height=9, left=4, right=8),\n", + " Link(height=10, left=0, right=2),\n", + " Link(height=11, left=5, right=7),\n", + " Link(height=12, left=4, right=8),\n", + " Link(height=13, left=1, right=5),\n", + " Link(height=14, left=6, right=8),\n", + " Link(height=15, left=6, right=9),\n", + " Link(height=16, left=2, right=5),\n", + " Link(height=17, left=1, right=8),\n", + " Link(height=18, left=5, right=7),\n", + " Link(height=19, left=2, right=9)]" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "small_net = read_net('04-small.txt')\n", + "small_net" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "10135" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "net = read_net('04-lines.txt')\n", + "len(net)" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def show_net(links, pair_sep=', '):\n", + " return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def link_ends(link):\n", + " return set((link.left, link.right))" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "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": 11, + "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": 12, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "19" + ] + }, + "execution_count": 12, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max(l.height for l in small_net)" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 13, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max(l.height for l in pack(small_net))" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "10134" + ] + }, + "execution_count": 14, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max(l.height for l in net)" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2286" + ] + }, + "execution_count": 15, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "max(l.height for l in pack(net))" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def 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": 17, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def follow_many(in_sequence, net):\n", + " hgs = height_groups(net)\n", + " seq = list(in_sequence)\n", + " for h in hgs:\n", + " for link in hgs[h]:\n", + " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n", + " return seq" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'djihegcafb'" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many('abcdefghij', small_net))" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "10000 loops, best of 3: 50.2 µs per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "follow_many('abcdefghij', small_net)" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 20, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, net))" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "10 loops, best of 3: 20.7 ms per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "follow_many(string.ascii_lowercase, net)" + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "pnet = pack(net)" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def eliminable_pairs(net):\n", + " hgs = height_groups(net)\n", + " eps = []\n", + " for h in range(1, max(hgs.keys())):\n", + " for l in hgs[h]:\n", + " o = Link(l.height - 1, l.left, l.right)\n", + " if o in hgs[h-1]:\n", + " eps += [(l, o)]\n", + " return eps" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "metadata": { + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[(Link(height=115, left=2, right=23), Link(height=114, left=2, right=23)),\n", + " (Link(height=149, left=15, right=23), Link(height=148, left=15, right=23)),\n", + " (Link(height=201, left=0, right=7), Link(height=200, left=0, right=7)),\n", + " (Link(height=207, left=22, right=23), Link(height=206, left=22, right=23)),\n", + " (Link(height=210, left=17, right=23), Link(height=209, left=17, right=23)),\n", + " (Link(height=247, left=16, right=20), Link(height=246, left=16, right=20)),\n", + " (Link(height=418, left=19, right=24), Link(height=417, left=19, right=24)),\n", + " (Link(height=424, left=9, right=21), Link(height=423, left=9, right=21)),\n", + " (Link(height=453, left=3, right=16), Link(height=452, left=3, right=16)),\n", + " (Link(height=456, left=2, right=22), Link(height=455, left=2, right=22)),\n", + " (Link(height=465, left=18, right=20), Link(height=464, left=18, right=20)),\n", + " (Link(height=491, left=14, right=18), Link(height=490, left=14, right=18)),\n", + " (Link(height=552, left=16, right=17), Link(height=551, left=16, right=17)),\n", + " (Link(height=772, left=0, right=7), Link(height=771, left=0, right=7)),\n", + " (Link(height=848, left=1, right=2), Link(height=847, left=1, right=2)),\n", + " (Link(height=895, left=6, right=21), Link(height=894, left=6, right=21)),\n", + " (Link(height=930, left=11, right=13), Link(height=929, left=11, right=13)),\n", + " (Link(height=987, left=8, right=17), Link(height=986, left=8, right=17)),\n", + " (Link(height=988, left=8, right=17), Link(height=987, left=8, right=17)),\n", + " (Link(height=1030, left=9, right=24), Link(height=1029, left=9, right=24)),\n", + " (Link(height=1134, left=4, right=23), Link(height=1133, left=4, right=23)),\n", + " (Link(height=1163, left=14, right=15), Link(height=1162, left=14, right=15)),\n", + " (Link(height=1164, left=14, right=15), Link(height=1163, left=14, right=15)),\n", + " (Link(height=1170, left=2, right=21), Link(height=1169, left=2, right=21)),\n", + " (Link(height=1232, left=6, right=22), Link(height=1231, left=6, right=22)),\n", + " (Link(height=1254, left=13, right=15), Link(height=1253, left=13, right=15)),\n", + " (Link(height=1255, left=1, right=24), Link(height=1254, left=1, right=24)),\n", + " (Link(height=1324, left=3, right=22), Link(height=1323, left=3, right=22)),\n", + " (Link(height=1370, left=15, right=19), Link(height=1369, left=15, right=19)),\n", + " (Link(height=1441, left=0, right=14), Link(height=1440, left=0, right=14)),\n", + " (Link(height=1441, left=11, right=24), Link(height=1440, left=11, right=24)),\n", + " (Link(height=1547, left=11, right=13), Link(height=1546, left=11, right=13)),\n", + " (Link(height=1578, left=14, right=23), Link(height=1577, left=14, right=23)),\n", + " (Link(height=1616, left=7, right=14), Link(height=1615, left=7, right=14)),\n", + " (Link(height=1671, left=8, right=20), Link(height=1670, left=8, right=20)),\n", + " (Link(height=1684, left=14, right=18), Link(height=1683, left=14, right=18)),\n", + " (Link(height=1717, left=0, right=17), Link(height=1716, left=0, right=17)),\n", + " (Link(height=1727, left=7, right=8), Link(height=1726, left=7, right=8)),\n", + " (Link(height=1866, left=8, right=16), Link(height=1865, left=8, right=16)),\n", + " (Link(height=1911, left=1, right=12), Link(height=1910, left=1, right=12)),\n", + " (Link(height=1966, left=20, right=23), Link(height=1965, left=20, right=23)),\n", + " (Link(height=1974, left=5, right=23), Link(height=1973, left=5, right=23)),\n", + " (Link(height=1994, left=18, right=19), Link(height=1993, left=18, right=19)),\n", + " (Link(height=2005, left=2, right=19), Link(height=2004, left=2, right=19)),\n", + " (Link(height=2031, left=12, right=17), Link(height=2030, left=12, right=17)),\n", + " (Link(height=2108, left=7, right=12), Link(height=2107, left=7, right=12)),\n", + " (Link(height=2137, left=7, right=16), Link(height=2136, left=7, right=16)),\n", + " (Link(height=2138, left=7, right=16), Link(height=2137, left=7, right=16)),\n", + " (Link(height=2229, left=10, right=11), Link(height=2228, left=10, right=11)),\n", + " (Link(height=2239, left=16, right=24), Link(height=2238, left=16, right=24)),\n", + " (Link(height=2240, left=16, right=24), Link(height=2239, left=16, right=24)),\n", + " (Link(height=2246, left=4, right=13), Link(height=2245, left=4, right=13)),\n", + " (Link(height=2247, left=4, right=13), Link(height=2246, left=4, right=13)),\n", + " (Link(height=2276, left=19, right=24), Link(height=2275, left=19, right=24)),\n", + " (Link(height=2277, left=4, right=18), Link(height=2276, left=4, right=18))]" + ] + }, + "execution_count": 24, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "eliminable_pairs(pnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "10 loops, best of 3: 26.4 ms per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "eliminable_pairs(pnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def eliminable_pair(hgs):\n", + " for h in range(1, max(hgs.keys())):\n", + " for l in hgs[h]:\n", + " o = Link(l.height - 1, l.left, l.right)\n", + " if o in hgs[h-1]:\n", + " return l, o\n", + " return None" + ] + }, + { + "cell_type": "code", + "execution_count": 27, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def eliminate_pairs(net):\n", + " hgs = height_groups(pack(net))\n", + " eliminable_links = eliminable_pair(hgs)\n", + " while eliminable_links:\n", + " net = pack(l for l in net if l not in eliminable_links)\n", + " hgs = height_groups(pack(net))\n", + " eliminable_links = eliminable_pair(hgs)\n", + " return net" + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "enet = eliminate_pairs(pnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "assert follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, enet)\n", + "assert follow_many(string.ascii_lowercase, pnet) == follow_many(string.ascii_lowercase, enet)" + ] + }, + { + "cell_type": "code", + "execution_count": 30, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1 loop, best of 3: 2.37 s per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "eliminate_pairs(pnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def triple_pair(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": 32, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def eliminate_a_triple_pair(net, debug=False):\n", + " hgs = height_groups(net)\n", + "\n", + " tps = triple_pair(hgs)\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": 33, + "metadata": {}, + "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=272, left=7, right=13),\n", + " Link(height=273, left=7, right=11),\n", + " Link(height=274, left=7, right=13),\n", + " Link(height=275, left=7, right=11)),\n", + " (Link(height=290, left=14, right=15),\n", + " Link(height=291, left=5, right=15),\n", + " Link(height=292, left=14, right=15),\n", + " Link(height=293, left=5, right=15)),\n", + " (Link(height=387, left=1, right=8),\n", + " Link(height=389, left=8, right=15),\n", + " Link(height=390, left=1, right=8),\n", + " Link(height=391, left=8, right=15)),\n", + " (Link(height=420, left=14, right=22),\n", + " Link(height=422, left=14, right=18),\n", + " Link(height=423, left=14, right=22),\n", + " Link(height=424, left=14, right=18)),\n", + " (Link(height=432, left=5, right=19),\n", + " Link(height=433, left=1, right=19),\n", + " Link(height=434, left=5, right=19),\n", + " Link(height=435, left=1, right=19)),\n", + " (Link(height=454, left=0, right=15),\n", + " Link(height=455, left=14, right=15),\n", + " Link(height=456, left=0, right=15),\n", + " Link(height=457, left=14, right=15)),\n", + " (Link(height=546, left=13, right=21),\n", + " Link(height=547, left=6, right=21),\n", + " Link(height=548, left=13, right=21),\n", + " Link(height=549, left=6, right=21)),\n", + " (Link(height=620, left=17, right=23),\n", + " Link(height=621, left=1, right=23),\n", + " Link(height=622, left=17, right=23),\n", + " Link(height=623, left=1, right=23)),\n", + " (Link(height=699, left=8, right=15),\n", + " Link(height=700, left=3, right=15),\n", + " Link(height=701, left=8, right=15),\n", + " Link(height=702, left=3, right=15)),\n", + " (Link(height=789, left=7, right=24),\n", + " Link(height=790, left=8, right=24),\n", + " Link(height=791, left=7, right=24),\n", + " Link(height=792, left=8, right=24)),\n", + " (Link(height=795, left=8, right=13),\n", + " Link(height=796, left=4, right=8),\n", + " Link(height=797, left=8, right=13),\n", + " Link(height=798, left=4, right=8)),\n", + " (Link(height=809, left=16, right=17),\n", + " Link(height=810, left=3, right=16),\n", + " Link(height=811, left=16, right=17),\n", + " Link(height=812, left=3, right=16)),\n", + " (Link(height=900, left=2, right=15),\n", + " Link(height=901, left=13, right=15),\n", + " Link(height=902, left=2, right=15),\n", + " Link(height=903, left=13, right=15)),\n", + " (Link(height=921, left=2, right=15),\n", + " Link(height=922, left=15, right=16),\n", + " Link(height=923, left=2, right=15),\n", + " Link(height=924, left=15, right=16)),\n", + " (Link(height=961, left=2, right=15),\n", + " Link(height=962, left=2, right=14),\n", + " Link(height=963, left=2, right=15),\n", + " Link(height=964, left=2, right=14)),\n", + " (Link(height=976, left=13, right=18),\n", + " Link(height=979, left=18, right=19),\n", + " Link(height=980, left=13, right=18),\n", + " Link(height=981, left=18, right=19)),\n", + " (Link(height=985, left=5, right=16),\n", + " Link(height=986, left=2, right=5),\n", + " Link(height=987, left=5, right=16),\n", + " Link(height=988, left=2, right=5)),\n", + " (Link(height=1050, left=9, right=24),\n", + " Link(height=1054, left=9, right=18),\n", + " Link(height=1055, left=9, right=24),\n", + " Link(height=1056, left=9, right=18)),\n", + " (Link(height=1159, left=11, right=21),\n", + " Link(height=1160, left=11, right=14),\n", + " Link(height=1161, left=11, right=21),\n", + " Link(height=1162, left=11, right=14)),\n", + " (Link(height=1284, left=0, right=11),\n", + " Link(height=1285, left=0, right=14),\n", + " Link(height=1286, left=0, right=11),\n", + " Link(height=1287, left=0, right=14)),\n", + " (Link(height=1331, left=4, right=9),\n", + " Link(height=1333, left=4, right=10),\n", + " Link(height=1334, left=4, right=9),\n", + " Link(height=1335, left=4, right=10)),\n", + " (Link(height=1332, left=12, right=18),\n", + " Link(height=1333, left=12, right=24),\n", + " Link(height=1334, left=12, right=18),\n", + " Link(height=1335, left=12, right=24)),\n", + " (Link(height=1343, left=0, right=17),\n", + " Link(height=1344, left=0, right=23),\n", + " Link(height=1345, left=0, right=17),\n", + " Link(height=1346, left=0, right=23)),\n", + " (Link(height=1357, left=4, right=16),\n", + " Link(height=1358, left=16, right=17),\n", + " Link(height=1359, left=4, right=16),\n", + " Link(height=1360, left=16, right=17)),\n", + " (Link(height=1441, left=6, right=20),\n", + " Link(height=1443, left=16, right=20),\n", + " Link(height=1444, left=6, right=20),\n", + " Link(height=1445, left=16, right=20)),\n", + " (Link(height=1464, left=17, right=23),\n", + " Link(height=1465, left=3, right=17),\n", + " Link(height=1466, left=17, right=23),\n", + " Link(height=1467, left=3, right=17)),\n", + " (Link(height=1540, left=8, right=23),\n", + " Link(height=1541, left=7, right=23),\n", + " Link(height=1542, left=8, right=23),\n", + " Link(height=1543, left=7, right=23)),\n", + " (Link(height=1570, left=0, right=1),\n", + " Link(height=1571, left=1, right=21),\n", + " Link(height=1572, left=0, right=1),\n", + " Link(height=1573, left=1, right=21)),\n", + " (Link(height=1600, left=15, right=22),\n", + " Link(height=1603, left=7, right=15),\n", + " Link(height=1604, left=15, right=22),\n", + " Link(height=1605, left=7, right=15)),\n", + " (Link(height=1632, left=12, right=18),\n", + " Link(height=1634, left=12, right=20),\n", + " Link(height=1635, left=12, right=18),\n", + " Link(height=1636, left=12, right=20)),\n", + " (Link(height=1702, left=13, right=24),\n", + " Link(height=1705, left=14, right=24),\n", + " Link(height=1706, left=13, right=24),\n", + " Link(height=1707, left=14, right=24)),\n", + " (Link(height=1721, left=3, right=24),\n", + " Link(height=1722, left=3, right=21),\n", + " Link(height=1723, left=3, right=24),\n", + " Link(height=1724, left=3, right=21)),\n", + " (Link(height=1722, left=3, right=21),\n", + " Link(height=1723, left=3, right=24),\n", + " Link(height=1724, left=3, right=21),\n", + " Link(height=1725, left=3, right=24)),\n", + " (Link(height=1762, left=0, right=21),\n", + " Link(height=1763, left=13, right=21),\n", + " Link(height=1764, left=0, right=21),\n", + " Link(height=1765, left=13, right=21)),\n", + " (Link(height=1769, left=7, right=9),\n", + " Link(height=1770, left=7, right=12),\n", + " Link(height=1771, left=7, right=9),\n", + " Link(height=1772, left=7, right=12)),\n", + " (Link(height=1914, left=10, right=24),\n", + " Link(height=1915, left=8, right=24),\n", + " Link(height=1916, left=10, right=24),\n", + " Link(height=1917, left=8, right=24)),\n", + " (Link(height=1920, left=4, right=23),\n", + " Link(height=1921, left=3, right=4),\n", + " Link(height=1922, left=4, right=23),\n", + " Link(height=1923, left=3, right=4)),\n", + " (Link(height=2023, left=4, right=7),\n", + " Link(height=2024, left=7, right=15),\n", + " Link(height=2025, left=4, right=7),\n", + " Link(height=2026, left=7, right=15)),\n", + " (Link(height=2025, left=8, right=19),\n", + " Link(height=2031, left=8, right=15),\n", + " Link(height=2032, left=8, right=19),\n", + " Link(height=2033, left=8, right=15)),\n", + " (Link(height=2152, left=10, right=15),\n", + " Link(height=2153, left=10, right=16),\n", + " Link(height=2154, left=10, right=15),\n", + " Link(height=2155, left=10, right=16)),\n", + " (Link(height=2194, left=22, right=24),\n", + " Link(height=2195, left=7, right=22),\n", + " Link(height=2196, left=22, right=24),\n", + " Link(height=2197, left=7, right=22)),\n", + " (Link(height=2211, left=5, right=6),\n", + " Link(height=2212, left=6, right=14),\n", + " Link(height=2213, left=5, right=6),\n", + " Link(height=2214, left=6, right=14))]" + ] + }, + "execution_count": 33, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "hgs = height_groups(enet)\n", + "triple_pair(hgs)" + ] + }, + { + "cell_type": "code", + "execution_count": 34, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "etnet = eliminate_a_triple_pair(enet)" + ] + }, + { + "cell_type": "code", + "execution_count": 35, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "assert follow_many(string.ascii_lowercase, etnet) == follow_many(string.ascii_lowercase, enet)" + ] + }, + { + "cell_type": "code", + "execution_count": 36, + "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": 37, + "metadata": { + "scrolled": true + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "10033\n", + "10033\n", + "10031\n", + "10029\n", + "10027\n", + "10025\n", + "10023\n", + "10021\n", + "10019\n", + "10017\n", + "10015\n", + "10013\n", + "10011\n", + "10009\n", + "10007\n", + "10005\n", + "10003\n", + "10001\n", + "9999\n", + "9997\n", + "9995\n", + "9993\n", + "9991\n", + "9989\n", + "9987\n", + "9985\n", + "9983\n", + "9981\n", + "9979\n", + "9977\n", + "9975\n", + "9973\n", + "9971\n", + "9969\n", + "9967\n", + "9965\n", + "9963\n", + "9961\n", + "9959\n", + "9957\n", + "9955\n", + "9953\n", + "9951\n", + "9949\n", + "9947\n", + "9945\n", + "9943\n", + "9941\n", + "9939\n" + ] + } + ], + "source": [ + "setnet = eliminate_triple_pairs(enet)" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "9937" + ] + }, + "execution_count": 38, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(setnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "assert follow_many(string.ascii_lowercase, etnet) == follow_many(string.ascii_lowercase, enet)" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 40, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, etnet))" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 41, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, setnet))" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 42, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, enet))" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 43, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, net))" + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[]" + ] + }, + "execution_count": 44, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "eliminable_pairs(etnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 45, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(10135, 10031)" + ] + }, + "execution_count": 45, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(net), len(etnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 46, + "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": 47, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "simple_net = simplify(pnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, simple_net)) == ''.join(follow_many(string.ascii_lowercase, net))" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 49, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, simple_net))" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'doqzmbishkwunvltpcexyjgfra'" + ] + }, + "execution_count": 50, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, net))" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "9931" + ] + }, + "execution_count": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(simple_net)" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "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": 53, + "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": [ + "spnet = simplify_with_checks(pnet)" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "True" + ] + }, + "execution_count": 54, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "''.join(follow_many(string.ascii_lowercase, spnet)) == ''.join(follow_many(string.ascii_lowercase, net))" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "9931" + ] + }, + "execution_count": 55, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(spnet)" + ] + }, + { + "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 +}