Finished amijakuji part 1, added pictures

[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
index d9a924911f735848c5da2f1fbb7de1d2f493feef..7f149b45750ae925dc5a4fef7d955608d627ceb6 100644 (file)
--- a/04-08-amidakuji/amidakuji-solution-1.ipynb
+++ b/04-08-amidakuji/amidakuji-solution-1.ipynb
@@ -2,7 +2,7 @@
  "cells": [
   {
    "cell_type": "code",
-   "execution_count": 1,
+   "execution_count": 27,
    "metadata": {
     "collapsed": true
    },
@@ -16,7 +16,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 2,
+   "execution_count": 28,
    "metadata": {
     "collapsed": true
    },
@@ -27,7 +27,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 3,
+   "execution_count": 29,
    "metadata": {
     "collapsed": true
    },
@@ -39,7 +39,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 4,
+   "execution_count": 30,
    "metadata": {
     "collapsed": true
    },
@@ -51,7 +51,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 5,
+   "execution_count": 31,
    "metadata": {
     "collapsed": true
    },
@@ -67,35 +67,30 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 6,
+   "execution_count": 32,
    "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)]"
+       "[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": 6,
+     "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -107,7 +102,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 7,
+   "execution_count": 33,
    "metadata": {},
    "outputs": [
     {
@@ -116,7 +111,7 @@
        "10135"
       ]
      },
-     "execution_count": 7,
+     "execution_count": 33,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -128,7 +123,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 8,
+   "execution_count": 34,
    "metadata": {
     "collapsed": true
    },
@@ -140,7 +135,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 9,
+   "execution_count": 35,
    "metadata": {
     "collapsed": true
    },
@@ -152,7 +147,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 36,
    "metadata": {
     "collapsed": true
    },
@@ -171,7 +166,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 11,
+   "execution_count": 37,
    "metadata": {
     "collapsed": true
    },
@@ -190,16 +185,16 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 12,
+   "execution_count": 38,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "19"
+       "14"
       ]
      },
-     "execution_count": 12,
+     "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -210,16 +205,16 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 13,
+   "execution_count": 39,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "7"
+       "10"
       ]
      },
-     "execution_count": 13,
+     "execution_count": 39,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -230,7 +225,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 14,
+   "execution_count": 40,
    "metadata": {},
    "outputs": [
     {
@@ -239,7 +234,7 @@
        "10134"
       ]
      },
-     "execution_count": 14,
+     "execution_count": 40,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -250,8 +245,10 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 15,
-   "metadata": {},
+   "execution_count": 41,
+   "metadata": {
+    "collapsed": true
+   },
    "outputs": [],
    "source": [
     "pnet = pack(net)"
@@ -259,7 +256,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 16,
+   "execution_count": 42,
    "metadata": {},
    "outputs": [
     {
@@ -268,7 +265,7 @@
        "2286"
       ]
      },
-     "execution_count": 16,
+     "execution_count": 42,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -279,7 +276,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 17,
+   "execution_count": 43,
    "metadata": {
     "collapsed": true
    },
@@ -291,7 +288,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 18,
+   "execution_count": 44,
    "metadata": {
     "collapsed": true
    },
@@ -308,34 +305,34 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 19,
+   "execution_count": 45,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "'djihegcafb'"
+       "'acfbed'"
       ]
      },
-     "execution_count": 19,
+     "execution_count": 45,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "''.join(follow_many('abcdefghij', small_net))"
+    "''.join(follow_many('abcdef', small_net))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 20,
+   "execution_count": 46,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10000 loops, best of 3: 50.4 µs per loop\n"
+      "10000 loops, best of 3: 39.5 µs per loop\n"
      ]
     }
    ],
@@ -346,7 +343,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 21,
+   "execution_count": 47,
    "metadata": {},
    "outputs": [
     {
@@ -355,7 +352,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 21,
+     "execution_count": 47,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -366,14 +363,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 22,
+   "execution_count": 48,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10 loops, best of 3: 21 ms per loop\n"
+      "10 loops, best of 3: 19.7 ms per loop\n"
      ]
     }
    ],
@@ -382,6 +379,24 @@
     "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,