hangman_api_user.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trexquant Interview Project (The Hangman Game)\n",
    "\n",
    "* Copyright Trexquant Investment LP. All Rights Reserved. \n",
    "* Redistribution of this question without written consent from Trexquant is prohibited"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instruction:\n",
    "For this coding test, your mission is to write an algorithm that plays the game of Hangman through our API server. \n",
    "\n",
    "When a user plays Hangman, the server first selects a secret word at random from a list. The server then returns a row of underscores (space separated)—one for each letter in the secret word—and asks the user to guess a letter. If the user guesses a letter that is in the word, the word is redisplayed with all instances of that letter shown in the correct positions, along with any letters correctly guessed on previous turns. If the letter does not appear in the word, the user is charged with an incorrect guess. The user keeps guessing letters until either (1) the user has correctly guessed all the letters in the word\n",
    "or (2) the user has made six incorrect guesses.\n",
    "\n",
    "You are required to write a \"guess\" function that takes current word (with underscores) as input and returns a guess letter. You will use the API codes below to play 1,000 Hangman games. You have the opportunity to practice before you want to start recording your game results.\n",
    "\n",
    "Your algorithm is permitted to use a training set of approximately 250,000 dictionary words. Your algorithm will be tested on an entirely disjoint set of 250,000 dictionary words. Please note that this means the words that you will ultimately be tested on do NOT appear in the dictionary that you are given. You are not permitted to use any dictionary other than the training dictionary we provided. This requirement will be strictly enforced by code review.\n",
    "\n",
    "You are provided with a basic, working algorithm. This algorithm will match the provided masked string (e.g. a _ _ l e) to all possible words in the dictionary, tabulate the frequency of letters appearing in these possible words, and then guess the letter with the highest frequency of appearence that has not already been guessed. If there are no remaining words that match then it will default back to the character frequency distribution of the entire dictionary.\n",
    "\n",
    "This benchmark strategy is successful approximately 18% of the time. Your task is to design an algorithm that significantly outperforms this benchmark."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    },
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import json\n",
    "import requests\n",
    "import random\n",
    "import string\n",
    "import secrets\n",
    "import time\n",
    "import re\n",
    "import collections\n",
    "\n",
    "try:\n",
    "    from urllib.parse import parse_qs, urlencode, urlparse\n",
    "except ImportError:\n",
    "    from urlparse import parse_qs, urlparse\n",
    "    from urllib import urlencode\n",
    "\n",
    "from requests.packages.urllib3.exceptions import InsecureRequestWarning\n",
    "\n",
    "requests.packages.urllib3.disable_warnings(InsecureRequestWarning)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GuessWord():\n",
    "    def __init__(self):\n",
    "        self.correctWord = \"H a n g m a n \"\n",
    "        self.guessWord= \"H _ n _ m _ n \"\n",
    "        self.wrongTries = 0\n",
    "    \n",
    "    def checkGuess(self, letter : string):\n",
    "        if letter in self.guessWord:  return \"Word Already There\"\n",
    "        if letter in self.correctWord :\n",
    "            self.guessWord = \"\".join([(letter if (self.correctWord[i] == letter) else self.guessWord[i]) for i in range(len(self.correctWord))])\n",
    "            # for i in range(len(self.correctWord)):\n",
    "            #     if self.correctWord[i] == letter:\n",
    "            #         self.guessWord[i] = letter\n",
    "            return self.guessWord\n",
    "        \n",
    "        self.wrongTries += 1\n",
    "        return \"Wrong Guess\" \n",
    "    \n",
    "    def currentStatus(self):\n",
    "        return [self.guessWord, self.wrongTries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "class HangmanAPI(object):\n",
    "    def __init__(self, access_token=None, session=None, timeout=None):\n",
    "        self.guessed_letters = []\n",
    "        self.incorrect_guesses = []\n",
    "        \n",
    "        \n",
    "        full_dictionary_location = \"words_250000_train.txt\"\n",
    "        self.full_dictionary = self.build_dictionary(full_dictionary_location)        \n",
    "        self.full_dictionary_common_letter_sorted = collections.Counter(\"\".join(self.full_dictionary)).most_common()\n",
    "        self.letter_set = sorted(set(\"\".join(self.full_dictionary)))\n",
    "        self.current_dictionary = []\n",
    "        self.probabilities = [0] * len(self.letter_set)\n",
    "        self.unigram, self.bigram, self.trigram, self.fourgram, self.fivegram = self.build_n_grams(self.full_dictionary)\n",
    "        \n",
    "        self.tries_remaining = 6\n",
    "        \n",
    "        self.current_dictionary = []\n",
    "\n",
    "    def guess(self, word): # word input example: \"_ p p _ e \"\n",
    "        '''\n",
    "        Given a word with either correctly gussed letters or blanks, this function\n",
    "        returns the best guess for the next letter based on the n-grams\n",
    "        '''\n",
    "        \n",
    "        # keep track of incorrect guesses to update the n-grams\n",
    "        self.incorrect_guesses = list(set(self.guessed_letters) - set(word))\n",
    "        \n",
    "        # only recalibrate if last guess was incorrect and running low on guesses\n",
    "        if len(self.guessed_letters) > 0 and self.guessed_letters[-1] in self.incorrect_guesses and self.tries_remaining <= 3:\n",
    "            self.recalibrate_n_grams()\n",
    "        \n",
    "        # clear out probabilities from last guess\n",
    "        self.probabilities = [0] * len(self.letter_set)\n",
    "\n",
    "        # clean the word so that we strip away the space characters\n",
    "        # replace \"_\" with \".\" as \".\" indicates any character in regular expressions\n",
    "        clean_word = word[::2]\n",
    "        \n",
    "        # run through n-gram function\n",
    "        return self.fivegram_probs(clean_word)\n",
    "    \n",
    "    def build_n_grams(self, dictionary):\n",
    "        '''\n",
    "        build nested dictionary containing occurences for n (1-5) sequences of letters\n",
    "        unigrams and bigrams have an extra level for length of the word\n",
    "        for unigram, take only unique letters within each word  \n",
    "        '''\n",
    "        unigram = collections.defaultdict(lambda: collections.defaultdict(int))\n",
    "        bi_gram = collections.defaultdict(lambda: collections.defaultdict(lambda: collections.defaultdict(int)))\n",
    "        tri_gram = collections.defaultdict(lambda: collections.defaultdict(lambda: collections.defaultdict(int)))\n",
    "        four_gram = collections.defaultdict(lambda:collections.defaultdict(lambda: collections.defaultdict(lambda: collections.defaultdict(int))))\n",
    "        five_gram = collections.defaultdict(lambda: collections.defaultdict(lambda:collections.defaultdict(lambda: collections.defaultdict(lambda: collections.defaultdict(int)))))\n",
    "        \n",
    "        # go through each word in the dictionary\n",
    "        for word in dictionary:\n",
    "            # check each letter in the dictionary and update the n-gram\n",
    "            for i in range(len(word) - 4):\n",
    "                bi_gram[len(word)][word[i]][word[i+1]] += 1\n",
    "                tri_gram[word[i]][word[i+1]][word[i+2]] += 1\n",
    "                four_gram[word[i]][word[i+1]][word[i+2]][word[i+3]] += 1\n",
    "                five_gram[word[i]][word[i+1]][word[i+2]][word[i+3]][word[i+4]] += 1\n",
    "            i = len(word) - 4\n",
    "            \n",
    "            # fill out the rest of the n-grams for words too short\n",
    "            if len(word) == 2:\n",
    "                bi_gram[len(word)][word[0]][word[1]] += 1\n",
    "            elif len(word) == 3:\n",
    "                bi_gram[len(word)][word[0]][word[1]] += 1\n",
    "                bi_gram[len(word)][word[1]][word[2]] += 1\n",
    "                tri_gram[word[0]][word[1]][word[2]] += 1\n",
    "                \n",
    "            # fill out rest of the (1-4)-grams\n",
    "            elif len(word) >= 4:\n",
    "                bi_gram[len(word)][word[i]][word[i+1]] += 1\n",
    "                bi_gram[len(word)][word[i+1]][word[i+2]] += 1\n",
    "                bi_gram[len(word)][word[i+2]][word[i+3]] += 1\n",
    "                tri_gram[word[i]][word[i+1]][word[i+2]] += 1\n",
    "                tri_gram[word[i+1]][word[i+2]][word[i+3]] += 1\n",
    "                four_gram[word[i]][word[i+1]][word[i+2]][word[i+3]] += 1\n",
    "            \n",
    "            # fill out unigrams\n",
    "            for letter in set(word):\n",
    "                unigram[len(word)][letter] += 1\n",
    "                    \n",
    "        return unigram, bi_gram, tri_gram, four_gram, five_gram\n",
    "\n",
    "    def recalibrate_n_grams(self):\n",
    "        '''\n",
    "        re-tabulates the n-grams after eliminating any incorrectly guessed letters\n",
    "        updates the dictionary to remove words containing incorrectly guessed letters\n",
    "        '''\n",
    "        # updates the dictionary to remove words containing incorrectly guessed letters\n",
    "        new_dict = [word for word in self.full_dictionary if not set(word).intersection(set(self.incorrect_guesses))]\n",
    "        self.unigram, self.bigram, self.trigram, self.fourgram, self.fivegram = self.build_n_grams(new_dict)\n",
    "\n",
    "    def fivegram_probs(self, word):\n",
    "        ''' \n",
    "        Input: the word in the \"clean\" format with no spaces and a '_' if letter has not been guessed\n",
    "        Flow: uses tri-gram to calculate the probability of a certain letter appearing in a five-letter sequence for a word of given length\n",
    "        Output: probabilities for each letter to be used in next level\n",
    "        '''\n",
    "                \n",
    "        # vector of probabilities for each letter\n",
    "        probs = [0] * len(self.letter_set)\n",
    "        \n",
    "        total_count = 0\n",
    "        letter_count = [0] * len(self.letter_set)\n",
    "\n",
    "        # traverse the word and find patterns that have three consecutive letters where one of them is blank\n",
    "        for i in range(len(word) - 4):\n",
    "                        \n",
    "            # case 1: \"letter letter letter letter blank\"\n",
    "            if word[i] != '_' and word[i+1] != '_' and word[i+2] != '_' and word[i+3] != '_' and word[i+4] == '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+1]\n",
    "                anchor_letter_3 = word[i+2]\n",
    "                anchor_letter_4 = word[i+3]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter_1 anchor_letter_2 blank\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fivegram[anchor_letter_1][anchor_letter_2][anchor_letter_3][anchor_letter_4][letter] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fivegram[anchor_letter_1][anchor_letter_2][anchor_letter_3][anchor_letter_4][letter]\n",
    "                        letter_count[j] += self.fivegram[anchor_letter_1][anchor_letter_2][anchor_letter_3][anchor_letter_4][letter]\n",
    "        \n",
    "            # case 2: \"letter letter letter blank letter\"\n",
    "            elif word[i] != '_' and word[i+1] != '_' and word[i+2] != '_' and word[i+3] == '_' and word[i+4] != '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+1]\n",
    "                anchor_letter_3 = word[i+2]\n",
    "                anchor_letter_4 = word[i+4]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter_1 blank anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fivegram[anchor_letter_1][anchor_letter_2][anchor_letter_3][letter][anchor_letter_4] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fivegram[anchor_letter_1][anchor_letter_2][anchor_letter_3][letter][anchor_letter_4]\n",
    "                        letter_count[j] += self.fivegram[anchor_letter_1][anchor_letter_2][anchor_letter_3][letter][anchor_letter_4]\n",
    "               \n",
    "            # case 3: letter letter blank letter letter\n",
    "            elif word[i] != '_' and word[i+1] != '_' and word[i+2] == '_' and word[i+3] != '_' and word[i+4] != '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+1]\n",
    "                anchor_letter_3 = word[i+3]\n",
    "                anchor_letter_4 = word[i+4]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter_1 anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fivegram[anchor_letter_1][anchor_letter_2][letter][anchor_letter_3][anchor_letter_4] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fivegram[anchor_letter_1][anchor_letter_2][letter][anchor_letter_3][anchor_letter_4]\n",
    "                        letter_count[j] += self.fivegram[anchor_letter_1][anchor_letter_2][letter][anchor_letter_3][anchor_letter_4]\n",
    "               \n",
    "            # case 4: letter blank letter letter letter\n",
    "            elif word[i] != '_' and word[i+1] == '_' and word[i+2] != '_' and word[i+3] != '_' and word[i+4] != '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+2]\n",
    "                anchor_letter_3 = word[i+3]\n",
    "                anchor_letter_4 = word[i+4]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter_1 anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fivegram[anchor_letter_1][letter][anchor_letter_2][anchor_letter_3][anchor_letter_4] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fivegram[anchor_letter_1][letter][anchor_letter_2][anchor_letter_3][anchor_letter_4]\n",
    "                        letter_count[j] += self.fivegram[anchor_letter_1][letter][anchor_letter_2][anchor_letter_3][anchor_letter_4]\n",
    "        \n",
    "            # case 5: blank letter letter letter letter\n",
    "            elif word[i] == '_' and word[i+1] != '_' and word[i+2] != '_' and word[i+3] != '_' and word[i+4] != '_':\n",
    "                anchor_letter_1 = word[i+1]\n",
    "                anchor_letter_2 = word[i+2]\n",
    "                anchor_letter_3 = word[i+3]\n",
    "                anchor_letter_4 = word[i+4]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter_1 anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fivegram[letter][anchor_letter_1][anchor_letter_2][anchor_letter_3][anchor_letter_4] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fivegram[letter][anchor_letter_1][anchor_letter_2][anchor_letter_3][anchor_letter_4]\n",
    "                        letter_count[j] += self.fivegram[letter][anchor_letter_1][anchor_letter_2][anchor_letter_3][anchor_letter_4]\n",
    "        \n",
    "        # calculate the probabilities of each letter appearing\n",
    "        if total_count > 0:\n",
    "            for i in range(len(self.letter_set)):\n",
    "                probs[i] = letter_count[i] / total_count\n",
    "        \n",
    "        # interpolate probabilities between trigram and bigram\n",
    "        for i, p in enumerate(self.probabilities):\n",
    "            self.probabilities[i] = p + probs[i] * (0.40)\n",
    "        \n",
    "        # run the next level down\n",
    "        return self.fourgram_probs(word)\n",
    "\n",
    "    def fourgram_probs(self, word):\n",
    "        ''' \n",
    "        Input: the word in the \"clean\" format with no spaces and a '_' if letter has not been guessed\n",
    "        Flow: uses tri-gram to calculate the probability of a certain letter appearing in a four-letter sequence for a word of given length\n",
    "        Output: probabilities for each letter to be used in next level\n",
    "        '''\n",
    "                \n",
    "        # vector of probabilities for each letter\n",
    "        probs = [0] * len(self.letter_set)\n",
    "        \n",
    "        total_count = 0\n",
    "        letter_count = [0] * len(self.letter_set)\n",
    "\n",
    "        # traverse the word and find patterns that have three consecutive letters where one of them is blank\n",
    "        for i in range(len(word) - 3):\n",
    "                        \n",
    "            # case 1: \"letter letter letter blank\"\n",
    "            if word[i] != '_' and word[i+1] != '_' and word[i+2] != '_' and word[i+3] == '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+1]\n",
    "                anchor_letter_3 = word[i+2]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter_1 anchor_letter_2 blank\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fourgram[anchor_letter_1][anchor_letter_2][anchor_letter_3][letter] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fourgram[anchor_letter_1][anchor_letter_2][anchor_letter_3][letter]\n",
    "                        letter_count[j] += self.fourgram[anchor_letter_1][anchor_letter_2][anchor_letter_3][letter]\n",
    "        \n",
    "            # case 2: \"letter letter blank letter\"\n",
    "            elif word[i] != '_' and word[i+1] != '_' and word[i+2] == '_' and word[i+3] != '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+1]\n",
    "                anchor_letter_3 = word[i+3]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter_1 blank anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fourgram[anchor_letter_1][anchor_letter_2][letter][anchor_letter_3] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fourgram[anchor_letter_1][anchor_letter_2][letter][anchor_letter_3]\n",
    "                        letter_count[j] += self.fourgram[anchor_letter_1][anchor_letter_2][letter][anchor_letter_3]\n",
    "               \n",
    "            # case 3: letter blank letter letter\n",
    "            elif word[i] != '_' and word[i+1] == '_' and word[i+2] != '_' and word[i+3] != '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+2]\n",
    "                anchor_letter_3 = word[i+3]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter_1 anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fourgram[anchor_letter_1][letter][anchor_letter_2][anchor_letter_3] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fourgram[anchor_letter_1][letter][anchor_letter_2][anchor_letter_3]\n",
    "                        letter_count[j] += self.fourgram[anchor_letter_1][letter][anchor_letter_2][anchor_letter_3]\n",
    "               \n",
    "            # case 4: blank letter letter letter\n",
    "            elif word[i] == '_' and word[i+1] != '_' and word[i+2] != '_' and word[i+3] != '_':\n",
    "                anchor_letter_1 = word[i+1]\n",
    "                anchor_letter_2 = word[i+2]\n",
    "                anchor_letter_3 = word[i+3]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter_1 anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.fourgram[letter][anchor_letter_1][anchor_letter_2][anchor_letter_3] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.fourgram[letter][anchor_letter_1][anchor_letter_2][anchor_letter_3]\n",
    "                        letter_count[j] += self.fourgram[letter][anchor_letter_1][anchor_letter_2][anchor_letter_3]\n",
    "        \n",
    "        # calculate the probabilities of each letter appearing\n",
    "        if total_count > 0:\n",
    "            for i in range(len(self.letter_set)):\n",
    "                probs[i] = letter_count[i] / total_count\n",
    "        \n",
    "        # interpolate probabilities between trigram and bigram\n",
    "        for i, p in enumerate(self.probabilities):\n",
    "            self.probabilities[i] = p + probs[i] * (0.25)\n",
    "        \n",
    "        # run the next level down\n",
    "        return self.trigram_probs(word)\n",
    "\n",
    "    def trigram_probs(self, word):\n",
    "        ''' \n",
    "        Input: the word in the \"clean\" format with no spaces and a '_' if letter has not been guessed\n",
    "        Flow: uses tri-gram to calculate the probability of a certain letter appearing in a three-letter sequence for a word of given length\n",
    "        Output: probabilities for each letter to be used in next level\n",
    "        '''\n",
    "                \n",
    "        # vector of probabilities for each letter\n",
    "        probs = [0] * len(self.letter_set)\n",
    "        \n",
    "        total_count = 0\n",
    "        letter_count = [0] * len(self.letter_set)\n",
    "\n",
    "        # traverse the word and find patterns that have three consecutive letters where one of them is blank\n",
    "        for i in range(len(word) - 2):\n",
    "                        \n",
    "            # case 1: \"letter letter blank\"\n",
    "            if word[i] != '_' and word[i+1] != '_' and word[i+2] == '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+1]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter_1 anchor_letter_2 blank\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.trigram[anchor_letter_1][anchor_letter_2][letter] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.trigram[anchor_letter_1][anchor_letter_2][letter]\n",
    "                        letter_count[j] += self.trigram[anchor_letter_1][anchor_letter_2][letter]\n",
    "        \n",
    "            # case 2: \"letter blank letter\"\n",
    "            elif word[i] != '_' and word[i+1] == '_' and word[i+2] != '_':\n",
    "                anchor_letter_1 = word[i]\n",
    "                anchor_letter_2 = word[i+2]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter_1 blank anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.trigram[anchor_letter_1][letter][anchor_letter_2] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.trigram[anchor_letter_1][letter][anchor_letter_2]\n",
    "                        letter_count[j] += self.trigram[anchor_letter_1][letter][anchor_letter_2]\n",
    "               \n",
    "            # case 3: blank letter letter\n",
    "            elif word[i] == '_' and word[i+1] != '_' and word[i+2] != '_':\n",
    "                anchor_letter_1 = word[i+1]\n",
    "                anchor_letter_2 = word[i+2]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter_1 anchor_letter_2\" and for each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.trigram[letter][anchor_letter_1][anchor_letter_2] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.trigram[letter][anchor_letter_1][anchor_letter_2]\n",
    "                        letter_count[j] += self.trigram[letter][anchor_letter_1][anchor_letter_2]\n",
    "        \n",
    "        # calculate the probabilities of each letter appearing\n",
    "        if total_count > 0:\n",
    "            for i in range(len(self.letter_set)):\n",
    "                probs[i] = letter_count[i] / total_count\n",
    "        \n",
    "        # interpolate probabilities between trigram and bigram\n",
    "        for i, p in enumerate(self.probabilities):\n",
    "            self.probabilities[i] = p + probs[i] * (0.20)\n",
    "        \n",
    "        # run the next level down\n",
    "        return self.bigram_probs(word)\n",
    "    \n",
    "    def bigram_probs(self, word):\n",
    "        ''' \n",
    "        Input: the word in the \"clean\" format with no spaces and a '_' if letter has not been guessed\n",
    "        Flow: uses bi-gram to calculate the probability of a certain letter appearing in a two-letter sequence for a word of given length\n",
    "              updates the probabilities set in trigram_probs\n",
    "        Output: probabilities for each letter to be used in next level\n",
    "        '''\n",
    "        \n",
    "        # vector of probabilities for each letter\n",
    "        probs = [0] * len(self.letter_set)\n",
    "        \n",
    "        total_count = 0\n",
    "        letter_count = [0] * len(self.letter_set)\n",
    "        \n",
    "        # traverse the word and find either patterns of \"letter blank\" or \"blank letter\"\n",
    "        for i in range(len(word) - 1):\n",
    "            # case 1: \"letter blank\"\n",
    "            if word[i] != '_' and word[i+1] == '_':\n",
    "                anchor_letter = word[i]\n",
    "                \n",
    "                # calculate occurences of \"anchor_letter blank\" and each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.bigram[len(word)][anchor_letter][letter] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.bigram[len(word)][anchor_letter][letter]\n",
    "                        letter_count[j] += self.bigram[len(word)][anchor_letter][letter]\n",
    "                            \n",
    "            # case 2: \"blank letter\"\n",
    "            elif word[i] == '_' and word[i+1]!= '_':\n",
    "                anchor_letter = word[i+1]\n",
    "                \n",
    "                # calculate occurences of \"blank anchor_letter\" and each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.bigram[len(word)][letter][anchor_letter] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.bigram[len(word)][letter][anchor_letter]\n",
    "                        letter_count[j] += self.bigram[len(word)][letter][anchor_letter]\n",
    "                                                                    \n",
    "        # calculate the probabilities of each letter appearing\n",
    "        if total_count > 0:\n",
    "            for i in range(len(self.letter_set)):\n",
    "                probs[i] = letter_count[i] / total_count\n",
    "\n",
    "        # interpolate probabilities between trigram and bigram\n",
    "        for i, p in enumerate(self.probabilities):\n",
    "            self.probabilities[i] = p + probs[i] * (0.10)\n",
    "        \n",
    "        # return letter associated with highest probability\n",
    "        return self.unigram_probs(word)\n",
    "    \n",
    "    def unigram_probs(self, word):\n",
    "        ''' \n",
    "        Input: the word in the \"clean\" format with no spaces and a '_' if letter has not been guessed\n",
    "        Flow: uses unigram to calculate the probability of a certain letter appearing in a any blank space\n",
    "              updates the probabilities set in bigram_probs\n",
    "        Output: letter with the overall highest probability\n",
    "        '''\n",
    "                \n",
    "        # vector of probabilities for each letter\n",
    "        probs = [0] * len(self.letter_set)\n",
    "        \n",
    "        total_count = 0\n",
    "        letter_count = [0] * len(self.letter_set)\n",
    "        \n",
    "        # traverse the word and find blank spaces\n",
    "        for i in range(len(word)):\n",
    "            # case 1: \"letter blank\"\n",
    "            if word[i] == '_':\n",
    "                                \n",
    "                # calculate occurences of pattern and each letter not guessed yet\n",
    "                for j, letter in enumerate(self.letter_set):\n",
    "                    if self.unigram[len(word)][letter] > 0 and letter not in self.guessed_letters:\n",
    "                        total_count += self.unigram[len(word)][letter]\n",
    "                        letter_count[j] += self.unigram[len(word)][letter]\n",
    "                       \n",
    "        # calculate the probabilities of each letter appearing\n",
    "        if total_count > 0:\n",
    "            for i in range(len(self.letter_set)):\n",
    "                probs[i] = letter_count[i] / total_count\n",
    "                \n",
    "        # interpolate probabilities\n",
    "        for i, p in enumerate(self.probabilities):\n",
    "            self.probabilities[i] = p + probs[i] * (0.05)\n",
    "        \n",
    "        # adjust probabilities so they sum to one (not necessary but looks better)\n",
    "        final_probs = [0] * len(self.letter_set)\n",
    "        if sum(self.probabilities) > 0:\n",
    "            for i in range(len(self.probabilities)):\n",
    "                final_probs[i] = self.probabilities[i] / sum(self.probabilities)\n",
    "            \n",
    "        self.probabilities = final_probs\n",
    "        \n",
    "        # find letter with largest probability\n",
    "        max_prob = 0\n",
    "        guess_letter = ''\n",
    "        for i, letter in enumerate(self.letter_set):\n",
    "            if self.probabilities[i] > max_prob:\n",
    "                max_prob = self.probabilities[i]\n",
    "                guess_letter = letter\n",
    "        \n",
    "        # if no letter chosen from above, pick a random one (extra weight on vowels)\n",
    "        if guess_letter == '':\n",
    "            letters = self.letter_set.copy()\n",
    "            random.shuffle(letters)\n",
    "            letters_shuffled = ['e','a','i','o','u'] + letters\n",
    "            for letter in letters_shuffled:\n",
    "                if letter not in self.guessed_letters:\n",
    "                    return letter\n",
    "            \n",
    "        return guess_letter\n",
    "\n",
    "    def build_dictionary(self, dictionary_file_location):\n",
    "        text_file = open(dictionary_file_location,\"r\")\n",
    "        full_dictionary = text_file.read().splitlines()\n",
    "        text_file.close()\n",
    "        return full_dictionary\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# API Usage Examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## To start a new game:\n",
    "1. Make sure you have implemented your own \"guess\" method.\n",
    "2. Use the access_token that we sent you to create your HangmanAPI object. \n",
    "3. Start a game by calling \"start_game\" method.\n",
    "4. If you wish to test your function without being recorded, set \"practice\" parameter to 1.\n",
    "5. Note: You have a rate limit of 20 new games per minute. DO NOT start more than 20 new games within one minute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H a n _ m a n \n",
      "Wrong Guess\n",
      "wronglly geuessed : o\n",
      "Wrong Guess\n",
      "wronglly geuessed : i\n",
      "Wrong Guess\n",
      "wronglly geuessed : e\n",
      "Wrong Guess\n",
      "wronglly geuessed : d\n",
      "Wrong Guess\n",
      "wronglly geuessed : u\n",
      "Wrong Guess\n",
      "wronglly geuessed : k\n",
      "H a n g m a n \n"
     ]
    }
   ],
   "source": [
    "api = HangmanAPI()\n",
    "wordBox = GuessWord()\n",
    "while((api.tries_remaining > -50) and (\"_\" in wordBox.guessWord)):\n",
    "    guess = api.guess(wordBox.guessWord)\n",
    "    api.guessed_letters.append(guess)\n",
    "\n",
    "    response = wordBox.checkGuess(guess)\n",
    "    print(response)\n",
    "    if response == \"Wrong Guess\":\n",
    "        api.tries_remaining -= 1\n",
    "        print(f\"wronglly geuessed : {guess}\")\n",
    "        api.incorrect_guesses.append(guess)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Playing practice games:\n",
    "You can use the command below to play up to 100,000 practice games."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    },
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'HangmanAPI' object has no attribute 'access_token'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32mc:\\Users\\Arush Bansal\\OneDrive - IIT Delhi\\Desktop\\hangman ai automation\\hangman_api_user.ipynb Cell 9\u001b[0m in \u001b[0;36m<cell line: 1>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=0'>1</a>\u001b[0m api\u001b[39m.\u001b[39;49mstart_game(practice\u001b[39m=\u001b[39;49m\u001b[39m1\u001b[39;49m,verbose\u001b[39m=\u001b[39;49m\u001b[39mTrue\u001b[39;49;00m)\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=1'>2</a>\u001b[0m [total_practice_runs,total_recorded_runs,total_recorded_successes,total_practice_successes] \u001b[39m=\u001b[39m api\u001b[39m.\u001b[39mmy_status() \u001b[39m# Get my game stats: (# of tries, # of wins)\u001b[39;00m\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=2'>3</a>\u001b[0m practice_success_rate \u001b[39m=\u001b[39m total_practice_successes \u001b[39m/\u001b[39m total_practice_runs\n",
      "\u001b[1;32mc:\\Users\\Arush Bansal\\OneDrive - IIT Delhi\\Desktop\\hangman ai automation\\hangman_api_user.ipynb Cell 9\u001b[0m in \u001b[0;36mHangmanAPI.start_game\u001b[1;34m(self, practice, verbose)\u001b[0m\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=476'>477</a>\u001b[0m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mguessed_letters \u001b[39m=\u001b[39m []\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=477'>478</a>\u001b[0m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mcurrent_dictionary \u001b[39m=\u001b[39m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mfull_dictionary  \n\u001b[1;32m--> <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=479'>480</a>\u001b[0m response \u001b[39m=\u001b[39m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mrequest(\u001b[39m\"\u001b[39;49m\u001b[39m/new_game\u001b[39;49m\u001b[39m\"\u001b[39;49m, {\u001b[39m\"\u001b[39;49m\u001b[39mpractice\u001b[39;49m\u001b[39m\"\u001b[39;49m:practice})\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=480'>481</a>\u001b[0m \u001b[39mif\u001b[39;00m response\u001b[39m.\u001b[39mget(\u001b[39m'\u001b[39m\u001b[39mstatus\u001b[39m\u001b[39m'\u001b[39m)\u001b[39m==\u001b[39m\u001b[39m\"\u001b[39m\u001b[39mapproved\u001b[39m\u001b[39m\"\u001b[39m:\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=481'>482</a>\u001b[0m     game_id \u001b[39m=\u001b[39m response\u001b[39m.\u001b[39mget(\u001b[39m'\u001b[39m\u001b[39mgame_id\u001b[39m\u001b[39m'\u001b[39m)\n",
      "\u001b[1;32mc:\\Users\\Arush Bansal\\OneDrive - IIT Delhi\\Desktop\\hangman ai automation\\hangman_api_user.ipynb Cell 9\u001b[0m in \u001b[0;36mHangmanAPI.request\u001b[1;34m(self, path, args, post_args, method)\u001b[0m\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=532'>533</a>\u001b[0m     method \u001b[39m=\u001b[39m \u001b[39m\"\u001b[39m\u001b[39mPOST\u001b[39m\u001b[39m\"\u001b[39m\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=534'>535</a>\u001b[0m \u001b[39m# Add `access_token` to post_args or args if it has not already been\u001b[39;00m\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=535'>536</a>\u001b[0m \u001b[39m# included.\u001b[39;00m\n\u001b[1;32m--> <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=536'>537</a>\u001b[0m \u001b[39mif\u001b[39;00m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49maccess_token:\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=537'>538</a>\u001b[0m     \u001b[39m# If post_args exists, we assume that args either does not exists\u001b[39;00m\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=538'>539</a>\u001b[0m     \u001b[39m# or it does not need `access_token`.\u001b[39;00m\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=539'>540</a>\u001b[0m     \u001b[39mif\u001b[39;00m post_args \u001b[39mand\u001b[39;00m \u001b[39m\"\u001b[39m\u001b[39maccess_token\u001b[39m\u001b[39m\"\u001b[39m \u001b[39mnot\u001b[39;00m \u001b[39min\u001b[39;00m post_args:\n\u001b[0;32m    <a href='vscode-notebook-cell:/c%3A/Users/Arush%20Bansal/OneDrive%20-%20IIT%20Delhi/Desktop/hangman%20ai%20automation/hangman_api_user.ipynb#X11sZmlsZQ%3D%3D?line=540'>541</a>\u001b[0m         post_args[\u001b[39m\"\u001b[39m\u001b[39maccess_token\u001b[39m\u001b[39m\"\u001b[39m] \u001b[39m=\u001b[39m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39maccess_token\n",
      "\u001b[1;31mAttributeError\u001b[0m: 'HangmanAPI' object has no attribute 'access_token'"
     ]
    }
   ],
   "source": [
    "api.start_game(practice=1,verbose=True)\n",
    "[total_practice_runs,total_recorded_runs,total_recorded_successes,total_practice_successes] = api.my_status() # Get my game stats: (# of tries, # of wins)\n",
    "practice_success_rate = total_practice_successes / total_practice_runs\n",
    "print('run %d practice games out of an allotted 100,000. practice success rate so far = %.3f' % (total_practice_runs, practice_success_rate))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Playing recorded games:\n",
    "Please finalize your code prior to running the cell below. Once this code executes once successfully your submission will be finalized. Our system will not allow you to rerun any additional games.\n",
    "\n",
    "Please note that it is expected that after you successfully run this block of code that subsequent runs will result in the error message \"Your account has been deactivated\".\n",
    "\n",
    "Once you've run this section of the code your submission is complete. Please send us your source code via email."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Playing  0  th game\n",
      "False\n",
      "Playing  1  th game\n",
      "True\n",
      "Playing  2  th game\n",
      "True\n",
      "Playing  3  th game\n",
      "False\n",
      "Playing  4  th game\n",
      "False\n",
      "Playing  5  th game\n",
      "False\n",
      "Playing  6  th game\n",
      "True\n",
      "Playing  7  th game\n",
      "True\n",
      "Playing  8  th game\n",
      "False\n",
      "Playing  9  th game\n",
      "True\n",
      "Playing  10  th game\n",
      "True\n",
      "Playing  11  th game\n",
      "True\n",
      "Playing  12  th game\n",
      "True\n",
      "Playing  13  th game\n",
      "True\n",
      "Playing  14  th game\n",
      "True\n",
      "Playing  15  th game\n",
      "False\n",
      "Playing  16  th game\n",
      "False\n",
      "Playing  17  th game\n",
      "False\n",
      "Playing  18  th game\n",
      "False\n",
      "Playing  19  th game\n",
      "False\n",
      "Playing  20  th game\n",
      "True\n",
      "Playing  21  th game\n",
      "True\n",
      "Playing  22  th game\n",
      "True\n",
      "Playing  23  th game\n",
      "False\n",
      "Playing  24  th game\n",
      "False\n",
      "Playing  25  th game\n",
      "False\n",
      "Playing  26  th game\n",
      "True\n",
      "Playing  27  th game\n",
      "True\n",
      "Playing  28  th game\n",
      "True\n",
      "Playing  29  th game\n",
      "False\n",
      "Playing  30  th game\n",
      "False\n",
      "Playing  31  th game\n",
      "False\n",
      "Playing  32  th game\n",
      "True\n",
      "Playing  33  th game\n",
      "True\n",
      "Playing  34  th game\n",
      "False\n",
      "Playing  35  th game\n",
      "True\n",
      "Playing  36  th game\n",
      "False\n",
      "Playing  37  th game\n",
      "False\n",
      "Playing  38  th game\n",
      "False\n",
      "Playing  39  th game\n",
      "False\n",
      "Playing  40  th game\n",
      "False\n",
      "Playing  41  th game\n",
      "False\n",
      "Playing  42  th game\n",
      "True\n",
      "Playing  43  th game\n",
      "False\n",
      "Playing  44  th game\n"
     ]
    }
   ],
   "source": [
    "for i in range(1000):\n",
    "    print('Playing ', i, ' th game')\n",
    "    # Uncomment the following line to execute your final runs. Do not do this until you are satisfied with your submission\n",
    "    print(api.start_game(practice=0,verbose=False))\n",
    "    \n",
    "    # DO NOT REMOVE as otherwise the server may lock you out for too high frequency of requests\n",
    "    time.sleep(0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## To check your game statistics\n",
    "1. Simply use \"my_status\" method.\n",
    "2. Returns your total number of games, and number of wins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "[total_practice_runs,total_recorded_runs,total_recorded_successes,total_practice_successes] = api.my_status() # Get my game stats: (# of tries, # of wins)\n",
    "success_rate = total_recorded_successes/total_recorded_runs\n",
    "print('overall success rate = %.3f' % success_rate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "outputs_hidden": 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.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}