03-door-codes/door-codes-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Door codes\n",
   8     "\n",
   9     "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",
  10     "\n",
  11     "Luckily, you know how their system works. \n",
  12     "\n",
  13     "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",
  14     "\n",
  15     "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",
  16     "\n",
  17     "You start with the first two letters of the pass phrase. This is the starting value of your code.\n",
  18     "\n",
  19     "Then, for each subsequent letter in the pass phrase, you:\n",
  20     "1. \"Add\" the second letter of the code to the first letter of the code, replacing the first letter of the code\n",
  21     "2. \"Add\" the current letter of the pass phrase to the second letter of the code, replacing the second letter of the code\n",
  22     "3. Move on to the next letter of the pass phrase\n",
  23     "\n",
  24     "\"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",
  25     "\n",
  26     "All letters are converted to lower-case, and anything that isn't a letter is ignored.\n",
  27     "\n",
  28     "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",
  29     "\n",
  30     "| 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",
  31     "|:---|:---|:---|:---|:---|:---|:---|\n",
  32     "| `th` | (20, 8) | `e` | 5 | 28 | 13 | `bm` |\n",
  33     "| `bm` | (2, 13) | `c` | 3 | 15 | 16 | `op` |\n",
  34     "| `op` | (15, 16) | `a` | 1 | 31 | 17 | `eq` |\n",
  35     "| `eq` | (5, 17) | `t` | 20 | 22 | 37 | `vk` |\n",
  36     "\n",
  37     "So the final code is `vk`\n",
  38     "\n",
  39     "## Part 1\n",
  40     "Your passphrase is \n",
  41     "\"the traveller in the grey riding-coat, who called himself mr. melville, was contemplating the malice of which the gods are capable.\"\n",
  42     "\n",
  43     "**What is your door code?**"
  44    ]
  45   },
  46   {
  47    "cell_type": "code",
  48    "execution_count": 3,
  49    "metadata": {
  50     "collapsed": true
  51    },
  52    "outputs": [],
  53    "source": [
  54     "import string"
  55    ]
  56   },
  57   {
  58    "cell_type": "code",
  59    "execution_count": 4,
  60    "metadata": {
  61     "collapsed": true
  62    },
  63    "outputs": [],
  64    "source": [
  65     "def o(letter):\n",
  66     "    return ord(letter) - ord('a') + 1\n",
  67     "\n",
  68     "def c(number):\n",
  69     "    return chr((number - 1) % 26 + ord('a'))"
  70    ]
  71   },
  72   {
  73    "cell_type": "code",
  74    "execution_count": 5,
  75    "metadata": {},
  76    "outputs": [
  77     {
  78      "data": {
  79       "text/plain": [
  80        "('a', 'z', 'z', 'a')"
  81       ]
  82      },
  83      "execution_count": 5,
  84      "metadata": {},
  85      "output_type": "execute_result"
  86     }
  87    ],
  88    "source": [
  89     "c(1), c(0), c(26), c(27)"
  90    ]
  91   },
  92   {
  93    "cell_type": "code",
  94    "execution_count": 6,
  95    "metadata": {
  96     "collapsed": true
  97    },
  98    "outputs": [],
  99    "source": [
 100     "def sanitise(phrase):\n",
 101     "    return ''.join(l.lower() for l in phrase if l in string.ascii_letters)"
 102    ]
 103   },
 104   {
 105    "cell_type": "code",
 106    "execution_count": 7,
 107    "metadata": {},
 108    "outputs": [
 109     {
 110      "data": {
 111       "text/plain": [
 112        "'helloworld'"
 113       ]
 114      },
 115      "execution_count": 7,
 116      "metadata": {},
 117      "output_type": "execute_result"
 118     }
 119    ],
 120    "source": [
 121     "sanitise('Hello World')"
 122    ]
 123   },
 124   {
 125    "cell_type": "code",
 126    "execution_count": 7,
 127    "metadata": {
 128     "collapsed": true
 129    },
 130    "outputs": [],
 131    "source": [
 132     "def whash1(word, show_steps=False):\n",
 133     "    if show_steps:\n",
 134     "        print('| old code | code as<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |'\n",
 135     "              'new second<br/>part of code | new code |')\n",
 136     "        print('|:---|:---|:---|:---|:---|:---|:---|')\n",
 137     "    h = list(word[:2])\n",
 138     "    for l in word[2:]:\n",
 139     "        if show_steps:\n",
 140     "            h_before = h.copy()\n",
 141     "        h[0] = c(o(h[0]) + o(h[1]))\n",
 142     "        h[1] = c(o(h[1]) + o(l))\n",
 143     "        if show_steps:\n",
 144     "            print('| `{}` | {} | `{}` | {} | {} | {} | `{}` |'.format(\n",
 145     "                  ''.join(h_before), \n",
 146     "                  (o(h_before[0]), o(h_before[1])),\n",
 147     "                  l, \n",
 148     "                  o(l), \n",
 149     "                  o(h_before[0]) + o(h_before[1]), \n",
 150     "                  o(h_before[1]) + o(l), \n",
 151     "                  ''.join(h)))\n",
 152     "    return ''.join(h)"
 153    ]
 154   },
 155   {
 156    "cell_type": "code",
 157    "execution_count": 8,
 158    "metadata": {},
 159    "outputs": [
 160     {
 161      "name": "stdout",
 162      "output_type": "stream",
 163      "text": [
 164       "| 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",
 165       "|:---|:---|:---|:---|:---|:---|:---|\n",
 166       "| `th` | (20, 8) | `e` | 5 | 28 | 13 | `bm` |\n",
 167       "| `bm` | (2, 13) | `c` | 3 | 15 | 16 | `op` |\n",
 168       "| `op` | (15, 16) | `a` | 1 | 31 | 17 | `eq` |\n",
 169       "| `eq` | (5, 17) | `t` | 20 | 22 | 37 | `vk` |\n"
 170      ]
 171     },
 172     {
 173      "data": {
 174       "text/plain": [
 175        "'vk'"
 176       ]
 177      },
 178      "execution_count": 8,
 179      "metadata": {},
 180      "output_type": "execute_result"
 181     }
 182    ],
 183    "source": [
 184     "whash1(sanitise('the cat'), show_steps=True)"
 185    ]
 186   },
 187   {
 188    "cell_type": "code",
 189    "execution_count": 9,
 190    "metadata": {
 191     "collapsed": true
 192    },
 193    "outputs": [],
 194    "source": [
 195     "passphrase = sanitise(\"the traveller in the grey riding-coat, who called himself mr. melville, was \"\n",
 196     "                      \"contemplating the malice of which the gods are capable.\")"
 197    ]
 198   },
 199   {
 200    "cell_type": "code",
 201    "execution_count": 10,
 202    "metadata": {},
 203    "outputs": [
 204     {
 205      "data": {
 206       "text/plain": [
 207        "'mc'"
 208       ]
 209      },
 210      "execution_count": 10,
 211      "metadata": {},
 212      "output_type": "execute_result"
 213     }
 214    ],
 215    "source": [
 216     "whash1(passphrase)"
 217    ]
 218   },
 219   {
 220    "cell_type": "markdown",
 221    "metadata": {},
 222    "source": [
 223     "You arrive at your door but the passcode doesn't work!\n",
 224     "\n",
 225     "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",
 226     "\n",
 227     "Indeed, the algorithm has been changed, \"to improve security,\" they say.\n",
 228     "\n",
 229     "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",
 230     "\n",
 231     "Then, for each letter in the pass phrase, the code is updated as follows:\n",
 232     "\n",
 233     "1. \"Multiply\" the second letter of the code by `alpha` then add the first letter of the code, replacing the first code letter\n",
 234     "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",
 235     "\n",
 236     "\"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",
 237     "\n",
 238     "Again, all letters are converted to lower-case and anything that isn't a letter is ignored.\n",
 239     "\n",
 240     "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",
 241     "\n",
 242     "`r` + `i` × `alpha` = `18` + `9` × `5` = `63` = `k`\n",
 243     "\n",
 244     "and the second letter of the code becomes:\n",
 245     "\n",
 246     "`i` + `t` × `beta` = `9` + `20` × `11` = `229` = `u`\n",
 247     "\n",
 248     "The passphrase letters are used to update the code as follows:\n",
 249     "\n",
 250     "| 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",
 251     "|:---|:---|:---|:---|:---|:---|:---|\n",
 252     "| `ri` | (18, 9) | `t` | 20 | 63 | 229 | `ku` |\n",
 253     "| `ku` | (11, 21) | `h` | 8 | 116 | 109 | `le` |\n",
 254     "| `le` | (12, 5) | `e` | 5 | 37 | 60 | `kh` |\n",
 255     "| `kh` | (11, 8) | `c` | 3 | 51 | 41 | `yo` |\n",
 256     "| `yo` | (25, 15) | `a` | 1 | 100 | 26 | `vz` |\n",
 257     "| `vz` | (22, 26) | `t` | 20 | 152 | 246 | `vl` |\n",
 258     "\n",
 259     "\n",
 260     "So the final code is `vl`\n",
 261     "\n",
 262     "## Part 2\n",
 263     "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",
 264     "\n",
 265     "Using this new algorithm, **what is your door code?**"
 266    ]
 267   },
 268   {
 269    "cell_type": "code",
 270    "execution_count": 11,
 271    "metadata": {},
 272    "outputs": [
 273     {
 274      "data": {
 275       "text/plain": [
 276        "(21, 231, 23, 'w')"
 277       ]
 278      },
 279      "execution_count": 11,
 280      "metadata": {},
 281      "output_type": "execute_result"
 282     }
 283    ],
 284    "source": [
 285     "o('u'), o('u') * 11, (o('u') * 11 - 1) % 26 + 1, c(o('u') * 11)"
 286    ]
 287   },
 288   {
 289    "cell_type": "code",
 290    "execution_count": 12,
 291    "metadata": {},
 292    "outputs": [
 293     {
 294      "data": {
 295       "text/plain": [
 296        "(18, 9, 45, 63, 'k')"
 297       ]
 298      },
 299      "execution_count": 12,
 300      "metadata": {},
 301      "output_type": "execute_result"
 302     }
 303    ],
 304    "source": [
 305     "o('r'), o('i'), o('i') * 5, o('r') + o('i') * 5, c(o('r') + o('i') * 5)"
 306    ]
 307   },
 308   {
 309    "cell_type": "code",
 310    "execution_count": 13,
 311    "metadata": {},
 312    "outputs": [
 313     {
 314      "data": {
 315       "text/plain": [
 316        "(9, 20, 220, 229, 'u')"
 317       ]
 318      },
 319      "execution_count": 13,
 320      "metadata": {},
 321      "output_type": "execute_result"
 322     }
 323    ],
 324    "source": [
 325     "o('i'), o('t'), o('t') * 11, o('i') + o('t') * 11, c(o('i') + o('t') * 11)"
 326    ]
 327   },
 328   {
 329    "cell_type": "code",
 330    "execution_count": 14,
 331    "metadata": {
 332     "collapsed": true
 333    },
 334    "outputs": [],
 335    "source": [
 336     "def whash2(word, h0=None, alpha=5, beta=11, show_steps=False):\n",
 337     "    if show_steps:\n",
 338     "        print('| old code | code as<br>numbers | passphrase<br/>letter | number of<br/>letter | new first<br/>part of code |'\n",
 339     "              'new second<br/>part of code | new code |')\n",
 340     "        print('|:---|:---|:---|:---|:---|:---|:---|')\n",
 341     "    if h0 is None:\n",
 342     "        h = list('ri')\n",
 343     "    else:\n",
 344     "        h = list(h0)\n",
 345     "    for l in word:\n",
 346     "        if show_steps:\n",
 347     "            h_before = h.copy()\n",
 348     "        h[0] = c(o(h[0]) + o(h[1]) * alpha)\n",
 349     "        h[1] = c(o(h[1]) + o(l) * beta)\n",
 350     "        if show_steps:\n",
 351     "            print('| `{}` | {} | `{}` | {} | {} | {} | `{}` |'.format(\n",
 352     "                  ''.join(h_before), \n",
 353     "                  (o(h_before[0]), o(h_before[1])),\n",
 354     "                  l, \n",
 355     "                  o(l), \n",
 356     "                  o(h_before[0]) + o(h_before[1]) * alpha, \n",
 357     "                  o(h_before[1]) + o(l) * beta, \n",
 358     "                  ''.join(h)))\n",
 359     "    return ''.join(h)"
 360    ]
 361   },
 362   {
 363    "cell_type": "code",
 364    "execution_count": 15,
 365    "metadata": {},
 366    "outputs": [
 367     {
 368      "name": "stdout",
 369      "output_type": "stream",
 370      "text": [
 371       "| 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",
 372       "|:---|:---|:---|:---|:---|:---|:---|\n",
 373       "| `ri` | (18, 9) | `t` | 20 | 63 | 229 | `ku` |\n",
 374       "| `ku` | (11, 21) | `h` | 8 | 116 | 109 | `le` |\n",
 375       "| `le` | (12, 5) | `e` | 5 | 37 | 60 | `kh` |\n",
 376       "| `kh` | (11, 8) | `c` | 3 | 51 | 41 | `yo` |\n",
 377       "| `yo` | (25, 15) | `a` | 1 | 100 | 26 | `vz` |\n",
 378       "| `vz` | (22, 26) | `t` | 20 | 152 | 246 | `vl` |\n"
 379      ]
 380     },
 381     {
 382      "data": {
 383       "text/plain": [
 384        "'vl'"
 385       ]
 386      },
 387      "execution_count": 15,
 388      "metadata": {},
 389      "output_type": "execute_result"
 390     }
 391    ],
 392    "source": [
 393     "whash2(sanitise('the cat'), show_steps=True)"
 394    ]
 395   },
 396   {
 397    "cell_type": "code",
 398    "execution_count": 16,
 399    "metadata": {},
 400    "outputs": [
 401     {
 402      "data": {
 403       "text/plain": [
 404        "'qb'"
 405       ]
 406      },
 407      "execution_count": 16,
 408      "metadata": {},
 409      "output_type": "execute_result"
 410     }
 411    ],
 412    "source": [
 413     "whash2(passphrase)"
 414    ]
 415   },
 416   {
 417    "cell_type": "code",
 418    "execution_count": null,
 419    "metadata": {
 420     "collapsed": true
 421    },
 422    "outputs": [],
 423    "source": []
 424   }
 425  ],
 426  "metadata": {
 427   "kernelspec": {
 428    "display_name": "Python 3",
 429    "language": "python",
 430    "name": "python3"
 431   },
 432   "language_info": {
 433    "codemirror_mode": {
 434     "name": "ipython",
 435     "version": 3
 436    },
 437    "file_extension": ".py",
 438    "mimetype": "text/x-python",
 439    "name": "python",
 440    "nbconvert_exporter": "python",
 441    "pygments_lexer": "ipython3",
 442    "version": "3.5.2+"
 443   }
 444  },
 445  "nbformat": 4,
 446  "nbformat_minor": 2
 447 }