11 "import collections\n",
19 "execution_count": 45,
25 "Link = collections.namedtuple('Link', 'height left right')"
30 "execution_count": 46,
36 "def extract_pairs(net_string):\n",
37 " return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
42 "execution_count": 47,
48 "def read_net_string(net_string):\n",
49 " return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
54 "execution_count": 48,
60 "def read_net(filename, rev=False):\n",
61 " with open(filename) as f:\n",
62 " pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
64 " lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n",
66 " lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
67 " return [Link(h, l, r) \n",
68 " for h, (l, r) in enumerate(lrs)]"
73 "execution_count": 15,
79 "[Link(height=0, left=2, right=5),\n",
80 " Link(height=1, left=1, right=4),\n",
81 " Link(height=2, left=0, right=3),\n",
82 " Link(height=3, left=0, right=3),\n",
83 " Link(height=4, left=0, right=5),\n",
84 " Link(height=5, left=3, right=5),\n",
85 " Link(height=6, left=0, right=2),\n",
86 " Link(height=7, left=3, right=4),\n",
87 " Link(height=8, left=2, right=4),\n",
88 " Link(height=9, left=1, right=2),\n",
89 " Link(height=10, left=0, right=4),\n",
90 " Link(height=11, left=1, right=2),\n",
91 " Link(height=12, left=2, right=4),\n",
92 " Link(height=13, left=0, right=4),\n",
93 " Link(height=14, left=1, right=4)]"
96 "execution_count": 15,
98 "output_type": "execute_result"
102 "small_net = read_net('04-small.txt')\n",
108 "execution_count": 16,
117 "execution_count": 16,
119 "output_type": "execute_result"
123 "net = read_net('04-lines.txt')\n",
129 "execution_count": 36,
138 "execution_count": 36,
140 "output_type": "execute_result"
144 "permnet = read_net('permutations.txt')\n",
150 "execution_count": 41,
159 "execution_count": 41,
161 "output_type": "execute_result"
165 "rpermnet = read_net('permutations.txt', rev=True)\n",
171 "execution_count": 18,
177 "def show_net(links, pair_sep=', '):\n",
178 " return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
183 "execution_count": 19,
189 "def link_ends(link):\n",
190 " return set((link.left, link.right))"
195 "execution_count": 20,
201 "def follow(initial_line, links):\n",
202 " line = initial_line\n",
203 " heights = sorted(set(l.height for l in links))\n",
204 " for h in heights:\n",
205 " for l in [l for l in links if l.height == h]:\n",
206 " if line in link_ends(l):\n",
207 " line = [e for e in link_ends(l) if e != line][0]\n",
208 "# print(l, line)\n",
214 "execution_count": 21,
221 " packed_links = []\n",
222 " line_heights = collections.defaultdict(lambda: -1)\n",
223 " for link in sorted(net):\n",
224 " link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
225 " line_heights[link.left] = link_height\n",
226 " line_heights[link.right] = link_height\n",
227 " packed_links += [Link(link_height, link.left, link.right)]\n",
228 " return sorted(packed_links)"
233 "execution_count": 22,
242 "execution_count": 22,
244 "output_type": "execute_result"
248 "max(l.height for l in small_net)"
253 "execution_count": 23,
262 "execution_count": 23,
264 "output_type": "execute_result"
268 "max(l.height for l in pack(small_net))"
273 "execution_count": 24,
282 "execution_count": 24,
284 "output_type": "execute_result"
288 "max(l.height for l in net)"
293 "execution_count": 25,
304 "execution_count": 26,
313 "execution_count": 26,
315 "output_type": "execute_result"
319 "max(l.height for l in pnet)"
324 "execution_count": 27,
330 "def height_groups(net):\n",
331 " return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
336 "execution_count": 28,
342 "def follow_many(in_sequence, net):\n",
343 " hgs = height_groups(net)\n",
344 " seq = list(in_sequence)\n",
346 " for link in hgs[h]:\n",
347 " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
353 "execution_count": 29,
362 "execution_count": 29,
364 "output_type": "execute_result"
368 "''.join(follow_many('abcdef', small_net))"
373 "execution_count": 69,
378 "output_type": "stream",
380 " 0 ['0', '1', '2', '3', '4', '5']\n",
381 " 1 (2, 5) ['0', '1', '5', '3', '4', '2']\n",
382 " 2 (1, 4) ['0', '4', '5', '3', '1', '2']\n",
383 " 3 (0, 3) ['3', '4', '5', '0', '1', '2']\n",
384 " 4 (0, 3) ['0', '4', '5', '3', '1', '2']\n",
385 " 5 (0, 5) ['2', '4', '5', '3', '1', '0']\n",
386 " 6 (3, 5) ['2', '4', '5', '0', '1', '3']\n",
387 " 7 (0, 2) ['5', '4', '2', '0', '1', '3']\n",
388 " 8 (3, 4) ['5', '4', '2', '1', '0', '3']\n",
389 " 9 (2, 4) ['5', '4', '0', '1', '2', '3']\n",
390 "10 (1, 2) ['5', '0', '4', '1', '2', '3']\n",
391 "11 (0, 4) ['2', '0', '4', '1', '5', '3']\n",
392 "12 (1, 2) ['2', '4', '0', '1', '5', '3']\n",
393 "13 (2, 4) ['2', '4', '5', '1', '0', '3']\n",
394 "14 (0, 4) ['0', '4', '5', '1', '2', '3']\n",
395 "15 (1, 4) ['0', '2', '5', '1', '4', '3']\n"
400 "for i in range(len(small_net)+1):\n",
401 " pre_net = small_net[:i]\n",
403 " print('{:2}'.format(i), \n",
404 " \" \".format(small_net[i-1].left, small_net[i-1].right),\n",
405 " follow_many(\"012345\", pre_net))\n",
407 " print('{:2}'.format(i), \n",
408 " \"({}, {})\".format(small_net[i-1].left, small_net[i-1].right),\n",
409 " follow_many(\"012345\", pre_net))\n",
416 "execution_count": 66,
422 "[Link(height=0, left=2, right=5),\n",
423 " Link(height=1, left=1, right=4),\n",
424 " Link(height=2, left=0, right=3),\n",
425 " Link(height=3, left=0, right=3),\n",
426 " Link(height=4, left=0, right=5),\n",
427 " Link(height=5, left=3, right=5),\n",
428 " Link(height=6, left=0, right=2),\n",
429 " Link(height=7, left=3, right=4),\n",
430 " Link(height=8, left=2, right=4),\n",
431 " Link(height=9, left=1, right=2),\n",
432 " Link(height=10, left=0, right=4),\n",
433 " Link(height=11, left=1, right=2),\n",
434 " Link(height=12, left=2, right=4),\n",
435 " Link(height=13, left=0, right=4),\n",
436 " Link(height=14, left=1, right=4)]"
439 "execution_count": 66,
441 "output_type": "execute_result"
450 "execution_count": 30,
455 "output_type": "stream",
457 "10000 loops, best of 3: 42 µs per loop\n"
463 "follow_many('abcdefghij', small_net)"
468 "execution_count": 37,
474 "'doqzmbishkwunvltpcexyjgfra'"
477 "execution_count": 37,
479 "output_type": "execute_result"
483 "''.join(follow_many(string.ascii_lowercase, net))"
488 "execution_count": 39,
494 "'zfrasxwigvjoembqcyhplnktud'"
497 "execution_count": 39,
499 "output_type": "execute_result"
503 "''.join(follow_many(string.ascii_lowercase, permnet))"
508 "execution_count": 42,
514 "'doqzmbishkwunvltpcexyjgfra'"
517 "execution_count": 42,
519 "output_type": "execute_result"
523 "''.join(follow_many(string.ascii_lowercase, rpermnet))"
528 "execution_count": 43,
537 "execution_count": 43,
539 "output_type": "execute_result"
543 "follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, rpermnet)"
548 "execution_count": 32,
553 "output_type": "stream",
555 "10 loops, best of 3: 19.3 ms per loop\n"
561 "follow_many(string.ascii_lowercase, net)"
566 "execution_count": 33,
571 "output_type": "stream",
573 "100 loops, best of 3: 18.7 ms per loop\n"
579 "follow_many(string.ascii_lowercase, pnet)"
584 "execution_count": null,
594 "display_name": "Python 3",
595 "language": "python",
603 "file_extension": ".py",
604 "mimetype": "text/x-python",
606 "nbconvert_exporter": "python",
607 "pygments_lexer": "ipython3",