11 "import collections\n",
19 "execution_count": 37,
25 "Link = collections.namedtuple('Link', 'height left right')"
30 "execution_count": 38,
36 "def link_ends(link):\n",
37 " return set((link.left, link.right))"
42 "execution_count": 39,
48 "def can_add(link, links):\n",
49 " ends = link_ends(link)\n",
50 " same_height_links = [l for l in links if l.height == link.height]\n",
51 " return all(ends.isdisjoint(link_ends(l)) for l in same_height_links)"
56 "execution_count": 40,
62 "def make_net(num_links, lines=10, height=50):\n",
64 " while len(links) < num_links:\n",
65 " a = random.randrange(lines)\n",
66 " b = random.randrange(lines)\n",
70 " h = random.randrange(height)\n",
71 " link = Link(h, l, r)\n",
72 " if can_add(link, links):\n",
79 "execution_count": 41,
85 "{Link(height=4, left=0, right=3),\n",
86 " Link(height=8, left=1, right=5),\n",
87 " Link(height=16, left=0, right=4),\n",
88 " Link(height=17, left=1, right=5),\n",
89 " Link(height=18, left=3, right=5),\n",
90 " Link(height=20, left=0, right=1),\n",
91 " Link(height=25, left=0, right=3),\n",
92 " Link(height=30, left=1, right=4),\n",
93 " Link(height=33, left=0, right=4),\n",
94 " Link(height=34, left=4, right=5),\n",
95 " Link(height=35, left=0, right=3),\n",
96 " Link(height=36, left=1, right=4),\n",
97 " Link(height=37, left=2, right=5),\n",
98 " Link(height=45, left=4, right=5),\n",
99 " Link(height=46, left=2, right=5)}"
102 "execution_count": 41,
104 "output_type": "execute_result"
108 "net = make_net(15, lines=6)\n",
114 "execution_count": 42,
120 "def follow(initial_line, links):\n",
121 " line = initial_line\n",
122 " heights = sorted(set(l.height for l in links))\n",
123 " for h in heights:\n",
124 " for l in [l for l in links if l.height == h]:\n",
125 " if line in link_ends(l):\n",
126 " line = [e for e in link_ends(l) if e != line][0]\n",
127 "# print(l, line)\n",
133 "execution_count": 43,
142 "execution_count": 43,
144 "output_type": "execute_result"
153 "execution_count": 44,
160 " packed_links = []\n",
161 " line_heights = collections.defaultdict(lambda: -1)\n",
162 " for link in sorted(net):\n",
163 " link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
164 " line_heights[link.left] = link_height\n",
165 " line_heights[link.right] = link_height\n",
166 " packed_links += [Link(link_height, link.left, link.right)]\n",
167 " return sorted(packed_links)"
172 "execution_count": 45,
178 "def follow_many_slow(in_sequence, links):\n",
179 " out_sequence = [(follow(i, links), term) \n",
180 " for i, term in enumerate(in_sequence)]\n",
181 " return [term for i, term in sorted(out_sequence)]"
186 "execution_count": 46,
192 "def follow_many(in_sequence, net):\n",
193 " height_groups = [list(g) for _, g in itertools.groupby(pack(net), lambda l: l.height)]\n",
194 " seq = list(in_sequence)\n",
195 " for links in height_groups:\n",
196 " for link in links:\n",
197 "# l = seq[link.left]\n",
198 "# r = seq[link.right]\n",
199 "# seq[link.right] = l\n",
200 "# seq[link.left] = r\n",
201 " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
207 "execution_count": 47,
212 "output_type": "stream",
214 "10000 loops, best of 3: 39.2 µs per loop\n"
220 "follow_many('abcdef', net)"
225 "execution_count": 48,
232 "# follow_many_slow('abcdefghij', net)"
237 "execution_count": 49,
243 "def show_net(links, randomise=False, pair_sep=', '):\n",
246 " heights = sorted(set(l.height for l in links))\n",
247 " for h in heights:\n",
248 " ls = [l for l in links if l.height == h]\n",
249 " random.shuffle(ls)\n",
250 " output += ['({}, {})'.format(l.left, l.right) for l in ls]\n",
251 " return pair_sep.join(output)\n",
252 " return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
257 "execution_count": 50,
263 "'(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)'"
266 "execution_count": 50,
268 "output_type": "execute_result"
277 "execution_count": 51,
283 "'(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)'"
286 "execution_count": 51,
288 "output_type": "execute_result"
292 "show_net(net, randomise=True)"
297 "execution_count": 52,
303 "'(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)'"
306 "execution_count": 52,
308 "output_type": "execute_result"
312 "show_net(net, pair_sep=' : ')"
317 "execution_count": 53,
323 "'(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)'"
326 "execution_count": 53,
328 "output_type": "execute_result"
332 "show_net(net, pair_sep='\\n')"
337 "execution_count": 54,
344 "output_type": "stream",
365 "print(show_net(net, pair_sep='\\n'))"
370 "execution_count": 55,
374 "# open('04-small.txt', 'w').write(show_net(net))"
379 "execution_count": 56,
385 "'(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)'"
388 "execution_count": 56,
390 "output_type": "execute_result"
399 "execution_count": 57,
408 "execution_count": 57,
410 "output_type": "execute_result"
414 "ls = [l for l in net if l.height == 1]\n",
420 "execution_count": 58,
431 "execution_count": 59,
437 "def read_net(net_string):\n",
438 " return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
443 "execution_count": 60,
449 "def extract_pairs(net_string):\n",
450 " return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
455 "execution_count": 61,
461 "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)')"
466 "execution_count": 62,
472 "[Link(height=0, left=1, right=5),\n",
473 " Link(height=1, left=2, right=4),\n",
474 " Link(height=2, left=0, right=2),\n",
475 " Link(height=3, left=0, right=4),\n",
476 " Link(height=4, left=0, right=1),\n",
477 " Link(height=5, left=0, right=2),\n",
478 " Link(height=6, left=1, right=5),\n",
479 " Link(height=7, left=0, right=3),\n",
480 " Link(height=8, left=1, right=2),\n",
481 " Link(height=9, left=4, right=5),\n",
482 " Link(height=10, left=0, right=5),\n",
483 " Link(height=11, left=3, right=5),\n",
484 " Link(height=12, left=1, right=4),\n",
485 " Link(height=13, left=0, right=1),\n",
486 " Link(height=14, left=2, right=3)]"
489 "execution_count": 62,
491 "output_type": "execute_result"
495 "read_net(show_net(net))"
500 "execution_count": 63,
506 "[Link(height=0, left=1, right=5),\n",
507 " Link(height=0, left=2, right=4),\n",
508 " Link(height=1, left=0, right=2),\n",
509 " Link(height=2, left=0, right=4),\n",
510 " Link(height=3, left=0, right=1),\n",
511 " Link(height=4, left=0, right=2),\n",
512 " Link(height=4, left=1, right=5),\n",
513 " Link(height=5, left=0, right=3),\n",
514 " Link(height=5, left=1, right=2),\n",
515 " Link(height=5, left=4, right=5),\n",
516 " Link(height=6, left=0, right=5),\n",
517 " Link(height=6, left=1, right=4),\n",
518 " Link(height=7, left=0, right=1),\n",
519 " Link(height=7, left=3, right=5),\n",
520 " Link(height=8, left=2, right=3)]"
523 "execution_count": 63,
525 "output_type": "execute_result"
534 "execution_count": 64,
540 "[Link(height=0, left=1, right=5),\n",
541 " Link(height=0, left=2, right=4),\n",
542 " Link(height=1, left=0, right=2),\n",
543 " Link(height=2, left=0, right=4),\n",
544 " Link(height=3, left=0, right=1),\n",
545 " Link(height=4, left=0, right=2),\n",
546 " Link(height=4, left=1, right=5),\n",
547 " Link(height=5, left=0, right=3),\n",
548 " Link(height=5, left=1, right=2),\n",
549 " Link(height=5, left=4, right=5),\n",
550 " Link(height=6, left=0, right=5),\n",
551 " Link(height=6, left=1, right=4),\n",
552 " Link(height=7, left=0, right=1),\n",
553 " Link(height=7, left=3, right=5),\n",
554 " Link(height=8, left=2, right=3)]"
557 "execution_count": 64,
559 "output_type": "execute_result"
563 "pack(read_net(show_net(net)))"
568 "execution_count": 65,
577 "execution_count": 65,
579 "output_type": "execute_result"
583 "pnet = pack(net)\n",
584 "rrnet = read_net(show_net(net, randomise=True))\n",
585 "rnet = read_net(show_net(net))\n",
586 "rnet == rrnet, pack(rrnet) == pnet"
591 "execution_count": 66,
597 "lnet = make_net(10207, 26, 100000)\n",
598 "plnet = pack(lnet)\n",
599 "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, plnet)\n",
600 "# for i in range(204):\n",
601 "# assert follow(i, lnet) == follow(i, plnet)"
606 "execution_count": 67,
612 "rlnet = read_net(show_net(lnet))\n",
613 "prlnet = pack(rlnet)"
618 "execution_count": 68,
627 "execution_count": 68,
629 "output_type": "execute_result"
633 "max(link.height for link in plnet)"
638 "execution_count": 69,
647 "execution_count": 69,
649 "output_type": "execute_result"
653 "max(link.height for link in lnet)"
658 "execution_count": 70,
667 "execution_count": 70,
669 "output_type": "execute_result"
673 "max(link.height for link in rlnet)"
678 "execution_count": 71,
687 "execution_count": 71,
689 "output_type": "execute_result"
693 "max(link.height for link in prlnet)"
698 "execution_count": 72,
704 "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, prlnet)"
709 "execution_count": 73,
714 "output_type": "stream",
716 "10 loops, best of 3: 25.9 ms per loop\n"
722 "follow_many(string.ascii_lowercase, lnet)"
727 "execution_count": 74,
734 "# follow_many_slow(string.ascii_lowercase, lnet)"
739 "execution_count": 75,
745 "def eliminable_pairs_slow(net):\n",
748 " o = Link(l.height + 1, l.left, l.right)\n",
750 " eps += [(l, o)]\n",
756 "execution_count": 76,
762 "def eliminable_pairs(net):\n",
763 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
765 " for h in range(1, max(height_groups.keys())):\n",
766 " for l in height_groups[h]:\n",
767 " o = Link(l.height - 1, l.left, l.right)\n",
768 " if o in height_groups[h-1]:\n",
769 " eps += [(l, o)]\n",
775 "execution_count": 77,
780 "output_type": "stream",
782 "10 loops, best of 3: 24.1 ms per loop\n"
788 "eliminable_pairs(plnet)"
793 "execution_count": 78,
799 "def eliminable_pair(net):\n",
801 " o = Link(l.height + 1, l.left, l.right)\n",
809 "execution_count": 79,
815 "def eliminable_pair_hg(height_groups):\n",
816 " for h in range(1, max(height_groups.keys())):\n",
817 " for l in height_groups[h]:\n",
818 " o = Link(l.height - 1, l.left, l.right)\n",
819 " if o in height_groups[h-1]:\n",
826 "execution_count": 80,
832 "def eliminate_pairs_slow(net):\n",
833 " eliminable_links = eliminable_pair(net)\n",
834 " while eliminable_links:\n",
835 " net = pack(l for l in net if l not in eliminable_links)\n",
836 " eliminable_links = eliminable_pair(net)\n",
842 "execution_count": 81,
848 "def eliminate_pairs(net):\n",
849 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
850 " eliminable_links = eliminable_pair_hg(height_groups)\n",
851 " while eliminable_links:\n",
852 " net = pack(l for l in net if l not in eliminable_links)\n",
853 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
854 " eliminable_links = eliminable_pair_hg(height_groups)\n",
860 "execution_count": 82,
865 "output_type": "stream",
876 "execution_count": 82,
878 "output_type": "execute_result"
882 "print(len(plnet))\n",
883 "elnet = eliminate_pairs(plnet)\n",
884 "len(plnet), len(elnet)"
889 "execution_count": 83,
898 "execution_count": 83,
900 "output_type": "execute_result"
904 "eliminable_pairs(elnet)"
909 "execution_count": 84,
915 "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, elnet)\n",
916 "assert follow_many(string.ascii_lowercase, plnet) == follow_many(string.ascii_lowercase, elnet)"
921 "execution_count": 85,
926 "output_type": "stream",
928 "1 loop, best of 3: 6.08 s per loop\n"
934 "elnet = eliminate_pairs(plnet)"
939 "execution_count": 86,
945 "# for i in range(26):\n",
946 "# assert follow(i, plnet) == follow(i, elnet)\n",
947 "# assert follow(i, lnet) == follow(i, elnet)"
952 "execution_count": 87,
958 "# follow(0, plnet), follow(0, elnet), follow(0, lnet)"
963 "execution_count": 88,
969 "def triple_slow(net):\n",
974 " bs = [l for l in net if l.height == a.height + 1 \n",
975 " if l.left == a.right or l.right == a.left]\n",
977 " c = Link(a.height + 2, a.left, a.right)\n",
979 " ts += [(a, b, c)]\n",
985 "execution_count": 89,
991 "def triple_pair_slow(net):\n",
994 " a_ends = link_ends(a)\n",
995 " bs = [l for l in net if l.height == a.height + 1 \n",
996 " if link_ends(l) & a_ends]\n",
997 " if len(bs) == 1:\n",
999 " lines = set((a.left, a.right, b.left, b.right))\n",
1000 " cs = [l for l in net \n",
1001 " if l.height == a.height + 2\n",
1002 " if link_ends(l) & lines]\n",
1003 " if len(cs) == 1:\n",
1004 " c = Link(a.height + 2, a.left, a.right)\n",
1006 " ds = [l for l in net \n",
1007 " if l.height == a.height + 3\n",
1008 " if link_ends(l) & lines]\n",
1009 " d = Link(a.height + 3, b.left, b.right)\n",
1011 " ts += [(a, b, c, d)]\n",
1016 "cell_type": "code",
1017 "execution_count": 90,
1023 "def find_height_groups(net):\n",
1024 " return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
1028 "cell_type": "code",
1029 "execution_count": 91,
1035 "def triple_pair_hg(height_groups, debug=False):\n",
1037 " for h in range(3, max(height_groups.keys())):\n",
1038 " for d in height_groups[h]:\n",
1039 " if debug: print('d:', d)\n",
1041 " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
1042 " if debug: print('cs:', cs)\n",
1043 " while ch > 2 and not cs:\n",
1045 " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
1046 " if debug: print('cs:', cs)\n",
1047 " if len(cs) == 1:\n",
1049 " lines = set((d.left, d.right, c.left, c.right))\n",
1050 " if debug: print('c:', '; lines:', lines)\n",
1051 " bs = [l for l in height_groups[ch-1] if link_ends(l) & lines]\n",
1052 " b = Link(ch - 1, d.left, d.right)\n",
1053 " if debug: print('b:', b, '; bs:', bs)\n",
1054 " if len(bs) == 1 and b in bs:\n",
1055 " ah = b.height - 1\n",
1056 " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
1057 " if debug: print('ah:', ah, '; als:', als)\n",
1058 " while ah > 0 and not als:\n",
1060 " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
1061 " if debug: print('ah:', ah, '; als:', als)\n",
1062 " a = Link(ah, c.left, c.right)\n",
1063 " if debug: print('a:', a)\n",
1065 " if debug: print('adding:', a, b, c, d)\n",
1066 " ts += [(a, b, c, d)]\n",
1071 "cell_type": "code",
1072 "execution_count": 92,
1078 "def eliminate_a_triple_pair_slow(net, debug=False):\n",
1079 " tps = triple_pair_slow(net)\n",
1080 " if debug: print('eatp', tps)\n",
1083 " a, b, c, d = tps[0]\n",
1084 "# x = Link(a.height, b.left, b.right)\n",
1085 "# y = Link(b.height, a.left, a.right)\n",
1086 " x = Link(b.height - 0.5, b.left, b.right)\n",
1087 " y = Link(b.height, a.left, a.right)\n",
1088 " if debug: print('removing', a, b, c, d, '; adding', x, y)\n",
1089 " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
1094 "cell_type": "code",
1095 "execution_count": 93,
1101 "def eliminate_a_triple_pair(net, debug=False):\n",
1102 " height_groups = find_height_groups(net)\n",
1104 " tps = triple_pair_hg(height_groups)\n",
1105 " if debug: print('eatp', tps)\n",
1107 " a, b, c, d = tps[0]\n",
1108 " x = Link(b.height - 0.5, b.left, b.right)\n",
1109 " y = Link(b.height, a.left, a.right)\n",
1110 " if debug: print('removing', a, b, c, d, '; adding', x, y)\n",
1111 " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
1116 "cell_type": "code",
1117 "execution_count": 94,
1123 "[(Link(height=1126, left=8, right=17),\n",
1124 " Link(height=1127, left=1, right=8),\n",
1125 " Link(height=1128, left=8, right=17),\n",
1126 " Link(height=1129, left=1, right=8)),\n",
1127 " (Link(height=1952, left=12, right=25),\n",
1128 " Link(height=1953, left=10, right=12),\n",
1129 " Link(height=1954, left=12, right=25),\n",
1130 " Link(height=1955, left=10, right=12))]"
1133 "execution_count": 94,
1135 "output_type": "execute_result"
1139 "height_groups = find_height_groups(elnet)\n",
1140 "triple_pair_hg(height_groups)"
1144 "cell_type": "code",
1145 "execution_count": 95,
1150 "output_type": "stream",
1152 "10 loops, best of 3: 98.7 ms per loop\n"
1158 "height_groups = find_height_groups(elnet)\n",
1159 "triple_pair_hg(height_groups)"
1163 "cell_type": "code",
1164 "execution_count": 96,
1170 "def eliminate_triple_pairs_slow(net):\n",
1171 " print(len(net))\n",
1172 " new_net = eliminate_a_triple_pair_slow(net)\n",
1173 " while new_net:\n",
1174 " print(len(net))\n",
1176 " new_net = eliminate_a_triple_pair_slow(net)\n",
1181 "cell_type": "code",
1182 "execution_count": 97,
1188 "def eliminate_triple_pairs(net):\n",
1189 " print(len(net))\n",
1190 " new_net = eliminate_a_triple_pair(net)\n",
1191 " while new_net:\n",
1192 " print(len(net))\n",
1194 " new_net = eliminate_a_triple_pair(net)\n",
1199 "cell_type": "code",
1200 "execution_count": 98,
1206 "etlnet = eliminate_a_triple_pair(elnet)"
1210 "cell_type": "code",
1211 "execution_count": 99,
1217 "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
1221 "cell_type": "code",
1222 "execution_count": 100,
1227 "output_type": "stream",
1236 "setlnet = eliminate_triple_pairs(elnet)"
1240 "cell_type": "code",
1241 "execution_count": 101,
1250 "execution_count": 101,
1252 "output_type": "execute_result"
1260 "cell_type": "code",
1261 "execution_count": 102,
1267 "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
1271 "cell_type": "code",
1272 "execution_count": 103,
1278 "'ypetfugkzdsacbvwjohqlnirmx'"
1281 "execution_count": 103,
1283 "output_type": "execute_result"
1287 "''.join(follow_many(string.ascii_lowercase, etlnet))"
1291 "cell_type": "code",
1292 "execution_count": 104,
1298 "'ypetfugkzdsacbvwjohqlnirmx'"
1301 "execution_count": 104,
1303 "output_type": "execute_result"
1307 "''.join(follow_many(string.ascii_lowercase, setlnet))"
1311 "cell_type": "code",
1312 "execution_count": 105,
1318 "'ypetfugkzdsacbvwjohqlnirmx'"
1321 "execution_count": 105,
1323 "output_type": "execute_result"
1327 "''.join(follow_many(string.ascii_lowercase, elnet))"
1331 "cell_type": "code",
1332 "execution_count": 106,
1338 "'ypetfugkzdsacbvwjohqlnirmx'"
1341 "execution_count": 106,
1343 "output_type": "execute_result"
1347 "''.join(follow_many(string.ascii_lowercase, lnet))"
1351 "cell_type": "code",
1352 "execution_count": 107,
1361 "execution_count": 107,
1363 "output_type": "execute_result"
1367 "eliminable_pairs(etlnet)"
1371 "cell_type": "code",
1372 "execution_count": 108,
1381 "execution_count": 108,
1383 "output_type": "execute_result"
1387 "len(lnet), len(etlnet)"
1391 "cell_type": "code",
1392 "execution_count": 109,
1398 "def simplify(net0):\n",
1399 " netp = eliminate_pairs(net0)\n",
1400 " new_net = eliminate_a_triple_pair(netp)\n",
1401 " while new_net:\n",
1402 "# print('sipl', len(net0), len(netp), len(new_net))\n",
1403 " netp = eliminate_pairs(new_net)\n",
1404 " new_net = eliminate_a_triple_pair(netp)\n",
1409 "cell_type": "code",
1410 "execution_count": 110,
1416 "simple_lnet = simplify(plnet)"
1420 "cell_type": "code",
1421 "execution_count": 111,
1430 "execution_count": 111,
1432 "output_type": "execute_result"
1436 "''.join(follow_many(string.ascii_lowercase, simple_lnet)) == ''.join(follow_many(string.ascii_lowercase, lnet))"
1440 "cell_type": "code",
1441 "execution_count": 112,
1447 "'ypetfugkzdsacbvwjohqlnirmx'"
1450 "execution_count": 112,
1452 "output_type": "execute_result"
1456 "''.join(follow_many(string.ascii_lowercase, simple_lnet))"
1460 "cell_type": "code",
1461 "execution_count": 113,
1467 "'ypetfugkzdsacbvwjohqlnirmx'"
1470 "execution_count": 113,
1472 "output_type": "execute_result"
1476 "''.join(follow_many(string.ascii_lowercase, lnet))"
1480 "cell_type": "code",
1481 "execution_count": 114,
1490 "execution_count": 114,
1492 "output_type": "execute_result"
1500 "cell_type": "code",
1501 "execution_count": 115,
1507 "def add_triple_pair(net, max_lines=None, trace=False):\n",
1508 " if not max_lines:\n",
1509 " max_lines = max(l.right for l in net)\n",
1510 " a, b, c = 0, 0, 0\n",
1511 " while len(set((a, b, c))) != 3:\n",
1512 " a = random.randrange(max_lines)\n",
1513 " b = random.randrange(max_lines)\n",
1514 " c = random.randrange(max_lines)\n",
1515 " tp = [(min(a, b), max(a, b)), (min(b, c), max(b, c))] * 2\n",
1517 " pairs = [(l.left, l.right) for l in sorted(net)]\n",
1518 " i = random.randrange(len(pairs))\n",
1519 " if trace: print(i, tp)\n",
1520 " new_pairs = pairs[:i] + tp + pairs[i:]\n",
1521 " return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)]) "
1525 "cell_type": "code",
1526 "execution_count": 116,
1532 "def add_pair(net, max_lines=None, trace=False):\n",
1533 " if not max_lines:\n",
1534 " max_lines = max(l.right for l in net)\n",
1538 " a = random.randrange(max_lines)\n",
1539 " b = random.randrange(max_lines)\n",
1540 " p = [(min(a, b), max(a, b))] * 2\n",
1542 " pairs = [(l.left, l.right) for l in sorted(net)]\n",
1543 " i = random.randrange(len(pairs))\n",
1545 " if trace: print(i, p)\n",
1546 " new_pairs = pairs[:i] + p + pairs[i:]\n",
1547 " return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)]) "
1551 "cell_type": "code",
1552 "execution_count": 117,
1561 "execution_count": 117,
1563 "output_type": "execute_result"
1567 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
1568 "tps = triple_pair_hg(height_groups)\n",
1573 "cell_type": "code",
1574 "execution_count": 118,
1585 "execution_count": 118,
1587 "output_type": "execute_result"
1591 "lnettp = simple_lnet\n",
1592 "for _ in range(10):\n",
1593 " lnettp = add_pair(lnettp)\n",
1594 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1595 "tps = triple_pair_hg(height_groups)\n",
1600 "cell_type": "code",
1601 "execution_count": 119,
1609 "[(Link(height=301, left=7, right=23),\n",
1610 " Link(height=302, left=16, right=23),\n",
1611 " Link(height=303, left=7, right=23),\n",
1612 " Link(height=304, left=16, right=23)),\n",
1613 " (Link(height=362, left=11, right=23),\n",
1614 " Link(height=363, left=3, right=23),\n",
1615 " Link(height=364, left=11, right=23),\n",
1616 " Link(height=365, left=3, right=23)),\n",
1617 " (Link(height=363, left=3, right=23),\n",
1618 " Link(height=364, left=11, right=23),\n",
1619 " Link(height=365, left=3, right=23),\n",
1620 " Link(height=366, left=11, right=23)),\n",
1621 " (Link(height=595, left=12, right=15),\n",
1622 " Link(height=596, left=10, right=15),\n",
1623 " Link(height=597, left=12, right=15),\n",
1624 " Link(height=598, left=10, right=15)),\n",
1625 " (Link(height=796, left=12, right=21),\n",
1626 " Link(height=797, left=4, right=12),\n",
1627 " Link(height=798, left=12, right=21),\n",
1628 " Link(height=799, left=4, right=12)),\n",
1629 " (Link(height=879, left=0, right=18),\n",
1630 " Link(height=880, left=0, right=8),\n",
1631 " Link(height=881, left=0, right=18),\n",
1632 " Link(height=882, left=0, right=8)),\n",
1633 " (Link(height=930, left=3, right=17),\n",
1634 " Link(height=931, left=3, right=21),\n",
1635 " Link(height=932, left=3, right=17),\n",
1636 " Link(height=933, left=3, right=21)),\n",
1637 " (Link(height=1120, left=5, right=19),\n",
1638 " Link(height=1121, left=18, right=19),\n",
1639 " Link(height=1122, left=5, right=19),\n",
1640 " Link(height=1123, left=18, right=19)),\n",
1641 " (Link(height=2040, left=9, right=21),\n",
1642 " Link(height=2041, left=9, right=15),\n",
1643 " Link(height=2042, left=9, right=21),\n",
1644 " Link(height=2043, left=9, right=15)),\n",
1645 " (Link(height=2110, left=13, right=21),\n",
1646 " Link(height=2111, left=13, right=24),\n",
1647 " Link(height=2112, left=13, right=21),\n",
1648 " Link(height=2113, left=13, right=24))]"
1651 "execution_count": 119,
1653 "output_type": "execute_result"
1657 "lnettp = simple_lnet\n",
1658 "for _ in range(10):\n",
1659 " lnettp = add_triple_pair(lnettp)\n",
1660 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1661 "tps = triple_pair_hg(height_groups)\n",
1666 "cell_type": "code",
1667 "execution_count": 120,
1675 "[(Link(height=49, left=10, right=20),\n",
1676 " Link(height=50, left=2, right=20),\n",
1677 " Link(height=51, left=10, right=20),\n",
1678 " Link(height=52, left=2, right=20)),\n",
1679 " (Link(height=54, left=2, right=24),\n",
1680 " Link(height=55, left=3, right=24),\n",
1681 " Link(height=56, left=2, right=24),\n",
1682 " Link(height=57, left=3, right=24)),\n",
1683 " (Link(height=62, left=2, right=15),\n",
1684 " Link(height=63, left=0, right=15),\n",
1685 " Link(height=64, left=2, right=15),\n",
1686 " Link(height=65, left=0, right=15)),\n",
1687 " (Link(height=114, left=14, right=18),\n",
1688 " Link(height=115, left=3, right=18),\n",
1689 " Link(height=116, left=14, right=18),\n",
1690 " Link(height=117, left=3, right=18)),\n",
1691 " (Link(height=138, left=13, right=19),\n",
1692 " Link(height=139, left=8, right=19),\n",
1693 " Link(height=140, left=13, right=19),\n",
1694 " Link(height=141, left=8, right=19)),\n",
1695 " (Link(height=160, left=12, right=13),\n",
1696 " Link(height=161, left=4, right=12),\n",
1697 " Link(height=162, left=12, right=13),\n",
1698 " Link(height=163, left=4, right=12)),\n",
1699 " (Link(height=315, left=23, right=24),\n",
1700 " Link(height=320, left=20, right=23),\n",
1701 " Link(height=321, left=23, right=24),\n",
1702 " Link(height=322, left=20, right=23)),\n",
1703 " (Link(height=324, left=3, right=18),\n",
1704 " Link(height=325, left=16, right=18),\n",
1705 " Link(height=326, left=3, right=18),\n",
1706 " Link(height=327, left=16, right=18)),\n",
1707 " (Link(height=342, left=21, right=22),\n",
1708 " Link(height=345, left=1, right=22),\n",
1709 " Link(height=346, left=21, right=22),\n",
1710 " Link(height=347, left=1, right=22)),\n",
1711 " (Link(height=405, left=8, right=19),\n",
1712 " Link(height=406, left=4, right=8),\n",
1713 " Link(height=407, left=8, right=19),\n",
1714 " Link(height=408, left=4, right=8)),\n",
1715 " (Link(height=468, left=11, right=22),\n",
1716 " Link(height=469, left=15, right=22),\n",
1717 " Link(height=470, left=11, right=22),\n",
1718 " Link(height=471, left=15, right=22)),\n",
1719 " (Link(height=549, left=1, right=2),\n",
1720 " Link(height=550, left=1, right=6),\n",
1721 " Link(height=551, left=1, right=2),\n",
1722 " Link(height=552, left=1, right=6)),\n",
1723 " (Link(height=568, left=16, right=21),\n",
1724 " Link(height=569, left=11, right=21),\n",
1725 " Link(height=570, left=16, right=21),\n",
1726 " Link(height=571, left=11, right=21)),\n",
1727 " (Link(height=608, left=17, right=20),\n",
1728 " Link(height=609, left=2, right=17),\n",
1729 " Link(height=610, left=17, right=20),\n",
1730 " Link(height=611, left=2, right=17)),\n",
1731 " (Link(height=613, left=18, right=21),\n",
1732 " Link(height=618, left=18, right=19),\n",
1733 " Link(height=619, left=18, right=21),\n",
1734 " Link(height=620, left=18, right=19)),\n",
1735 " (Link(height=635, left=2, right=4),\n",
1736 " Link(height=636, left=4, right=20),\n",
1737 " Link(height=637, left=2, right=4),\n",
1738 " Link(height=638, left=4, right=20)),\n",
1739 " (Link(height=681, left=7, right=20),\n",
1740 " Link(height=682, left=20, right=22),\n",
1741 " Link(height=683, left=7, right=20),\n",
1742 " Link(height=684, left=20, right=22)),\n",
1743 " (Link(height=750, left=23, right=24),\n",
1744 " Link(height=751, left=18, right=24),\n",
1745 " Link(height=752, left=23, right=24),\n",
1746 " Link(height=753, left=18, right=24)),\n",
1747 " (Link(height=760, left=12, right=18),\n",
1748 " Link(height=761, left=17, right=18),\n",
1749 " Link(height=762, left=12, right=18),\n",
1750 " Link(height=763, left=17, right=18)),\n",
1751 " (Link(height=765, left=0, right=9),\n",
1752 " Link(height=766, left=0, right=14),\n",
1753 " Link(height=767, left=0, right=9),\n",
1754 " Link(height=768, left=0, right=14)),\n",
1755 " (Link(height=805, left=16, right=22),\n",
1756 " Link(height=806, left=0, right=16),\n",
1757 " Link(height=807, left=16, right=22),\n",
1758 " Link(height=808, left=0, right=16)),\n",
1759 " (Link(height=834, left=1, right=6),\n",
1760 " Link(height=835, left=3, right=6),\n",
1761 " Link(height=836, left=1, right=6),\n",
1762 " Link(height=837, left=3, right=6)),\n",
1763 " (Link(height=881, left=2, right=12),\n",
1764 " Link(height=882, left=2, right=23),\n",
1765 " Link(height=883, left=2, right=12),\n",
1766 " Link(height=884, left=2, right=23)),\n",
1767 " (Link(height=904, left=12, right=23),\n",
1768 " Link(height=905, left=12, right=14),\n",
1769 " Link(height=906, left=12, right=23),\n",
1770 " Link(height=907, left=12, right=14)),\n",
1771 " (Link(height=936, left=7, right=17),\n",
1772 " Link(height=937, left=15, right=17),\n",
1773 " Link(height=938, left=7, right=17),\n",
1774 " Link(height=939, left=15, right=17)),\n",
1775 " (Link(height=1010, left=4, right=6),\n",
1776 " Link(height=1011, left=6, right=17),\n",
1777 " Link(height=1012, left=4, right=6),\n",
1778 " Link(height=1013, left=6, right=17)),\n",
1779 " (Link(height=1030, left=1, right=12),\n",
1780 " Link(height=1031, left=1, right=20),\n",
1781 " Link(height=1032, left=1, right=12),\n",
1782 " Link(height=1033, left=1, right=20)),\n",
1783 " (Link(height=1197, left=2, right=9),\n",
1784 " Link(height=1198, left=9, right=22),\n",
1785 " Link(height=1199, left=2, right=9),\n",
1786 " Link(height=1200, left=9, right=22)),\n",
1787 " (Link(height=1222, left=2, right=3),\n",
1788 " Link(height=1223, left=2, right=5),\n",
1789 " Link(height=1224, left=2, right=3),\n",
1790 " Link(height=1225, left=2, right=5)),\n",
1791 " (Link(height=1318, left=12, right=23),\n",
1792 " Link(height=1319, left=4, right=12),\n",
1793 " Link(height=1320, left=12, right=23),\n",
1794 " Link(height=1321, left=4, right=12)),\n",
1795 " (Link(height=1341, left=17, right=22),\n",
1796 " Link(height=1342, left=11, right=17),\n",
1797 " Link(height=1343, left=17, right=22),\n",
1798 " Link(height=1344, left=11, right=17)),\n",
1799 " (Link(height=1396, left=4, right=9),\n",
1800 " Link(height=1397, left=3, right=9),\n",
1801 " Link(height=1398, left=4, right=9),\n",
1802 " Link(height=1399, left=3, right=9)),\n",
1803 " (Link(height=1426, left=18, right=24),\n",
1804 " Link(height=1427, left=17, right=18),\n",
1805 " Link(height=1428, left=18, right=24),\n",
1806 " Link(height=1429, left=17, right=18)),\n",
1807 " (Link(height=1456, left=2, right=15),\n",
1808 " Link(height=1457, left=3, right=15),\n",
1809 " Link(height=1458, left=2, right=15),\n",
1810 " Link(height=1459, left=3, right=15)),\n",
1811 " (Link(height=1505, left=13, right=18),\n",
1812 " Link(height=1506, left=13, right=21),\n",
1813 " Link(height=1507, left=13, right=18),\n",
1814 " Link(height=1508, left=13, right=21)),\n",
1815 " (Link(height=1551, left=10, right=12),\n",
1816 " Link(height=1552, left=4, right=12),\n",
1817 " Link(height=1553, left=10, right=12),\n",
1818 " Link(height=1554, left=4, right=12)),\n",
1819 " (Link(height=1622, left=4, right=11),\n",
1820 " Link(height=1623, left=11, right=16),\n",
1821 " Link(height=1624, left=4, right=11),\n",
1822 " Link(height=1625, left=11, right=16)),\n",
1823 " (Link(height=1653, left=8, right=24),\n",
1824 " Link(height=1654, left=4, right=8),\n",
1825 " Link(height=1655, left=8, right=24),\n",
1826 " Link(height=1656, left=4, right=8)),\n",
1827 " (Link(height=1688, left=0, right=5),\n",
1828 " Link(height=1689, left=0, right=23),\n",
1829 " Link(height=1690, left=0, right=5),\n",
1830 " Link(height=1691, left=0, right=23)),\n",
1831 " (Link(height=1724, left=10, right=23),\n",
1832 " Link(height=1725, left=10, right=11),\n",
1833 " Link(height=1726, left=10, right=23),\n",
1834 " Link(height=1727, left=10, right=11)),\n",
1835 " (Link(height=1863, left=1, right=12),\n",
1836 " Link(height=1864, left=1, right=13),\n",
1837 " Link(height=1865, left=1, right=12),\n",
1838 " Link(height=1866, left=1, right=13)),\n",
1839 " (Link(height=1873, left=10, right=22),\n",
1840 " Link(height=1874, left=10, right=15),\n",
1841 " Link(height=1875, left=10, right=22),\n",
1842 " Link(height=1876, left=10, right=15)),\n",
1843 " (Link(height=1879, left=18, right=20),\n",
1844 " Link(height=1880, left=17, right=20),\n",
1845 " Link(height=1881, left=18, right=20),\n",
1846 " Link(height=1882, left=17, right=20)),\n",
1847 " (Link(height=1916, left=18, right=19),\n",
1848 " Link(height=1917, left=7, right=18),\n",
1849 " Link(height=1918, left=18, right=19),\n",
1850 " Link(height=1919, left=7, right=18)),\n",
1851 " (Link(height=1961, left=11, right=20),\n",
1852 " Link(height=1962, left=7, right=20),\n",
1853 " Link(height=1963, left=11, right=20),\n",
1854 " Link(height=1964, left=7, right=20)),\n",
1855 " (Link(height=1962, left=9, right=18),\n",
1856 " Link(height=1963, left=18, right=19),\n",
1857 " Link(height=1964, left=9, right=18),\n",
1858 " Link(height=1965, left=18, right=19)),\n",
1859 " (Link(height=2031, left=3, right=6),\n",
1860 " Link(height=2032, left=3, right=4),\n",
1861 " Link(height=2033, left=3, right=6),\n",
1862 " Link(height=2034, left=3, right=4)),\n",
1863 " (Link(height=2077, left=2, right=9),\n",
1864 " Link(height=2078, left=2, right=23),\n",
1865 " Link(height=2079, left=2, right=9),\n",
1866 " Link(height=2080, left=2, right=23)),\n",
1867 " (Link(height=2165, left=1, right=8),\n",
1868 " Link(height=2166, left=4, right=8),\n",
1869 " Link(height=2167, left=1, right=8),\n",
1870 " Link(height=2168, left=4, right=8)),\n",
1871 " (Link(height=2185, left=6, right=21),\n",
1872 " Link(height=2186, left=11, right=21),\n",
1873 " Link(height=2187, left=6, right=21),\n",
1874 " Link(height=2188, left=11, right=21))]"
1877 "execution_count": 120,
1879 "output_type": "execute_result"
1883 "lnettp = simple_lnet\n",
1884 "for _ in range(50):\n",
1885 " lnettp = add_pair(lnettp)\n",
1886 "for _ in range(50):\n",
1887 " lnettp = add_triple_pair(lnettp)\n",
1888 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1889 "tps = triple_pair_hg(height_groups)\n",
1894 "cell_type": "code",
1895 "execution_count": 121,
1904 "execution_count": 121,
1906 "output_type": "execute_result"
1910 "lnettp == pack(lnettp)"
1914 "cell_type": "code",
1915 "execution_count": 122,
1926 "execution_count": 122,
1928 "output_type": "execute_result"
1932 "lnettps = simplify(lnettp)\n",
1937 "cell_type": "code",
1938 "execution_count": 123,
1944 "(9809, 10109, 9909)"
1947 "execution_count": 123,
1949 "output_type": "execute_result"
1953 "len(simple_lnet), len(lnettp), len(lnettps)"
1957 "cell_type": "code",
1958 "execution_count": 124,
1967 "execution_count": 124,
1969 "output_type": "execute_result"
1973 "''.join(follow_many(string.ascii_lowercase, lnet)) == ''.join(follow_many(string.ascii_lowercase, simple_lnet))"
1977 "cell_type": "code",
1978 "execution_count": 125,
1987 "execution_count": 125,
1989 "output_type": "execute_result"
1993 "''.join(follow_many(string.ascii_lowercase, lnettps)) == ''.join(follow_many(string.ascii_lowercase, lnettp))"
1997 "cell_type": "code",
1998 "execution_count": 126,
2007 "execution_count": 126,
2009 "output_type": "execute_result"
2013 "max(l.height for l in lnettp)"
2017 "cell_type": "code",
2018 "execution_count": 127,
2024 "def simplify_with_checks(net0):\n",
2025 " netp = eliminate_pairs(net0)\n",
2026 " if follow_many(string.ascii_lowercase, net0) != follow_many(string.ascii_lowercase, netp):\n",
2027 " print('pairs', eliminable_pairs(net0))\n",
2030 " print('pairs ok')\n",
2031 " new_net = eliminate_a_triple_pair(netp)\n",
2032 " if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
2033 " hg = find_height_groups(netp)\n",
2034 " print('triple', triple_pair_hg(hg))\n",
2037 " print('triple ok')\n",
2038 " while new_net:\n",
2039 "# print('sipl', len(net0), len(netp), len(new_net))\n",
2040 " netp = eliminate_pairs(new_net)\n",
2041 " if follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
2042 " print('pairs', eliminable_pairs(new_net))\n",
2043 " return new_net\n",
2045 " print('pairs ok')\n",
2046 " new_net = eliminate_a_triple_pair(netp)\n",
2047 " if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
2048 " hg = find_height_groups(netp)\n",
2049 " print('triple', triple_pair_hg(hg))\n",
2052 " print('triple ok')\n",
2053 " print('** done')\n",
2058 "cell_type": "code",
2059 "execution_count": 128,
2066 "output_type": "stream",
2167 "lnettps = simplify_with_checks(lnettp)"
2171 "cell_type": "code",
2172 "execution_count": 129,
2181 "execution_count": 129,
2183 "output_type": "execute_result"
2187 "''.join(follow_many(string.ascii_lowercase, lnettps)) == ''.join(follow_many(string.ascii_lowercase, lnettp))"
2191 "cell_type": "code",
2192 "execution_count": 130,
2201 "execution_count": 130,
2203 "output_type": "execute_result"
2211 "cell_type": "code",
2212 "execution_count": 131,
2216 "# open('04-lines.txt', 'w').write(show_net(lnettp, randomise=True, pair_sep='\\n'))"
2220 "cell_type": "code",
2221 "execution_count": 114,
2230 "execution_count": 114,
2232 "output_type": "execute_result"
2236 "# open('04-small.txt', 'w').write(show_net(make_net(20), randomise=True, pair_sep='\\n'))"
2240 "cell_type": "code",
2241 "execution_count": 143,
2246 "output_type": "stream",
2248 "8 [(2, 4), (0, 4), (2, 4), (0, 4)]\n",
2249 "10 [(1, 2), (1, 2)]\n"
2255 "[Link(height=0, left=2, right=5),\n",
2256 " Link(height=1, left=1, right=4),\n",
2257 " Link(height=2, left=0, right=3),\n",
2258 " Link(height=3, left=0, right=3),\n",
2259 " Link(height=4, left=0, right=5),\n",
2260 " Link(height=5, left=3, right=5),\n",
2261 " Link(height=6, left=0, right=2),\n",
2262 " Link(height=7, left=3, right=4),\n",
2263 " Link(height=8, left=2, right=4),\n",
2264 " Link(height=9, left=1, right=2),\n",
2265 " Link(height=10, left=0, right=4),\n",
2266 " Link(height=11, left=1, right=2),\n",
2267 " Link(height=12, left=2, right=4),\n",
2268 " Link(height=13, left=1, right=2),\n",
2269 " Link(height=14, left=0, right=4),\n",
2270 " Link(height=15, left=1, right=4)]"
2273 "execution_count": 143,
2275 "output_type": "execute_result"
2279 "net = make_net(10, lines=6)\n",
2280 "net = add_triple_pair(net, trace=True)\n",
2281 "net = add_pair(net, trace=True)\n",
2282 "net = read_net(show_net(net, randomise=True))\n",
2287 "cell_type": "code",
2288 "execution_count": 147,
2294 "'(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)'"
2297 "execution_count": 147,
2299 "output_type": "execute_result"
2307 "cell_type": "code",
2308 "execution_count": 149,
2314 "[Link(height=0, left=2, right=5),\n",
2315 " Link(height=1, left=1, right=4),\n",
2316 " Link(height=2, left=0, right=3),\n",
2317 " Link(height=3, left=0, right=3),\n",
2318 " Link(height=4, left=0, right=5),\n",
2319 " Link(height=5, left=3, right=5),\n",
2320 " Link(height=6, left=0, right=2),\n",
2321 " Link(height=7, left=3, right=4),\n",
2322 " Link(height=8, left=2, right=4),\n",
2323 " Link(height=9, left=1, right=2),\n",
2324 " Link(height=10, left=0, right=4),\n",
2325 " Link(height=11, left=1, right=2),\n",
2326 " Link(height=12, left=2, right=4),\n",
2327 " Link(height=13, left=0, right=4),\n",
2328 " Link(height=14, left=1, right=4)]"
2331 "execution_count": 149,
2333 "output_type": "execute_result"
2337 "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",
2342 "cell_type": "code",
2343 "execution_count": 150,
2349 "[Link(height=0, left=0, right=3),\n",
2350 " Link(height=0, left=1, right=4),\n",
2351 " Link(height=0, left=2, right=5),\n",
2352 " Link(height=1, left=0, right=3),\n",
2353 " Link(height=2, left=0, right=5),\n",
2354 " Link(height=3, left=0, right=2),\n",
2355 " Link(height=3, left=3, right=5),\n",
2356 " Link(height=4, left=3, right=4),\n",
2357 " Link(height=5, left=2, right=4),\n",
2358 " Link(height=6, left=0, right=4),\n",
2359 " Link(height=6, left=1, right=2),\n",
2360 " Link(height=7, left=1, right=2),\n",
2361 " Link(height=8, left=2, right=4),\n",
2362 " Link(height=9, left=0, right=4),\n",
2363 " Link(height=10, left=1, right=4)]"
2366 "execution_count": 150,
2368 "output_type": "execute_result"
2376 "cell_type": "code",
2377 "execution_count": 151,
2383 "[Link(height=0, left=1, right=4),\n",
2384 " Link(height=0, left=2, right=5),\n",
2385 " Link(height=1, left=0, right=5),\n",
2386 " Link(height=2, left=0, right=2),\n",
2387 " Link(height=2, left=3, right=5),\n",
2388 " Link(height=3, left=3, right=4),\n",
2389 " Link(height=4, left=2, right=4),\n",
2390 " Link(height=5, left=0, right=4),\n",
2391 " Link(height=6, left=2, right=4),\n",
2392 " Link(height=7, left=0, right=4),\n",
2393 " Link(height=8, left=1, right=4)]"
2396 "execution_count": 151,
2398 "output_type": "execute_result"
2402 "epnet = eliminate_pairs(net)\n",
2407 "cell_type": "code",
2408 "execution_count": 152,
2413 "output_type": "stream",
2422 "[Link(height=0, left=1, right=4),\n",
2423 " Link(height=0, left=2, right=5),\n",
2424 " Link(height=1, left=0, right=5),\n",
2425 " Link(height=2, left=0, right=2),\n",
2426 " Link(height=2, left=3, right=5),\n",
2427 " Link(height=3, left=3, right=4),\n",
2428 " Link(height=4, left=0, right=4),\n",
2429 " Link(height=5, left=2, right=4),\n",
2430 " Link(height=6, left=1, right=4)]"
2433 "execution_count": 152,
2435 "output_type": "execute_result"
2439 "eptnet = eliminate_triple_pairs(epnet)\n",
2444 "cell_type": "code",
2445 "execution_count": 153,
2454 "execution_count": 153,
2456 "output_type": "execute_result"
2460 "''.join(follow_many(string.ascii_lowercase, net)) == ''.join(follow_many(string.ascii_lowercase, eptnet))"
2464 "cell_type": "code",
2465 "execution_count": 155,
2474 "execution_count": 155,
2476 "output_type": "execute_result"
2480 "open('04-small.txt', 'w').write(show_net(net, pair_sep='\\n'))"
2484 "cell_type": "code",
2485 "execution_count": null,
2495 "display_name": "Python 3",
2496 "language": "python",
2500 "codemirror_mode": {
2504 "file_extension": ".py",
2505 "mimetype": "text/x-python",
2507 "nbconvert_exporter": "python",
2508 "pygments_lexer": "ipython3",