--- /dev/null
+{
+ "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 `u` + `k`, convert them to numbers (`u`=`21`, `k`=`11`), add them (`21` + `11` = `32`), then convert back to a letter (`32` is larger than 26, so it becomes `32` - 26 = `6`, which is `f`).\n",
+ "\n",
+ "Anything that isn't a lower-case 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<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |new second<br/>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": "code",
+ "execution_count": 98,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import string"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 99,
+ "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": 100,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def sanitise(phrase):\n",
+ " return ''.join(l for l in phrase if l in string.ascii_lowercase)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 101,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "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",
+ " 'new second<br/>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": 102,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "| old code | code as<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |new second<br/>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": 102,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "whash1(sanitise('the cat'), show_steps=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 103,
+ "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": 104,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'mc'"
+ ]
+ },
+ "execution_count": 104,
+ "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, `m1`= 5 and `m2` = 11.\n",
+ "\n",
+ "Then, for each letter in the pass phrase, the code is updated as follows:\n",
+ "\n",
+ "1. \"Add\" the second letter of the code to the first letter of the code \"multiplied by\" `m1`, replacing the first letter of the code\n",
+ "2. \"Add\" the current letter of the pass phrase to the second letter of the code \"multiplied by\" `m2`, 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 `22`, which is `w`).\n",
+ "\n",
+ "Again, anything that isn't a lower-case 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<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |new second<br/>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",
+ "So the final code is `pl`\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": "code",
+ "execution_count": 105,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(21, 231, 22, 'w')"
+ ]
+ },
+ "execution_count": 105,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "o('u'), o('u') * 11, (o('u') * 11 - 1) % 26, c(o('u') * 11)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 113,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def whash2(word, h0=None, m1=5, m2=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",
+ " 'new second<br/>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]) * m1)\n",
+ " h[1] = c(o(h[1]) + o(l) * m2)\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]) * m1, \n",
+ " o(h_before[1]) + o(l) * m2, \n",
+ " ''.join(h)))\n",
+ " return ''.join(h)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 116,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "| old code | code as<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |new second<br/>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": 116,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "whash2(sanitise('the cat'), show_steps=True)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 117,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'qb'"
+ ]
+ },
+ "execution_count": 117,
+ "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
+}
projects / ou-summer-of-code-2017.git / blobdiff