"(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",
+ "[<list of links at height 0>, <list of links at height 1>, … <list of links at height 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": 44,
+ "execution_count": 1,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 45,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 46,
+ "execution_count": 3,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 4,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 48,
+ "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
},
"source": [
"def read_net(filename, rev=False):\n",
" with open(filename) as f:\n",
- " pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\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",
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 21,
"metadata": {},
"outputs": [
{
" Link(height=14, left=1, right=4)]"
]
},
- "execution_count": 15,
+ "execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 22,
"metadata": {},
"outputs": [
{
"10135"
]
},
- "execution_count": 16,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
projects / ou-summer-of-code-2017.git / blobdiff