--- /dev/null
+{
+ "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
+}
projects / ou-summer-of-code-2017.git / blobdiff