{
"cells": [
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import collections\n",
"import string\n",
"import itertools\n",
"import re"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"Link = collections.namedtuple('Link', 'height left right')"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def extract_pairs(net_string):\n",
" return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def read_net_string(net_string):\n",
" return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def read_net(filename, rev=False):\n",
" with open(filename) as f:\n",
" pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
" if rev:\n",
" lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n",
" else:\n",
" lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
" return [Link(h, l, r) \n",
" for h, (l, r) in enumerate(lrs)]"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Link(height=0, left=2, right=5),\n",
" Link(height=1, left=1, right=4),\n",
" Link(height=2, left=0, right=3),\n",
" Link(height=3, left=0, right=3),\n",
" Link(height=4, left=0, right=5),\n",
" Link(height=5, left=3, right=5),\n",
" Link(height=6, left=0, right=2),\n",
" Link(height=7, left=3, right=4),\n",
" Link(height=8, left=2, right=4),\n",
" Link(height=9, left=1, right=2),\n",
" Link(height=10, left=0, right=4),\n",
" Link(height=11, left=1, right=2),\n",
" Link(height=12, left=2, right=4),\n",
" Link(height=13, left=0, right=4),\n",
" Link(height=14, left=1, right=4)]"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"small_net = read_net('04-small.txt')\n",
"small_net"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10135"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"net = read_net('04-lines.txt')\n",
"len(net)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"23"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"permnet = read_net('permutations.txt')\n",
"len(permnet)"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"23"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rpermnet = read_net('permutations.txt', rev=True)\n",
"len(rpermnet)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def show_net(links, pair_sep=', '):\n",
" return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def link_ends(link):\n",
" return set((link.left, link.right))"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def follow(initial_line, links):\n",
" line = initial_line\n",
" heights = sorted(set(l.height for l in links))\n",
" for h in heights:\n",
" for l in [l for l in links if l.height == h]:\n",
" if line in link_ends(l):\n",
" line = [e for e in link_ends(l) if e != line][0]\n",
"# print(l, line)\n",
" return line"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def pack(net):\n",
" packed_links = []\n",
" line_heights = collections.defaultdict(lambda: -1)\n",
" for link in sorted(net):\n",
" link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
" line_heights[link.left] = link_height\n",
" line_heights[link.right] = link_height\n",
" packed_links += [Link(link_height, link.left, link.right)]\n",
" return sorted(packed_links)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"14"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(l.height for l in small_net)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(l.height for l in pack(small_net))"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10134"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(l.height for l in net)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"pnet = pack(net)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2286"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(l.height for l in pnet)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def height_groups(net):\n",
" return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def follow_many(in_sequence, net):\n",
" hgs = height_groups(net)\n",
" seq = list(in_sequence)\n",
" for h in hgs:\n",
" for link in hgs[h]:\n",
" seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
" return seq"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'acfbed'"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many('abcdef', small_net))"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0 ['0', '1', '2', '3', '4', '5']\n",
" 1 (2, 5) ['0', '1', '5', '3', '4', '2']\n",
" 2 (1, 4) ['0', '4', '5', '3', '1', '2']\n",
" 3 (0, 3) ['3', '4', '5', '0', '1', '2']\n",
" 4 (0, 3) ['0', '4', '5', '3', '1', '2']\n",
" 5 (0, 5) ['2', '4', '5', '3', '1', '0']\n",
" 6 (3, 5) ['2', '4', '5', '0', '1', '3']\n",
" 7 (0, 2) ['5', '4', '2', '0', '1', '3']\n",
" 8 (3, 4) ['5', '4', '2', '1', '0', '3']\n",
" 9 (2, 4) ['5', '4', '0', '1', '2', '3']\n",
"10 (1, 2) ['5', '0', '4', '1', '2', '3']\n",
"11 (0, 4) ['2', '0', '4', '1', '5', '3']\n",
"12 (1, 2) ['2', '4', '0', '1', '5', '3']\n",
"13 (2, 4) ['2', '4', '5', '1', '0', '3']\n",
"14 (0, 4) ['0', '4', '5', '1', '2', '3']\n",
"15 (1, 4) ['0', '2', '5', '1', '4', '3']\n"
]
}
],
"source": [
"for i in range(len(small_net)+1):\n",
" pre_net = small_net[:i]\n",
" if i == 0:\n",
" print('{:2}'.format(i), \n",
" \" \".format(small_net[i-1].left, small_net[i-1].right),\n",
" follow_many(\"012345\", pre_net))\n",
" else:\n",
" print('{:2}'.format(i), \n",
" \"({}, {})\".format(small_net[i-1].left, small_net[i-1].right),\n",
" follow_many(\"012345\", pre_net))\n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Link(height=0, left=2, right=5),\n",
" Link(height=1, left=1, right=4),\n",
" Link(height=2, left=0, right=3),\n",
" Link(height=3, left=0, right=3),\n",
" Link(height=4, left=0, right=5),\n",
" Link(height=5, left=3, right=5),\n",
" Link(height=6, left=0, right=2),\n",
" Link(height=7, left=3, right=4),\n",
" Link(height=8, left=2, right=4),\n",
" Link(height=9, left=1, right=2),\n",
" Link(height=10, left=0, right=4),\n",
" Link(height=11, left=1, right=2),\n",
" Link(height=12, left=2, right=4),\n",
" Link(height=13, left=0, right=4),\n",
" Link(height=14, left=1, right=4)]"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"small_net[:15]"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10000 loops, best of 3: 42 µs per loop\n"
]
}
],
"source": [
"%%timeit\n",
"follow_many('abcdefghij', small_net)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'doqzmbishkwunvltpcexyjgfra'"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, net))"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'zfrasxwigvjoembqcyhplnktud'"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, permnet))"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'doqzmbishkwunvltpcexyjgfra'"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(follow_many(string.ascii_lowercase, rpermnet))"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, rpermnet)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10 loops, best of 3: 19.3 ms per loop\n"
]
}
],
"source": [
"%%timeit\n",
"follow_many(string.ascii_lowercase, net)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"100 loops, best of 3: 18.7 ms per loop\n"
]
}
],
"source": [
"%%timeit\n",
"follow_many(string.ascii_lowercase, pnet)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2+"
}
},
"nbformat": 4,
"nbformat_minor": 2
}