{
"cell_type": "code",
"execution_count": 7,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"def whash1(word, show_steps=False):\n",
"\n",
"\"Multiplying\" letters is done by converting the letters to their position in the alphabet (starting at one) and multiplying. For instance, to multiply `u` by 11, convert `u` to `21`, multiply by 11 (`21` × `11` = `231`), then convert back to a letter (`231` is larger than 26, so it becomes `23`, which is `w`).\n",
"\n",
- "Again, anything that isn't a lower-case letter is ignored.\n",
+ "Again, all letters are converted to lower-case and anything that isn't a letter is ignored.\n",
"\n",
"For example, to find the code from the pass phrase `the cat`, the code starts as being the first two letters `ri`. When the first letter is encrypted, the first letter of the code becomes:\n",
"\n",
{
"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",
+ "\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,
" 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",
+ "\n",
+ "\n",
+ "can be packed into this form, with the first three cross-links all placed at the start of the labyrinth. \n",
+ "\n",
+ "\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",
+ ""
+ ]
+ },
{
"cell_type": "code",
"execution_count": 21,
projects / ou-summer-of-code-2017.git / commitdiff