11 "import collections\n",
25 "Link = collections.namedtuple('Link', 'height left right')"
36 "def extract_pairs(net_string):\n",
37 " return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
48 "def read_net_string(net_string):\n",
49 " return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
60 "# def read_net(filename):\n",
61 "# with open(filename) as f:\n",
62 "# pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
63 "# lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
64 "# return [Link(h, l, r) \n",
65 "# for h, (l, r) in enumerate(lrs)]"
70 "execution_count": 28,
76 "def read_net(filename, rev=False):\n",
77 " with open(filename) as f:\n",
78 " pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
80 " lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n",
82 " lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
83 " return [Link(h, l, r) \n",
84 " for h, (l, r) in enumerate(lrs)]"
95 "[Link(height=0, left=2, right=5),\n",
96 " Link(height=1, left=1, right=4),\n",
97 " Link(height=2, left=0, right=3),\n",
98 " Link(height=3, left=0, right=3),\n",
99 " Link(height=4, left=0, right=5),\n",
100 " Link(height=5, left=3, right=5),\n",
101 " Link(height=6, left=0, right=2),\n",
102 " Link(height=7, left=3, right=4),\n",
103 " Link(height=8, left=2, right=4),\n",
104 " Link(height=9, left=1, right=2),\n",
105 " Link(height=10, left=0, right=4),\n",
106 " Link(height=11, left=1, right=2),\n",
107 " Link(height=12, left=2, right=4),\n",
108 " Link(height=13, left=0, right=4),\n",
109 " Link(height=14, left=1, right=4)]"
112 "execution_count": 6,
114 "output_type": "execute_result"
118 "small_net = read_net('04-small.txt')\n",
124 "execution_count": 7,
133 "execution_count": 7,
135 "output_type": "execute_result"
139 "net = read_net('04-lines.txt')\n",
145 "execution_count": 26,
154 "execution_count": 26,
156 "output_type": "execute_result"
160 "permnet = read_net('permutations.txt')\n",
166 "execution_count": 29,
175 "execution_count": 29,
177 "output_type": "execute_result"
181 "rpermnet = read_net('permutations.txt', rev=True)\n",
187 "execution_count": 9,
193 "def show_net(links, pair_sep=', '):\n",
194 " return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
199 "execution_count": 10,
205 "def link_ends(link):\n",
206 " return set((link.left, link.right))"
211 "execution_count": 11,
217 "def follow(initial_line, links):\n",
218 " line = initial_line\n",
219 " heights = sorted(set(l.height for l in links))\n",
220 " for h in heights:\n",
221 " for l in [l for l in links if l.height == h]:\n",
222 " if line in link_ends(l):\n",
223 " line = [e for e in link_ends(l) if e != line][0]\n",
224 "# print(l, line)\n",
230 "execution_count": 12,
237 " packed_links = []\n",
238 " line_heights = collections.defaultdict(lambda: -1)\n",
239 " for link in sorted(net):\n",
240 " link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
241 " line_heights[link.left] = link_height\n",
242 " line_heights[link.right] = link_height\n",
243 " packed_links += [Link(link_height, link.left, link.right)]\n",
244 " return sorted(packed_links)"
249 "execution_count": 13,
258 "execution_count": 13,
260 "output_type": "execute_result"
264 "max(l.height for l in small_net)"
269 "execution_count": 14,
278 "execution_count": 14,
280 "output_type": "execute_result"
284 "max(l.height for l in pack(small_net))"
289 "execution_count": 15,
298 "execution_count": 15,
300 "output_type": "execute_result"
304 "max(l.height for l in net)"
309 "execution_count": 16,
318 "execution_count": 16,
320 "output_type": "execute_result"
324 "max(l.height for l in pack(net))"
329 "execution_count": 17,
335 "def height_groups(net):\n",
336 " return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
341 "execution_count": 18,
347 "def follow_many(in_sequence, net):\n",
348 " hgs = height_groups(net)\n",
349 " seq = list(in_sequence)\n",
351 " for link in hgs[h]:\n",
352 " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
358 "execution_count": 19,
367 "execution_count": 19,
369 "output_type": "execute_result"
373 "''.join(follow_many('abcdefghij', small_net))"
378 "execution_count": 20,
383 "output_type": "stream",
385 "10000 loops, best of 3: 40.1 µs per loop\n"
391 "follow_many('abcdefghij', small_net)"
396 "execution_count": 24,
402 "'doqzmbishkwunvltpcexyjgfra'"
405 "execution_count": 24,
407 "output_type": "execute_result"
411 "''.join(follow_many(string.ascii_lowercase, net))"
416 "execution_count": 27,
422 "'zfrasxwigvjoembqcyhplnktud'"
425 "execution_count": 27,
427 "output_type": "execute_result"
431 "''.join(follow_many(string.ascii_lowercase, permnet))"
436 "execution_count": 30,
442 "'doqzmbishkwunvltpcexyjgfra'"
445 "execution_count": 30,
447 "output_type": "execute_result"
451 "''.join(follow_many(string.ascii_lowercase, rpermnet))"
456 "execution_count": 21,
461 "output_type": "stream",
463 "100 loops, best of 3: 19 ms per loop\n"
469 "follow_many(string.ascii_lowercase, net)"
474 "execution_count": 22,
485 "execution_count": 23,
491 "def eliminable_pairs(net):\n",
492 " hgs = height_groups(net)\n",
494 " for h in range(1, max(hgs.keys())):\n",
495 " for l in hgs[h]:\n",
496 " o = Link(l.height - 1, l.left, l.right)\n",
497 " if o in hgs[h-1]:\n",
498 " eps += [(l, o)]\n",
504 "execution_count": 24,
512 "[(Link(height=115, left=2, right=23), Link(height=114, left=2, right=23)),\n",
513 " (Link(height=149, left=15, right=23), Link(height=148, left=15, right=23)),\n",
514 " (Link(height=201, left=0, right=7), Link(height=200, left=0, right=7)),\n",
515 " (Link(height=207, left=22, right=23), Link(height=206, left=22, right=23)),\n",
516 " (Link(height=210, left=17, right=23), Link(height=209, left=17, right=23)),\n",
517 " (Link(height=247, left=16, right=20), Link(height=246, left=16, right=20)),\n",
518 " (Link(height=418, left=19, right=24), Link(height=417, left=19, right=24)),\n",
519 " (Link(height=424, left=9, right=21), Link(height=423, left=9, right=21)),\n",
520 " (Link(height=453, left=3, right=16), Link(height=452, left=3, right=16)),\n",
521 " (Link(height=456, left=2, right=22), Link(height=455, left=2, right=22)),\n",
522 " (Link(height=465, left=18, right=20), Link(height=464, left=18, right=20)),\n",
523 " (Link(height=491, left=14, right=18), Link(height=490, left=14, right=18)),\n",
524 " (Link(height=552, left=16, right=17), Link(height=551, left=16, right=17)),\n",
525 " (Link(height=772, left=0, right=7), Link(height=771, left=0, right=7)),\n",
526 " (Link(height=848, left=1, right=2), Link(height=847, left=1, right=2)),\n",
527 " (Link(height=895, left=6, right=21), Link(height=894, left=6, right=21)),\n",
528 " (Link(height=930, left=11, right=13), Link(height=929, left=11, right=13)),\n",
529 " (Link(height=987, left=8, right=17), Link(height=986, left=8, right=17)),\n",
530 " (Link(height=988, left=8, right=17), Link(height=987, left=8, right=17)),\n",
531 " (Link(height=1030, left=9, right=24), Link(height=1029, left=9, right=24)),\n",
532 " (Link(height=1134, left=4, right=23), Link(height=1133, left=4, right=23)),\n",
533 " (Link(height=1163, left=14, right=15), Link(height=1162, left=14, right=15)),\n",
534 " (Link(height=1164, left=14, right=15), Link(height=1163, left=14, right=15)),\n",
535 " (Link(height=1170, left=2, right=21), Link(height=1169, left=2, right=21)),\n",
536 " (Link(height=1232, left=6, right=22), Link(height=1231, left=6, right=22)),\n",
537 " (Link(height=1254, left=13, right=15), Link(height=1253, left=13, right=15)),\n",
538 " (Link(height=1255, left=1, right=24), Link(height=1254, left=1, right=24)),\n",
539 " (Link(height=1324, left=3, right=22), Link(height=1323, left=3, right=22)),\n",
540 " (Link(height=1370, left=15, right=19), Link(height=1369, left=15, right=19)),\n",
541 " (Link(height=1441, left=0, right=14), Link(height=1440, left=0, right=14)),\n",
542 " (Link(height=1441, left=11, right=24), Link(height=1440, left=11, right=24)),\n",
543 " (Link(height=1547, left=11, right=13), Link(height=1546, left=11, right=13)),\n",
544 " (Link(height=1578, left=14, right=23), Link(height=1577, left=14, right=23)),\n",
545 " (Link(height=1616, left=7, right=14), Link(height=1615, left=7, right=14)),\n",
546 " (Link(height=1671, left=8, right=20), Link(height=1670, left=8, right=20)),\n",
547 " (Link(height=1684, left=14, right=18), Link(height=1683, left=14, right=18)),\n",
548 " (Link(height=1717, left=0, right=17), Link(height=1716, left=0, right=17)),\n",
549 " (Link(height=1727, left=7, right=8), Link(height=1726, left=7, right=8)),\n",
550 " (Link(height=1866, left=8, right=16), Link(height=1865, left=8, right=16)),\n",
551 " (Link(height=1911, left=1, right=12), Link(height=1910, left=1, right=12)),\n",
552 " (Link(height=1966, left=20, right=23), Link(height=1965, left=20, right=23)),\n",
553 " (Link(height=1974, left=5, right=23), Link(height=1973, left=5, right=23)),\n",
554 " (Link(height=1994, left=18, right=19), Link(height=1993, left=18, right=19)),\n",
555 " (Link(height=2005, left=2, right=19), Link(height=2004, left=2, right=19)),\n",
556 " (Link(height=2031, left=12, right=17), Link(height=2030, left=12, right=17)),\n",
557 " (Link(height=2108, left=7, right=12), Link(height=2107, left=7, right=12)),\n",
558 " (Link(height=2137, left=7, right=16), Link(height=2136, left=7, right=16)),\n",
559 " (Link(height=2138, left=7, right=16), Link(height=2137, left=7, right=16)),\n",
560 " (Link(height=2229, left=10, right=11), Link(height=2228, left=10, right=11)),\n",
561 " (Link(height=2239, left=16, right=24), Link(height=2238, left=16, right=24)),\n",
562 " (Link(height=2240, left=16, right=24), Link(height=2239, left=16, right=24)),\n",
563 " (Link(height=2246, left=4, right=13), Link(height=2245, left=4, right=13)),\n",
564 " (Link(height=2247, left=4, right=13), Link(height=2246, left=4, right=13)),\n",
565 " (Link(height=2276, left=19, right=24), Link(height=2275, left=19, right=24)),\n",
566 " (Link(height=2277, left=4, right=18), Link(height=2276, left=4, right=18))]"
569 "execution_count": 24,
571 "output_type": "execute_result"
575 "eliminable_pairs(pnet)"
580 "execution_count": 25,
585 "output_type": "stream",
587 "10 loops, best of 3: 23.5 ms per loop\n"
593 "eliminable_pairs(pnet)"
598 "execution_count": 26,
604 "def eliminable_pair(hgs):\n",
605 " for h in range(1, max(hgs.keys())):\n",
606 " for l in hgs[h]:\n",
607 " o = Link(l.height - 1, l.left, l.right)\n",
608 " if o in hgs[h-1]:\n",
615 "execution_count": 27,
621 "def eliminate_pairs(net):\n",
622 " hgs = height_groups(pack(net))\n",
623 " eliminable_links = eliminable_pair(hgs)\n",
624 " while eliminable_links:\n",
625 " net = pack(l for l in net if l not in eliminable_links)\n",
626 " hgs = height_groups(pack(net))\n",
627 " eliminable_links = eliminable_pair(hgs)\n",
633 "execution_count": 28,
639 "enet = eliminate_pairs(pnet)"
644 "execution_count": 29,
650 "assert follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, enet)\n",
651 "assert follow_many(string.ascii_lowercase, pnet) == follow_many(string.ascii_lowercase, enet)"
656 "execution_count": 30,
661 "output_type": "stream",
663 "1 loop, best of 3: 2.35 s per loop\n"
669 "eliminate_pairs(pnet)"
674 "execution_count": 31,
680 "def triple_pair(height_groups, debug=False):\n",
682 " for h in range(3, max(height_groups.keys())):\n",
683 " for d in height_groups[h]:\n",
684 " if debug: print('d:', d)\n",
686 " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
687 " if debug: print('cs:', cs)\n",
688 " while ch > 2 and not cs:\n",
690 " cs = [l for l in height_groups[ch] if link_ends(l) & link_ends(d)]\n",
691 " if debug: print('cs:', cs)\n",
692 " if len(cs) == 1:\n",
694 " lines = set((d.left, d.right, c.left, c.right))\n",
695 " if debug: print('c:', '; lines:', lines)\n",
696 " bs = [l for l in height_groups[ch-1] if link_ends(l) & lines]\n",
697 " b = Link(ch - 1, d.left, d.right)\n",
698 " if debug: print('b:', b, '; bs:', bs)\n",
699 " if len(bs) == 1 and b in bs:\n",
700 " ah = b.height - 1\n",
701 " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
702 " if debug: print('ah:', ah, '; als:', als)\n",
703 " while ah > 0 and not als:\n",
705 " als = [l for l in height_groups[ah] if link_ends(l) & link_ends(c)]\n",
706 " if debug: print('ah:', ah, '; als:', als)\n",
707 " a = Link(ah, c.left, c.right)\n",
708 " if debug: print('a:', a)\n",
710 " if debug: print('adding:', a, b, c, d)\n",
711 " ts += [(a, b, c, d)]\n",
717 "execution_count": 32,
723 "def eliminate_a_triple_pair(net, debug=False):\n",
724 " hgs = height_groups(net)\n",
726 " tps = triple_pair(hgs)\n",
727 " if debug: print('eatp', tps)\n",
729 " a, b, c, d = tps[0]\n",
730 " x = Link(b.height - 0.5, b.left, b.right)\n",
731 " y = Link(b.height, a.left, a.right)\n",
732 " if debug: print('removing', a, b, c, d, '; adding', x, y)\n",
733 " return pack([l for l in net if l not in [a, b, c, d]] + [x, y])\n",
739 "execution_count": 33,
745 "[(Link(height=8, left=1, right=5),\n",
746 " Link(height=9, left=1, right=21),\n",
747 " Link(height=10, left=1, right=5),\n",
748 " Link(height=11, left=1, right=21)),\n",
749 " (Link(height=40, left=16, right=23),\n",
750 " Link(height=41, left=16, right=19),\n",
751 " Link(height=42, left=16, right=23),\n",
752 " Link(height=43, left=16, right=19)),\n",
753 " (Link(height=62, left=0, right=10),\n",
754 " Link(height=63, left=10, right=13),\n",
755 " Link(height=64, left=0, right=10),\n",
756 " Link(height=65, left=10, right=13)),\n",
757 " (Link(height=137, left=23, right=24),\n",
758 " Link(height=139, left=0, right=24),\n",
759 " Link(height=140, left=23, right=24),\n",
760 " Link(height=141, left=0, right=24)),\n",
761 " (Link(height=138, left=10, right=21),\n",
762 " Link(height=139, left=2, right=10),\n",
763 " Link(height=140, left=10, right=21),\n",
764 " Link(height=141, left=2, right=10)),\n",
765 " (Link(height=139, left=2, right=10),\n",
766 " Link(height=140, left=10, right=21),\n",
767 " Link(height=141, left=2, right=10),\n",
768 " Link(height=142, left=10, right=21)),\n",
769 " (Link(height=156, left=6, right=11),\n",
770 " Link(height=157, left=3, right=6),\n",
771 " Link(height=158, left=6, right=11),\n",
772 " Link(height=159, left=3, right=6)),\n",
773 " (Link(height=184, left=2, right=21),\n",
774 " Link(height=185, left=5, right=21),\n",
775 " Link(height=186, left=2, right=21),\n",
776 " Link(height=187, left=5, right=21)),\n",
777 " (Link(height=272, left=7, right=13),\n",
778 " Link(height=273, left=7, right=11),\n",
779 " Link(height=274, left=7, right=13),\n",
780 " Link(height=275, left=7, right=11)),\n",
781 " (Link(height=290, left=14, right=15),\n",
782 " Link(height=291, left=5, right=15),\n",
783 " Link(height=292, left=14, right=15),\n",
784 " Link(height=293, left=5, right=15)),\n",
785 " (Link(height=387, left=1, right=8),\n",
786 " Link(height=389, left=8, right=15),\n",
787 " Link(height=390, left=1, right=8),\n",
788 " Link(height=391, left=8, right=15)),\n",
789 " (Link(height=420, left=14, right=22),\n",
790 " Link(height=422, left=14, right=18),\n",
791 " Link(height=423, left=14, right=22),\n",
792 " Link(height=424, left=14, right=18)),\n",
793 " (Link(height=432, left=5, right=19),\n",
794 " Link(height=433, left=1, right=19),\n",
795 " Link(height=434, left=5, right=19),\n",
796 " Link(height=435, left=1, right=19)),\n",
797 " (Link(height=454, left=0, right=15),\n",
798 " Link(height=455, left=14, right=15),\n",
799 " Link(height=456, left=0, right=15),\n",
800 " Link(height=457, left=14, right=15)),\n",
801 " (Link(height=546, left=13, right=21),\n",
802 " Link(height=547, left=6, right=21),\n",
803 " Link(height=548, left=13, right=21),\n",
804 " Link(height=549, left=6, right=21)),\n",
805 " (Link(height=620, left=17, right=23),\n",
806 " Link(height=621, left=1, right=23),\n",
807 " Link(height=622, left=17, right=23),\n",
808 " Link(height=623, left=1, right=23)),\n",
809 " (Link(height=699, left=8, right=15),\n",
810 " Link(height=700, left=3, right=15),\n",
811 " Link(height=701, left=8, right=15),\n",
812 " Link(height=702, left=3, right=15)),\n",
813 " (Link(height=789, left=7, right=24),\n",
814 " Link(height=790, left=8, right=24),\n",
815 " Link(height=791, left=7, right=24),\n",
816 " Link(height=792, left=8, right=24)),\n",
817 " (Link(height=795, left=8, right=13),\n",
818 " Link(height=796, left=4, right=8),\n",
819 " Link(height=797, left=8, right=13),\n",
820 " Link(height=798, left=4, right=8)),\n",
821 " (Link(height=809, left=16, right=17),\n",
822 " Link(height=810, left=3, right=16),\n",
823 " Link(height=811, left=16, right=17),\n",
824 " Link(height=812, left=3, right=16)),\n",
825 " (Link(height=900, left=2, right=15),\n",
826 " Link(height=901, left=13, right=15),\n",
827 " Link(height=902, left=2, right=15),\n",
828 " Link(height=903, left=13, right=15)),\n",
829 " (Link(height=921, left=2, right=15),\n",
830 " Link(height=922, left=15, right=16),\n",
831 " Link(height=923, left=2, right=15),\n",
832 " Link(height=924, left=15, right=16)),\n",
833 " (Link(height=961, left=2, right=15),\n",
834 " Link(height=962, left=2, right=14),\n",
835 " Link(height=963, left=2, right=15),\n",
836 " Link(height=964, left=2, right=14)),\n",
837 " (Link(height=976, left=13, right=18),\n",
838 " Link(height=979, left=18, right=19),\n",
839 " Link(height=980, left=13, right=18),\n",
840 " Link(height=981, left=18, right=19)),\n",
841 " (Link(height=985, left=5, right=16),\n",
842 " Link(height=986, left=2, right=5),\n",
843 " Link(height=987, left=5, right=16),\n",
844 " Link(height=988, left=2, right=5)),\n",
845 " (Link(height=1050, left=9, right=24),\n",
846 " Link(height=1054, left=9, right=18),\n",
847 " Link(height=1055, left=9, right=24),\n",
848 " Link(height=1056, left=9, right=18)),\n",
849 " (Link(height=1159, left=11, right=21),\n",
850 " Link(height=1160, left=11, right=14),\n",
851 " Link(height=1161, left=11, right=21),\n",
852 " Link(height=1162, left=11, right=14)),\n",
853 " (Link(height=1284, left=0, right=11),\n",
854 " Link(height=1285, left=0, right=14),\n",
855 " Link(height=1286, left=0, right=11),\n",
856 " Link(height=1287, left=0, right=14)),\n",
857 " (Link(height=1331, left=4, right=9),\n",
858 " Link(height=1333, left=4, right=10),\n",
859 " Link(height=1334, left=4, right=9),\n",
860 " Link(height=1335, left=4, right=10)),\n",
861 " (Link(height=1332, left=12, right=18),\n",
862 " Link(height=1333, left=12, right=24),\n",
863 " Link(height=1334, left=12, right=18),\n",
864 " Link(height=1335, left=12, right=24)),\n",
865 " (Link(height=1343, left=0, right=17),\n",
866 " Link(height=1344, left=0, right=23),\n",
867 " Link(height=1345, left=0, right=17),\n",
868 " Link(height=1346, left=0, right=23)),\n",
869 " (Link(height=1357, left=4, right=16),\n",
870 " Link(height=1358, left=16, right=17),\n",
871 " Link(height=1359, left=4, right=16),\n",
872 " Link(height=1360, left=16, right=17)),\n",
873 " (Link(height=1441, left=6, right=20),\n",
874 " Link(height=1443, left=16, right=20),\n",
875 " Link(height=1444, left=6, right=20),\n",
876 " Link(height=1445, left=16, right=20)),\n",
877 " (Link(height=1464, left=17, right=23),\n",
878 " Link(height=1465, left=3, right=17),\n",
879 " Link(height=1466, left=17, right=23),\n",
880 " Link(height=1467, left=3, right=17)),\n",
881 " (Link(height=1540, left=8, right=23),\n",
882 " Link(height=1541, left=7, right=23),\n",
883 " Link(height=1542, left=8, right=23),\n",
884 " Link(height=1543, left=7, right=23)),\n",
885 " (Link(height=1570, left=0, right=1),\n",
886 " Link(height=1571, left=1, right=21),\n",
887 " Link(height=1572, left=0, right=1),\n",
888 " Link(height=1573, left=1, right=21)),\n",
889 " (Link(height=1600, left=15, right=22),\n",
890 " Link(height=1603, left=7, right=15),\n",
891 " Link(height=1604, left=15, right=22),\n",
892 " Link(height=1605, left=7, right=15)),\n",
893 " (Link(height=1632, left=12, right=18),\n",
894 " Link(height=1634, left=12, right=20),\n",
895 " Link(height=1635, left=12, right=18),\n",
896 " Link(height=1636, left=12, right=20)),\n",
897 " (Link(height=1702, left=13, right=24),\n",
898 " Link(height=1705, left=14, right=24),\n",
899 " Link(height=1706, left=13, right=24),\n",
900 " Link(height=1707, left=14, right=24)),\n",
901 " (Link(height=1721, left=3, right=24),\n",
902 " Link(height=1722, left=3, right=21),\n",
903 " Link(height=1723, left=3, right=24),\n",
904 " Link(height=1724, left=3, right=21)),\n",
905 " (Link(height=1722, left=3, right=21),\n",
906 " Link(height=1723, left=3, right=24),\n",
907 " Link(height=1724, left=3, right=21),\n",
908 " Link(height=1725, left=3, right=24)),\n",
909 " (Link(height=1762, left=0, right=21),\n",
910 " Link(height=1763, left=13, right=21),\n",
911 " Link(height=1764, left=0, right=21),\n",
912 " Link(height=1765, left=13, right=21)),\n",
913 " (Link(height=1769, left=7, right=9),\n",
914 " Link(height=1770, left=7, right=12),\n",
915 " Link(height=1771, left=7, right=9),\n",
916 " Link(height=1772, left=7, right=12)),\n",
917 " (Link(height=1914, left=10, right=24),\n",
918 " Link(height=1915, left=8, right=24),\n",
919 " Link(height=1916, left=10, right=24),\n",
920 " Link(height=1917, left=8, right=24)),\n",
921 " (Link(height=1920, left=4, right=23),\n",
922 " Link(height=1921, left=3, right=4),\n",
923 " Link(height=1922, left=4, right=23),\n",
924 " Link(height=1923, left=3, right=4)),\n",
925 " (Link(height=2023, left=4, right=7),\n",
926 " Link(height=2024, left=7, right=15),\n",
927 " Link(height=2025, left=4, right=7),\n",
928 " Link(height=2026, left=7, right=15)),\n",
929 " (Link(height=2025, left=8, right=19),\n",
930 " Link(height=2031, left=8, right=15),\n",
931 " Link(height=2032, left=8, right=19),\n",
932 " Link(height=2033, left=8, right=15)),\n",
933 " (Link(height=2152, left=10, right=15),\n",
934 " Link(height=2153, left=10, right=16),\n",
935 " Link(height=2154, left=10, right=15),\n",
936 " Link(height=2155, left=10, right=16)),\n",
937 " (Link(height=2194, left=22, right=24),\n",
938 " Link(height=2195, left=7, right=22),\n",
939 " Link(height=2196, left=22, right=24),\n",
940 " Link(height=2197, left=7, right=22)),\n",
941 " (Link(height=2211, left=5, right=6),\n",
942 " Link(height=2212, left=6, right=14),\n",
943 " Link(height=2213, left=5, right=6),\n",
944 " Link(height=2214, left=6, right=14))]"
947 "execution_count": 33,
949 "output_type": "execute_result"
953 "hgs = height_groups(enet)\n",
959 "execution_count": 34,
965 "etnet = eliminate_a_triple_pair(enet)"
970 "execution_count": 35,
976 "assert follow_many(string.ascii_lowercase, etnet) == follow_many(string.ascii_lowercase, enet)"
981 "execution_count": 36,
987 "def eliminate_triple_pairs(net):\n",
988 " print(len(net))\n",
989 " new_net = eliminate_a_triple_pair(net)\n",
991 " print(len(net))\n",
993 " new_net = eliminate_a_triple_pair(net)\n",
999 "execution_count": 37,
1006 "output_type": "stream",
1061 "setnet = eliminate_triple_pairs(enet)"
1065 "cell_type": "code",
1066 "execution_count": 38,
1075 "execution_count": 38,
1077 "output_type": "execute_result"
1085 "cell_type": "code",
1086 "execution_count": 39,
1092 "assert follow_many(string.ascii_lowercase, etnet) == follow_many(string.ascii_lowercase, enet)"
1096 "cell_type": "code",
1097 "execution_count": 40,
1103 "'doqzmbishkwunvltpcexyjgfra'"
1106 "execution_count": 40,
1108 "output_type": "execute_result"
1112 "''.join(follow_many(string.ascii_lowercase, etnet))"
1116 "cell_type": "code",
1117 "execution_count": 41,
1123 "'doqzmbishkwunvltpcexyjgfra'"
1126 "execution_count": 41,
1128 "output_type": "execute_result"
1132 "''.join(follow_many(string.ascii_lowercase, setnet))"
1136 "cell_type": "code",
1137 "execution_count": 42,
1143 "'doqzmbishkwunvltpcexyjgfra'"
1146 "execution_count": 42,
1148 "output_type": "execute_result"
1152 "''.join(follow_many(string.ascii_lowercase, enet))"
1156 "cell_type": "code",
1157 "execution_count": 43,
1163 "'doqzmbishkwunvltpcexyjgfra'"
1166 "execution_count": 43,
1168 "output_type": "execute_result"
1172 "''.join(follow_many(string.ascii_lowercase, net))"
1176 "cell_type": "code",
1177 "execution_count": 44,
1186 "execution_count": 44,
1188 "output_type": "execute_result"
1192 "eliminable_pairs(etnet)"
1196 "cell_type": "code",
1197 "execution_count": 45,
1206 "execution_count": 45,
1208 "output_type": "execute_result"
1212 "len(net), len(etnet)"
1216 "cell_type": "code",
1217 "execution_count": 46,
1223 "def simplify(net0):\n",
1224 " netp = eliminate_pairs(net0)\n",
1225 " new_net = eliminate_a_triple_pair(netp)\n",
1226 " while new_net:\n",
1227 "# print('sipl', len(net0), len(netp), len(new_net))\n",
1228 " netp = eliminate_pairs(new_net)\n",
1229 " new_net = eliminate_a_triple_pair(netp)\n",
1234 "cell_type": "code",
1235 "execution_count": 47,
1241 "simple_net = simplify(pnet)"
1245 "cell_type": "code",
1246 "execution_count": 48,
1255 "execution_count": 48,
1257 "output_type": "execute_result"
1261 "''.join(follow_many(string.ascii_lowercase, simple_net)) == ''.join(follow_many(string.ascii_lowercase, net))"
1265 "cell_type": "code",
1266 "execution_count": 49,
1272 "'doqzmbishkwunvltpcexyjgfra'"
1275 "execution_count": 49,
1277 "output_type": "execute_result"
1281 "''.join(follow_many(string.ascii_lowercase, simple_net))"
1285 "cell_type": "code",
1286 "execution_count": 50,
1292 "'doqzmbishkwunvltpcexyjgfra'"
1295 "execution_count": 50,
1297 "output_type": "execute_result"
1301 "''.join(follow_many(string.ascii_lowercase, net))"
1305 "cell_type": "code",
1306 "execution_count": 51,
1315 "execution_count": 51,
1317 "output_type": "execute_result"
1325 "cell_type": "code",
1326 "execution_count": 52,
1332 "def simplify_with_checks(net0):\n",
1333 " netp = eliminate_pairs(net0)\n",
1334 " if follow_many(string.ascii_lowercase, net0) != follow_many(string.ascii_lowercase, netp):\n",
1335 " print('pairs', eliminable_pairs(net0))\n",
1338 " print('pairs ok')\n",
1339 " new_net = eliminate_a_triple_pair(netp)\n",
1340 " if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
1341 " hg = find_height_groups(netp)\n",
1342 " print('triple', triple_pair_hg(hg))\n",
1345 " print('triple ok')\n",
1346 " while new_net:\n",
1347 "# print('sipl', len(net0), len(netp), len(new_net))\n",
1348 " netp = eliminate_pairs(new_net)\n",
1349 " if follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
1350 " print('pairs', eliminable_pairs(new_net))\n",
1351 " return new_net\n",
1353 " print('pairs ok')\n",
1354 " new_net = eliminate_a_triple_pair(netp)\n",
1355 " if new_net and follow_many(string.ascii_lowercase, new_net) != follow_many(string.ascii_lowercase, netp):\n",
1356 " hg = find_height_groups(netp)\n",
1357 " print('triple', triple_pair_hg(hg))\n",
1360 " print('triple ok')\n",
1361 " print('** done')\n",
1366 "cell_type": "code",
1367 "execution_count": 53,
1374 "output_type": "stream",
1479 "spnet = simplify_with_checks(pnet)"
1483 "cell_type": "code",
1484 "execution_count": 54,
1493 "execution_count": 54,
1495 "output_type": "execute_result"
1499 "''.join(follow_many(string.ascii_lowercase, spnet)) == ''.join(follow_many(string.ascii_lowercase, net))"
1503 "cell_type": "code",
1504 "execution_count": 55,
1513 "execution_count": 55,
1515 "output_type": "execute_result"
1523 "cell_type": "code",
1524 "execution_count": null,
1534 "display_name": "Python 3",
1535 "language": "python",
1539 "codemirror_mode": {
1543 "file_extension": ".py",
1544 "mimetype": "text/x-python",
1546 "nbconvert_exporter": "python",
1547 "pygments_lexer": "ipython3",