projects / ou-summer-of-code-2017.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Various changes to day 4
[ou-summer-of-code-2017.git] / 04-08-amidakuji / amidakuji-solution-1.ipynb
diff --git a/04-08-amidakuji/amidakuji-solution-1.ipynb b/04-08-amidakuji/amidakuji-solution-1.ipynb
deleted file mode 100644 (file)
index 7f149b4..0000000
--- a/04-08-amidakuji/amidakuji-solution-1.ipynb
+++ /dev/null
@@ -1,431 +0,0 @@
-{
- "cells": [
-  {
-   "cell_type": "code",
-   "execution_count": 27,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "import collections\n",
-    "import string\n",
-    "import itertools\n",
-    "import re"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 28,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "Link = collections.namedtuple('Link', 'height left right')"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 29,
-   "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": 30,
-   "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": 31,
-   "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": 32,
-   "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": 32,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "small_net = read_net('04-small.txt')\n",
-    "small_net"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 33,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "10135"
-      ]
-     },
-     "execution_count": 33,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "net = read_net('04-lines.txt')\n",
-    "len(net)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 34,
-   "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": 35,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "def link_ends(link):\n",
-    "    return set((link.left, link.right))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 36,
-   "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": 37,
-   "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": 38,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "14"
-      ]
-     },
-     "execution_count": 38,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "max(l.height for l in small_net)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 39,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "10"
-      ]
-     },
-     "execution_count": 39,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "max(l.height for l in pack(small_net))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 40,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "10134"
-      ]
-     },
-     "execution_count": 40,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "max(l.height for l in net)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 41,
-   "metadata": {
-    "collapsed": true
-   },
-   "outputs": [],
-   "source": [
-    "pnet = pack(net)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 42,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "2286"
-      ]
-     },
-     "execution_count": 42,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "max(l.height for l in pnet)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 43,
-   "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": 44,
-   "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": 45,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "'acfbed'"
-      ]
-     },
-     "execution_count": 45,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "''.join(follow_many('abcdef', small_net))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 46,
-   "metadata": {},
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "10000 loops, best of 3: 39.5 µs per loop\n"
-     ]
-    }
-   ],
-   "source": [
-    "%%timeit\n",
-    "follow_many('abcdefghij', small_net)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 47,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "'doqzmbishkwunvltpcexyjgfra'"
-      ]
-     },
-     "execution_count": 47,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "''.join(follow_many(string.ascii_lowercase, net))"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 48,
-   "metadata": {},
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "10 loops, best of 3: 19.7 ms per loop\n"
-     ]
-    }
-   ],
-   "source": [
-    "%%timeit\n",
-    "follow_many(string.ascii_lowercase, net)"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 49,
-   "metadata": {},
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "100 loops, best of 3: 18.6 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
-}
OU Summer of Code challenge, 2017