X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=04-amidakuji%2Famidakuji-solution-2.ipynb;h=6d22d214d229480292e80c86eb52ecc035ff7cfb;hb=256cad02e44f18b53ee0ca8c5a2737b3c1cd71bc;hp=3745c3c446f167d29efe0963ae898dfde0ecb501;hpb=55f602f3ca4d1297233e471706caaad9c7a99b5e;p=ou-summer-of-code-2017.git

diff --git a/04-amidakuji/amidakuji-solution-2.ipynb b/04-amidakuji/amidakuji-solution-2.ipynb
index 3745c3c..6d22d21 100644
--- a/04-amidakuji/amidakuji-solution-2.ipynb
+++ b/04-amidakuji/amidakuji-solution-2.ipynb
@@ -67,7 +67,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 28,
+   "execution_count": 6,
    "metadata": {
     "collapsed": true
    },
@@ -86,7 +86,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 6,
+   "execution_count": 7,
    "metadata": {},
    "outputs": [
     {
@@ -109,7 +109,7 @@
        " Link(height=14, left=1, right=4)]"
       ]
      },
-     "execution_count": 6,
+     "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -121,7 +121,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 7,
+   "execution_count": 8,
    "metadata": {},
    "outputs": [
     {
@@ -130,7 +130,7 @@
        "10135"
       ]
      },
-     "execution_count": 7,
+     "execution_count": 8,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -142,7 +142,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 26,
+   "execution_count": 9,
    "metadata": {},
    "outputs": [
     {
@@ -151,7 +151,7 @@
        "23"
       ]
      },
-     "execution_count": 26,
+     "execution_count": 9,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -163,7 +163,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 29,
+   "execution_count": 10,
    "metadata": {},
    "outputs": [
     {
@@ -172,7 +172,7 @@
        "23"
       ]
      },
-     "execution_count": 29,
+     "execution_count": 10,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -184,7 +184,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 9,
+   "execution_count": 11,
    "metadata": {
     "collapsed": true
    },
@@ -196,7 +196,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 12,
    "metadata": {
     "collapsed": true
    },
@@ -208,7 +208,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 11,
+   "execution_count": 13,
    "metadata": {
     "collapsed": true
    },
@@ -227,7 +227,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 12,
+   "execution_count": 14,
    "metadata": {
     "collapsed": true
    },
@@ -246,7 +246,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 13,
+   "execution_count": 15,
    "metadata": {},
    "outputs": [
     {
@@ -255,7 +255,7 @@
        "14"
       ]
      },
-     "execution_count": 13,
+     "execution_count": 15,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -266,7 +266,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 14,
+   "execution_count": 16,
    "metadata": {},
    "outputs": [
     {
@@ -275,7 +275,7 @@
        "10"
       ]
      },
-     "execution_count": 14,
+     "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -286,7 +286,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 15,
+   "execution_count": 17,
    "metadata": {},
    "outputs": [
     {
@@ -295,7 +295,7 @@
        "10134"
       ]
      },
-     "execution_count": 15,
+     "execution_count": 17,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -306,7 +306,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 16,
+   "execution_count": 18,
    "metadata": {},
    "outputs": [
     {
@@ -315,7 +315,7 @@
        "2286"
       ]
      },
-     "execution_count": 16,
+     "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -326,7 +326,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 17,
+   "execution_count": 19,
    "metadata": {
     "collapsed": true
    },
@@ -338,7 +338,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 18,
+   "execution_count": 20,
    "metadata": {
     "collapsed": true
    },
@@ -355,7 +355,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 19,
+   "execution_count": 21,
    "metadata": {},
    "outputs": [
     {
@@ -364,7 +364,7 @@
        "'acfbedghij'"
       ]
      },
-     "execution_count": 19,
+     "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -375,14 +375,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 20,
+   "execution_count": 22,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10000 loops, best of 3: 40.1 µs per loop\n"
+      "10000 loops, best of 3: 41.3 µs per loop\n"
      ]
     }
    ],
@@ -393,7 +393,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 23,
    "metadata": {},
    "outputs": [
     {
@@ -402,7 +402,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 24,
+     "execution_count": 23,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -413,7 +413,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 27,
+   "execution_count": 24,
    "metadata": {},
    "outputs": [
     {
@@ -422,7 +422,7 @@
        "'zfrasxwigvjoembqcyhplnktud'"
       ]
      },
-     "execution_count": 27,
+     "execution_count": 24,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -433,7 +433,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 30,
+   "execution_count": 25,
    "metadata": {},
    "outputs": [
     {
@@ -442,7 +442,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 30,
+     "execution_count": 25,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -453,14 +453,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 21,
+   "execution_count": 26,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "100 loops, best of 3: 19 ms per loop\n"
+      "10 loops, best of 3: 20.8 ms per loop\n"
      ]
     }
    ],
@@ -471,7 +471,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 22,
+   "execution_count": 27,
    "metadata": {
     "collapsed": true
    },
@@ -482,7 +482,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 23,
+   "execution_count": 28,
    "metadata": {
     "collapsed": true
    },
@@ -501,7 +501,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 29,
    "metadata": {
     "scrolled": true
    },
@@ -566,7 +566,7 @@
        " (Link(height=2277, left=4, right=18), Link(height=2276, left=4, right=18))]"
       ]
      },
-     "execution_count": 24,
+     "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -577,14 +577,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
+   "execution_count": 30,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10 loops, best of 3: 23.5 ms per loop\n"
+      "10 loops, best of 3: 24.7 ms per loop\n"
      ]
     }
    ],
@@ -595,7 +595,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 26,
+   "execution_count": 31,
    "metadata": {
     "collapsed": true
    },
@@ -612,7 +612,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 27,
+   "execution_count": 32,
    "metadata": {
     "collapsed": true
    },
@@ -630,7 +630,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 28,
+   "execution_count": 33,
    "metadata": {
     "collapsed": true
    },
@@ -641,7 +641,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 29,
+   "execution_count": 34,
    "metadata": {
     "collapsed": true
    },
@@ -653,14 +653,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 30,
+   "execution_count": 35,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 2.35 s per loop\n"
+      "1 loop, best of 3: 2.41 s per loop\n"
      ]
     }
    ],
@@ -671,7 +671,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 31,
+   "execution_count": 36,
    "metadata": {
     "collapsed": true
    },
@@ -714,7 +714,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 32,
+   "execution_count": 37,
    "metadata": {
     "collapsed": true
    },
@@ -736,7 +736,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 33,
+   "execution_count": 38,
    "metadata": {},
    "outputs": [
     {
@@ -944,7 +944,7 @@
        "  Link(height=2214, left=6, right=14))]"
       ]
      },
-     "execution_count": 33,
+     "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -956,7 +956,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 34,
+   "execution_count": 39,
    "metadata": {
     "collapsed": true
    },
@@ -967,7 +967,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 35,
+   "execution_count": 40,
    "metadata": {
     "collapsed": true
    },
@@ -978,7 +978,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 36,
+   "execution_count": 41,
    "metadata": {
     "collapsed": true
    },
@@ -996,7 +996,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 37,
+   "execution_count": 42,
    "metadata": {
     "scrolled": true
    },
@@ -1063,7 +1063,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 38,
+   "execution_count": 43,
    "metadata": {},
    "outputs": [
     {
@@ -1072,7 +1072,7 @@
        "9937"
       ]
      },
-     "execution_count": 38,
+     "execution_count": 43,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1083,7 +1083,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 39,
+   "execution_count": 44,
    "metadata": {
     "collapsed": true
    },
@@ -1094,7 +1094,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 40,
+   "execution_count": 45,
    "metadata": {},
    "outputs": [
     {
@@ -1103,7 +1103,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 40,
+     "execution_count": 45,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1114,7 +1114,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 41,
+   "execution_count": 46,
    "metadata": {},
    "outputs": [
     {
@@ -1123,7 +1123,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 41,
+     "execution_count": 46,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1134,7 +1134,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 42,
+   "execution_count": 47,
    "metadata": {},
    "outputs": [
     {
@@ -1143,7 +1143,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 42,
+     "execution_count": 47,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1154,7 +1154,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 43,
+   "execution_count": 48,
    "metadata": {},
    "outputs": [
     {
@@ -1163,7 +1163,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 43,
+     "execution_count": 48,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1174,7 +1174,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 44,
+   "execution_count": 49,
    "metadata": {},
    "outputs": [
     {
@@ -1183,7 +1183,7 @@
        "[]"
       ]
      },
-     "execution_count": 44,
+     "execution_count": 49,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1194,7 +1194,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 45,
+   "execution_count": 50,
    "metadata": {},
    "outputs": [
     {
@@ -1203,7 +1203,7 @@
        "(10135, 10031)"
       ]
      },
-     "execution_count": 45,
+     "execution_count": 50,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1214,7 +1214,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 46,
+   "execution_count": 51,
    "metadata": {
     "collapsed": true
    },
@@ -1232,7 +1232,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 47,
+   "execution_count": 52,
    "metadata": {
     "collapsed": true
    },
@@ -1243,7 +1243,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 48,
+   "execution_count": 53,
    "metadata": {},
    "outputs": [
     {
@@ -1252,7 +1252,7 @@
        "True"
       ]
      },
-     "execution_count": 48,
+     "execution_count": 53,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1263,7 +1263,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 49,
+   "execution_count": 54,
    "metadata": {},
    "outputs": [
     {
@@ -1272,7 +1272,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 49,
+     "execution_count": 54,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1283,7 +1283,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 50,
+   "execution_count": 55,
    "metadata": {},
    "outputs": [
     {
@@ -1292,7 +1292,7 @@
        "'doqzmbishkwunvltpcexyjgfra'"
       ]
      },
-     "execution_count": 50,
+     "execution_count": 55,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1303,7 +1303,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 51,
+   "execution_count": 56,
    "metadata": {},
    "outputs": [
     {
@@ -1312,7 +1312,7 @@
        "9931"
       ]
      },
-     "execution_count": 51,
+     "execution_count": 56,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1323,7 +1323,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 52,
+   "execution_count": 57,
    "metadata": {
     "collapsed": true
    },
@@ -1364,7 +1364,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 53,
+   "execution_count": 58,
    "metadata": {
     "scrolled": true
    },
@@ -1481,7 +1481,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 54,
+   "execution_count": 59,
    "metadata": {},
    "outputs": [
     {
@@ -1490,7 +1490,7 @@
        "True"
       ]
      },
-     "execution_count": 54,
+     "execution_count": 59,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1501,7 +1501,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 55,
+   "execution_count": 60,
    "metadata": {},
    "outputs": [
     {
@@ -1510,7 +1510,7 @@
        "9931"
       ]
      },
-     "execution_count": 55,
+     "execution_count": 60,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -1519,6 +1519,66 @@
     "len(spnet)"
    ]
   },
+  {
+   "cell_type": "code",
+   "execution_count": 61,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "2205"
+      ]
+     },
+     "execution_count": 61,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "max(height_groups(spnet).keys())"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 62,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "9931"
+      ]
+     },
+     "execution_count": 62,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(simple_net)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 63,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "2205"
+      ]
+     },
+     "execution_count": 63,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "max(height_groups(simple_net).keys())"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": null,