11 "import collections\n",
19 "execution_count": 28,
25 "Link = collections.namedtuple('Link', 'height left right')"
30 "execution_count": 29,
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": 30,
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": 31,
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": 32,
76 "[Link(height=0, left=2, right=5),\n",
77 " Link(height=1, left=1, right=4),\n",
78 " Link(height=2, left=0, right=3),\n",
79 " Link(height=3, left=0, right=3),\n",
80 " Link(height=4, left=0, right=5),\n",
81 " Link(height=5, left=3, right=5),\n",
82 " Link(height=6, left=0, right=2),\n",
83 " Link(height=7, left=3, right=4),\n",
84 " Link(height=8, left=2, right=4),\n",
85 " Link(height=9, left=1, right=2),\n",
86 " Link(height=10, left=0, right=4),\n",
87 " Link(height=11, left=1, right=2),\n",
88 " Link(height=12, left=2, right=4),\n",
89 " Link(height=13, left=0, right=4),\n",
90 " Link(height=14, left=1, right=4)]"
93 "execution_count": 32,
95 "output_type": "execute_result"
99 "small_net = read_net('04-small.txt')\n",
105 "execution_count": 33,
114 "execution_count": 33,
116 "output_type": "execute_result"
120 "net = read_net('04-lines.txt')\n",
126 "execution_count": 34,
132 "def show_net(links, pair_sep=', '):\n",
133 " return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
138 "execution_count": 35,
144 "def link_ends(link):\n",
145 " return set((link.left, link.right))"
150 "execution_count": 36,
156 "def follow(initial_line, links):\n",
157 " line = initial_line\n",
158 " heights = sorted(set(l.height for l in links))\n",
159 " for h in heights:\n",
160 " for l in [l for l in links if l.height == h]:\n",
161 " if line in link_ends(l):\n",
162 " line = [e for e in link_ends(l) if e != line][0]\n",
163 "# print(l, line)\n",
169 "execution_count": 37,
176 " packed_links = []\n",
177 " line_heights = collections.defaultdict(lambda: -1)\n",
178 " for link in sorted(net):\n",
179 " link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
180 " line_heights[link.left] = link_height\n",
181 " line_heights[link.right] = link_height\n",
182 " packed_links += [Link(link_height, link.left, link.right)]\n",
183 " return sorted(packed_links)"
188 "execution_count": 38,
197 "execution_count": 38,
199 "output_type": "execute_result"
203 "max(l.height for l in small_net)"
208 "execution_count": 39,
217 "execution_count": 39,
219 "output_type": "execute_result"
223 "max(l.height for l in pack(small_net))"
228 "execution_count": 40,
237 "execution_count": 40,
239 "output_type": "execute_result"
243 "max(l.height for l in net)"
248 "execution_count": 41,
259 "execution_count": 42,
268 "execution_count": 42,
270 "output_type": "execute_result"
274 "max(l.height for l in pnet)"
279 "execution_count": 43,
285 "def height_groups(net):\n",
286 " return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
291 "execution_count": 44,
297 "def follow_many(in_sequence, net):\n",
298 " hgs = height_groups(net)\n",
299 " seq = list(in_sequence)\n",
301 " for link in hgs[h]:\n",
302 " seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
308 "execution_count": 45,
317 "execution_count": 45,
319 "output_type": "execute_result"
323 "''.join(follow_many('abcdef', small_net))"
328 "execution_count": 46,
333 "output_type": "stream",
335 "10000 loops, best of 3: 39.5 µs per loop\n"
341 "follow_many('abcdefghij', small_net)"
346 "execution_count": 47,
352 "'doqzmbishkwunvltpcexyjgfra'"
355 "execution_count": 47,
357 "output_type": "execute_result"
361 "''.join(follow_many(string.ascii_lowercase, net))"
366 "execution_count": 48,
371 "output_type": "stream",
373 "10 loops, best of 3: 19.7 ms per loop\n"
379 "follow_many(string.ascii_lowercase, net)"
384 "execution_count": 49,
389 "output_type": "stream",
391 "100 loops, best of 3: 18.6 ms per loop\n"
397 "follow_many(string.ascii_lowercase, pnet)"
402 "execution_count": null,
412 "display_name": "Python 3",
413 "language": "python",
421 "file_extension": ".py",
422 "mimetype": "text/x-python",
424 "nbconvert_exporter": "python",
425 "pygments_lexer": "ipython3",