12_hashTable/anonLetter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b8107b43-ac66-4d64-8d48-3c4069438130",
   "metadata": {},
   "source": [
    "# **12.2 Is an Anonymous Letter Constructable?**\n",
    "---\n",
    "- take text for an anonymous letter + text for a magazine \n",
    "    - is it possible to write the letter using the text from the magazine? \n",
    "- each letter in the letter can occur no more than the same letter in the magazine \n",
    "- count the number of distinct characters in the letter "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "28bed96d-074a-4dd3-a133-6abbdab68bd6",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "letter = \"Bob mustered up the energy to eat a burger today\"\n",
    "mag = \"mustered up the burger eat a Bob to energy today\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "034d35cf-b803-4e52-8a1d-7af8ff7a0966",
   "metadata": {},
   "outputs": [],
   "source": [
    "def anon_v_mag(letter: str, mag: str) -> bool:\n",
    "    \n",
    "    # how many times each character occurs in the letter\n",
    "    letter_char_freq = Counter(letter)\n",
    "    \n",
    "    for c in mag:\n",
    "        # is the character from the magazine in the letter? \n",
    "        if c in letter_char_freq:\n",
    "            # yes? drop the count of the characters \n",
    "            letter_char_freq[c] -= 1\n",
    "            \n",
    "            # did the last drop bring the count to zero?\n",
    "            if letter_char_freq[c] == 0:\n",
    "                # delete the character from the dictionary \n",
    "                del letter_char_freq[c]\n",
    "                \n",
    "                # if the dictionary is empty:\n",
    "                if not letter_char_freq:\n",
    "                    # the letter is anonymously constructable\n",
    "                    return True\n",
    "                \n",
    "    return not letter_char_freq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1a6d7ebd-5153-4fbc-a08a-d20cc7a6ab35",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "anon_v_mag(letter,mag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f34e94d2-ae56-4a94-b9e5-c0826c3c43c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "letterf = \"Bob mustered up the energy to eat a burger todays\"\n",
    "mag = \"mustered up the burger eat a Bob to energy today\"\n",
    "\n",
    "anon_v_mag(letterf,mag)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bff6f950-bc6c-49b9-9480-98bcfc204639",
   "metadata": {},
   "source": [
    "#### Time Complexity: `O(m + n)`\n",
    "- `m` = characters in the magazine \n",
    "- `n` = characters in the letter\n",
    "- worse case: letter is not constructable/ last character of the magazine is required\n",
    "\n",
    "#### Space Complexity: `O(L)`\n",
    "- `L` number of distinct characters in the letter \n",
    "- size of the hash table constructed \n",
    "\n",
    "### If characters coded in ASCII:\n",
    "- do away with the hash table and use a `256 entry integery array`\n",
    "   - `A[i]` being set to the number of times character `i` appears in the letter \n",
    "- ASCII: American Standard Code for Information Interchange\n",
    "    - character encoding standard for electronic commnication "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "471475e4-cf65-4d0c-98f3-8266f1dae141",
   "metadata": {},
   "source": [
    "---\n",
    "### Pythonic Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "607663b6-e041-4e99-b06d-cf842f7a87c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def python_anon_v_mag(letter: str, mag: str) -> bool:\n",
    "    \n",
    "    # subtraction only keeps keys with positive counts \n",
    "    return (not Counter(letter) - Counter(mag))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "aa1579eb-b3f7-4818-8bf1-d3d7f6c796a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_anon_v_mag(letter,mag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9f28d0f8-d08f-4750-9428-c4834fc14ea0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "letterf = \"Bob mustered up the energy to eat a burger todays\"\n",
    "mag = \"mustered up the burger eat a Bob to energy today\"\n",
    "\n",
    "python_anon_v_mag(letterf,mag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98e8b7bb-1d98-4f21-bf15-cbca91feee98",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3cf70ab7-5236-4d8b-b8ef-259c9e8d557d",
   "metadata": {},
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}