X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=04-amidakuji%2Famidakuji-solution-1.ipynb;fp=04-amidakuji%2Famidakuji-solution-1.ipynb;h=15a816add45d15161e4fa63f28547c67de0db43c;hb=7feed95175973490721236795cc7895e252965e2;hp=df69a1f3a30c50ffc3f736ce54ce8bd1a2c6d01c;hpb=256cad02e44f18b53ee0ca8c5a2737b3c1cd71bc;p=ou-summer-of-code-2017.git

diff --git a/04-amidakuji/amidakuji-solution-1.ipynb b/04-amidakuji/amidakuji-solution-1.ipynb
index df69a1f..15a816a 100644
--- a/04-amidakuji/amidakuji-solution-1.ipynb
+++ b/04-amidakuji/amidakuji-solution-1.ipynb
@@ -1,5 +1,50 @@
 {
  "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "Time to hit the beach!\n",
+    "\n",
+    "To stop people going straight to the best sunbeds, the hotel has arranged a labyrinthine way of getting to the beach. Instead of heading straight to your chosen sunbed, you pick a lane and follow it through the maze. When you get to a cross-path, you walk along it to the other lane, then carry on down to the beach.\n",
+    "\n",
+    "This example network has six lines, numbered zero to five, and fifteen links. You start at the top and move down.\n",
+    "\n",
+    "![Example labyrinth](small-expanded-trace.svg.png)\n",
+    "\n",
+    "The dashed coloured lines show you some paths you would take going through this labyrinth to the beach. For instance, if you started in lane 1 (the red line), you would switch to lane 4 then lane 3, and you'd emerge on sunbed 3. Entering on lane 5 (the green line) would immediately switch to lane 2, then lane 0, then then lane 4, then finally back to lane 2 where they emerge. Entering on lane zero would take you all round the houses, including crossing the previous tracks, to finally end up back on lane 0.\n",
+    "\n",
+    "If you and five friends labelled yourselves `a`, `b`, `c`, `d`, `e`, `f`, your labels when you came out would be in order acfbed.\n",
+    "\n",
+    "You'd rather like to know where you and your friends are ending up on the beach, so you've got a copy of the layout plan of the labyrinth. It's given as a sequence of pairs, showing the lane to and from for each cross-path. For instance, the labyrinth above would be described as:\n",
+    "\n",
+    "```\n",
+    "(2, 5)\n",
+    "(1, 4)\n",
+    "(0, 3)\n",
+    "(0, 3)\n",
+    "(0, 5)\n",
+    "(3, 5)\n",
+    "(0, 2)\n",
+    "(3, 4)\n",
+    "(2, 4)\n",
+    "(1, 2)\n",
+    "(0, 4)\n",
+    "(1, 2)\n",
+    "(2, 4)\n",
+    "(0, 4)\n",
+    "(1, 4)\n",
+    "```\n",
+    "\n",
+    "For each pair `(a, b)`, you can assume $0 \\le a < b < n$, if there are _n_ lanes. (In other words, all lane numbers are valid, the first lane number is always less than the second, and cross-paths don't go from a lane back to the same lane.)\n",
+    "\n",
+    "# Part 1\n",
+    "\n",
+    "The full labyrinth description is given in (04-lines.txt). The labyrinth has 26 lines, labelled 0 to 25 inclusive. If you and 25 friends, labelled `a` to `z` in order, entered the labyrinth, in what order would you come out?\n",
+    "\n",
+    "(Your answer should be one string of 26 letters, without spaces or punctuation, like `acfbed` .)"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 44,
@@ -209,6 +254,45 @@
     "    return line"
    ]
   },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "You've noticed that the beach labyrinth is longer than it needs to be. Rather than putting each cross-link on a separate step away from the hotel, it's possible to put several cross-links at the same distance, so long as none of them shares an end. \n",
+    "\n",
+    "For instance, the sample labyrinth\n",
+    "\n",
+    "![Example labyrinth](small-expanded.svg.png)\n",
+    "\n",
+    "can be packed into this form, with the first three cross-links all placed at the start of the labyrinth. \n",
+    "\n",
+    "![Packed labyrinth](small-packed.svg.png)\n",
+    "\n",
+    "You can pack a labyrinth by sliding a link up until just before either of its ends would touch an earlier link. The first 2-5 link stays where it is. The next two links (1-4 and 0-3) slide up to also be on the same level. The next 0-3 link then slides up until it's one step from the start. The other links slide up in turn.\n",
+    "\n",
+    "This packed labyrinth has the same shuffling behaviour of the original. But where the last cross-link in the original labyrinth is fourteen steps beyond the start, the last cross-link in the packed labyrinth is only ten steps on.\n",
+    "\n",
+    "Only slide links; don't be tempted to remove any. The packed labyrinth should have the same number of cross-links as the original.\n",
+    "\n",
+    "# Part 2\n",
+    "\n",
+    "The labyrinth is still given in 04-lines.txt. \n",
+    "\n",
+    "After all the packing and sliding, how far is the last cross-link from the first?"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "## Note to self\n",
+    "Several solutions tried a simplistic approach of packing a layer until a link could not go on that layer, then starting the next. But, this didn't allow for links that could slide more than one layer.\n",
+    "\n",
+    "The simple algorithm moved from left net to centre net, but missed you could still pack to form right net.\n",
+    "\n",
+    "![Packing variants](packing-variants.svg.png)"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 21,