11 "import collections\n",
24 "Link = collections.namedtuple('Link', 'height left right')"
35 "def link_ends(link):\n",
36 " return set((link.left, link.right))"
41 "execution_count": 19,
47 "def read_net(net_string):\n",
48 " return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
59 "def follow(initial_line, links):\n",
60 " line = initial_line\n",
61 " heights = sorted(set(l.height for l in links))\n",
62 " for h in heights:\n",
63 " for l in [l for l in links if l.height == h]:\n",
64 " if line in link_ends(l):\n",
65 " line = [e for e in link_ends(l) if e != line][0]\n",
79 " packed_links = []\n",
80 " line_heights = collections.defaultdict(lambda: -1)\n",
81 " for link in sorted(net):\n",
82 " link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
83 " line_heights[link.left] = link_height\n",
84 " line_heights[link.right] = link_height\n",
85 " packed_links += [Link(link_height, link.left, link.right)]\n",
86 " return sorted(packed_links)"
91 "execution_count": 10,
97 "def follow_many_slow(in_sequence, links):\n",
98 " out_sequence = [(follow(i, links), term) \n",
99 " for i, term in enumerate(in_sequence)]\n",
100 " return [term for i, term in sorted(out_sequence)]"
105 "execution_count": 11,
111 "def follow_many(in_sequence, net):\n",
112 " height_groups = [list(g) for _, g in itertools.groupby(pack(net), lambda l: l.height)]\n",
113 " seq = list(in_sequence)\n",
114 " for links in height_groups:\n",
115 " for link in links:\n",
116 " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
122 "execution_count": 12,
127 "output_type": "stream",
129 "10000 loops, best of 3: 47.5 µs per loop\n"
135 "follow_many('abcdefghij', net)"
140 "execution_count": 13,
147 "# follow_many_slow('abcdefghij', net)"
152 "execution_count": 14,
158 "def show_net(links, randomise=False):\n",
161 " heights = sorted(set(l.height for l in links))\n",
162 " for h in heights:\n",
163 " ls = [l for l in links if l.height == h]\n",
164 " random.shuffle(ls)\n",
165 " output += ['({}, {})'.format(l.left, l.right) for l in ls]\n",
166 " return ', '.join(output)\n",
167 " return ', '.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
172 "execution_count": 20,
178 "def extract_pairs(net_string):\n",
179 " return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
184 "execution_count": 25,
193 "execution_count": 25,
195 "output_type": "execute_result"
199 "rrnet = read_net(show_net(net, randomise=True))\n",
200 "rnet = read_net(show_net(net))\n",
201 "rnet == rrnet, pack(rrnet) == pnet"
206 "execution_count": 26,
212 "lnet = make_net(10207, 26, 100000)\n",
213 "plnet = pack(lnet)\n",
214 "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, plnet)\n",
215 "# for i in range(204):\n",
216 "# assert follow(i, lnet) == follow(i, plnet)"
221 "execution_count": 27,
227 "rlnet = read_net(show_net(lnet))\n",
228 "prlnet = pack(rlnet)"
233 "execution_count": 28,
242 "execution_count": 28,
244 "output_type": "execute_result"
248 "max(link.height for link in plnet)"
253 "execution_count": 29,
262 "execution_count": 29,
264 "output_type": "execute_result"
268 "max(link.height for link in lnet)"
273 "execution_count": 30,
282 "execution_count": 30,
284 "output_type": "execute_result"
288 "max(link.height for link in rlnet)"
293 "execution_count": 31,
302 "execution_count": 31,
304 "output_type": "execute_result"
308 "max(link.height for link in prlnet)"
313 "execution_count": 32,
319 "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, prlnet)"
324 "execution_count": 33,
329 "output_type": "stream",
331 "10 loops, best of 3: 24.5 ms per loop\n"
337 "follow_many(string.ascii_lowercase, lnet)"
342 "execution_count": 34,
349 "# follow_many_slow(string.ascii_lowercase, lnet)"
354 "execution_count": 35,
360 "def eliminable_pairs_slow(net):\n",
363 " o = Link(l.height + 1, l.left, l.right)\n",
365 " eps += [(l, o)]\n",
371 "execution_count": 36,
377 "def eliminable_pairs(net):\n",
378 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
380 " for h in range(1, max(height_groups.keys())):\n",
381 " for l in height_groups[h]:\n",
382 " o = Link(l.height - 1, l.left, l.right)\n",
383 " if o in height_groups[h-1]:\n",
384 " eps += [(l, o)]\n",
390 "execution_count": 37,
395 "output_type": "stream",
397 "10 loops, best of 3: 23.5 ms per loop\n"
403 "eliminable_pairs(plnet)"
408 "execution_count": 38,
413 "output_type": "stream",
415 "1 loop, best of 3: 2.33 s per loop\n"
421 "eliminable_pairs_slow(plnet)"
426 "execution_count": 39,
432 "assert sorted(sorted(p) for p in eliminable_pairs(plnet)) == sorted(sorted(p) for p in eliminable_pairs_slow(plnet))"
437 "execution_count": 40,
443 "def eliminable_pair(net):\n",
445 " o = Link(l.height + 1, l.left, l.right)\n",
453 "execution_count": 41,
459 "def eliminable_pair_hg(height_groups):\n",
460 " for h in range(1, max(height_groups.keys())):\n",
461 " for l in height_groups[h]:\n",
462 " o = Link(l.height - 1, l.left, l.right)\n",
463 " if o in height_groups[h-1]:\n",
470 "execution_count": 42,
476 "def eliminate_pairs_slow(net):\n",
477 " eliminable_links = eliminable_pair(net)\n",
478 " while eliminable_links:\n",
479 " net = pack(l for l in net if l not in eliminable_links)\n",
480 " eliminable_links = eliminable_pair(net)\n",
486 "execution_count": 43,
492 "def eliminate_pairs(net):\n",
493 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
494 " eliminable_links = eliminable_pair_hg(height_groups)\n",
495 " while eliminable_links:\n",
496 " net = pack(l for l in net if l not in eliminable_links)\n",
497 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
498 " eliminable_links = eliminable_pair_hg(height_groups)\n",
504 "execution_count": 44,
509 "output_type": "stream",
520 "execution_count": 44,
522 "output_type": "execute_result"
526 "print(len(plnet))\n",
527 "elnet = eliminate_pairs_slow(plnet)\n",
528 "len(plnet), len(elnet)"
533 "execution_count": 45,
538 "output_type": "stream",
549 "execution_count": 45,
551 "output_type": "execute_result"
555 "print(len(plnet))\n",
556 "elnet = eliminate_pairs(plnet)\n",
557 "len(plnet), len(elnet)"
562 "execution_count": 46,
571 "execution_count": 46,
573 "output_type": "execute_result"
577 "eliminable_pairs(elnet)"
582 "execution_count": 47,
588 "assert eliminate_pairs_slow(plnet) == eliminate_pairs(plnet)"
593 "execution_count": 48,
599 "assert follow_many(string.ascii_lowercase, lnet) == follow_many(string.ascii_lowercase, elnet)\n",
600 "assert follow_many(string.ascii_lowercase, plnet) == follow_many(string.ascii_lowercase, elnet)"
605 "execution_count": 49,
610 "output_type": "stream",
612 "1 loop, best of 3: 3min 30s per loop\n"
618 "elnet = eliminate_pairs_slow(plnet)"
623 "execution_count": 50,
628 "output_type": "stream",
630 "1 loop, best of 3: 6.27 s per loop\n"
636 "elnet = eliminate_pairs(plnet)"
641 "execution_count": 51,
647 "# for i in range(26):\n",
648 "# assert follow(i, plnet) == follow(i, elnet)\n",
649 "# assert follow(i, lnet) == follow(i, elnet)"
654 "execution_count": 52,
660 "# follow(0, plnet), follow(0, elnet), follow(0, lnet)"
665 "execution_count": 53,
671 "def triple(net):\n",
676 " bs = [l for l in net if l.height == a.height + 1 \n",
677 " if l.left == a.right or l.right == a.left]\n",
679 " c = Link(a.height + 2, a.left, a.right)\n",
681 " ts += [(a, b, c)]\n",
687 "execution_count": 54,
693 "def triple_pair(net):\n",
696 " a_ends = link_ends(a)\n",
697 " bs = [l for l in net if l.height == a.height + 1 \n",
698 " if link_ends(l) & a_ends]\n",
699 " if len(bs) == 1:\n",
701 " lines = set((a.left, a.right, b.left, b.right))\n",
702 " cs = [l for l in net \n",
703 " if l.height == a.height + 2\n",
704 " if link_ends(l) & lines]\n",
705 " if len(cs) == 1:\n",
706 " c = Link(a.height + 2, a.left, a.right)\n",
708 " ds = [l for l in net \n",
709 " if l.height == a.height + 3\n",
710 " if link_ends(l) & lines]\n",
711 " d = Link(a.height + 3, b.left, b.right)\n",
713 " ts += [(a, b, c, d)]\n",
719 "execution_count": 129,
725 "def triple_pair_hg(height_groups, debug=False):\n",
727 " for h in range(3, max(height_groups.keys())):\n",
728 " for d in height_groups[h]:\n",
729 " if debug: print('d:', d)\n",
731 " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
732 " if debug: print('cs:', cs)\n",
733 " while ch > 2 and not cs:\n",
735 " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
736 " if debug: print('cs:', cs)\n",
737 " if len(cs) == 1:\n",
739 " lines = set((d.left, d.right, c.left, c.right))\n",
740 " if debug: print('c:', '; lines:', lines)\n",
741 " bs = [l for l in height_groups[ch-1] if link_ends(l) & lines]\n",
742 " b = Link(ch - 1, d.left, d.right)\n",
743 " if debug: print('b:', b, '; bs:', bs)\n",
744 " if len(bs) == 1 and b in bs:\n",
745 " ah = b.height - 1\n",
746 " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
747 " if debug: print('ah:', ah, '; als:', als)\n",
748 " while ah > 0 and not als:\n",
750 " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
751 " if debug: print('ah:', ah, '; als:', als)\n",
752 " a = Link(ah, c.left, c.right)\n",
753 " if debug: print('a:', a)\n",
755 " if debug: print('adding:', a, b, c, d)\n",
756 " ts += [(a, b, c, d)]\n",
762 "execution_count": 132,
768 "def eliminate_a_triple_pair_slow(net):\n",
769 " tps = triple_pair(net)\n",
770 " print('eatp', tps)\n",
773 " a, b, c, d = tps[0]\n",
774 "# x = Link(a.height, b.left, b.right)\n",
775 "# y = Link(b.height, a.left, a.right)\n",
776 " x = Link(a.height, b.left, b.right)\n",
777 " y = Link(b.height, a.left, a.right)\n",
778 " print('removing', a, b, c, d, '; adding', x, y)\n",
779 " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
785 "execution_count": 133,
791 "def eliminate_a_triple_pair(net):\n",
792 " height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
794 " tps = triple_pair_hg(height_groups)\n",
795 " print('eatp', tps)\n",
797 " a, b, c, d = tps[0]\n",
798 " x = Link(a.height, b.left, b.right)\n",
799 " y = Link(b.height, a.left, a.right)\n",
800 " print('removing', a, b, c, d, '; adding', x, y)\n",
801 " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
807 "execution_count": 58,
813 "[(Link(height=12, left=0, right=5),\n",
814 " Link(height=13, left=5, right=11),\n",
815 " Link(height=14, left=0, right=5)),\n",
816 " (Link(height=29, left=2, right=18),\n",
817 " Link(height=30, left=1, right=2),\n",
818 " Link(height=31, left=2, right=18)),\n",
819 " (Link(height=40, left=2, right=3),\n",
820 " Link(height=41, left=3, right=18),\n",
821 " Link(height=42, left=2, right=3)),\n",
822 " (Link(height=43, left=1, right=10),\n",
823 " Link(height=44, left=10, right=20),\n",
824 " Link(height=45, left=1, right=10)),\n",
825 " (Link(height=91, left=5, right=8),\n",
826 " Link(height=92, left=3, right=5),\n",
827 " Link(height=93, left=5, right=8)),\n",
828 " (Link(height=91, left=5, right=8),\n",
829 " Link(height=92, left=8, right=18),\n",
830 " Link(height=93, left=5, right=8)),\n",
831 " (Link(height=99, left=13, right=17),\n",
832 " Link(height=100, left=4, right=13),\n",
833 " Link(height=101, left=13, right=17)),\n",
834 " (Link(height=120, left=18, right=20),\n",
835 " Link(height=121, left=9, right=18),\n",
836 " Link(height=122, left=18, right=20)),\n",
837 " (Link(height=147, left=19, right=21),\n",
838 " Link(height=148, left=7, right=19),\n",
839 " Link(height=149, left=19, right=21)),\n",
840 " (Link(height=147, left=19, right=21),\n",
841 " Link(height=148, left=21, right=23),\n",
842 " Link(height=149, left=19, right=21)),\n",
843 " (Link(height=179, left=13, right=25),\n",
844 " Link(height=180, left=12, right=13),\n",
845 " Link(height=181, left=13, right=25)),\n",
846 " (Link(height=265, left=3, right=20),\n",
847 " Link(height=266, left=20, right=23),\n",
848 " Link(height=267, left=3, right=20)),\n",
849 " (Link(height=291, left=5, right=23),\n",
850 " Link(height=292, left=2, right=5),\n",
851 " Link(height=293, left=5, right=23)),\n",
852 " (Link(height=292, left=18, right=25),\n",
853 " Link(height=293, left=0, right=18),\n",
854 " Link(height=294, left=18, right=25)),\n",
855 " (Link(height=302, left=11, right=19),\n",
856 " Link(height=303, left=6, right=11),\n",
857 " Link(height=304, left=11, right=19)),\n",
858 " (Link(height=309, left=15, right=20),\n",
859 " Link(height=310, left=20, right=25),\n",
860 " Link(height=311, left=15, right=20)),\n",
861 " (Link(height=325, left=13, right=18),\n",
862 " Link(height=326, left=11, right=13),\n",
863 " Link(height=327, left=13, right=18)),\n",
864 " (Link(height=362, left=11, right=22),\n",
865 " Link(height=363, left=22, right=24),\n",
866 " Link(height=364, left=11, right=22)),\n",
867 " (Link(height=372, left=22, right=23),\n",
868 " Link(height=373, left=1, right=22),\n",
869 " Link(height=374, left=22, right=23)),\n",
870 " (Link(height=386, left=4, right=17),\n",
871 " Link(height=387, left=17, right=21),\n",
872 " Link(height=388, left=4, right=17)),\n",
873 " (Link(height=393, left=4, right=16),\n",
874 " Link(height=394, left=0, right=4),\n",
875 " Link(height=395, left=4, right=16)),\n",
876 " (Link(height=531, left=0, right=4),\n",
877 " Link(height=532, left=4, right=15),\n",
878 " Link(height=533, left=0, right=4)),\n",
879 " (Link(height=575, left=5, right=21),\n",
880 " Link(height=576, left=1, right=5),\n",
881 " Link(height=577, left=5, right=21)),\n",
882 " (Link(height=639, left=7, right=11),\n",
883 " Link(height=640, left=11, right=17),\n",
884 " Link(height=641, left=7, right=11)),\n",
885 " (Link(height=687, left=2, right=4),\n",
886 " Link(height=688, left=4, right=15),\n",
887 " Link(height=689, left=2, right=4)),\n",
888 " (Link(height=706, left=8, right=11),\n",
889 " Link(height=707, left=11, right=22),\n",
890 " Link(height=708, left=8, right=11)),\n",
891 " (Link(height=722, left=22, right=23),\n",
892 " Link(height=723, left=21, right=22),\n",
893 " Link(height=724, left=22, right=23)),\n",
894 " (Link(height=768, left=9, right=11),\n",
895 " Link(height=769, left=11, right=17),\n",
896 " Link(height=770, left=9, right=11)),\n",
897 " (Link(height=792, left=5, right=12),\n",
898 " Link(height=793, left=12, right=17),\n",
899 " Link(height=794, left=5, right=12)),\n",
900 " (Link(height=805, left=20, right=22),\n",
901 " Link(height=806, left=19, right=20),\n",
902 " Link(height=807, left=20, right=22)),\n",
903 " (Link(height=806, left=19, right=20),\n",
904 " Link(height=807, left=18, right=19),\n",
905 " Link(height=808, left=19, right=20)),\n",
906 " (Link(height=806, left=19, right=20),\n",
907 " Link(height=807, left=20, right=22),\n",
908 " Link(height=808, left=19, right=20)),\n",
909 " (Link(height=882, left=7, right=14),\n",
910 " Link(height=883, left=14, right=22),\n",
911 " Link(height=884, left=7, right=14)),\n",
912 " (Link(height=884, left=6, right=11),\n",
913 " Link(height=885, left=11, right=19),\n",
914 " Link(height=886, left=6, right=11)),\n",
915 " (Link(height=892, left=12, right=17),\n",
916 " Link(height=893, left=10, right=12),\n",
917 " Link(height=894, left=12, right=17)),\n",
918 " (Link(height=916, left=18, right=24),\n",
919 " Link(height=917, left=16, right=18),\n",
920 " Link(height=918, left=18, right=24)),\n",
921 " (Link(height=919, left=14, right=17),\n",
922 " Link(height=920, left=6, right=14),\n",
923 " Link(height=921, left=14, right=17)),\n",
924 " (Link(height=994, left=0, right=3),\n",
925 " Link(height=995, left=3, right=24),\n",
926 " Link(height=996, left=0, right=3)),\n",
927 " (Link(height=1012, left=9, right=12),\n",
928 " Link(height=1013, left=12, right=24),\n",
929 " Link(height=1014, left=9, right=12)),\n",
930 " (Link(height=1034, left=1, right=6),\n",
931 " Link(height=1035, left=6, right=12),\n",
932 " Link(height=1036, left=1, right=6)),\n",
933 " (Link(height=1035, left=7, right=21),\n",
934 " Link(height=1036, left=4, right=7),\n",
935 " Link(height=1037, left=7, right=21)),\n",
936 " (Link(height=1047, left=3, right=10),\n",
937 " Link(height=1048, left=10, right=11),\n",
938 " Link(height=1049, left=3, right=10)),\n",
939 " (Link(height=1088, left=7, right=8),\n",
940 " Link(height=1089, left=8, right=14),\n",
941 " Link(height=1090, left=7, right=8)),\n",
942 " (Link(height=1104, left=3, right=10),\n",
943 " Link(height=1105, left=10, right=11),\n",
944 " Link(height=1106, left=3, right=10)),\n",
945 " (Link(height=1135, left=5, right=8),\n",
946 " Link(height=1136, left=8, right=19),\n",
947 " Link(height=1137, left=5, right=8)),\n",
948 " (Link(height=1138, left=1, right=3),\n",
949 " Link(height=1139, left=3, right=23),\n",
950 " Link(height=1140, left=1, right=3)),\n",
951 " (Link(height=1146, left=5, right=7),\n",
952 " Link(height=1147, left=7, right=24),\n",
953 " Link(height=1148, left=5, right=7)),\n",
954 " (Link(height=1197, left=5, right=14),\n",
955 " Link(height=1198, left=14, right=15),\n",
956 " Link(height=1199, left=5, right=14)),\n",
957 " (Link(height=1205, left=7, right=23),\n",
958 " Link(height=1206, left=3, right=7),\n",
959 " Link(height=1207, left=7, right=23)),\n",
960 " (Link(height=1276, left=18, right=25),\n",
961 " Link(height=1277, left=17, right=18),\n",
962 " Link(height=1278, left=18, right=25)),\n",
963 " (Link(height=1319, left=14, right=20),\n",
964 " Link(height=1320, left=20, right=24),\n",
965 " Link(height=1321, left=14, right=20)),\n",
966 " (Link(height=1328, left=8, right=21),\n",
967 " Link(height=1329, left=1, right=8),\n",
968 " Link(height=1330, left=8, right=21)),\n",
969 " (Link(height=1329, left=2, right=14),\n",
970 " Link(height=1330, left=14, right=25),\n",
971 " Link(height=1331, left=2, right=14)),\n",
972 " (Link(height=1385, left=10, right=14),\n",
973 " Link(height=1386, left=14, right=15),\n",
974 " Link(height=1387, left=10, right=14)),\n",
975 " (Link(height=1419, left=2, right=8),\n",
976 " Link(height=1420, left=8, right=15),\n",
977 " Link(height=1421, left=2, right=8)),\n",
978 " (Link(height=1465, left=13, right=21),\n",
979 " Link(height=1466, left=21, right=24),\n",
980 " Link(height=1467, left=13, right=21)),\n",
981 " (Link(height=1514, left=11, right=15),\n",
982 " Link(height=1515, left=15, right=21),\n",
983 " Link(height=1516, left=11, right=15)),\n",
984 " (Link(height=1545, left=3, right=11),\n",
985 " Link(height=1546, left=11, right=25),\n",
986 " Link(height=1547, left=3, right=11)),\n",
987 " (Link(height=1561, left=7, right=18),\n",
988 " Link(height=1562, left=0, right=7),\n",
989 " Link(height=1563, left=7, right=18)),\n",
990 " (Link(height=1671, left=9, right=15),\n",
991 " Link(height=1672, left=15, right=23),\n",
992 " Link(height=1673, left=9, right=15)),\n",
993 " (Link(height=1701, left=13, right=21),\n",
994 " Link(height=1702, left=4, right=13),\n",
995 " Link(height=1703, left=13, right=21)),\n",
996 " (Link(height=1706, left=5, right=13),\n",
997 " Link(height=1707, left=13, right=23),\n",
998 " Link(height=1708, left=5, right=13)),\n",
999 " (Link(height=1730, left=7, right=16),\n",
1000 " Link(height=1731, left=1, right=7),\n",
1001 " Link(height=1732, left=7, right=16)),\n",
1002 " (Link(height=1781, left=0, right=8),\n",
1003 " Link(height=1782, left=8, right=17),\n",
1004 " Link(height=1783, left=0, right=8)),\n",
1005 " (Link(height=1784, left=8, right=18),\n",
1006 " Link(height=1785, left=1, right=8),\n",
1007 " Link(height=1786, left=8, right=18)),\n",
1008 " (Link(height=1804, left=19, right=24),\n",
1009 " Link(height=1805, left=7, right=19),\n",
1010 " Link(height=1806, left=19, right=24)),\n",
1011 " (Link(height=1827, left=3, right=23),\n",
1012 " Link(height=1828, left=23, right=25),\n",
1013 " Link(height=1829, left=3, right=23)),\n",
1014 " (Link(height=1837, left=1, right=16),\n",
1015 " Link(height=1838, left=16, right=17),\n",
1016 " Link(height=1839, left=1, right=16)),\n",
1017 " (Link(height=1849, left=18, right=25),\n",
1018 " Link(height=1850, left=4, right=18),\n",
1019 " Link(height=1851, left=18, right=25)),\n",
1020 " (Link(height=1856, left=6, right=13),\n",
1021 " Link(height=1857, left=13, right=17),\n",
1022 " Link(height=1858, left=6, right=13)),\n",
1023 " (Link(height=1875, left=2, right=11),\n",
1024 " Link(height=1876, left=11, right=15),\n",
1025 " Link(height=1877, left=2, right=11)),\n",
1026 " (Link(height=1970, left=6, right=24),\n",
1027 " Link(height=1971, left=1, right=6),\n",
1028 " Link(height=1972, left=6, right=24)),\n",
1029 " (Link(height=2075, left=20, right=25),\n",
1030 " Link(height=2076, left=5, right=20),\n",
1031 " Link(height=2077, left=20, right=25)),\n",
1032 " (Link(height=2081, left=4, right=19),\n",
1033 " Link(height=2082, left=1, right=4),\n",
1034 " Link(height=2083, left=4, right=19)),\n",
1035 " (Link(height=2111, left=3, right=25),\n",
1036 " Link(height=2112, left=1, right=3),\n",
1037 " Link(height=2113, left=3, right=25)),\n",
1038 " (Link(height=2225, left=3, right=12),\n",
1039 " Link(height=2226, left=12, right=24),\n",
1040 " Link(height=2227, left=3, right=12)),\n",
1041 " (Link(height=2242, left=3, right=18),\n",
1042 " Link(height=2243, left=18, right=23),\n",
1043 " Link(height=2244, left=3, right=18))]"
1046 "execution_count": 58,
1048 "output_type": "execute_result"
1056 "cell_type": "code",
1057 "execution_count": 59,
1063 "[(Link(height=316, left=8, right=17),\n",
1064 " Link(height=317, left=8, right=21),\n",
1065 " Link(height=318, left=8, right=17),\n",
1066 " Link(height=319, left=8, right=21)),\n",
1067 " (Link(height=867, left=4, right=11),\n",
1068 " Link(height=868, left=5, right=11),\n",
1069 " Link(height=869, left=4, right=11),\n",
1070 " Link(height=870, left=5, right=11))]"
1073 "execution_count": 59,
1075 "output_type": "execute_result"
1079 "triple_pair(elnet)"
1083 "cell_type": "code",
1084 "execution_count": 60,
1090 "[(Link(height=316, left=8, right=17),\n",
1091 " Link(height=317, left=8, right=21),\n",
1092 " Link(height=318, left=8, right=17),\n",
1093 " Link(height=319, left=8, right=21)),\n",
1094 " (Link(height=867, left=4, right=11),\n",
1095 " Link(height=868, left=5, right=11),\n",
1096 " Link(height=869, left=4, right=11),\n",
1097 " Link(height=870, left=5, right=11))]"
1100 "execution_count": 60,
1102 "output_type": "execute_result"
1106 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(elnet), lambda l: l.height)}\n",
1107 "triple_pair_hg(height_groups)"
1111 "cell_type": "code",
1112 "execution_count": 61,
1118 "[Link(height=1368, left=13, right=19),\n",
1119 " Link(height=1368, left=14, right=16),\n",
1120 " Link(height=1369, left=3, right=6)]"
1123 "execution_count": 61,
1125 "output_type": "execute_result"
1129 "[l for l in elnet if l.height >= 1367 if l.height <= 1370 if link_ends(l) & set((6, 16, 19))]"
1133 "cell_type": "code",
1134 "execution_count": 62,
1139 "output_type": "stream",
1141 "1 loop, best of 3: 21.3 s per loop\n"
1147 "triple_pair(elnet)"
1151 "cell_type": "code",
1152 "execution_count": 63,
1157 "output_type": "stream",
1159 "10 loops, best of 3: 105 ms per loop\n"
1165 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(elnet), lambda l: l.height)}\n",
1166 "triple_pair_hg(height_groups)"
1170 "cell_type": "code",
1171 "execution_count": 64,
1177 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(elnet), lambda l: l.height)}\n",
1178 "assert triple_pair_hg(height_groups) == triple_pair(elnet)"
1182 "cell_type": "code",
1183 "execution_count": 65,
1189 "[Link(height=242, left=8, right=9),\n",
1190 " Link(height=242, left=15, right=21),\n",
1191 " Link(height=243, left=1, right=9),\n",
1192 " Link(height=243, left=8, right=14),\n",
1193 " Link(height=243, left=11, right=15),\n",
1194 " Link(height=244, left=1, right=18),\n",
1195 " Link(height=244, left=6, right=8),\n",
1196 " Link(height=244, left=9, right=20),\n",
1197 " Link(height=244, left=15, right=25),\n",
1198 " Link(height=245, left=0, right=15),\n",
1199 " Link(height=245, left=1, right=16),\n",
1200 " Link(height=245, left=9, right=12),\n",
1201 " Link(height=245, left=18, right=21)]"
1204 "execution_count": 65,
1206 "output_type": "execute_result"
1210 "[l for l in elnet if l.height >= 242 if l.height <= 245 ] #if l.left in [13, 17, 20] or l.right in [13, 17, 20]]"
1214 "cell_type": "code",
1215 "execution_count": 86,
1221 "def eliminate_triple_pairs_slow(net):\n",
1222 " print(len(net))\n",
1223 " new_net = eliminate_a_triple_pair_slow(net)\n",
1224 " while new_net:\n",
1225 " print(len(net))\n",
1227 " new_net = eliminate_a_triple_pair_slow(net)\n",
1232 "cell_type": "code",
1233 "execution_count": 118,
1239 "def eliminate_triple_pairs(net):\n",
1240 " print(len(net))\n",
1241 " new_net = eliminate_a_triple_pair(net)\n",
1242 " while new_net:\n",
1243 " print(len(net))\n",
1245 " new_net = eliminate_a_triple_pair(net)\n",
1250 "cell_type": "code",
1251 "execution_count": 134,
1256 "output_type": "stream",
1259 "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
1260 "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=316, left=8, right=21) Link(height=317, left=8, right=17)\n",
1262 "eatp [(Link(height=866, left=4, right=11), Link(height=867, left=5, right=11), Link(height=868, left=4, right=11), Link(height=869, left=5, right=11))]\n",
1263 "removing Link(height=866, left=4, right=11) Link(height=867, left=5, right=11) Link(height=868, left=4, right=11) Link(height=869, left=5, right=11) ; adding Link(height=866, left=5, right=11) Link(height=867, left=4, right=11)\n",
1270 "etlnet = eliminate_triple_pairs(elnet)"
1274 "cell_type": "code",
1275 "execution_count": 112,
1280 "output_type": "stream",
1282 "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
1283 "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=317, left=8, right=17) Link(height=318, left=8, right=21)\n"
1288 "etlnet = eliminate_a_triple_pair(elnet)"
1292 "cell_type": "code",
1293 "execution_count": 135,
1299 "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
1303 "cell_type": "code",
1304 "execution_count": 136,
1310 "[Link(height=315, left=17, right=20),\n",
1311 " Link(height=316, left=8, right=17),\n",
1312 " Link(height=317, left=8, right=21),\n",
1313 " Link(height=318, left=8, right=17),\n",
1314 " Link(height=319, left=8, right=21),\n",
1315 " Link(height=319, left=14, right=17),\n",
1316 " Link(height=320, left=2, right=8),\n",
1317 " Link(height=320, left=17, right=21)]"
1320 "execution_count": 136,
1322 "output_type": "execute_result"
1326 "[l for l in elnet if l.height >= 315 if l.height <= 320 if link_ends(l) & set((8, 17, 21))] "
1330 "cell_type": "code",
1331 "execution_count": 137,
1337 "[Link(height=0, left=17, right=20),\n",
1338 " Link(height=1, left=8, right=17),\n",
1339 " Link(height=2, left=8, right=21),\n",
1340 " Link(height=3, left=8, right=17),\n",
1341 " Link(height=4, left=8, right=21),\n",
1342 " Link(height=4, left=14, right=17),\n",
1343 " Link(height=5, left=2, right=8),\n",
1344 " Link(height=5, left=17, right=21)]"
1347 "execution_count": 137,
1349 "output_type": "execute_result"
1353 "nf = [l for l in elnet if l.height >= 315 if l.height <= 320 if link_ends(l) & set((8, 17, 21))]\n",
1359 "cell_type": "code",
1360 "execution_count": 138,
1365 "output_type": "stream",
1367 "d: Link(height=3, left=8, right=17)\n",
1368 "cs: [Link(height=2, left=8, right=21)]\n",
1369 "c: ; lines: {8, 17, 21}\n",
1370 "b: Link(height=1, left=8, right=17) ; bs: [Link(height=1, left=8, right=17)]\n",
1371 "ah: 0 ; als: []\n",
1372 "a: Link(height=0, left=8, right=21)\n",
1373 "d: Link(height=4, left=8, right=21)\n",
1374 "cs: [Link(height=3, left=8, right=17)]\n",
1375 "c: ; lines: {8, 17, 21}\n",
1376 "b: Link(height=2, left=8, right=21) ; bs: [Link(height=2, left=8, right=21)]\n",
1377 "ah: 1 ; als: [Link(height=1, left=8, right=17)]\n",
1378 "a: Link(height=1, left=8, right=17)\n",
1379 "adding: Link(height=1, left=8, right=17) Link(height=2, left=8, right=21) Link(height=3, left=8, right=17) Link(height=4, left=8, right=21)\n",
1380 "d: Link(height=4, left=14, right=17)\n",
1381 "cs: [Link(height=3, left=8, right=17)]\n",
1382 "c: ; lines: {8, 17, 14}\n",
1383 "b: Link(height=2, left=14, right=17) ; bs: [Link(height=2, left=8, right=21)]\n"
1389 "[(Link(height=1, left=8, right=17),\n",
1390 " Link(height=2, left=8, right=21),\n",
1391 " Link(height=3, left=8, right=17),\n",
1392 " Link(height=4, left=8, right=21))]"
1395 "execution_count": 138,
1397 "output_type": "execute_result"
1401 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(pnf), lambda l: l.height)}\n",
1402 "triple_pair_hg(height_groups, debug=True)"
1406 "cell_type": "code",
1407 "execution_count": 139,
1412 "output_type": "stream",
1415 "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
1416 "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=316, left=8, right=21) Link(height=317, left=8, right=17)\n",
1418 "eatp [(Link(height=866, left=4, right=11), Link(height=867, left=5, right=11), Link(height=868, left=4, right=11), Link(height=869, left=5, right=11))]\n",
1419 "removing Link(height=866, left=4, right=11) Link(height=867, left=5, right=11) Link(height=868, left=4, right=11) Link(height=869, left=5, right=11) ; adding Link(height=866, left=5, right=11) Link(height=867, left=4, right=11)\n",
1426 "setlnet = eliminate_triple_pairs_slow(elnet)"
1430 "cell_type": "code",
1431 "execution_count": 140,
1440 "execution_count": 140,
1442 "output_type": "execute_result"
1450 "cell_type": "code",
1451 "execution_count": 141,
1457 "assert follow_many(string.ascii_lowercase, etlnet) == follow_many(string.ascii_lowercase, elnet)"
1461 "cell_type": "code",
1462 "execution_count": 142,
1468 "'zdunvslcfiqywjmkobhxtraegp'"
1471 "execution_count": 142,
1473 "output_type": "execute_result"
1477 "''.join(follow_many(string.ascii_lowercase, etlnet))"
1481 "cell_type": "code",
1482 "execution_count": 143,
1488 "'zdunvslcfiqywjmkobhxtraegp'"
1491 "execution_count": 143,
1493 "output_type": "execute_result"
1497 "''.join(follow_many(string.ascii_lowercase, setlnet))"
1501 "cell_type": "code",
1502 "execution_count": 144,
1508 "'zdunvslcfiqywjmkobhxtraegp'"
1511 "execution_count": 144,
1513 "output_type": "execute_result"
1517 "''.join(follow_many(string.ascii_lowercase, elnet))"
1521 "cell_type": "code",
1522 "execution_count": 145,
1528 "'zdunvslcfiqywjmkobhxtraegp'"
1531 "execution_count": 145,
1533 "output_type": "execute_result"
1537 "''.join(follow_many(string.ascii_lowercase, lnet))"
1541 "cell_type": "code",
1542 "execution_count": 146,
1551 "execution_count": 146,
1553 "output_type": "execute_result"
1557 "eliminable_pairs(etlnet)"
1561 "cell_type": "code",
1562 "execution_count": 147,
1571 "execution_count": 147,
1573 "output_type": "execute_result"
1577 "len(lnet), len(etlnet)"
1581 "cell_type": "code",
1582 "execution_count": 148,
1588 "def simplify(net0):\n",
1589 " netp = eliminate_pairs(net0)\n",
1590 " new_net = eliminate_a_triple_pair(netp)\n",
1591 " while new_net:\n",
1592 "# print('sipl', len(net0), len(netp), len(new_net))\n",
1593 " netp = eliminate_pairs(new_net)\n",
1594 " new_net = eliminate_a_triple_pair(netp)\n",
1599 "cell_type": "code",
1600 "execution_count": 149,
1605 "output_type": "stream",
1607 "eatp [(Link(height=316, left=8, right=17), Link(height=317, left=8, right=21), Link(height=318, left=8, right=17), Link(height=319, left=8, right=21)), (Link(height=867, left=4, right=11), Link(height=868, left=5, right=11), Link(height=869, left=4, right=11), Link(height=870, left=5, right=11))]\n",
1608 "removing Link(height=316, left=8, right=17) Link(height=317, left=8, right=21) Link(height=318, left=8, right=17) Link(height=319, left=8, right=21) ; adding Link(height=316, left=8, right=21) Link(height=317, left=8, right=17)\n",
1609 "eatp [(Link(height=866, left=4, right=11), Link(height=867, left=5, right=11), Link(height=868, left=4, right=11), Link(height=869, left=5, right=11))]\n",
1610 "removing Link(height=866, left=4, right=11) Link(height=867, left=5, right=11) Link(height=868, left=4, right=11) Link(height=869, left=5, right=11) ; adding Link(height=866, left=5, right=11) Link(height=867, left=4, right=11)\n",
1616 "simple_lnet = simplify(plnet)"
1620 "cell_type": "code",
1621 "execution_count": 150,
1630 "execution_count": 150,
1632 "output_type": "execute_result"
1636 "''.join(follow_many(string.ascii_lowercase, simple_lnet)) == ''.join(follow_many(string.ascii_lowercase, lnet))"
1640 "cell_type": "code",
1641 "execution_count": 151,
1647 "'zdunvslcfiqywjmkobhxtraegp'"
1650 "execution_count": 151,
1652 "output_type": "execute_result"
1656 "''.join(follow_many(string.ascii_lowercase, simple_lnet))"
1660 "cell_type": "code",
1661 "execution_count": 152,
1667 "'zdunvslcfiqywjmkobhxtraegp'"
1670 "execution_count": 152,
1672 "output_type": "execute_result"
1676 "''.join(follow_many(string.ascii_lowercase, lnet))"
1680 "cell_type": "code",
1681 "execution_count": 153,
1690 "execution_count": 153,
1692 "output_type": "execute_result"
1700 "cell_type": "code",
1701 "execution_count": null,
1707 "def add_triple_pair(net, max_lines=None):\n",
1708 " if not max_lines:\n",
1709 " max_lines = max(l.right for l in net)\n",
1710 " a, b, c = 0, 0, 0\n",
1711 " while len(set((a, b, c))) != 3:\n",
1712 " a = random.randrange(max_lines)\n",
1713 " b = random.randrange(max_lines)\n",
1714 " c = random.randrange(max_lines)\n",
1715 " tp = [(min(a, b), max(a, b)), (min(b, c), max(b, c))] * 2\n",
1717 " pairs = [(l.left, l.right) for l in sorted(net)]\n",
1718 " i = random.randrange(len(pairs))\n",
1720 " new_pairs = pairs[:i] + tp + pairs[i:]\n",
1721 " return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)]) "
1725 "cell_type": "code",
1726 "execution_count": null,
1732 "def add_pair(net, max_lines=None):\n",
1733 " if not max_lines:\n",
1734 " max_lines = max(l.right for l in net)\n",
1738 " a = random.randrange(max_lines)\n",
1739 " b = random.randrange(max_lines)\n",
1740 " p = [(min(a, b), max(a, b))] * 2\n",
1742 " pairs = [(l.left, l.right) for l in sorted(net)]\n",
1743 " i = random.randrange(len(pairs))\n",
1746 " new_pairs = pairs[:i] + p + pairs[i:]\n",
1747 " return pack([Link(h, l, r) for h, (l, r) in enumerate(new_pairs)]) "
1751 "cell_type": "code",
1752 "execution_count": null,
1758 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}\n",
1759 "tps = triple_pair_hg(height_groups)\n",
1764 "cell_type": "code",
1765 "execution_count": null,
1772 "lnettp = simple_lnet\n",
1773 "for _ in range(10):\n",
1774 " lnettp = add_pair(lnettp)\n",
1775 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1776 "tps = triple_pair_hg(height_groups)\n",
1781 "cell_type": "code",
1782 "execution_count": null,
1789 "lnettp = simple_lnet\n",
1790 "for _ in range(10):\n",
1791 " lnettp = add_triple_pair(lnettp)\n",
1792 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1793 "tps = triple_pair_hg(height_groups)\n",
1798 "cell_type": "code",
1799 "execution_count": null,
1806 "lnettp = simple_lnet\n",
1807 "for _ in range(10):\n",
1808 " lnettp = add_pair(lnettp)\n",
1809 "for _ in range(10):\n",
1810 " lnettp = add_triple_pair(lnettp)\n",
1811 "height_groups = {h: list(g) for h, g in itertools.groupby(pack(lnettp), lambda l: l.height)}\n",
1812 "tps = triple_pair_hg(height_groups)\n",
1817 "cell_type": "code",
1818 "execution_count": null,
1824 "lnettp == pack(lnettp)"
1828 "cell_type": "code",
1829 "execution_count": null,
1835 "lnettps = simplify(lnettp)\n",
1840 "cell_type": "code",
1841 "execution_count": null,
1847 "len(simple_lnet), len(lnettp), len(lnettps)"
1851 "cell_type": "code",
1852 "execution_count": null,
1862 "display_name": "Python 3",
1863 "language": "python",
1867 "codemirror_mode": {
1871 "file_extension": ".py",
1872 "mimetype": "text/x-python",
1874 "nbconvert_exporter": "python",
1875 "pygments_lexer": "ipython3",