"**What is your door code?**"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Worked example of solution: Part 1\n",
+ "\n",
+ "While the overall shape of this is the same as previous days (walk along a list, updating the code as you reach each letter), there are a couple of wrinkles:\n",
+ "\n",
+ "1. Not every character in the input should be processed (and the others should be converted to lower-case letters).\n",
+ "2. The 'update the code' part is complex.\n",
+ "\n",
+ "\"Sanitising\" the input is, again, walking over the input, convering letters and discarding the rest. These are examples of standard approaches: `filter` is applying a predicate to every item in a sequence, returning just hose that pass; `map` is applying a function to every item in a sequence, returning the sequence of results. In this case, sanitising the input is `filter`ing to keep just the letters then `map`ping over the \"convert to lowercase\" function. Python's comprehensions do this: the general form is `f(x) for x in sequence if predicate(x)`\n",
+ "\n",
+ "Updating the code involves lots of faffing around, converting between characters and numbers. Rather than retyping lots of arithmetic, I define a couple of functions to do the conversions how I want. I've deliberately given them short names, as I want the functions to almost disappear in the program, becoming little more than punctuation. That will keep the focus on the important part, the updating.\n",
+ "\n",
+ "The `ord(letter) - ord('a')` and `chr(number + ord('a')` are standard idioms for converting from letters to positions in the alphabet. There's also moving the result by 1 to give one-based numbering, and the modulus operation `%` to keep the numbers in the range 0-25 before converting back to letters.\n",
+ "\n",
+ "Finally, the `string` library defines some convenient constants, which helps prevent annoying and hard-to-find typos if I wrote out the alphabet verbatim here."
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 3,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 4,
+ "execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
- "def o(letter):\n",
- " return ord(letter) - ord('a') + 1\n",
- "\n",
- "def c(number):\n",
- " return chr((number - 1) % 26 + ord('a'))"
+ "def sanitise(phrase):\n",
+ " return ''.join(l.lower() for l in phrase if l in string.ascii_letters)"
]
},
{
"cell_type": "code",
- "execution_count": 5,
+ "execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
- "('a', 'z', 'z', 'a')"
+ "'helloworld'"
]
},
- "execution_count": 5,
+ "execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "c(1), c(0), c(26), c(27)"
+ "sanitise('Hello World')"
]
},
{
"cell_type": "code",
- "execution_count": 6,
+ "execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
- "def sanitise(phrase):\n",
- " return ''.join(l.lower() for l in phrase if l in string.ascii_letters)"
+ "def o(letter):\n",
+ " return ord(letter) - ord('a') + 1\n",
+ "\n",
+ "def c(number):\n",
+ " return chr((number - 1) % 26 + ord('a'))"
]
},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
- "'helloworld'"
+ "('a', 'z', 'z', 'a')"
]
},
- "execution_count": 7,
+ "execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "sanitise('Hello World')"
+ "c(1), c(0), c(26), c(27)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def whash1(word):\n",
+ " h = list(word[:2])\n",
+ " for l in word[2:]:\n",
+ " h[0] = c(o(h[0]) + o(h[1]))\n",
+ " h[1] = c(o(h[1]) + o(l))\n",
+ " return ''.join(h)"
]
},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 20,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
+ "# Extended version that generates the tables used in the question text.\n",
"def whash1(word, show_steps=False):\n",
" if show_steps:\n",
" print('| old code | code as<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |'\n",
},
{
"cell_type": "code",
- "execution_count": 8,
+ "execution_count": 9,
"metadata": {},
"outputs": [
{
"'vk'"
]
},
- "execution_count": 8,
+ "execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 9,
+ "execution_count": 10,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 24,
"metadata": {},
"outputs": [
{
"'mc'"
]
},
- "execution_count": 10,
+ "execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
"Using this new algorithm, **what is your door code?**"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Worked example of solution: Part 2\n",
+ "\n",
+ "This is almost identical to part 1, but the arithmetic is slightly different. Note the use of keyword arguments with default values, to allow the code to use different starting values."
+ ]
+ },
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 12,
"metadata": {},
"outputs": [
{
"(21, 231, 23, 'w')"
]
},
- "execution_count": 11,
+ "execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 13,
"metadata": {},
"outputs": [
{
"(18, 9, 45, 63, 'k')"
]
},
- "execution_count": 12,
+ "execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 14,
"metadata": {},
"outputs": [
{
"(9, 20, 220, 229, 'u')"
]
},
- "execution_count": 13,
+ "execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 21,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
+ "def whash2(word, h0=None, alpha=5, beta=11):\n",
+ " if h0 is None:\n",
+ " h = list('ri')\n",
+ " else:\n",
+ " h = list(h0)\n",
+ " for l in word:\n",
+ " h[0] = c(o(h[0]) + o(h[1]) * alpha)\n",
+ " h[1] = c(o(h[1]) + o(l) * beta)\n",
+ " return ''.join(h)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# Extended version that generates the tables used in the question text.\n",
"def whash2(word, h0=None, alpha=5, beta=11, show_steps=False):\n",
" if show_steps:\n",
" print('| old code | code as<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |'\n",
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 16,
"metadata": {},
"outputs": [
{
"'vl'"
]
},
- "execution_count": 15,
+ "execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 22,
"metadata": {},
"outputs": [
{
"'qb'"
]
},
- "execution_count": 16,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
projects / ou-summer-of-code-2017.git / blobdiff