{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Door codes\n",
"\n",
"After a fairly dull flight, you've finally arrived at your hotel. The good news is that the hotel has high-security electronic locks on the room doors. The bad news is that the staff are rather busy, and you think it will take a long time to get to your room.\n",
"\n",
"Luckily, you know how their system works. \n",
"\n",
"Each door in the hotel has a keyboard on the lock. You have to enter the correct two-letter code to get in to the room. Because the staff know that people won't remember the codes, they tell you a pass phrase you can use the generate the code from.\n",
"\n",
"There's a long queue for people to be told how to generate the code from the pass phrase. You were here last year and you still remember how to do it.\n",
"\n",
"You start with the first two letters of the pass phrase. This is the starting value of your code.\n",
"\n",
"Then, for each subsequent letter in the pass phrase, you:\n",
"1. \"Add\" the second letter of the code to the first letter of the code, replacing the first letter of the code\n",
"2. \"Add\" the current letter of the pass phrase to the second letter of the code, replacing the second letter of the code\n",
"3. Move on to the next letter of the pass phrase\n",
"\n",
"\"Adding\" letters is done by converting the letters to their position in the alphabet (starting at one), adding, then converting the number back to a letter. Numbers greater than 26 are \"wrapped around\". For instance, to add `t` + `h`, convert them to numbers (`t`=`20`, `h`=`8`), add them (`20` + `8` = `28`), then convert back to a letter (`28` is larger than 26, so it becomes `28` - `26` = `2`, which is `b`).\n",
"\n",
"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 `th`, then the subsequent letters are used to update the code as follows:\n",
"\n",
"| old code | code as
numbers | passphrase
letter | number of
letter | new first
part of code |new second
part of code | new code |\n",
"|:---|:---|:---|:---|:---|:---|:---|\n",
"| `th` | (20, 8) | `e` | 5 | 28 | 13 | `bm` |\n",
"| `bm` | (2, 13) | `c` | 3 | 15 | 16 | `op` |\n",
"| `op` | (15, 16) | `a` | 1 | 31 | 17 | `eq` |\n",
"| `eq` | (5, 17) | `t` | 20 | 22 | 37 | `vk` |\n",
"\n",
"So the final code is `vk`\n",
"\n",
"## Part 1\n",
"Your passphrase is \n",
"\"the traveller in the grey riding-coat, who called himself mr. melville, was contemplating the malice of which the gods are capable.\"\n",
"\n",
"**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": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import string"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def sanitise(phrase):\n",
" return ''.join(l.lower() for l in phrase if l in string.ascii_letters)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'helloworld'"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sanitise('Hello World')"
]
},
{
"cell_type": "code",
"execution_count": 3,
"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'))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('a', 'z', 'z', 'a')"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"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": 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
numbers | passphrase
letter | number of
letter | new first
part of code |'\n",
" 'new second
part of code | new code |')\n",
" print('|:---|:---|:---|:---|:---|:---|:---|')\n",
" h = list(word[:2])\n",
" for l in word[2:]:\n",
" if show_steps:\n",
" h_before = h.copy()\n",
" h[0] = c(o(h[0]) + o(h[1]))\n",
" h[1] = c(o(h[1]) + o(l))\n",
" if show_steps:\n",
" print('| `{}` | {} | `{}` | {} | {} | {} | `{}` |'.format(\n",
" ''.join(h_before), \n",
" (o(h_before[0]), o(h_before[1])),\n",
" l, \n",
" o(l), \n",
" o(h_before[0]) + o(h_before[1]), \n",
" o(h_before[1]) + o(l), \n",
" ''.join(h)))\n",
" return ''.join(h)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"| old code | code as
numbers | passphrase
letter | number of
letter | new first
part of code |new second
part of code | new code |\n",
"|:---|:---|:---|:---|:---|:---|:---|\n",
"| `th` | (20, 8) | `e` | 5 | 28 | 13 | `bm` |\n",
"| `bm` | (2, 13) | `c` | 3 | 15 | 16 | `op` |\n",
"| `op` | (15, 16) | `a` | 1 | 31 | 17 | `eq` |\n",
"| `eq` | (5, 17) | `t` | 20 | 22 | 37 | `vk` |\n"
]
},
{
"data": {
"text/plain": [
"'vk'"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"whash1(sanitise('the cat'), show_steps=True)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"passphrase = sanitise(\"the traveller in the grey riding-coat, who called himself mr. melville, was \"\n",
" \"contemplating the malice of which the gods are capable.\")"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'mc'"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"whash1(passphrase)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You arrive at your door but the passcode doesn't work!\n",
"\n",
"Looking at the lock, you see it's a different model from last time you were here. Reluctantly, you return to the hotel front desk and join the queue for instructions. \n",
"\n",
"Indeed, the algorithm has been changed, \"to improve security,\" they say.\n",
"\n",
"The new algorithm starts with the same initial value of the code for every passphrase. In in this case, the initial code is `ri`. The algorithm also uses two contants, `alpha`= 5 and `beta` = 11.\n",
"\n",
"Then, for each letter in the pass phrase, the code is updated as follows:\n",
"\n",
"1. \"Multiply\" the second letter of the code by `alpha` then add the first letter of the code, replacing the first code letter\n",
"2. \"Multiply\" the current letter of the pass phrase by `beta` and add the second letter of the code, replacing the second letter of the code\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, 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",
"`r` + `i` × `alpha` = `18` + `9` × `5` = `63` = `k`\n",
"\n",
"and the second letter of the code becomes:\n",
"\n",
"`i` + `t` × `beta` = `9` + `20` × `11` = `229` = `u`\n",
"\n",
"The passphrase letters are used to update the code as follows:\n",
"\n",
"| old code | code as
numbers | passphrase
letter | number of
letter | new first
part of code |new second
part of code | new code |\n",
"|:---|:---|:---|:---|:---|:---|:---|\n",
"| `ri` | (18, 9) | `t` | 20 | 63 | 229 | `ku` |\n",
"| `ku` | (11, 21) | `h` | 8 | 116 | 109 | `le` |\n",
"| `le` | (12, 5) | `e` | 5 | 37 | 60 | `kh` |\n",
"| `kh` | (11, 8) | `c` | 3 | 51 | 41 | `yo` |\n",
"| `yo` | (25, 15) | `a` | 1 | 100 | 26 | `vz` |\n",
"| `vz` | (22, 26) | `t` | 20 | 152 | 246 | `vl` |\n",
"\n",
"\n",
"So the final code is `vl`\n",
"\n",
"## Part 2\n",
"Your passphrase remains \"the traveller in the grey riding-coat, who called himself mr. melville, was contemplating the malice of which the gods are capable.\"\n",
"\n",
"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": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(21, 231, 23, 'w')"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"o('u'), o('u') * 11, (o('u') * 11 - 1) % 26 + 1, c(o('u') * 11)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(18, 9, 45, 63, 'k')"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"o('r'), o('i'), o('i') * 5, o('r') + o('i') * 5, c(o('r') + o('i') * 5)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(9, 20, 220, 229, 'u')"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"o('i'), o('t'), o('t') * 11, o('i') + o('t') * 11, c(o('i') + o('t') * 11)"
]
},
{
"cell_type": "code",
"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
numbers | passphrase
letter | number of
letter | new first
part of code |'\n",
" 'new second
part of code | new code |')\n",
" print('|:---|:---|:---|:---|:---|:---|:---|')\n",
" if h0 is None:\n",
" h = list('ri')\n",
" else:\n",
" h = list(h0)\n",
" for l in word:\n",
" if show_steps:\n",
" h_before = h.copy()\n",
" h[0] = c(o(h[0]) + o(h[1]) * alpha)\n",
" h[1] = c(o(h[1]) + o(l) * beta)\n",
" if show_steps:\n",
" print('| `{}` | {} | `{}` | {} | {} | {} | `{}` |'.format(\n",
" ''.join(h_before), \n",
" (o(h_before[0]), o(h_before[1])),\n",
" l, \n",
" o(l), \n",
" o(h_before[0]) + o(h_before[1]) * alpha, \n",
" o(h_before[1]) + o(l) * beta, \n",
" ''.join(h)))\n",
" return ''.join(h)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"| old code | code as
numbers | passphrase
letter | number of
letter | new first
part of code |new second
part of code | new code |\n",
"|:---|:---|:---|:---|:---|:---|:---|\n",
"| `ri` | (18, 9) | `t` | 20 | 63 | 229 | `ku` |\n",
"| `ku` | (11, 21) | `h` | 8 | 116 | 109 | `le` |\n",
"| `le` | (12, 5) | `e` | 5 | 37 | 60 | `kh` |\n",
"| `kh` | (11, 8) | `c` | 3 | 51 | 41 | `yo` |\n",
"| `yo` | (25, 15) | `a` | 1 | 100 | 26 | `vz` |\n",
"| `vz` | (22, 26) | `t` | 20 | 152 | 246 | `vl` |\n"
]
},
{
"data": {
"text/plain": [
"'vl'"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"whash2(sanitise('the cat'), show_steps=True)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'qb'"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"whash2(passphrase)"
]
},
{
"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
}