--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import collections\n",
+ "import string\n",
+ "import itertools\n",
+ "import re"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "Link = collections.namedtuple('Link', 'height left right')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "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": 4,
+ "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": 5,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def read_net(filename):\n",
+ " with open(filename) as f:\n",
+ " pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\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": 6,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[Link(height=0, left=2, right=3),\n",
+ " Link(height=1, left=2, right=6),\n",
+ " Link(height=2, left=3, right=7),\n",
+ " Link(height=3, left=5, right=6),\n",
+ " Link(height=4, left=0, right=1),\n",
+ " Link(height=5, left=0, right=1),\n",
+ " Link(height=6, left=6, right=7),\n",
+ " Link(height=7, left=2, right=5),\n",
+ " Link(height=8, left=6, right=9),\n",
+ " Link(height=9, left=4, right=8),\n",
+ " Link(height=10, left=0, right=2),\n",
+ " Link(height=11, left=5, right=7),\n",
+ " Link(height=12, left=4, right=8),\n",
+ " Link(height=13, left=1, right=5),\n",
+ " Link(height=14, left=6, right=8),\n",
+ " Link(height=15, left=6, right=9),\n",
+ " Link(height=16, left=2, right=5),\n",
+ " Link(height=17, left=1, right=8),\n",
+ " Link(height=18, left=5, right=7),\n",
+ " Link(height=19, left=2, right=9)]"
+ ]
+ },
+ "execution_count": 6,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "small_net = read_net('04-small.txt')\n",
+ "small_net"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "10135"
+ ]
+ },
+ "execution_count": 7,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "net = read_net('04-lines.txt')\n",
+ "len(net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "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": 9,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def link_ends(link):\n",
+ " return set((link.left, link.right))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "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": 11,
+ "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": 12,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "19"
+ ]
+ },
+ "execution_count": 12,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(l.height for l in small_net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "7"
+ ]
+ },
+ "execution_count": 13,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(l.height for l in pack(small_net))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "10134"
+ ]
+ },
+ "execution_count": 14,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(l.height for l in net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "pnet = pack(net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2286"
+ ]
+ },
+ "execution_count": 16,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max(l.height for l in pnet)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "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": 18,
+ "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": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'djihegcafb'"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many('abcdefghij', small_net))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10000 loops, best of 3: 50.4 µs per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "follow_many('abcdefghij', small_net)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'doqzmbishkwunvltpcexyjgfra'"
+ ]
+ },
+ "execution_count": 21,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(follow_many(string.ascii_lowercase, net))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10 loops, best of 3: 21 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "follow_many(string.ascii_lowercase, net)"
+ ]
+ },
+ {
+ "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