X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;ds=sidebyside;f=04-08-amidakuji%2Famidakuji-solution-1.ipynb;fp=04-08-amidakuji%2Famidakuji-solution-1.ipynb;h=d9a924911f735848c5da2f1fbb7de1d2f493feef;hb=787b6246ddfd5d1eaa228cdd11c537096362eb2f;hp=0000000000000000000000000000000000000000;hpb=b39e05e955bfcbc82abd31571d4cff37021b5942;p=ou-summer-of-code-2017.git diff --git a/04-08-amidakuji/amidakuji-solution-1.ipynb b/04-08-amidakuji/amidakuji-solution-1.ipynb new file mode 100644 index 0000000..d9a9249 --- /dev/null +++ b/04-08-amidakuji/amidakuji-solution-1.ipynb @@ -0,0 +1,416 @@ +{ + "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 +}