{ "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](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": "markdown", "metadata": {}, "source": [ "# Worked solution\n", "\n", "> Note: the code in this notebook doesn't really follow the structure of the problem. That's because I was working on this task for a while, looking at different approaches and different challenges to pose based on the idea. I'll pick out the important parts from the code that's below.\n", "\n", "> Also note that terminology changes throughout the code here. The question talks about lanes and distances, but the code refers to lines and heights.\n", "\n", "\n", "## Data structure\n", "This task requires a bit of though behind the data structures before you can start tackling the problem. The first thing to do is think about the data structure to use to represent the network, and the operations we need to perform on it.\n", "\n", "The operations are:\n", "1. Create the network from a collection of links.\n", "2. Follow a person through the labyrinth.\n", "3. Follow lots of people together through the layrinth (if that's different and easier).\n", "4. (Looking ahead) Shuffle the heights of links for packing.\n", "\n", "We could consider the labyrinth as a collection of links that affect lanes, or as a collection of lanes that know about links. Given that we're presented with a set of links, and need to move the links around, let's go with representing the network as a bunch of links. \n", "\n", "How to represent each link? As we're doing things with links later, it's easier if I just store the labyrinth as a bunch of links, and have each link know everything about itself that I would want. Given that we could, later, have more than one link at each height, each link will need to know its own left end, right end, and height. \n", "\n", "Python doesn't have anything like records from other languages. I could use a `dict` to store each link, but in this case I'll use a `namedtuple` from the `collections` library. It will allow me to say things like `this_link.height` and `this_link.left`, which is easier to read (and write!) than `this_link['height']` and `this_link['left']`.\n", "\n", "## Reading the input\n", "Each line of the file consists of two sequences of digits with sequences of non-digits surrounding them. I use a regular expression and the `re.split()` function to split the line, treating non-digits (the `\\D+` term) as the separators. The `read_net` procedure reads the file, splits each line into the substrings, converts the relevant parts into numbers, then builds the links. Note the use of the `enumerate` built-in function, which iterates through a sequence, returning both the item and the count each time. That gives me the heights of the links. \n", "\n", "## Following people through\n", "`follow()` follows one person through the labyrinth. The `line` variable holds the line/lane this person is currently on as they move through the laybrinth.\n", "\n", "The procedure is structured to allow for there being several links at the same height. It finds the distinct heights, puts them in order, then iterates through the heights. It then finds all the links at that height and, if one of them has an end on `line`, it uses that link to do the swap. \n", "\n", "This is fine for one person, but it's slow to execute the whole process 26 times for 26 people, when most of the work is the same for each person going through. But I've implemented that process to work on packed networks (the part 2 problem), so let's look at that first.\n", "\n", "## Packing\n", "The idea of packing is to keep track of the position of the furthest link that's on each lane. When we add a link to the packed network, we look up the lanes it joins, find the furthest link on either of them, then add the new link at one level beyond that. We then update the positions recorded for the two lanes. \n", "\n", "The current lane distances are held in the `line_heights` dictionary. It's a `defaultdict`, defined to return the value of `-1` for any line that hasn't been processed yet. The height for a new link is the maximum existing height for either of its ends, +1. This means that the first link is placed at height zero.\n", "\n", "## Following again\n", "Once we have the idea of a packed network, I clarified the idea of a `height_group`, the set of links that are all at a particular height. The `height_groups()` function uses some library magic to split a network into a list of lists of links, with each inner list being all the links at that height, i.e. it returns a list like this:\n", "\n", "```\n", "[, , … ]\n", "```\n", "\n", "Once you have the height groups, you can use them to follow many items through the network at the same time. `follow_many()` takes a sequence of things in their starting order, and follows them all through the network. There must be at least as many items in the input as there are lanes in the network, and I don't check for that being true. The input sequence is converted to a `list`, as that can be updated in place, while Python won't allow changes inside `string`s.\n", "\n", "As the packing and height-group-finding ensures that there is at most one link on each lane in any particular height group, I don't need to go through the height group in any particular order. I just take each link swap the items at the ends, and update the `seq` accordingly. (Note the simultaneous assignment for swapping without a temporary variable.)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import collections\n", "import string\n", "import itertools\n", "import re" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "Link = collections.namedtuple('Link', 'height left right')" ] }, { "cell_type": "code", "execution_count": 3, "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": 4, "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": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['', '2', '4', '']" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "re.split('\\D+', '(2, 4)')" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def read_net(filename, rev=False):\n", " with open(filename) as f:\n", " pairs = [re.split('\\D+', p.strip()) for p in f]\n", " if rev:\n", " lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n", " else:\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": 21, "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": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_net = read_net('04-small.txt')\n", "small_net" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10135" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "net = read_net('04-lines.txt')\n", "len(net)" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "23" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "permnet = read_net('permutations.txt')\n", "len(permnet)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "23" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rpermnet = read_net('permutations.txt', rev=True)\n", "len(rpermnet)" ] }, { "cell_type": "code", "execution_count": 18, "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": 19, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def link_ends(link):\n", " return set((link.left, link.right))" ] }, { "cell_type": "code", "execution_count": 20, "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": "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, "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": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "14" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(l.height for l in small_net)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(l.height for l in pack(small_net))" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10134" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(l.height for l in net)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": true }, "outputs": [], "source": [ "pnet = pack(net)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2286" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(l.height for l in pnet)" ] }, { "cell_type": "code", "execution_count": 27, "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": 28, "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": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'acfbed'" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(follow_many('abcdef', small_net))" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0 ['0', '1', '2', '3', '4', '5']\n", " 1 (2, 5) ['0', '1', '5', '3', '4', '2']\n", " 2 (1, 4) ['0', '4', '5', '3', '1', '2']\n", " 3 (0, 3) ['3', '4', '5', '0', '1', '2']\n", " 4 (0, 3) ['0', '4', '5', '3', '1', '2']\n", " 5 (0, 5) ['2', '4', '5', '3', '1', '0']\n", " 6 (3, 5) ['2', '4', '5', '0', '1', '3']\n", " 7 (0, 2) ['5', '4', '2', '0', '1', '3']\n", " 8 (3, 4) ['5', '4', '2', '1', '0', '3']\n", " 9 (2, 4) ['5', '4', '0', '1', '2', '3']\n", "10 (1, 2) ['5', '0', '4', '1', '2', '3']\n", "11 (0, 4) ['2', '0', '4', '1', '5', '3']\n", "12 (1, 2) ['2', '4', '0', '1', '5', '3']\n", "13 (2, 4) ['2', '4', '5', '1', '0', '3']\n", "14 (0, 4) ['0', '4', '5', '1', '2', '3']\n", "15 (1, 4) ['0', '2', '5', '1', '4', '3']\n" ] } ], "source": [ "for i in range(len(small_net)+1):\n", " pre_net = small_net[:i]\n", " if i == 0:\n", " print('{:2}'.format(i), \n", " \" \".format(small_net[i-1].left, small_net[i-1].right),\n", " follow_many(\"012345\", pre_net))\n", " else:\n", " print('{:2}'.format(i), \n", " \"({}, {})\".format(small_net[i-1].left, small_net[i-1].right),\n", " follow_many(\"012345\", pre_net))\n", "\n", " " ] }, { "cell_type": "code", "execution_count": 66, "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": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_net[:15]" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10000 loops, best of 3: 42 µs per loop\n" ] } ], "source": [ "%%timeit\n", "follow_many('abcdefghij', small_net)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'doqzmbishkwunvltpcexyjgfra'" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(follow_many(string.ascii_lowercase, net))" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'zfrasxwigvjoembqcyhplnktud'" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(follow_many(string.ascii_lowercase, permnet))" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'doqzmbishkwunvltpcexyjgfra'" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(follow_many(string.ascii_lowercase, rpermnet))" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, rpermnet)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 19.3 ms per loop\n" ] } ], "source": [ "%%timeit\n", "follow_many(string.ascii_lowercase, net)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100 loops, best of 3: 18.7 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 }