Perfect Hangman Algorithm.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Anp215aL-ofa"
      },
      "source": [
        "# Perfect Hangman Algorithm"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ogcNN4En530F",
        "outputId": "f45384b7-1a43-4c59-8788-f9d233325588"
      },
      "outputs": [
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "[nltk_data] Downloading package words to /root/nltk_data...\n",
            "[nltk_data]   Package words is already up-to-date!\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "execution_count": 17,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import nltk\n",
        "nltk.download('words')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "V3y57vBu5AZr"
      },
      "outputs": [],
      "source": [
        "import time\n",
        "from nltk.corpus import words as wordlist\n",
        "import pandas as pd\n",
        "import seaborn as sns\n",
        "import matplotlib.pyplot as graph\n",
        "from collections import Counter\n",
        "\n",
        "\n",
        "words = list(set(w.lower() for w in wordlist.words()))\n",
        "df_words = pd.DataFrame({'word': words})\n",
        "df_words['len'] = df_words['word'].apply(lambda w: len(w))\n",
        "df_words['set'] = df_words['word'].apply(lambda w: set(w))\n",
        "\n",
        "\n",
        "def is_letter_in_word(word, letter):\n",
        "    return letter in word"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ocB5oZPEaBNX"
      },
      "source": [
        "# Basic Algorithm\n",
        "\n",
        "```\n",
        "0. Start with the what words have the n letters in them\n",
        "\n",
        "remaining_words = complete_dictionary\n",
        "while len(potential != 1):\n",
        "    most_common_letter = get_common_letter(remaining_words)\n",
        "    if most_common_letter in remaining_words:\n",
        "        remaining_words = {word for word in remaining_words if most_common_letter in word}\n",
        "    else:\n",
        "        do opposite\n",
        "DONE\n",
        "```"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Ydgb1kv26IFP"
      },
      "outputs": [],
      "source": [
        "class BlindGuesser:\n",
        "    def __init__(self, ans_word_len: int) -> None:\n",
        "        self.memory = set()\n",
        "        self.df_remain_ = df_words[df_words['len'] == ans_word_len]\n",
        "\n",
        "    def guess(self, hidden_word: HiddenWord):\n",
        "        if len(self.df_remain_) == 1:\n",
        "            return self.df_remain_.iloc[0]['word']\n",
        "        else:\n",
        "            counts = Counter()\n",
        "            self.df_remain_['set'].apply(lambda s: counts.update(s))\n",
        "            for letter in self.memory:\n",
        "                del counts[letter]\n",
        "            most_common_letter = counts.most_common(1)[0][0]\n",
        "            self.memory.add(most_common_letter)\n",
        "\n",
        "            time.sleep(1)\n",
        "\n",
        "            # Check if the letter is in the word\n",
        "            hidden_word.check_letter(most_common_letter)\n",
        "            response = most_common_letter in hidden_word.letters\n",
        "            selector = self.df_remain_['set'].apply(lambda s: most_common_letter in s)\n",
        "            self.df_remain_ = self.df_remain_[selector if response else ~selector]\n",
        "            print(f'-> Number of remaining words: {len(self.df_remain_):,}')\n",
        "            return None\n",
        "\n",
        "\n",
        "class HiddenWord:\n",
        "    def __init__(self, word: str) -> None:\n",
        "        assert word in df_words['word'].values, f'`{word}` is not a valid word'\n",
        "        self.word = word\n",
        "        self.letters = set(word)\n",
        "        self.past_inputs = set()\n",
        "\n",
        "    def __repr__(self) -> str:\n",
        "        return f'HiddenWord(\"{self.word}\")'\n",
        "\n",
        "    def __len__(self) -> int:\n",
        "        return len(self.word)\n",
        "\n",
        "    def check_letter(self, letter, should_print=True):\n",
        "        self.past_inputs.add(letter)\n",
        "        matches = self.letters.intersection(self.past_inputs)\n",
        "        if should_print:\n",
        "            print(' '.join([l if l in matches else '_' for l in self.word]))\n",
        "        return {f'{i}:{l}' for i, l in enumerate(self.word) if l in matches}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "i_zNYw9N7KMf",
        "outputId": "1aa51832-5d2a-49f0-b629-b26b97727211"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "HiddenWord(\"mitochondria\")\n",
            "_ i _ _ _ _ _ _ _ _ i _\n",
            "-> Number of remaining words: 15,474\n",
            "\n",
            "_ i _ _ _ _ _ _ _ _ i _\n",
            "-> Number of remaining words: 4,345\n",
            "\n",
            "_ i _ o _ _ o _ _ _ i _\n",
            "-> Number of remaining words: 3,472\n",
            "\n",
            "_ i _ o _ _ o _ _ _ i a\n",
            "-> Number of remaining words: 2,664\n",
            "\n",
            "_ i t o _ _ o _ _ _ i a\n",
            "-> Number of remaining words: 1,849\n",
            "\n",
            "_ i t o _ _ o n _ _ i a\n",
            "-> Number of remaining words: 1,153\n",
            "\n",
            "_ i t o c _ o n _ _ i a\n",
            "-> Number of remaining words: 592\n",
            "\n",
            "_ i t o c _ o n _ r i a\n",
            "-> Number of remaining words: 280\n",
            "\n",
            "_ i t o c _ o n _ r i a\n",
            "-> Number of remaining words: 179\n",
            "\n",
            "_ i t o c _ o n _ r i a\n",
            "-> Number of remaining words: 118\n",
            "\n",
            "_ i t o c h o n _ r i a\n",
            "-> Number of remaining words: 49\n",
            "\n",
            "_ i t o c h o n _ r i a\n",
            "-> Number of remaining words: 29\n",
            "\n",
            "m i t o c h o n _ r i a\n",
            "-> Number of remaining words: 14\n",
            "\n",
            "m i t o c h o n _ r i a\n",
            "-> Number of remaining words: 11\n",
            "\n",
            "m i t o c h o n d r i a\n",
            "-> Number of remaining words: 3\n",
            "\n",
            "m i t o c h o n d r i a\n",
            "-> Number of remaining words: 2\n",
            "\n"
          ]
        },
        {
          "ename": "IndexError",
          "evalue": "ignored",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-24-2b7471a52c83>\u001b[0m in \u001b[0;36m<cell line: 7>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0mans\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0mans\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m     \u001b[0mans\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgame\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mguess\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtarget_word\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      9\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m' '\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mans\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-23-791be61e543a>\u001b[0m in \u001b[0;36mguess\u001b[0;34m(self, hidden_word)\u001b[0m\n\u001b[1;32m     12\u001b[0m             \u001b[0;32mfor\u001b[0m \u001b[0mletter\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmemory\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m                 \u001b[0;32mdel\u001b[0m \u001b[0mcounts\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mletter\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m             \u001b[0mmost_common_letter\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcounts\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmost_common\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmemory\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmost_common_letter\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mIndexError\u001b[0m: list index out of range"
          ]
        }
      ],
      "source": [
        "target_word = HiddenWord('mitochondria')\n",
        "print(target_word)\n",
        "\n",
        "game = BlindGuesser(len(target_word))\n",
        "\n",
        "ans = None\n",
        "while ans is None:\n",
        "    ans = game.guess(target_word)\n",
        "    print()\n",
        "print(' '.join(ans))\n",
        "print(f'Your word is `{ans}`')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 112
        },
        "id": "8yKo4vkvgS5V",
        "outputId": "d366aa2f-ccdd-425a-a0b9-7d97a19f698d"
      },
      "outputs": [
        {
          "data": {
            "text/html": [
              "\n",
              "  <div id=\"df-cf9590a7-d283-4863-8d43-c8dfae4aba68\" class=\"colab-df-container\">\n",
              "    <div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>word</th>\n",
              "      <th>len</th>\n",
              "      <th>set</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>104235</th>\n",
              "      <td>mitochondria</td>\n",
              "      <td>12</td>\n",
              "      <td>{a, c, d, o, i, h, t, r, n, m}</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>125148</th>\n",
              "      <td>machairodont</td>\n",
              "      <td>12</td>\n",
              "      <td>{a, c, d, o, i, h, t, r, n, m}</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>\n",
              "    <div class=\"colab-df-buttons\">\n",
              "\n",
              "  <div class=\"colab-df-container\">\n",
              "    <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-cf9590a7-d283-4863-8d43-c8dfae4aba68')\"\n",
              "            title=\"Convert this dataframe to an interactive table.\"\n",
              "            style=\"display:none;\">\n",
              "\n",
              "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\" viewBox=\"0 -960 960 960\">\n",
              "    <path d=\"M120-120v-720h720v720H120Zm60-500h600v-160H180v160Zm220 220h160v-160H400v160Zm0 220h160v-160H400v160ZM180-400h160v-160H180v160Zm440 0h160v-160H620v160ZM180-180h160v-160H180v160Zm440 0h160v-160H620v160Z\"/>\n",
              "  </svg>\n",
              "    </button>\n",
              "\n",
              "  <style>\n",
              "    .colab-df-container {\n",
              "      display:flex;\n",
              "      gap: 12px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert {\n",
              "      background-color: #E8F0FE;\n",
              "      border: none;\n",
              "      border-radius: 50%;\n",
              "      cursor: pointer;\n",
              "      display: none;\n",
              "      fill: #1967D2;\n",
              "      height: 32px;\n",
              "      padding: 0 0 0 0;\n",
              "      width: 32px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert:hover {\n",
              "      background-color: #E2EBFA;\n",
              "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
              "      fill: #174EA6;\n",
              "    }\n",
              "\n",
              "    .colab-df-buttons div {\n",
              "      margin-bottom: 4px;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert {\n",
              "      background-color: #3B4455;\n",
              "      fill: #D2E3FC;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert:hover {\n",
              "      background-color: #434B5C;\n",
              "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
              "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
              "      fill: #FFFFFF;\n",
              "    }\n",
              "  </style>\n",
              "\n",
              "    <script>\n",
              "      const buttonEl =\n",
              "        document.querySelector('#df-cf9590a7-d283-4863-8d43-c8dfae4aba68 button.colab-df-convert');\n",
              "      buttonEl.style.display =\n",
              "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
              "\n",
              "      async function convertToInteractive(key) {\n",
              "        const element = document.querySelector('#df-cf9590a7-d283-4863-8d43-c8dfae4aba68');\n",
              "        const dataTable =\n",
              "          await google.colab.kernel.invokeFunction('convertToInteractive',\n",
              "                                                    [key], {});\n",
              "        if (!dataTable) return;\n",
              "\n",
              "        const docLinkHtml = 'Like what you see? Visit the ' +\n",
              "          '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
              "          + ' to learn more about interactive tables.';\n",
              "        element.innerHTML = '';\n",
              "        dataTable['output_type'] = 'display_data';\n",
              "        await google.colab.output.renderOutput(dataTable, element);\n",
              "        const docLink = document.createElement('div');\n",
              "        docLink.innerHTML = docLinkHtml;\n",
              "        element.appendChild(docLink);\n",
              "      }\n",
              "    </script>\n",
              "  </div>\n",
              "\n",
              "\n",
              "<div id=\"df-380d75d2-b8b9-40dc-b1fe-e641d43cda4a\">\n",
              "  <button class=\"colab-df-quickchart\" onclick=\"quickchart('df-380d75d2-b8b9-40dc-b1fe-e641d43cda4a')\"\n",
              "            title=\"Suggest charts.\"\n",
              "            style=\"display:none;\">\n",
              "\n",
              "<svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
              "     width=\"24px\">\n",
              "    <g>\n",
              "        <path d=\"M19 3H5c-1.1 0-2 .9-2 2v14c0 1.1.9 2 2 2h14c1.1 0 2-.9 2-2V5c0-1.1-.9-2-2-2zM9 17H7v-7h2v7zm4 0h-2V7h2v10zm4 0h-2v-4h2v4z\"/>\n",
              "    </g>\n",
              "</svg>\n",
              "  </button>\n",
              "\n",
              "<style>\n",
              "  .colab-df-quickchart {\n",
              "      --bg-color: #E8F0FE;\n",
              "      --fill-color: #1967D2;\n",
              "      --hover-bg-color: #E2EBFA;\n",
              "      --hover-fill-color: #174EA6;\n",
              "      --disabled-fill-color: #AAA;\n",
              "      --disabled-bg-color: #DDD;\n",
              "  }\n",
              "\n",
              "  [theme=dark] .colab-df-quickchart {\n",
              "      --bg-color: #3B4455;\n",
              "      --fill-color: #D2E3FC;\n",
              "      --hover-bg-color: #434B5C;\n",
              "      --hover-fill-color: #FFFFFF;\n",
              "      --disabled-bg-color: #3B4455;\n",
              "      --disabled-fill-color: #666;\n",
              "  }\n",
              "\n",
              "  .colab-df-quickchart {\n",
              "    background-color: var(--bg-color);\n",
              "    border: none;\n",
              "    border-radius: 50%;\n",
              "    cursor: pointer;\n",
              "    display: none;\n",
              "    fill: var(--fill-color);\n",
              "    height: 32px;\n",
              "    padding: 0;\n",
              "    width: 32px;\n",
              "  }\n",
              "\n",
              "  .colab-df-quickchart:hover {\n",
              "    background-color: var(--hover-bg-color);\n",
              "    box-shadow: 0 1px 2px rgba(60, 64, 67, 0.3), 0 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
              "    fill: var(--button-hover-fill-color);\n",
              "  }\n",
              "\n",
              "  .colab-df-quickchart-complete:disabled,\n",
              "  .colab-df-quickchart-complete:disabled:hover {\n",
              "    background-color: var(--disabled-bg-color);\n",
              "    fill: var(--disabled-fill-color);\n",
              "    box-shadow: none;\n",
              "  }\n",
              "\n",
              "  .colab-df-spinner {\n",
              "    border: 2px solid var(--fill-color);\n",
              "    border-color: transparent;\n",
              "    border-bottom-color: var(--fill-color);\n",
              "    animation:\n",
              "      spin 1s steps(1) infinite;\n",
              "  }\n",
              "\n",
              "  @keyframes spin {\n",
              "    0% {\n",
              "      border-color: transparent;\n",
              "      border-bottom-color: var(--fill-color);\n",
              "      border-left-color: var(--fill-color);\n",
              "    }\n",
              "    20% {\n",
              "      border-color: transparent;\n",
              "      border-left-color: var(--fill-color);\n",
              "      border-top-color: var(--fill-color);\n",
              "    }\n",
              "    30% {\n",
              "      border-color: transparent;\n",
              "      border-left-color: var(--fill-color);\n",
              "      border-top-color: var(--fill-color);\n",
              "      border-right-color: var(--fill-color);\n",
              "    }\n",
              "    40% {\n",
              "      border-color: transparent;\n",
              "      border-right-color: var(--fill-color);\n",
              "      border-top-color: var(--fill-color);\n",
              "    }\n",
              "    60% {\n",
              "      border-color: transparent;\n",
              "      border-right-color: var(--fill-color);\n",
              "    }\n",
              "    80% {\n",
              "      border-color: transparent;\n",
              "      border-right-color: var(--fill-color);\n",
              "      border-bottom-color: var(--fill-color);\n",
              "    }\n",
              "    90% {\n",
              "      border-color: transparent;\n",
              "      border-bottom-color: var(--fill-color);\n",
              "    }\n",
              "  }\n",
              "</style>\n",
              "\n",
              "  <script>\n",
              "    async function quickchart(key) {\n",
              "      const quickchartButtonEl =\n",
              "        document.querySelector('#' + key + ' button');\n",
              "      quickchartButtonEl.disabled = true;  // To prevent multiple clicks.\n",
              "      quickchartButtonEl.classList.add('colab-df-spinner');\n",
              "      try {\n",
              "        const charts = await google.colab.kernel.invokeFunction(\n",
              "            'suggestCharts', [key], {});\n",
              "      } catch (error) {\n",
              "        console.error('Error during call to suggestCharts:', error);\n",
              "      }\n",
              "      quickchartButtonEl.classList.remove('colab-df-spinner');\n",
              "      quickchartButtonEl.classList.add('colab-df-quickchart-complete');\n",
              "    }\n",
              "    (() => {\n",
              "      let quickchartButtonEl =\n",
              "        document.querySelector('#df-380d75d2-b8b9-40dc-b1fe-e641d43cda4a button');\n",
              "      quickchartButtonEl.style.display =\n",
              "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
              "    })();\n",
              "  </script>\n",
              "</div>\n",
              "    </div>\n",
              "  </div>\n"
            ],
            "text/plain": [
              "                word  len                             set\n",
              "104235  mitochondria   12  {a, c, d, o, i, h, t, r, n, m}\n",
              "125148  machairodont   12  {a, c, d, o, i, h, t, r, n, m}"
            ]
          },
          "execution_count": 25,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "game.df_remain_"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HbN6rqE7jaop"
      },
      "source": [
        "# Location Aware Strategy"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "oeGSbtStjMJE"
      },
      "outputs": [],
      "source": [
        "class LocationAwareGuesser:\n",
        "    def __init__(self, ans_word_len: int) -> None:\n",
        "        self.memory = None\n",
        "        self.past_guesses = set()\n",
        "        self.df_remain_ = df_words[df_words['len'] == ans_word_len]\n",
        "        self.df_remain_['encoded'] = self.df_remain_['word'].apply(lambda word: {f'{i}:{l}' for i, l in enumerate(word)})\n",
        "\n",
        "    def guess(self, hidden_word: HiddenWord):\n",
        "        if len(self.df_remain_) == 1:\n",
        "            return self.df_remain_.iloc[0]['word']\n",
        "        else:\n",
        "            # Guess the most common letter not currently guessed\n",
        "            counts = Counter()\n",
        "            self.df_remain_['set'].apply(lambda s: counts.update(s))\n",
        "            for letter in self.past_guesses:\n",
        "                del counts[letter]\n",
        "            most_common_letter = counts.most_common(1)[0][0]\n",
        "            self.past_guesses.add(most_common_letter)\n",
        "\n",
        "            time.sleep(1)\n",
        "\n",
        "            # Check if the letter is in the word\n",
        "            response = hidden_word.check_letter(most_common_letter)\n",
        "            selector = self.df_remain_['encoded'].apply(lambda s: response.issubset(s))\n",
        "            self.df_remain_ = self.df_remain_[selector]\n",
        "            print(f'-> Number of remaining words: {len(self.df_remain_):,}')\n",
        "            return None\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OF9h4sdlvs7x",
        "outputId": "7f18e5f8-c464-41cf-c915-b8d1ee1dfb30"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "HiddenWord(\"jazz\")\n"
          ]
        },
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "<ipython-input-4-879c30e191cd>:6: SettingWithCopyWarning: \n",
            "A value is trying to be set on a copy of a slice from a DataFrame.\n",
            "Try using .loc[row_indexer,col_indexer] = value instead\n",
            "\n",
            "See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy\n",
            "  self.df_remain_['encoded'] = self.df_remain_['word'].apply(lambda word: {f'{i}:{l}' for i, l in enumerate(word)})\n"
          ]
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "_ a _ _\n",
            "-> Number of remaining words: 961\n",
            "\n",
            "j a _ _\n",
            "-> Number of remaining words: 29\n",
            "\n",
            "j a z z\n",
            "-> Number of remaining words: 1\n",
            "\n",
            "\n",
            "j a z z\n",
            "Your word is `jazz`\n"
          ]
        }
      ],
      "source": [
        "target_word = HiddenWord('jazz')  # ('mitochondria')\n",
        "print(target_word)\n",
        "\n",
        "perfect_algo = LocationAwareGuesser(len(target_word))\n",
        "ans = None\n",
        "while ans is None:\n",
        "    ans = perfect_algo.guess(target_word)\n",
        "    print()\n",
        "print(' '.join(ans))\n",
        "print(f'Your word is `{ans}`')"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}