"Given the input in [02-lifts.txt](02-lifts.txt), where would you get out?"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Worked example of solution: Part 1\n",
+ "\n",
+ "This is an example of a very common pattern: walking along a list, finding some total or final value. As such, there are a great many ways of doing it.\n",
+ "\n",
+ "The most obvious way is to have a variable that holds the current floor, and update it with every instruction that's read from the list of instructions. As the current floor is just a number, we can have a simple variable.\n",
+ "\n",
+ "The list of instructions will be read as a string, and we can iterate through a string easily, so we'll leave the instructions as a string. Happily, each instruction is one character, so no need to count characters and instructions separately.\n",
+ "\n",
+ "The only complication is that there's no obvious trick for converting the instruction characters. Given that, let's just do a simple `if`-`elisf`-`else` structure (or a `case` statement of your language of choice has it) to convert an instruction into a floor change. \n",
+ "\n",
+ "(I could also have used a `dict` like \n",
+ "\n",
+ "```\n",
+ "value = {'^': 1, 'v': -1, '=': 0}\n",
+ "```\n",
+ "\n",
+ "and it would behave in the same way.)\n",
+ "\n",
+ "(Another common solution was to count the number of `^` characters and the number of `v` characters, subtract one from the other, and give the result. That works for part 1 but doesn't work for part 2!)"
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 1,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
" return 0"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Now we can find the floor-change of each instruction, we set the initial floor to 0 and run down the list, updating the current floor at each step."
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": 3,
"metadata": {
"collapsed": true
},
" return current"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Finally, open the file of instructions and find the final floor."
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 3,
+ "execution_count": 4,
"metadata": {},
"outputs": [
{
"209"
]
},
- "execution_count": 3,
+ "execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
"exit"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "(For my testing purposes, find all the floors visited so I can give sensible hints for wrong answers.)"
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 4,
+ "execution_count": 5,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 5,
+ "execution_count": 6,
"metadata": {},
"outputs": [
{
"(10002, 216, -6)"
]
},
- "execution_count": 5,
+ "execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 6,
+ "execution_count": 7,
"metadata": {},
"outputs": [
{
"209"
]
},
- "execution_count": 6,
+ "execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
"The sequence `v^^^^^v=v=` would allow you to exit on floors 3 and 2, so the highest floor you could leave from would be floor 3 (even though the lift reaches floor 4)."
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Worked example of solution: part 2\n",
+ "This is another common pattern: walking down a list, keeping some extreme value (the largest, the smallest, or something like that.)\n",
+ "\n",
+ "The basic idea is to keep a variable holding the highest exit seen so far, and update it if we see a higher exit. We start with some initial value, such as zero. \n",
+ "\n",
+ "The `highest_exit` function is very similar to the `final` function, but with the `if` statement in the loop. This just checks if we're at an exit and it's higher than what we've seen so far; if so, it updates the `highest_exit` variable.\n",
+ "\n",
+ "It was pointed out in the forums that by starting with the `highest_exit` at 0, we're assuming that the highest exit is above ground. That's true in this case, but its a valid concern. In this case, I should set the initial value to be smaller than the smallest valid value we can find, so that the first exit we find is correctly recorded. In this case, the smallest value for the exit is if all the instructions are down, or -1 × (number of instructions)."
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 22,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def highest_exit(sequence):\n",
+ " highest_exit = -1 - len(sequence) # or 0\n",
+ " current = 0\n",
+ " for i in sequence:\n",
+ " if value(i) == 0 and current > highest_exit:\n",
+ " highest_exit = current\n",
+ " else:\n",
+ " current += value(i)\n",
+ " return highest_exit"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "215"
+ ]
+ },
+ "execution_count": 21,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "highest_exit(instructions)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "A variation that returns a list of all the exits, so I can generate hints for obvious wrong answers (the last exit, the lowest exit, the first exit, the number of exits)."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 8,
+ "execution_count": 11,
"metadata": {},
"outputs": [
{
"215"
]
},
- "execution_count": 8,
+ "execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 9,
+ "execution_count": 12,
"metadata": {},
"outputs": [
{
"-5"
]
},
- "execution_count": 9,
+ "execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 13,
"metadata": {},
"outputs": [
{
"209"
]
},
- "execution_count": 10,
+ "execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 14,
"metadata": {},
"outputs": [
{
"-2"
]
},
- "execution_count": 11,
+ "execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 15,
"metadata": {},
"outputs": [
{
"1259"
]
},
- "execution_count": 12,
+ "execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 16,
"metadata": {},
"outputs": [
{
" 215: 2})"
]
},
- "execution_count": 13,
+ "execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 17,
"metadata": {},
"outputs": [
{
"-2"
]
},
- "execution_count": 14,
+ "execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 18,
"metadata": {},
"outputs": [
{
"(209, 215)"
]
},
- "execution_count": 12,
+ "execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 19,
"metadata": {},
"outputs": [
{
"(209, 215)"
]
},
- "execution_count": 13,
+ "execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
projects / ou-summer-of-code-2017.git / blobdiff