Lecture 06 - Decryption using MCMC.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Lecture 06 - Decryption using MCMC.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "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.7.4"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9DdBseIoEnvg"
      },
      "source": [
        "# Encryption\n",
        " \n",
        "We can use ngram models for solving (simple) substitution encryption. A substitution crypto is an encrypted message where each symbol (in this case characters) has been substituted with some other symbol. This follows from our ability to evaluate the probability of a character sequence. By training a character ngram model on (in this case) english text, we can guess an encryption key, decrypt a message, and then evaluate a probability. By changing the key slightly, we can evaluate if the probability of our result is english has increased. By this method we will slowly work our way toward a solution. This is a slow process and not very well suited for human labour. The problem formulation is, however, very well suited for a computer.\n",
        "\n",
        "We'll start by downloading some reference text to use for training the model."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IwP2GCvH2t98",
        "outputId": "747952b9-bb55-41d9-a5d6-298d3a4f998b"
      },
      "source": [
        "# Download reference text\n",
        "import nltk\n",
        "nltk.download('gutenberg')\n",
        "\n",
        "# These are some books in the collection of the gutenberg project\n",
        "books = ['carroll-alice.txt', 'melville-moby_dick.txt', 'milton-paradise.txt',  \n",
        "         'austen-emma.txt', 'austen-persuasion.txt', 'austen-sense.txt']\n",
        "#books = ['carroll-alice.txt']\n",
        "# books = ['austen-emma.txt']"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[nltk_data] Downloading package gutenberg to /root/nltk_data...\n",
            "[nltk_data]   Package gutenberg is already up-to-date!\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8raanrCaTdXj"
      },
      "source": [
        "We can create a vocabulary from the corpus. This might be usefull for evaluating performance after having found a resonable decryption key."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Lo8KPf_BSxwe",
        "outputId": "101b0fa2-e74f-40c7-932e-39066be6772f"
      },
      "source": [
        "vocabulary = set(nltk.corpus.gutenberg.words(books))\n",
        "vocabulary = set([word.lower() for word in vocabulary])\n",
        "print(\"Created a lower case vocabulary with %i entries\" % len(vocabulary))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Created a lower case vocabulary with 24570 entries\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G8nxvtYF0Mhp"
      },
      "source": [
        "We can now load the raw data and see what it looks like."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1WzdP3JFOThi",
        "outputId": "d3667626-2d90-4182-f2a7-299ea44a1c7b"
      },
      "source": [
        "raw_text = nltk.corpus.gutenberg.raw(books)\n",
        "print(raw_text[:500])"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[Alice's Adventures in Wonderland by Lewis Carroll 1865]\n",
            "\n",
            "CHAPTER I. Down the Rabbit-Hole\n",
            "\n",
            "Alice was beginning to get very tired of sitting by her sister on the\n",
            "bank, and of having nothing to do: once or twice she had peeped into the\n",
            "book her sister was reading, but it had no pictures or conversations in\n",
            "it, 'and what is the use of a book,' thought Alice 'without pictures or\n",
            "conversation?'\n",
            "\n",
            "So she was considering in her own mind (as well as she could, for the\n",
            "hot day made her feel very sleepy an\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5iXaWmSk0mUw"
      },
      "source": [
        "To make our likes easier, we define an allowed character (i.e. a constrained character set). This is so we don't have to care about special characters in this example."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LYQ2utoI0mby"
      },
      "source": [
        "# Define an allowed character set for the pre-processing\n",
        "character_set = set('abcdefghijklmnopqrstuvwxyz -.,:')"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LJG8dNGg0YBp"
      },
      "source": [
        "Pre-processing of the training data to make printouts in this notebook a bit more clear and to reduce code complexity slightly."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S0QhvCHU0SD4"
      },
      "source": [
        "# I will pre-process the text for simplicity\n",
        "def pre_process(unprocessed_text):\n",
        "  # Force lower case\n",
        "  unprocessed_text = unprocessed_text.lower()\n",
        "  # Restrict character set\n",
        "  old_character_set = \"\".join(set(list(unprocessed_text)))\n",
        "  new_character_set = \"\".join([c if c in character_set else \" \" for c in old_character_set])\n",
        "  text = unprocessed_text.translate(str.maketrans(old_character_set, new_character_set))\n",
        "  # Remove multiple spaces and return\n",
        "  import re\n",
        "  return re.sub(\"\\s\\s+\" , \" \", text.strip())\n",
        "\n",
        "# Call the pre-processing for the \n",
        "training_data = pre_process(raw_text)"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o34iBF9w0alj"
      },
      "source": [
        "This is what the pre-processed text looks like"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kCgWIEsq0YYx",
        "outputId": "786a6b97-6e1f-4325-c073-aab2e11ac465"
      },
      "source": [
        "print(training_data[:300])"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "alice s adventures in wonderland by lewis carroll chapter i. down the rabbit-hole alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it,\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nA0iQQCq0S3w"
      },
      "source": [
        "This is a naive character ngram model. Most of the time one should use a more tested class from som NLP library. However, the code here is included to show you how short the code can be."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ytX_XXOePJhr",
        "outputId": "36753602-805a-4e03-b041-e82788a5b3ab"
      },
      "source": [
        "import numpy as np # Math library\n",
        "\n",
        "class NaiveCharacterNGram(object):\n",
        "  def __init__(self, order=1):\n",
        "    \"\"\"\n",
        "    Naive NGram counter\n",
        "\n",
        "    Assumes that all characters can be found in the training set.\n",
        "    \"\"\"\n",
        "    assert order >= 1\n",
        "    self.order_ = order\n",
        "    self.counts_ = dict()\n",
        "\n",
        "  def _tokeniser(self, X, order, limit=-1):\n",
        "    \"\"\"\n",
        "    Internal tokeniser\n",
        "\n",
        "    X: text data\n",
        "    order: order if the character tokens\n",
        "    limit: max number of tokens to output (unlimited if <1)\n",
        "    \"\"\"\n",
        "    if limit < 1:\n",
        "      limit = len(X)-order+1\n",
        "    for i in range(limit):\n",
        "      yield X[i:i+order]\n",
        "\n",
        "  def fit(self, X):\n",
        "    \"\"\"\n",
        "    Train the model\n",
        "\n",
        "    X: text data\n",
        "    \"\"\"\n",
        "    assert type(X) == str\n",
        "    self._probability_lut = dict()\n",
        "    for order in range(1, self.order_+1):\n",
        "      for ngram in self._tokeniser(X, order):\n",
        "        if ngram not in self.counts_.keys():\n",
        "          self.counts_[ngram] = 1\n",
        "        else:\n",
        "          self.counts_[ngram] += 1\n",
        "    self.unigram_total_ = np.sum([self.counts_[ngram] for ngram in self.counts_.keys() if len(ngram) == 1])\n",
        "    return self\n",
        "\n",
        "  def _P(self, ngram):\n",
        "    \"\"\"\n",
        "    Internal method for getting the probability of a single ngram\n",
        "    \"\"\"\n",
        "    # Check if the ngram is in the internal look up table (LUT)\n",
        "    if ngram in self._probability_lut.keys():\n",
        "      return self._probability_lut[ngram]\n",
        "    else:\n",
        "      # Calculate the probability\n",
        "      assert 0 < len(ngram) <= self.order_, \"The model only supports ngram with length 0 < len <= %i\" % self.order_\n",
        "      # Check if this ngram was present in the training data\n",
        "      if ngram in self.counts_.keys():\n",
        "        if len(ngram) == 1:\n",
        "          p = np.log(self.counts_[ngram] / self.unigram_total_)\n",
        "        else:\n",
        "          contitional_ngram = ngram[1:]\n",
        "          p = np.log(self.counts_[ngram] / self.counts_[contitional_ngram])\n",
        "      else:\n",
        "        # Fallback is the model had not seen this ngram before\n",
        "        p = np.min([model._P(k) for k in model.counts_.keys() if len(k) == len(ngram)]) - np.log(2)\n",
        "      self._probability_lut[ngram] = p # Store the calculations for the future\n",
        "      return p\n",
        "\n",
        "  def predict_proba(self, X):\n",
        "    \"\"\"\n",
        "    Predicts the probability of a text string under the model.\n",
        "\n",
        "    X: text data\n",
        "    Returns log probability\n",
        "    \"\"\"\n",
        "    ngrams = list(self._tokeniser(X, self.order_))\n",
        "    if self.order_ > 1:\n",
        "      for order in range(1, self.order_+1):\n",
        "        ngrams.extend(self._tokeniser(X, order, limit=1))\n",
        "    p = 0\n",
        "    for ngram in ngrams:\n",
        "      p += model._P(ngram)\n",
        "    return p\n",
        "\n",
        "# Make a model and test it\n",
        "model = NaiveCharacterNGram(order=1).fit(training_data)\n",
        "assert np.isclose(model.predict_proba('acb'), model.predict_proba('abc'))\n",
        "\n",
        "# A higher order model\n",
        "model = NaiveCharacterNGram(order=3).fit(training_data)\n",
        "model.predict_proba('alice')"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-14.017937498823205"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IM-DaMUm3g_P"
      },
      "source": [
        "We can now evaluate sentences under the trained model.\n",
        "\n",
        "$P(\\text{\"I am not good at spelling\"} | model)$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3bXCx80x3gyJ",
        "outputId": "9a3c6d1a-6986-4354-eb3f-1ea9ca1a960f"
      },
      "source": [
        "model.predict_proba(\"I am not good at spelling\")"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-87.4429702131386"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HU8JMd0YgKY0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2bf512e7-52d4-45cf-ad47-947aa2b7a36b"
      },
      "source": [
        "model.predict_proba(\"spleling\")"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-26.005396467210918"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "L60l-YW1gKY1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "334f32c8-48c3-4fac-a88f-f74031b25f2d"
      },
      "source": [
        "model.predict_proba(\"spelling\")"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-20.014447326269273"
            ]
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-VSsJszA7AI0"
      },
      "source": [
        "unigram_model = NaiveCharacterNGram(order=1).fit(training_data)\n",
        "bigram_model = NaiveCharacterNGram(order=2).fit(training_data)\n",
        "trigram_model = NaiveCharacterNGram(order=3).fit(training_data)\n",
        "#quadgram_model = NaiveCharacterNGram(order=4).fit(training_data) # Quadgram is buggy, fix this in the future!"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ljR53vaUgKY1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "62497375-cb1d-4658-b69d-9e2a84dc3921"
      },
      "source": [
        "print(\"Unigram\", unigram_model.predict_proba(\"I am not good at spelling\"))\n",
        "print(\"Bigram\", bigram_model.predict_proba(\"I am not good at spelling\"))\n",
        "print(\"Trigram\", trigram_model.predict_proba(\"I am not good at spelling\"))\n",
        "#print(\"Quadgram\", quadgram_model.predict_proba(\"I am not good at spelling\")) # Quadgram is buggy, fix this in the future!"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Unigram -77.14799973232988\n",
            "Bigram -89.43303052287294\n",
            "Trigram -87.4429702131386\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 257
        },
        "id": "ope6RIb-XRBZ",
        "outputId": "8c68d2fd-d344-479a-9140-f48bc5e48f06"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "\n",
        "fig = plt.figure(figsize=(6, 2.5), dpi=100)\n",
        "ax = fig.subplots(2, 1)\n",
        "\n",
        "symbols = list(set([k for k in model.counts_.keys() if len(k)==1]))\n",
        "symbols.sort()\n",
        "prob = np.exp([model._P(s) for s in symbols])\n",
        "ax[0].bar(symbols, prob)\n",
        "ax[0].set_ylabel(\"Probability\")\n",
        "\n",
        "symbols = list(set([k for k in model.counts_.keys() if len(k)==2]))\n",
        "symbols.sort()\n",
        "prob = np.exp([model._P(s) for s in symbols])\n",
        "ax[1].bar(symbols, prob)\n",
        "ax[1].set_ylabel(\"Probability\")\n",
        "\n",
        "fig.tight_layout()\n",
        "fig.show()"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk4AAADwCAYAAAD2BuvZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3debwcVZ338c83gQSBRAGRRUBUVBSURQXBUYKooMyMG24wDwI6PriDAoIbiToDg4qgqKOgLC6M8oiowBAHNLiwOKyCKCoQDIkEWbKxJCH5PX+cqtxKpZeqXm73vff7fr361d3Vder8aus+fc6pU4oIzMzMzKy9SYMOwMzMzGyscMHJzMzMrCIXnMzMzMwqcsHJzMzMrCIXnMzMzMwqcsHJzMzMrCIXnMzMzMwqcsHJzMzMrKL1Bh3AaJMkYGtg6aBjMTMzs6ExDVgQbUYGn3AFJ1Kh6Z5BB2FmZmZDZxtgfqsZJmLBaSnAvHnzmD59+qBjMTMzswFbsmQJ2267LVRojZqIBScApk+f7oKTmZmZ1eLO4WZmZmYVTdgap37a/vhLas0/9+QD+xSJmZmZ9VJHNU6S9u11IGZmZmbDrtOmussk3SHpE5K27WlEZmZmZkOq04LTU4EzgIOAOyXNlvQWSVN6F5qZmZnZcOmo4BQR90fEFyNiV2BP4E/AV4EFkr4kaZdeBmlmZmY2DLq+qi4ibgBOItVAbQwcAVwv6VeSdup2+WZmZmbDouOCk6T1JR0k6VLgbmB/4P3AFsAO2bQLehKlmZmZ2RDoaDgCSV8G3g4I+DZwXETcWpjlYUnHAAu6D9HMzMxsOHQ6jtPzgA8AF0bE8ibz3A942AIzMzMbNzptqpsFXFAuNElaT9LLASLi8Yi4stsAzczMzIZFpwWnXwCbNpj+xOwzMzMzs3Gn04KTgGgwfTPg4c7DMTMzMxtetfo4SbowexnAOZKKTXWTgRcAV/UoNjMzM7OhUrdz+OLsWcBS4NHCZyuAa4AzexCXmZmZ2dCpVXCKiMMBJM0FPh8RbpYzMzOzCaOj4QgiYlavAzEzMzMbdpULTpJuAPaLiIck3UjjzuEARMTuvQjOzMzMbJjUqXH6MZB3Br+oD7GYmZmZDbXKBadi85yb6szMzGwi6vgmv2ZmZmYTTZ0+Tg/Rol9TUUQ0GlXczMzMbEyr08fpqL5FYWZmZjYG1OnjdG4/AzEzMzMbdnWa6qZHxJL8dat58/nMzMzMxpM6TXUPSdoqIu4DFtG4v1N+89/JvQjOzMzMbJjUKTi9Angwe71vH2IxMzMzG2p1+jhd2ei1mZmZ2UTR0b3qACRtArwTeG426Tbg7Ih4sHkqMzMzs7GrowEwJb0cmAt8ENgke3wQuCv7zMzMzGzc6XTk8K8A3weeHhFvjIg3As8A/iv7rDJJ75M0V9Jjkq6VtEeLeXeS9MNs/pDksaXMzMxs1HRacNoB+EJErMonZK9PzT6rRNJbszSzgN2Bm4HZkp7SJMmGwJ3A8cC9nYVuZmZm1plOC043MNK3qei5pMJPVR8GzoyIsyPiNuBI4BHgiEYzR8T/RsSxEfFfwPKaMZuZmZl1pc4AmC8ovP0ScLqkHYBrsmkvAd5Hqg2qsrwpwAuBk/JpEbFa0uXAXlXjqpDPVGBqYdK0Xi3bzMzMJpY6V9XdRBrcUoVppzSY73uk/k/tPJk0UObC0vSFwI414mrnBODEHi7PzMzMJqg6Baen9y2K/jqJ1I8qNw24Z0CxmK2x/fGX1Jp/7skH9ikSMzOrqs4AmHf3OO/7gVXAFqXpW9DDjt8RsZxCfyhJLeY2MzMza67jATABJD0P2A6YUpweET9plzYiVki6HtgPuChb3qTs/RndxGVmZmbWDx0VnCQ9A/gR8HzW7veU3/i36k1+TwXOlXQd8FvgKGAj4Owsn/OA+RFxQvZ+CvC8LO0U4KmSdgWWRcRfOlkXMzMzs6o6HY7gdOAu4Cmk4QN2Al4OXAfMqLqQiPg+cAzwaVLn812BAyIi7zC+HbBVIcnWwI3ZY6ss7Y3AWR2uh5mZmVllnTbV7QW8IiLul7QaWB0Rv5Z0Ammogt2qLigizqBJ01xEzCi9n8vaV/WZmZmZjZpOa5wmA0uz1/eTaoIA7gae021QZmZmZsOo0xqnW4FdSM111wLHSVoBvJt0SxQzMzOzcafTgtNnSZ24AT4FXAz8CngAeGsP4jIzMzMbOh0VnCJiduH1X4AdJW0KPBQR0TylmZmZ2djV1ThOAJK2BYiIed2HY2ZmZja8OuocLmk9SZ+RtBiYC8yVtFjSZyWt39MIzczMzIZEpzVOXwbeCBwHXJ1N2wuYCWwGvKfryMzMzEZR3ftHgu8hORF1WnA6GHhbRPx3YdrvJM0DzscFJzMzMxuHOh3HaTmpia7sLmBFx9GYmZmZDbFOa5zOAD4p6fCIWA4gaSrwcXyDXqvJ1eNmZjZWVC44SbqwNOmVwD2Sbs7e70K68e4VPYrNzMy6UPdPif+QmLVXp8Zpcen9D0vvPRyBmZmZjWuVC04RcXg/AzGz8c81IPW4Gdts+HQ1AKakzRm5qe/tEfH37kMyMzMzG04dFZwkbUQay+lQRq7MWyXpPOADEfFIj+IzsyHjWiMbZj4+rd86HY7gVGAf4J+AJ2WP12XTvtCb0MzMzMyGS6dNdW8CDoqIOYVpl0p6FPgBHgDTzMw65FojG2ad1jhtCCxsMP2+7DMzMzOzcafTgtPVwCxJG+QTJD0BOJGRe9eZmZmZjSudNtUdBVzGugNgPgbs34vAzMzMzIZNRwWniLhF0rOAQ4Ads8nnA9+NiEd7FZyZmZnZMKldcJK0PvBH4B8j4szeh2Q2NnhwwonDnZXNLFe7j1NErAQ2aDujmZmZ2TjTaefwrwAfldTVyONmZmZmY0mnBZ8XA/sBr5Z0C/Bw8cOIeGO3gZmZmZkNm04LTouAH/YyEDMzs7HMfeEmhloFJ0mTgGOBZwNTgJ8DM30lnZlZY/4xNRtf6tY4fRyYCVwOPAp8ENgcOKK3YZmNjrH6ozZW4zaz3vP3weiqW3A6FHhvRHwdQNIrgUskvSsiVvc8ugnIJ4D1m4dRMLNemYi/WXULTtsBl+ZvIuJySQFsDdzTy8DMqpqIJ65Zv/m8Mmus7nAE65Fuq1K0Eli/myAkvU/SXEmPSbpW0h5t5n+zpD9m898i6bXd5G9mZmZWRd0aJwHnSFpemLYB8J+S1gxJUGc4AklvBU4FjgSuJd0Hb7ak50TEfQ3m35t0e5cTgIuBg4GLJO0eEbfWXB8zM7OBcw3f2FG34HRug2nf6TKGDwNnRsTZAJKOBA4kdTg/ucH8HwIui4jPZe8/KelVwPtJhS/rkE9cG898fJtZL9QqOEXE4b3MXNIU4IXASYU8Vku6HNirSbK9SDVURbOB1/cytrHInX7NzMz6a9C3THkyMBlYWJq+ENixSZotm8y/ZaOZJU0FphYmTQNYsmRJ3VgrW738kVrzF2MZzbS9zLsbg4x7rG7viRj3zifOrpX21ln7r/V+rGzvibivYO395e09emmhu3NrUL8bvVYnLkVEH0Npk7m0NTAf2Dsiri5MPwXYJyL2bJBmBfCOiDi/MO29wIkRsUWD+WcCJ/YhfDMzMxtftomI+a1mGHSN0/3AKqBc4NkCuLdJmntrzn8S6zbtbQo8WD3MnphGGrJhG2DpKKYdZN4TMe6JuM6DzNtxO+5hTjvIvCdq3N2YBixoN9NAC04RsULS9aQbBl8Ea27rsh9wRpNkV2efn1aY9qpseqM8lgPLS5NHva5QUv5yaUTUyr+btIPMeyLGPRHXeZB5O27HPcxpB5n3RI27S5XyG3SNE6TaoHMlXQf8ljQcwUZAfpXdecD8iDghm/904EpJHwEuAd4GvAh492gHbmZmZhPLwAtOEfF9SZsDnyZ18L4JOCAi8g7g2wGrC/NfJelg4LPAvwN/Bl7vMZzMzMys3wZecAKIiDNo0jQXETMaTLsAuKDPYfXacmAW6zYb9jvtIPOeiHFPxHUeZN6Oe+ykHWTeXuexk3e3cffdQK+qMzMzMxtL6t6rzszMzGzCcsHJzMzMrCIXnMzMzMwqcsHJxhVJcySd1n7O0TGa8Sj5hqQHJYWkXUchz67Xr9tlSDpH0kWjmWevlmFmY89QXFVnZj1xAHAYMAO4kzQy/1jwRmBlF+k/BKjtXGYdkDQHuCkijhp0LDYcXHAyGz+eCfwtIq4adCB1RERXtz+KiMW9isXGBklTImLFoOOwiclNdTZ0JB0g6deSFkl6QNLFkp5ZYxHrSTpD0mJJ90v6jArj+LfJe5Kk4yT9RdJySX+V9PGKaTeSdJ6kZZL+lo1uX0mW7wmS7pL0qKSbJR1UI/05wJeB7bJmurk10k6T9F1JD2dxH12zGWqSpFOyJsJ7sxtrVzaIproGyzgwO14O6WY5LZY/R9KXJZ0m6SFJCyX9a3bMnC1paXbMvabNMr7U6baWNDVLf5+kx7Jz7MU14j+ji/NqnXOjzn4v5H+apPuB2VXSZWkPknRLdl49IOlySRtVTHsOsA/woey8CknbV0g3V9JRpWk3Vdlfkt4taYHS7ceK038s6Vst0v1j9p05OXu/axbvyYV5zpL0nRbL2Dw7rj5WmLa3pBWS9msT96HZ9p1amn6RpG+3SpvNt31hGxcfc9qlHW0uOFlfSTpMUt3BwjYi3YrnRaT7Eq4GflT+ImnhHcDjwB6kZpwPA++qmPYk4HjgM8DzgIOBhS1TjPgc6Uv2dcCrSU1mu1dMewJwKHAksBPwReA7kvapmP5DwKdIN8fcCqj0g5g5FXgp8M+k+z6+jOpxQ9reDwN7AscBn5L0qhrpB0rpTgTnA4dExHf7mNU7SM2ne5AKuV8jDeR7FWl7/wz4tqQN2yyj0219CvCmbBm7A38BZkvatEb8nZ5X3ZwbxfxXkI7VI6skkLQVad9+C3hulu+FVG/a/RDpPqhnks6rrYB5dYLuwAXAZsC++YRsHx0AtDo+f0W6Se1u2ft9SMfbjMI8+wBzmi0gIv4OHAHMlPQiSdOAbwNnRMQVFeKeTPoeyeN+CnAgafu3M4+RbbxVth4PAL+skHZ0RYQf4/gBHAIsKzxeNsr5vwH4Y5fLeDIQwM4V5p0D3EY2uGs27WTgtgpppwGPAe/qIMaNSSPdvrkwbVPgEeC0Nmmnkn4M9ypNPwv4Xo0YjgLm1ox7GunH6KDCtCdm8bSMu7C9f1Wa9lvg5BoxzKmSV4v05wAX1Uwzh3Sj8PcBi4B9Osi3ctzl7UT6gVkGnFeYtmV2nL+k19ua9GdkBXBwYdr6wHzg2Irxd3pedXxulPK/oYN9tHu2TZ/WxfFV+/gE5gJHlabdBMysmP4i4JuF9+/O9tWkNumuB47JXv8I+Fi27TcGnppti2dVyP8rwO2kgtrvgKkV4/4qcGnh/YeBO4rHTcXlbABcA/y03ToP4uEap/HvJ8Cuhcd1o5l5RPwoInask0bSsySdL+lOSUtIX0KQ7ltYxTWRnX2Zq4Fn5VXYLTyXVIhp98+qkWcCU4Br8wmR+u7cXiHtDsCGwP9kTRnLJC0j1UDVaaLsxDNIP6C/zSdE6jNUJe7c70rv/wY8pfvQ+u4gUs3eqyLiylHIb812iohVpH/TtxQ+z2s2W227Trf1M0n7+TeFGFaS9vtzK6SHzs+rbs6Noutrzg9wM+l8vkXSBVnz6CYdLGe0fRd4U6HZ6xDgvyJidYs0AFcCM7Im1JeRatf+APwDqbZpQUT8uUL+x5D6QL+ZVBNb9fYnZwKvlvTU7P1hwDml46aKb5H+1B1cYZ1HnTuHj3MRsRRYOug4avopcDfwr8ACUpPyraQv3356tM/Lb2bj7PlA0r/KoqG9X1NB+Yq4YGx0A7iRVCNxhKTrOvhyr6vRdlozLSIi6zLUatuN1W3dCw/XTRARq7KmzL1JTYQfAP5N0p4RcVevAyxYzbrNgevXSP/TLP2Bkv6XVAg6ukK6OaSmtl2AlRHxx6yP0AxgE1LBqopnAluTjq3tWbuA31RE3CjpZuBQST8jdTs4sGKeAEj6BLA/sEf2+zV0JsoJZ2OEpM2A5wCfjYgrIuIPpBO+jj1L718C/Dn7l9/Kn0mFp5adIJu4g/Sjtibv7J/tsyukvY1UQNouIv5SevS7P8WdpLjX9ImS9ESqxT3W3UHqR/I6Up+j8ewORvoHASBpfdJ+v63iMjo9r7o5N7oWyW8i4kRSv5kVpC4EVa0gNa3W8XdSPx0AJE0Hnl41cUQ8RqotOgR4O3B7RNxQIWnez+loRgpJc0gFpxm06N9UiHUK8B3g+8AngbOyvkpVnUWqaTocuLzOd5ikN5H6ar4lIu6okeeoco2TtSTp/cAbIqKTwgSS3gCcVKO57iFSE8a7Jf2N1Dx3cusk69hO0qnA10k1Ch8A2l7hFhGPSfoP4BRJK0jNGpsDO0XEN9ukXSbpm8DnJD0A3Af8G+mfZ7t8l0r6PPDFrAP8r0n9jF4KLImIc9sto1NZ3udmcT+YxT0ri3vc3wE8Iv4kaV9gjqTHY5yO1RMRD0v6GiP7+a+kzuUbAi2P7YJOz6uOz41uSdqT9EfoZ1m+e5LO6T/UWMxcYM/sarplwIMVmo9+Dhwm6aekPnSfBtoVMMu+C1xMqrVpeiVcUUQ8JOl3pALX+7PJvwR+QKrxqlLj9G+k758Pktb3taSms3+sGPf3gM+TWgwOrZgGSTsD5wH/Afxe0pbZRyuiyyFLes0FpzFA0mHA2RExiEH+nkx3/WyeSKpBqiQiVkt6G/AlUvPc7aQTeE6NPM8DnkDqv7EKOB34RsW0nyFdOfRpUlX134D/rJj2WFKz209JzaNfIK1/FZ8k/Us9gdTvaBFwA/DvFdN348OkdbwYWEK6+mpbUkf5cS8ibpf0ClLhaVVEVB5GYow5ntTK8G1SrcR1wP4R8VDF9N2cV92cG91YArycdOHEdFIXgI9ExH/XWMbngXNJNXNPINUczW2T5qRsvouBxaTzu3KNU+bnwIOk78/v1Uh3Jak/6xxI/ckk3QZsEREt+5VJmkHaVvtGxJJs2v8Bbpb0noj4WrvMI2KxpB+SmujqDBPyIlJB/hPZo7g+M2osp+/U/2Z965akWaSrfmYMOhYb/7IxbuaTfmCq1kYMjKTzgVUR8S+DjmW8Uh9Gz+7HMm04SLoC+H1EfHDQsfSDa5zGhtcwUu1q1lOSdgN2JNUkPJHUxwDgxwMLqgJJ65H6yexFaj4yswHK+q7NyB7vHWgwfeSC0xgQEXsMOgYb944hNQmsIF32/bKIGPZ73e1MGjzyF1RvTjWz/rmRdDHPR9s1C45lbqozMzMzq8jDEZiZmZlV5IKTmZmZWUUuOJmZmZlV5IKTmZmZWUUuOJmZmZlV5IKTmZmZWUUuOJmZmZlV5IKTmZmZWUUuOJmZmZlV5IKTmZmZWUUuOJmZmZlV5IKTmZmZWUUuOJmZmZlVtN6gAxhtkgRsDSwddCxmZmY2NKYBCyIiWs004QpOpELTPYMOwszMzIbONsD8VjNMxILTUoB58+Yxffr0QcdiZmZmA7ZkyRK23XZbqNAaNRELTgBMnz7dBSczMzOrxZ3DzczMzCpywcnMzMysoo4LTpL27WUgZmZmZsOumxqnyyTdIekTkrbtWURmZmZmQ6qbgtNTgTOAg4A7Jc2W9BZJU3oTmpmZmdlw6bjgFBH3R8QXI2JXYE/gT8BXgQWSviRpl14FOZZtf/wlo5rOzMzM+qcnncMj4gbgJFIN1MbAEcD1kn4laade5GFmZmY2aF0VnCStL+kgSZcCdwP7A+8HtgB2yKZd0HWUZmZmZkOg4wEwJX0ZeDsg4NvAcRFxa2GWhyUdAyzoLkQzMzOz4dDNyOHPAz4AXBgRy5vMcz/gYQvMzMxsXOimqW4WcEG50CRpPUkvB4iIxyPiym4CNDMzMxsW3RScfgFs2mD6E7PPzMzMzMaVbgpOAqLB9M2Ah7tYrpmZmdlQqt3HSdKF2csAzpFUbKqbDLwAuKoHsZmZmZkNlU46hy/OngUsBR4tfLYCuAY4s8u4zMzMzIZO7YJTRBwOIGku8PmIcLOcmZmZTQgdD0cQEbN6GYiZmZnZsKtVcJJ0A7BfRDwk6UYadw4HICJ27zY4MzMzs2FSt8bpx0DeGfyiHsdiZmZmNtRqFZyKzXNuqjMzM7OJpqub/PaKpPdJmivpMUnXStqjxbyHSYrS47HRjNfMzMwmprp9nB6iRb+moohoNKp4o2W+FTgVOBK4FjgKmC3pORFxX5NkS4DnFLOrkpeZmZlZN+r2cTqqDzF8GDgzIs4GkHQkcCBwBHBykzQREff2IRYzMzOzpur2cTq3l5lLmgK8EDipkMdqSZcDe7VIurGku0lNjTcAH4uI3zfJYyowtTBpWteBm5mZ2YRUq4+TpOnF160eFRf5ZNJtWhaWpi8EtmyS5nZSbdTrgH/J1uEqSds0mf8E0mjn+eOeirGZmZmZraVuU91DkrbK+h4tonHfovzmv5O7Da6RiLgauHpNZtJVwB+A/wt8skGSk0h9qHLTcOHJzMzMOlC34PQK4MHs9b49yP9+YBWwRWn6FkClPkwRsTIbjHOHJp8vZ2TsKSR1FqmZmZlNeHX7OF3Z6HWnImKFpOuB/cgG1JQ0KXt/RpVlSJoMPB+4tNt4Bmn74y9h7skHDjoMMzMza6Hje9UBSNoEeCfw3GzSbcDZEfFg81TrOBU4V9J1wG9JV+5tBORX2Z0HzI+IE7L3nwKuAf4CPAk4FngacFY362JmZmbWTscDYEp6OTAX+CCwSfb4IHBX9lklEfF94Bjg08BNwK7AARGRdxjfDtiqkGQT4ExSv6ZLgenA3hFxW6frYmY2zLY//pJBh2BmmW5qnL4CfB94T0SsgjXNZl/NPnt+1QVFxBk0aZqLiBml90cDR3cWspmZmVnnurnlyg7AF/JCE0D2+lSadNQ2MzMzG8u6KTjdwEjfpqLnAjd3sVwzs3W4ucrMhkHde9W9oPD2S8DpknYgddYGeAnwPuD43oRnZmZmNjzq9nG6iTS4ZXEwpFMazPc9Uv8nMzMzs3GjbsHp6X2JwszMzGwMqDsA5t39CsTMzMxs2HXTORwASc+TdICkfy4+ehHcRFSlA6w7yZqZmQ1Gx+M4SXoG8CPSeE3Ffk/5jX/7cpNfMzMzs0HppsbpdOAu4CnAI8BOwMuB64AZXUdmZmZmNmS6GTl8L+AVEXG/pNXA6oj4taQTSEMV7NaTCM3MzMyGRDc1TpOBpdnr+4Gts9d3A8/pJigzMzOzYdRNwelWYJfs9bXAcZJeCnwKuLPbwMzMrD98gYlZ57ppqvsssFH2+lPAxcCvgAeAt3YZl5mZmdnQ6bjgFBGzC6//AuwoaVPgoYiI5inNzMzMxqZuapzWkLQtQETM68XyzMzMzIZRx32cJK0n6TOSFgNzgbmSFkv6rKT1exah2Tjn/ibWjI8Ns+HTTefwLwPvBo4jDT2wW/b6naThCMzManFBwcyGXTcFp4OBwyLi6xHxu+zxdVLB6eDehDf++IfBzMxs7Oqm4LSc1ERXdhewoovlmpmZmQ2lbgpOZwCflDQ1n5C9/nj2mZmZmdm4UuuqOkkXlia9ErhH0s3Z+12AKcAVPYjNzMzMbKjUrXFaXHr8kDTw5bzscTFwYfaZWUMTqZ/XRFpXM7OJoFaNU0Qc3q9AzMzMzIZd1wNgStqckZv63h4Rf+92mWZmZmbDqJsBMDeS9C3gb8Avs8cCSd+UtGGvAjQzMzMbFt1cVXcqsA/wT8CTssfrsmlf6D608a3Y98X9YMzMzMaGbprq3gQcFBFzCtMulfQo8APgPd0EZmZmZjZsuqlx2hBY2GD6fdlnZhNKXnPoGkQzs/Grm4LT1cAsSRvkEyQ9ATgx+8wmMBcezMYWn7Nm1XRTcDoKeClpAMwrJF1BGstpb+BDvQjObDzzD9XY4X019nifWb90XHCKiFuAZwEnADdlj+OBZ0XE73sTno0X/hKzTvnYMbNh0lHBSdL6ku4AnhYRZ0bER7LHWRHxaI9jHLf8g2Bj1Wgcuz4/zGwYdVRwioiVwAZtZzQrKP8Q+ofRzMDfBTa2dNPH6SvARyV1Pfq4mU08LkiPDd4vibeD5bopOL0YeCPwV0mzJV1YfPQoPhtyVb5MhvkLZ5hjs4m5fybiOpcN0zYYplhsOHRTcFoE/BCYDSwAFpceVsFYL3iMF97Gg+Xtb73S7bHkY9HaqV1wkjRJ0keBZwM7kwa8fG9EHF589DrQicQnbn+M5nb1PrS6fMwMjzr7ohf7zbfgGls6qXH6OPDvwDJgPvBBUn8n69J4O2Farc94W9fceF2viabfP2SdLnMsHl/DFvOwxdNKr2MdS+s+zDopOB1KqmHaPyJeT7rJ7yGSumn2syZ8oHdurG+7sR5/M2NlvcZKnLlexTtsNbPbH39JTwqyY21/5ibiH9Bh10lhZzvg0vxNRFwOBLB1r4Ky0dXLk88nstnaBtGP0efhcPB+GJ86KTitBzxWmrYSWL/TICS9T9JcSY9JulbSHm3mf7OkP2bz3yLptZ3mPVqG9QQa1riKBhHjIH7IxsK+GO8mwsCeg85/WNQZDmO0b+DtfTTcOik4CTinNPTABsB/djIcgaS3AqcCs4DdgZuB2ZKe0mT+vYHzgW8CuwEXARdJ2rmDdbEeGZYTvWoco1kwqtvM0M38+fvioxPFtKO9bwd1LPWyqavZstrl0W0z1LDWHvdrnzbb1oM6dsv5D7tB1XSOle3TTCcFp3NJV9IVhx74DusOSVDVh4EzI+LsiLgNOBJ4BDiiyfwfAi6LiM9FxB8i4pPADcD7O1gXG2XdnDC9OikHfblyL/potPqx6GUs/VjmaKh7VdQwdQDvZwzjqUlwGLbvMBgPNfJjTe1Rv3s51ICkKcALgZMKy18t6XJgrybJ9iLVUBXNBl7fJI+pwNTCpGkAS5Ys6TDqelYvf4QlS5Y0fG5nu6MvWPO6GG++jGZ2PnE2t87av+Wy83nyOKpuj/KyG61XOe5W61rOt1Hs5TxaKa5PMZZ8XRvF1mjZrfIqL6fVuhXXvfi+2THR6Bgp5rXd0ResWbOXmIAAAA86SURBVJc8vnbHVqP1KO7/JUuWNNyvRXm+VbdPlTzL61DOr7wOrfLMl13Oo9E8jeJtlFf5dXkblPMsn1ON4i5+Vlxes+3d7NhotQ7lY798DhTzyLXKq3yM7Hzi7HXStNrOjY7j4no3yqPRNmv1vVI+d4tanSeNzvlG+RVVORearVd5GxXXt7jPy+uYL7/Zti3mX152o7jy+cppq2p1HNb5Tq/yWzVa6mwHRUQfQ2mTubQ1aUiDvSPi6sL0U4B9ImLPBmlWAO+IiPML094LnBgRWzSYfyZwYh/CNzMzs/Flm4iY32qGiXCfuZNYt4ZqU+DBPuU3DbinT8s2MzObyLYBlvZp2dNI3Y5aGnTB6X5gFVCuKdoCuLdJmnvrzB8Ry4Hlpcl9a6eT1K9Fm5mZTXRLI6Jfv+GVljvQQSsjYgVwPbBfPi0bSHM/4Oomya4uzp95VYv5zczMzHpi0DVOkJrRzpV0HfBb4ChgI+BsAEnnAfMj4oRs/tOBKyV9BLgEeBvwIuDdox24mZmZTSyTZ86cOdAAZs6c+ftZs2YtAj4BHJNNPiQibgeYNWvWh4BVM2fOvCibf96sWbP+CBwLnABsCbwzIn4z+tGva9asWQCTs7ffB34DrAb+H6lZst/Po5nneM1rvK+ft6XzGsY8x2te4339RjOv7wFXzJw5cxUDNNCr6szMzMzGEt+Y18zMzKwiF5zMzMzMKnLByczMzKyqiPCjTw/gMGBR+T3wP0AUHos7XP5c4KjS+2NJnfTyZS8pzlMlzmzalwrLOa1F2u2zeXYtvT+htI4BXEcaUyuyZT+ePW7M0i7KPnsceDR7jizNadn7VcCVVeIpvH5tg1jyeOeQBixdXYhprdiAxwrT8/SPF57vabSNgBnZPE9qMO3ewrI+UJyPdCPtb5Tyq/rYtcrxUjhWHi6lX00aXC7fJvdl8xfX97TCvio/Xl/Yrvm0FVm6Rdm+vLGwvcvp822fx3AacA6wLJv+SCndiux5VSmuR0njxOUxzy2sw7WF/Z6nzfPNj7sbC8taWYpxTWw1ztVGx8JLCzFe0STdmm1aeH9TIZZvluepE0fh/bEN9sWTKi5zzXHV4NjK99VDtP8eKq9rHtuNna5vtpxzgIvK77PtmMe3tDhPF9vutzW3XXmdt2ywH+qs60zgpnbf8dn7R7J9tDjLZ3mVZZOuYM/TzK8aSyH9T0nnXNP0jPxWrokbOAuIqtuinw/XOA3GS7Pn3YHjSAfQGpIOk7Sow2XvQfrh/SWwG+kLay2S5ko6qs1y3gpcQSp4/bGDeF6XPX8MeHWTeSZnsVa1IIvn0nxCxXXJ/UvxjaTtgX2A9SukFSOxLiN94aw9Q71Y8tFp3wTcVvrsWOBfWXvbrKKw3qQv/FwAb8leP6Ni/pCOlQ1Itz0q25J6+6Z8Vesbgddkr48H/kYq2LyIVJBdAPyckYLaV7Npp5HOjz2AvYE3AH8E9gT+IZu+lHXXv91VNk8j/WH5EbCwxnpBOk4bDbB7RI393cippEIGpGFYkDRDUkh6Uot0m2TP3wE+Uv4wS9/w3p0tvLPw+v82WGaVuIryY2sJcDKlgQVrniubZs+fpnfruzGwC+kOEnNY+ztljqTl2XJD0uOSbgQuzma5R9I9wM+y958pLHe37PmkbFl1t9vRhdfrbJ8K6/p51h3nsJUnAFeR/hw+Wsin2W/QJOAMYBbpnL1f0kxJN1XMbxLp/L83T1/Is91yrqWPg1fX4YLTYDwBICJuBP7ebCZJk7MBQRt+1iTZZtnzgxGR/zNttvwpTaZvDDyFNDhpkE6qup6SPd8J/LmD9I3k/w7LI8E3XZeSdQqRHcr/LTVUMZY7sufrWfdH/6mF13k+8xmpHcprayDVjiyLiPyOpKtrxLAZqTalk/1btta2jYgHI+Ky7O2dpHVcFBG3RMTfsrgnZfk/TjpGVgJ/jYhrI+IPEfFXRo6/P0fENRFxKyP/xKvKC4C3k754V7eYt5HVNDjm1sqg2vYueybwp+z1Oj8Ian4bgvzYuSciWv6hkVTlTwHAVoXXLW85IanK+H/5sbWaVFBtuL8kbSRpSqFgsUH2fgqwYTbtL9nzHaW0m0vaqJSu6tiEebpHSLUnj7aYt51KeVaM7ZmF13e3Wd46+zYilkXEA4V52h2XAm6m9fdZ8XdoCumP5o9Iv111zsM8/STSNm+YvkXMec3vwHk4gj6RtBlpgM49SF8ezQo6uaDeP/x8/hWkA7lV2hWkA9bMzGy82Tkifj9ambnGqX82IFXDVyk0QSr4rGzy2eOF16tJ/94vy15PydK2KgFPoXFTxnxSVXU5bdVq1zwe651W+7HcPGVmjRXPj2bfq50ubzwYtvWpE88yUk19XqO5hFSrPWpccOqTiJhPKtxMZqQzcKv22dXAfaVpqwqf5SaRmjX2Y+39l9c4RYM0MNJZt2hDUpt4sbZqJanzZNGiBssrxjMsBjqabEXtCpqtPi9uaxdY1zVsPwZjQS8KFcPu1hrzNjuvGnWpGMvH22jcjb7V9il/Vo6nvB/yi4ogNbNuA8wjfSe+NyK6aWqtzU11fSJpGTCV6vcD/Dup8+HhhWl1m+/qCuD1wI9L01dRrZbMrJFuj9t+H/ejlYf110qqXdhRR95/sPy9/XiDaTY4ecFFwHoRMap/moeptmC8+RojHUqXk5rE/s7atSLFUusq0pVwxX+AIl1BVJx/FXA+I5dhw9qdhfPn8j/JS7MYikS6iqnoe8AXGq2Q9cTjbT77ZcXlDLrGqd//uAb9j27FgPNvpB/bZBhrnKL03Ew/fiwn0biA1OjigEEfo2NJp9sqvxDkAUa+85aRfrtGtZapyAWn/tkRuCF7nV89NJ21/+UWf/ymZ8+NmtNyIvU/+gKp31KefhIj+zJffvlL5Resexk3wNNL78+lcImo9VyrL5DJpAsKul3OaOhnbU0vlt1u+7TLYxibfSdKDZlKz73WyZ+ODRtMG/Sfl7Gk032ZjwF3JyO/cRtnzxsCK0e7tgncVNc3kk4lNbtVHb8D0mW7T2btZrJyk8KFpHF/PtFmWeV0K7PHBrQvMN/HyHACNrqqXgHppiazzvjcGVsCuIuRMeqKXUkeBHYC/j6aBSgXnPpE0qak6sVWVjNSiKl7Mv8JeHbFZZuZmY1XT4+IuaOVmX9Y++eJpCrGZ0eEGj0YGXl2cURMKn2WF7quBA7N3k8tfH4NcG6LZT8tS/8wcHSDz+8mjXi7Gvincqyk2rLFzZZfmO+vwOEtPj+ssE12K32WNxPulr1eTeog33C9gG2z+b/b4LNJpAHyHmoVT4N0eQyrgRcC57XarlmavAl2YZNtO4lUtfw4sG+L5eyYLSfve7ZJ6fN9s+mvzeK7qsEyNiYNJveu0vti+38+hAWkGq3iiMT/y9q+ky+vsE0/Qup7NavFuuTH63safAYj/ffe1Gq/ko7Lo0ufP8xIlf3D2Tx3NzkOjiANmDilSZznkvpIfLY0/YekPy8vbLGO92RxvrLJsfeRJuk2Ig3iuc6xUNjH5X3/S+DsbJtt2WabA7yhyXZ/O+lq3je1iqOQJu/zmI+yv4C1b4eTH0P56z8x0k8q78O5MpvnptL+/WohnyuzeVZkx9dC4OY2590yRgZafUOT7bhNvr5VjodsnpNJ58vvgB83OF5+nD2vbrXtsvm/2WR/vry4L2lzPrU7p7LPpxXXtfTZp4BbstfPoP1vUcPve9II6AFsUZo+izRw5s8ZuT0TheMkP2a+ke2zIHUBeTx7fijb9w81iadpzDT4PYxRLDSBrxLop9cC34iINaNmSzqGdNuHh0m3yHg1zYco2JR0AJ4OfBb4ekSsyJYj0n2S/qGw7FeQfjRvAbbL0gUNOtBlI85OzmK8hlTIWivWKiTtRPqRPa8w7VBSoWE+8BLgi7SvTdsMOCaL5QX5erVYp8uKiSVtDrwN2JpUpXseFWTbYfPs7S2ke2LNoLBdS3HcTrodyC6kH4l1RtwuxfLziJhT+vy9pMLK46Tb0ZCtz8ENQsyvGDqe9EVztKTdSAWu35IK51/I5ttV0gLS7TjWZ+0/RcFI1fYk1u78v3spzy2z518D78/e/xD4MHBgYT3eQPohmwf8MyMj1q91a5LCiMMvJjUB/6TNfi0e0+sBO7N28/J62TquBhoNePda4GMRsTJbxtNI59mVpKtc9yIVIL6Xfb5+FvsBwPURkReKy8ffVqRj5UEKHfgL+3tLUkGnkX1pcCw0ky3z2aRtckFELMymN9rmvyOdM+Vl5NvrLaThRH4C7F+Oo3A8PkDaTkeSOkKXh0ZZa/Gk/fE4abs8ytpXt+W3J5oiaW/glGze4sjf+TE6iXR8nUK6/VFxHfLYHib9WG5MGirlsCYxQbpdUb6+UDoesuUWj4lnkm43M5X0vVX+nlqf9F38GuC6FufzA6TvhreVPp9KOm5mku1LSU/M8j2wNG+dc+rJpAJncV3zuz5sTzp38+4c6/wWtSNpQ9K+fTfwi4goHw8bkM7D52fvi31si0PjbMrILYIeI52/t5EKkmTr2kij3888puMp/B4ORAzBDfMmygP4AekL6dHssZD0hbGowbyHkQ60laR7xm3cZtn7k8YreYR0Mq0kDYs/l9LNNRm5OeV9wPObLO+wRnFVWMfjsjwfIxWqHgb+I8tv19K82zPyz+T2ciwt1mn90nxBKsgcXDPWGYX8D6qwbZeTfrD/Svria7RtW8ZCKkguYOSf+QWkMbmC0o1BSf+Eg3RBwFOzabuRBn9bRvoRv4ZUgHissC6dPpaTCvbPr7AehzJS27AqiyEo3ZC0sI/vB/Zrt19Z+0bEuzZYr1XZYzbpX327fbwt6T56i0l/Uu4DftXgGGh3/C0kHcuzenHsNci/ePPfw7J1vD7f7y22+WZVt3ub4/Ex0sUji0i1TXlc8xm5aje/1VD+WMbaN1a+j5GbY+fzL8z27TzWvhFwvoy5FWLL1/c3pB/eRuv7tmz6Pa3Wt8ExEdlx8WZKNwPO5r03W58vVth+f2LkJsT5jYAb7ssenVPzyuuarcNy4PvA5BrH4WGsfRPgmbT47aH5Tb7zR74OzT5flMW4zg2JW8TYMqbRfCgLyMzMzMzacB8nMzMzs4pccDIzMzOryAUnMzMzs4pccDIzMzOryAUnMzMzs4pccDIzMzOryAUnMzMzs4pccDIzMzOryAUnMzMzs4r+P3s+leTY1HnpAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 600x250 with 2 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "57wtrFOIgKY2"
      },
      "source": [
        "## Load poem\n",
        "\n",
        "### Poem 1"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_mU1GRxLgKY2"
      },
      "source": [
        "!wget -N https://raw.githubusercontent.com/fredrikwahlberg/5LN445/master/poem1.txt\n",
        "\n",
        "with open('poem1.txt', 'r') as f:\n",
        "  encrypted_text = f.read()\n",
        "\n",
        "print(\"Encrypted text:\", encrypted_text[:100], \"...\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z8VAmJ1cgKY3"
      },
      "source": [
        "### Poem 2"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PGB5pCkFgKY3"
      },
      "source": [
        "!wget -N https://raw.githubusercontent.com/fredrikwahlberg/5LN445/master/poem2.txt\n",
        "\n",
        "with open('poem2.txt', 'r') as f:\n",
        "  encrypted_text = f.read()\n",
        "\n",
        "print(\"Encrypted text:\", encrypted_text[:100], \"...\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I7lFd33AgKY3"
      },
      "source": [
        "### Poem 3"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6MMDNvzPgKY3"
      },
      "source": [
        "!wget -N https://raw.githubusercontent.com/fredrikwahlberg/5LN445/master/poem3.txt\n",
        "\n",
        "with open('poem3.txt', 'r') as f:\n",
        "  encrypted_text = f.read()\n",
        "\n",
        "print(\"Encrypted text:\", encrypted_text[:100], \"...\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d6_px_X8gKY3"
      },
      "source": [
        "### Poem 4"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZQtEfV-kgKY3"
      },
      "source": [
        "!wget -N https://raw.githubusercontent.com/fredrikwahlberg/5LN445/master/poem4.txt\n",
        "\n",
        "with open('poem4.txt', 'r') as f:\n",
        "  encrypted_text = f.read()\n",
        "\n",
        "print(\"Encrypted text:\", encrypted_text[:100], \"...\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3UmAPdrjsM4I"
      },
      "source": [
        "### Poem 5"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5MCqtDC9sNAN"
      },
      "source": [
        "!wget -N https://raw.githubusercontent.com/fredrikwahlberg/5LN445/master/poem5.txt\n",
        "\n",
        "with open('poem5.txt', 'r') as f:\n",
        "  encrypted_text = f.read()\n",
        "\n",
        "print(\"Encrypted text:\", encrypted_text[:100], \"...\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4A0-WGPg7CCS"
      },
      "source": [
        "Train models to use for evaluating a key\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2NN55Rlk7FAF"
      },
      "source": [
        "Define the probability meassure using the models. *Note that you can run this cell and redefine P and still go back to a \"running\" decryption.*\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "13oGhI4g-zFw"
      },
      "source": [
        "def P(decrypted_text):\n",
        "  ret = unigram_model.predict_proba(decrypted_text)\n",
        "  ret += bigram_model.predict_proba(decrypted_text)\n",
        "  ret += trigram_model.predict_proba(decrypted_text)\n",
        "  #ret += quadgram_model.predict_proba(decrypted_text) # Quadgram is buggy, fix this in the future!\n",
        "  return ret"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GbQopkUs7qEJ"
      },
      "source": [
        "### Make a new (random) key"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3x-oLCV_GnvY"
      },
      "source": [
        "unencoded = \"\".join(character_set)\n",
        "encoded = unencoded.upper().translate({ord(' '): ord('0'),\n",
        "                                       ord('-'): ord('1'),\n",
        "                                       ord('.'): ord('2'),\n",
        "                                       ord(','): ord('3'),\n",
        "                                       ord(':'): ord('4')})\n",
        "# Split the symbols\n",
        "symbols = list(encoded)\n",
        "# Shuffle the symbols\n",
        "import random\n",
        "random.shuffle(symbols)\n",
        "# Join the symbols\n",
        "encoded = ''.join(symbols)\n",
        "print(\"New key\")\n",
        "print(\"Unencoded:\", unencoded)\n",
        "print(\"Encoded:  \", encoded)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Neb_W-hmgKY4"
      },
      "source": [
        "### Run optimisation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m1YICxFiK_Si"
      },
      "source": [
        "import time\n",
        "\n",
        "# Decrypt using scrambled key\n",
        "key = str.maketrans(encoded, unencoded)\n",
        "decrypted_text = encrypted_text.translate(key)\n",
        "\n",
        "p = P(decrypted_text)\n",
        "\n",
        "print(\"Initial decrypted text %s\" % decrypted_text[:80])\n",
        "print(\"P: %f\" % p)\n",
        "\n",
        "msg_time = time.time()\n",
        "n_words = 0\n",
        "best_key = None\n",
        "for i in range(5000):\n",
        "  # Store the probability and key from the last iteration of the loop\n",
        "  old_p = p\n",
        "  old_unencoded = unencoded\n",
        "\n",
        "  # Randomly swap two charcters in the key\n",
        "  unencoded = list(unencoded)\n",
        "  a = random.randint(0, len(unencoded)-1)\n",
        "  b = random.randint(0, len(unencoded)-1)\n",
        "  c = unencoded[a]\n",
        "  unencoded[a] = unencoded[b]\n",
        "  unencoded[b] = c\n",
        "  unencoded = \"\".join(unencoded)\n",
        "\n",
        "  # Decode the message\n",
        "  key = str.maketrans(encoded, unencoded)\n",
        "  decrypted_text = encrypted_text.translate(key)\n",
        "\n",
        "  # Find the probability of the decrypted text to be english\n",
        "  p = P(decrypted_text)\n",
        "  \n",
        "  # Find the number words that we could find in the vocabulary\n",
        "  old_n_words = n_words\n",
        "  n_words = np.sum([word in vocabulary for word in decrypted_text.split()])\n",
        "  if best_key is None or best_key[1] < n_words:\n",
        "    best_key = (key.copy(), n_words)\n",
        "\n",
        "  # Print-out\n",
        "  if i % 200 == 0 or (time.time()-msg_time)>2:\n",
        "    msg_time = time.time()\n",
        "    print(\"%4i | %s | %.2f | %3i | %s\" % (i, decrypted_text[:50], p, n_words, unencoded))\n",
        "\n",
        "  # Metropolis hastings rejection step\n",
        "  alpha = p - old_p\n",
        "  if np.log(random.random()) > alpha or (old_n_words > 20 and n_words < old_n_words//2): # Second condition is experimental\n",
        "    # Reject candidate\n",
        "    p = old_p\n",
        "    unencoded = old_unencoded"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QZEbsVLf8hrM"
      },
      "source": [
        "### Print the decrypted text \n",
        "\n",
        "...with some spaces made into line feeds."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tcUrbyZM-7bb"
      },
      "source": [
        "n = 0\n",
        "for word in decrypted_text.split():\n",
        "  if n < 60:\n",
        "    print(word, end=\" \")\n",
        "    n += len(word)+1\n",
        "  else:\n",
        "    print(word, end=\"\\n\")\n",
        "    n = 0"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mHAkEALpTyN1"
      },
      "source": [
        "n = 0\n",
        "for word in encrypted_text.translate(best_key[0]).split():\n",
        "  if n < 60:\n",
        "    print(word, end=\" \")\n",
        "    n += len(word)+1\n",
        "  else:\n",
        "    print(word, end=\"\\n\")\n",
        "    n = 0"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PZpVzmmCYCAq"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}