sem05_dict/sem05_set_dict_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Анализ данных на Python\n",
    "\n",
    "### Семинар 5. Множества и словари"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Множества (set)\n",
    "\n",
    "Мы уже знаем списки и кортежи - упорядоченные структуры, которые могут хранить в себе объекты любых типов, к которым мы можем обратиться по индексу. Теперь поговорим о стуктурах неупорядоченных - множествах и словарях. \n",
    "\n",
    "Множества хранят некоторое количество объектов, но, в отличие от списка, один объект может храниться в множестве не более одного раза. Кроме того, порядок элементов множества произволен, им нельзя управлять.\n",
    "\n",
    "Тип называется set, это же является конструктором типа, т.е. в функцию set можно передать произвольную последовательность, и из этой последовательности будет построено множество:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{10, 20, 30}\n",
      "{4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "set()\n"
     ]
    }
   ],
   "source": [
    "print(set([10, 20, 30])) # передаем список\n",
    "print(set((4, 5, 6))) # передаем tuple\n",
    "print(set(range(10))) # послед-сть от 0 до 10 не включая\n",
    "print(set()) # пустое множество"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Другой способ создать множество - это перечислить его элементы в фигурных скобках (список - в квадратных, кортеж в круглых, а множество - в фигурных)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{2, 3, 5, 7}\n",
      "{'dog', 'horse', 'cat'}\n"
     ]
    }
   ],
   "source": [
    "primes = {2, 3, 5, 7}\n",
    "animals = {\"cat\", \"dog\", \"horse\", 'cat'}\n",
    "print(primes)\n",
    "print(animals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Кстати, обратите внимание, что множество может состоять только из уникальных объектов. Выше множество animals включает в себя только одну кошку несмотря на то, что в конструктор мы передали 'cat' два раза. Преобразовать список в множество - самый простой способ узнать количество уникальных объектов.\n",
    "\n",
    "Со множествами работает почти всё, что работает с последовательностями (но не работают индексы, потому что элементы не хранятся упорядоченно)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(len(primes)) # длина\n",
    "print(11 in primes) # проверка на наличие элемента in хорошо и быстро работает для множеств\n",
    "print(\"cow\" in animals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Все возможные операции с множествами: https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset\n",
    "\n",
    "Отдельно мы посмотрим на так называемые операции над множествами. Если вы знаете круги Эйлера, то помните как различают объекты множеств - пересечение, объекты, которые принадлежат множеству а, но не принадлежат b и так далее. Давайте посмотрим, как эти операции реализованы в питоне."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "{1, 2, 3, 4, 5, 6}\n",
      "{3, 4}\n",
      "{1, 2}\n",
      "{1, 2, 5, 6}\n",
      "{1, 2, 3, 4}\n"
     ]
    }
   ],
   "source": [
    "a = {1, 2, 3, 4}\n",
    "b = {3, 4, 5, 6}\n",
    "c = {2, 3}\n",
    "\n",
    "print(c <= a) # проверка на подмножество (с подномжество a)\n",
    "print(c <= b) # не подмножество, т.к. в b нет 2 \n",
    "print(a >= c) # а надмножество с\n",
    "print(a | b) # объединение\n",
    "print(a & b) # пересечение\n",
    "print(a - b) # разность множеств (все что в a, кроме b)\n",
    "print(a ^ b) # симметрическая разность множеств (объединение без пересечения)\n",
    "\n",
    "c = a.copy() # копирование множества, или set(a)\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Предыдущие операции не меняли множества, создавали новые. А как менять множество:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{10, 1, 2, 3}\n",
      "{10, 2, 3}\n",
      "{2, 3}\n",
      "10\n",
      "set()\n"
     ]
    }
   ],
   "source": [
    "s = {1, 2, 3}\n",
    "s.add(10) # добавить\n",
    "print(s) # обратите внимание, что порядок элементов непредсказуем\n",
    "s.remove(1) # удаление элемента\n",
    "s.discard(1) # аналогично, но не будет ошибки, если вдруг такого элемента нет в множестве\n",
    "print(s)\n",
    "x = s.pop() # удаляет и возвращает один произвольный элемент множества (можем сохранить его в переменную)\n",
    "print(s)\n",
    "print(x)\n",
    "s.clear() # очистить\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как мы сокращали арифметические операции раньше (например, +=), так же можно сокращать операции над множествами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{10, 20}\n"
     ]
    }
   ],
   "source": [
    "s |= {10, 20} # s = s | {10, 20} # объединение множества s с {10,20}\n",
    "print(s)\n",
    "# s ^=, s &= и т.п."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 1 (на самом деле очень простая)\n",
    "\n",
    "Дан список чисел, который может содержать до 100000 чисел. Определите, сколько в нем встречается различных чисел.\n",
    "\n",
    "#### Пример 1\n",
    "\n",
    "##### Ввод\t\n",
    "\n",
    "1 2 3 2 1\n",
    "\n",
    "##### Вывод\n",
    "\n",
    "3\n",
    "\n",
    "#### Пример 2\n",
    "##### Ввод\t\n",
    "\n",
    "1 2 3 4 5 1 2 1 2 7 3\n",
    "\n",
    "##### Вывод\n",
    "6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 2 1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# решение здесь\n",
    "\n",
    "lst = set(map(int, input().split()))\n",
    "print(len(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 2 (факультативы)\n",
    "Группа из 3 студентов пишет заявки на желаемые факультативы из списка: английский, немецкий, право, математика, сольфеджио. Факультатив откроют, если на него запишутся все студенты. Каждый студент может выбрать минимум один и максимум три факультатива. Нужно посчитать количество факультативов, которые откроются.\n",
    "\n",
    "*Пример*\n",
    "\n",
    "**Ввод:**\n",
    "\n",
    "английский сольфеджио право  \n",
    "математика сольфеджио  \n",
    "немецкий право\n",
    "\n",
    "**Вывод:**\n",
    "\n",
    "0\n",
    "\n",
    "**Ввод:**\n",
    "\n",
    "математика немецкий право  \n",
    "математика немецкий  \n",
    "немецкий право математика \n",
    "\n",
    "**Вывод:**  \n",
    "2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "математика немецкий право\n",
      "математика немецкий\n",
      "немецкий право математика\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# считываем значения для каждого студента. input() принимает на ввод строку вида 'немецкий право математика'\n",
    "# split() разбивает ее по пробелам и делает из нее список вида ['немецкий', 'право', 'математика'] (каждое слово, отделенное пробелом, стало объектом в нем)\n",
    "# set() из этого списка делает множество (уникальные предметы, которые выбрал студент)\n",
    "stud1 = set(input().split())\n",
    "stud2 = set(input().split())\n",
    "stud3 = set(input().split())\n",
    "print(len(stud1 & stud2 & stud3)) # находим пересечение трех множеств (факультативы, которые общие для всех трех студентов) и смотрим, сколько объектов в этом множестве (len())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте модифицируем эту задачу, и представим, что только два студента выбирают факультативы, откроются факультативы, которые выбрал, хотя бы один студент. Но затем выясняется, что один из факультативов из списка отменили. Выводить будет через запятую те факультативы, которые откроются.\n",
    "\n",
    "*Пример*  \n",
    "**Ввод:**\n",
    "\n",
    "математика немецкий право  \n",
    "математика английский  \n",
    "право\n",
    "\n",
    "**Вывод:**  \n",
    "математика, немецкий, английский"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "математика немецкий право\n",
      "математика английский\n",
      "право\n",
      "математика, немецкий, английский\n"
     ]
    }
   ],
   "source": [
    "# решение здесь\n",
    "\n",
    "stud1 = set(input().split())\n",
    "stud2 = set(input().split())\n",
    "cancelled = input()\n",
    "\n",
    "opened = (stud1 | stud2)\n",
    "opened.discard(cancelled)\n",
    "print(*opened, sep=', ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задача 3: [камешки](https://leetcode.com/problems/jewels-and-stones/)\n",
    "\n",
    "У Дори в глубинах океана есть кучка камней. Часть камней из этой кучки драгоценные. Недавно она пересчитала все драгоценные и забыла сколько их. Чтобы больше не забывать, Дори решила написать на питоне функцию, которая будет считать камни за неё.\n",
    "\n",
    "Напишите на python функцию, которая принимает на вход список драгоценных камней $J$ и список камней, которые есть у Дори $S$. На выход функция возвращает число драгоценных камней в запасах Дори.\n",
    "\n",
    "__Примеры:__ \n",
    "\n",
    "> Input: J = \"aA\", S = \"aAAbbbb\" <br />\n",
    "Output: 3\n",
    "\n",
    "Тут драгоценными считаются камни a и A. У Дори есть камни aAAbbbb. Среди них три драгоценных, aAA.\n",
    "\n",
    ">Input: J = \"z\", S = \"ZZ\" <br />\n",
    "Output: 0\n",
    "\n",
    "Драгоценными мы считаем только камень z. У Дори два камня, оба обычные."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://steemitimages.com/0x0/https://media.makeameme.org/created/repeat-repeat-repeat-5984a6.jpg\" height=\"400\" width=\"400\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numJewelsInStones(J, S):\n",
    "    \n",
    "    ### ╰( ͡° ͜ʖ ͡° )つ▬▬ι═══════  bzzzzzzzzzz\n",
    "    # will the code be with you\n",
    "    answer = 0\n",
    "    J = set(J)\n",
    "    for stone  in S:\n",
    "        if stone  in J:\n",
    "            answer += 1\n",
    "    \n",
    "    return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_problem_13(func, test_data):\n",
    "    for inputs, true_answer in test_data:\n",
    "        answer = func(*inputs)\n",
    "        assert answer == true_answer, f'Expected {true_answer}, got {answer}. Input: {inputs}'\n",
    "    print(\"OK!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "NUM_JEWELS_IN_STONES_TESTS_DATA = [\n",
    "        ((\"aA\", \"aAAbbbb\"), 3),\n",
    "        ((\"z\",\"ZZ\"),0)\n",
    "    ]\n",
    "test_problem_13(numJewelsInStones, NUM_JEWELS_IN_STONES_TESTS_DATA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Пара слов об эффективности:__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import random\n",
    "n_obs = 10**6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist = [random() for _ in range(n_obs)]\n",
    "myset = set(mylist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10.3 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "0.5 in mylist  # список"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "56.7 ns ± 1.97 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "0.5 in myset   # множество"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Словари (dict)\n",
    "Обычный массив (в питоне это список) можно понимать как функцию, которая сопоставляет начальному отрезку натурального ряда какие-то значения."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте посмотрим на списки непривычным способом. Списки - это функции (отображения), которые отображают начальный ряд натуральных чисел в объекты (проще говоря - преводят число 0,1,2,3... во что-то): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "20\n",
      "30\n",
      "a\n"
     ]
    }
   ],
   "source": [
    "l = [10, 20, 30, 'a']\n",
    "print(l[0])\n",
    "print(l[1])\n",
    "print(l[2])\n",
    "print(l[3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В словарях отображать можно не только начала натурального ряда, а произвольные объекты. Представьте себе настоящий словарь или телефонную книжку. Имени человека соответствует номер телефона.\n",
    "\n",
    "Классическое использование словарей в анализе данных: хранить частоту слова в тексте.\n",
    "\n",
    "кот $\\rightarrow$ 10\n",
    "\n",
    "и $\\rightarrow$ 100\n",
    "\n",
    "Тейлора $\\rightarrow$ 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Словарь состоит из набора ключей и соответствующих им значений. Значения могут быть любыми объектами (также как и в списке, хранить можно произвольные объекты). А ключи могут быть почти любыми объектами, но только неизменяемыми. В частности числами, строками, кортежами. Список или множество не могут быть ключом.\n",
    "\n",
    "Одному ключу соответствует ровно одно значение. Но одно и то же значение, в принципе, можно сопоставить разным ключам."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(2, 3): [2, 3]}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = dict()\n",
    "a[(2,3)] = [2,3] # кортеж может быть ключом, потому что он неизменямый\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'list'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-19-c056762b57aa>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mb\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdict\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----> 2\u001b[0;31m \u001b[0mb\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;31m# а список уже нет, получим ошибку\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'"
     ]
    }
   ],
   "source": [
    "b = dict()\n",
    "b[[2,3]] = [2,3] # а список уже нет, получим ошибку\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Создание словаря\n",
    "В фигурных скобках (как множество), через двоеточие ключ:значение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'кот': 10, 'и': 100, 'Тейлора': 2}\n"
     ]
    }
   ],
   "source": [
    "d1 = {\"кот\": 10, \"и\": 100, \"Тейлора\": 2}\n",
    "print(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Через функцию dict(). Обратите внимание, что тогда ключ-значение задаются не через двоеточие, а через знак присваивания. А строковые ключи пишем без кавычек - по сути мы создаем переменные с такими названиями и присваиваим им значения (а потом функция dict() уже превратит их в строки)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'кот': 10, 'и': 100, 'Тейлора': 2}\n"
     ]
    }
   ],
   "source": [
    "d2 = dict(кот=10, и=100, Тейлора=2)\n",
    "print(d2) # получили тот же результат, что выше"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И третий способ - передаем функции dict() список списков или кортежей с парами ключ-значение."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'кот': 10, 'и': 100, 'Тейлора': 2}\n"
     ]
    }
   ],
   "source": [
    "d3 = dict([(\"кот\", 10), (\"и\", 100), (\"Тейлора\", 2)]) # перечисление (например, список) tuple\n",
    "print(d3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Помните, когда мы говорили про списки, мы обсуждали проблему того, что важно создавать именно копию объекта, чтобы сохранять исходный список. Копию словаря можно сделать так"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'кот': 10, 'и': 100, 'Тейлора': 2}\n"
     ]
    }
   ],
   "source": [
    "d4 = dict(d3) # фактически, копируем dict который строчкой выше\n",
    "print(d4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d1 == d2 == d3 == d4 # Содержание всех словарей одинаковое"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пустой словарь можно создать двумя способами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{} {}\n"
     ]
    }
   ],
   "source": [
    "d2 = {} # это пустой словарь (но не пустое множество)\n",
    "d4 = dict()\n",
    "print(d2, d4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Операции со словарями"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как мы уже говорили, словари неупорядоченные структуры и обратиться по индексу к объекту уже больше не удастся."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "1",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-26-627b04325301>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0md1\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;31m# выдаст ошибку во всех случах кроме того, если в вашем словаре вдруг есть ключ 1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m: 1"
     ]
    }
   ],
   "source": [
    "d1[1] # выдаст ошибку во всех случах кроме того, если в вашем словаре вдруг есть ключ 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Но можно обращаться к значению по ключу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "print(d1['кот'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно создать новую пару ключ-значение. Для этого просто указываем в квадратных скобках название нового ключа."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test\n"
     ]
    }
   ],
   "source": [
    "d1[1] = 'test'\n",
    "print(d1[1]) # теперь работает!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Внимание: если элемент с указанным ключом уже существует, новый с таким же ключом не добавится! Ключ – это уникальный идентификатор элемента. Если мы добавим в словарь новый элемент с уже существующим ключом, мы просто изменим старый – словари являются изменяемыми объектами. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "d1[\"кот\"] = 11 # так же как в списке по индексу - можно присвоить новое значение по ключу\n",
    "print(d1['кот'])\n",
    "d1[\"кот\"] += 1 # или даже изменить его за счет арифметической операции\n",
    "print(d1['кот'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А вот одинаковые значения в словаре могут быть."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'кот': 12, 'и': 100, 'Тейлора': 2, 1: 'test', 'собака': 12}\n"
     ]
    }
   ],
   "source": [
    "d1['собака'] = 12\n",
    "print(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Кроме обращения по ключу, можно достать значение с помощью метода .get(). Отличие работы метода в том, что если ключа еще нет в словаре, он не генерирует ошибку, а возвращает объект типа None (\"ничего\"). Это очень полезно в решении некоторых задач. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n",
      "None\n"
     ]
    },
    {
     "ename": "KeyError",
     "evalue": "'ктоо'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-32-028409b2ab17>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0md1\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"кот\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# вернул значение 11\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0md1\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"ктоо\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# вернут None\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0md1\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'ктоо'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# ошибка\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m: 'ктоо'"
     ]
    }
   ],
   "source": [
    "print(d1.get(\"кот\")) # вернул значение 11\n",
    "print(d1.get(\"ктоо\")) # вернут None\n",
    "print(d1['ктоо']) # ошибка"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Удобство метода .get() заключается в том, что мы сами можем установить, какое значение будет возвращено, в случае, если пары с выбранным ключом нет в словаре. Так, вместо None мы можем вернуть строку Not found, и ломаться ничего не будет:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not found\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(d1.get(\"ктоо\", 'Not found')) # передаем вторым аргументом, что возвращать\n",
    "print(d1.get(\"ктоо\", False)) # передаем вторым аргументом, что возвращать"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Также со словарями работают уже знакомые нам операции - проверка количества элементов, проверка на наличие объектов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'кот': 12, 'и': 100, 'Тейлора': 2, 1: 'test', 'собака': 12}\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(d1)\n",
    "print(\"кот\" in d1) # проверка на наличие ключа\n",
    "print(\"ктоо\" not in d1) # проверка на отстуствие ключа\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Удалить отдельный ключ или же очистить весь словарь можно специальными операциями."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'и': 100, 'Тейлора': 2, 1: 'test', 'собака': 12}\n",
      "{}\n"
     ]
    }
   ],
   "source": [
    "del d1[\"кот\"] # удалить ключ со своим значением\n",
    "print(d1)\n",
    "d1.clear() # удалить все\n",
    "print(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "У словарей есть три метода, с помощью которых мы можем сгенерировать список только ключей, только значений и список пар ключ-значения (на самом деле там несколько другая структура, но ведет себя она очень похоже на список)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_values([])\n",
      "dict_keys([])\n",
      "dict_items([])\n"
     ]
    }
   ],
   "source": [
    "print(d1.values()) # только значения\n",
    "print(d1.keys()) # только ключи\n",
    "print(d1.items()) # только значения"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Пример"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<zip at 0x7fa42a2b1780>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "product = ['яйца', 'чай', 'кофе', 'банан', 'петрушка', 'сода', \n",
    "           'яблочко', 'йогурт', 'соя', 'беозар', 'бобы', 'печень дракона']\n",
    "\n",
    "price = [60, 16, 35, 20, 15, 10, 60, 35, 20, 42, 10, 2]\n",
    "\n",
    "zip(product, price)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'яйца': 60,\n",
       " 'чай': 16,\n",
       " 'кофе': 35,\n",
       " 'банан': 20,\n",
       " 'петрушка': 15,\n",
       " 'сода': 10,\n",
       " 'яблочко': 60,\n",
       " 'йогурт': 35,\n",
       " 'соя': 20,\n",
       " 'беозар': 42,\n",
       " 'бобы': 10,\n",
       " 'печень дракона': 2}"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict = dict(zip(product, price))\n",
    "book_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['яйца', 'чай', 'кофе', 'банан', 'петрушка', 'сода', 'яблочко', 'йогурт', 'соя', 'беозар', 'бобы', 'печень дракона'])"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([60, 16, 35, 20, 15, 10, 60, 35, 20, 42, 10, 2])"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([('яйца', 60), ('чай', 16), ('кофе', 35), ('банан', 20), ('петрушка', 15), ('сода', 10), ('яблочко', 60), ('йогурт', 35), ('соя', 20), ('беозар', 42), ('бобы', 10), ('печень дракона', 2)])"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Продукт яйца стоит 60 рублей\n",
      "Продукт чай стоит 16 рублей\n",
      "Продукт кофе стоит 35 рублей\n",
      "Продукт банан стоит 20 рублей\n",
      "Продукт петрушка стоит 15 рублей\n",
      "Продукт сода стоит 10 рублей\n",
      "Продукт яблочко стоит 60 рублей\n",
      "Продукт йогурт стоит 35 рублей\n",
      "Продукт соя стоит 20 рублей\n",
      "Продукт беозар стоит 42 рублей\n",
      "Продукт бобы стоит 10 рублей\n",
      "Продукт печень дракона стоит 2 рублей\n"
     ]
    }
   ],
   "source": [
    "for k, v in book_dict.items():\n",
    "    print(f\"Продукт {k} стоит {v} рублей\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 8, 5: 125, 8: 512, 11: 1331, 14: 2744, 17: 4913}"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{i: i**3 for i in range(2, 20, 3)} # словарь "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ну, и раз уж питоновские словари так похожи на обычные, давайте представим, что у нас есть словарь, где все слова многозначные. Ключом будет слово, а значением ‒ целый список. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_dict = {'swear' : ['клясться', 'ругаться'], 'dream' : ['спать', 'мечтать']}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "По ключу мы получим значение в виде списка:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['клясться', 'ругаться']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_dict['swear']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Так как значением является список, можем отдельно обращаться к его элементам:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'клясться'"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_dict['swear'][0] # первый элемент"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можем пойти дальше и создать словарь, где значениями являются словари! Например, представим, что в некотором сообществе проходят выборы, и каждый участник может проголосовать за любое число кандидатов. Данные сохраняются в виде словаря, где ключами являются имена пользователей, а значениями – пары *кандидат-голос*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "votes = {'user1': {'cand1': '+', 'cand2': '-'},\n",
    "         'user2' : {'cand1': 0, 'cand3' : '+'}} # '+' - за, '-' - против, 0 - воздержался"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'user1': {'cand1': '+', 'cand2': '-'}, 'user2': {'cand1': 0, 'cand3': '+'}}"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "По аналогии с вложенными списками по ключам мы сможем обратиться к значению в словаре, который сам является значением в `votes` (да, эту фразу нужно осмыслить):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'+'"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes['user1']['cand1'] # берем значение, соответствующее ключу user1, в нем – ключу cand1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"Объединять словари можно через метод update(). Обратите внимание, что если в словарях есть одинаковые ключи, то они перезапишутся ключами того словаря, который добавляем.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'user1': {'cand1': '+', 'cand2': '-'},\n",
       " 'user2': {'cand1': 0, 'cand3': '+'},\n",
       " 'swear': ['клясться', 'ругаться'],\n",
       " 'dream': ['спать', 'мечтать']}"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes.update(my_dict)\n",
    "votes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'user1': {'cand1': '+', 'cand2': '-'}, 'user2': {'cand1': 0, 'cand3': '+'}, 'swear': ['клясться', 'ругаться'], 'dream': ['спать', 'мечтать']}\n"
     ]
    }
   ],
   "source": [
    "votes['swear'] = 1 # добавим в словарь votes ключ swear, чтобы проверить, что произойдет, когда объединим с my_dict, в котором есть такой ключ\\n\",\n",
    "votes.update(my_dict)\n",
    "print(votes) # swear в votes перезаписался swear из mydict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задача 4: слова\n",
    "\n",
    "Напишите функцию `stats(s)`, принимающую на вход строку `s`, содержащую слова, разделённые пробелами, и находящую самое часто встречающееся слово. Если такое слово одно, верните его, если их несколько, верните список, отсортированный в лексикографическом порядке.\n",
    "\n",
    "Например: `stats(\"hello hello world\")` должна вернуть строчку `\"hello\"`, а `stats(\"a a b b c\")` должна вернуть список `['a','b']`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stats(s):\n",
    "    \n",
    "    ### ╰( ͡° ͜ʖ ͡° )つ▬▬ι═══════  bzzzzzzzzzz\n",
    "    # will the code be with you\n",
    "    \n",
    "    # Сначала составим словарь вида {слово: частота}\n",
    "    word_cnt = dict()\n",
    "    for word in s.split(\" \"):\n",
    "        if word in word_cnt:\n",
    "            word_cnt[word] += 1\n",
    "        else:\n",
    "            word_cnt[word] = 0\n",
    "    \n",
    "    # заведем массив для слов и счётчик для максимума\n",
    "    word_max, cnt_max = [ ], 0\n",
    "    \n",
    "    # пройдемся по всем словам из словаря\n",
    "    for k,v in word_cnt.items():\n",
    "        \n",
    "        # если максимум совпадает с текущим словом, добавляем его в список\n",
    "        if v == cnt_max:\n",
    "            word_max.append(k)\n",
    "            \n",
    "        # если текущее слово новый максимум, сбрасываем список\n",
    "        if v > cnt_max:\n",
    "            word_max = [k]\n",
    "            cnt_max = v\n",
    "    \n",
    "    if len(word_max) == 1:\n",
    "        return word_max[0]\n",
    "    else:\n",
    "        return sorted(word_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_problem(func, test_data):\n",
    "    for inputs, true_answer in test_data:\n",
    "        answer = func(inputs)\n",
    "        assert answer == true_answer, f'Expected {true_answer}, got {answer}. Input: {inputs}'\n",
    "    print(\"OK!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "STATS_TESTS_DATA = [\n",
    "        (\"hello hello world\", \"hello\"),\n",
    "        (\"a a b b c\", ['a','b'])\n",
    "    ]\n",
    "test_problem(stats, STATS_TESTS_DATA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задача 5: сумма двух \n",
    "\n",
    "Дан массив из целых чисел `nums` и ещё одно целое число `target`.  Найдите все такие пары чисел из массива `nums`, которые в сумме дают число `target`. Выведите на экран их индексы. Одно и то же число использовать при подсчёте суммы дважды нельзя. Попытайтесь решить эту задачу максимально эффективно. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 2), (3, 4)]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# сложность O(n*(n-1)/2) = O(n^2)\n",
    "# https://leetcode.com/problems/two-sum/\n",
    "\n",
    "def two_sum_slow(nums, target):\n",
    "    answer = [ ]\n",
    "    \n",
    "    n = len(nums)\n",
    "    for i in range(n):\n",
    "        for j in range(i + 1, n):\n",
    "            if nums[i] + nums[j] == target:\n",
    "                answer.append((i,j))\n",
    "    \n",
    "    return answer\n",
    "\n",
    "nums = [1,5,4,3,2]\n",
    "target = 5\n",
    "two_sum_slow(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 3), (1, 2)]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# сложность O(n logn + n) = O(n logn)\n",
    "# https://leetcode.com/problems/two-sum-ii-input-array-is-sorted\n",
    "\n",
    "def two_sum_medium(nums, target):\n",
    "    nums.sort() # O(n log(n))\n",
    "    \n",
    "    answer = [ ]\n",
    "\n",
    "    i = 0\n",
    "    j = len(nums) - 1\n",
    "\n",
    "    # O(n)\n",
    "    while i < j:\n",
    "        if nums[i] + nums[j] > target:\n",
    "            j -= 1\n",
    "        elif nums[i] + nums[j] < target:\n",
    "            i += 1\n",
    "        else:\n",
    "            answer.append((i,j))\n",
    "            i += 1\n",
    "            j -= 1\n",
    "            \n",
    "    return answer\n",
    "\n",
    "nums = [1,5,4,3,2]\n",
    "target = 5\n",
    "two_sum_medium(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 2), (1, 3)]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# сложность O(n) по времени\n",
    "# сложность O(n) по памяти\n",
    "\n",
    "def two_sum_fast(nums, target):\n",
    "    \n",
    "    # ┬─┬ ノ( ゜-゜ノ)\n",
    "    \n",
    "    # (╯° □°)╯︵ ┻━┻\n",
    "    \n",
    "    d = dict()\n",
    "    answer = [ ]\n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] in d:\n",
    "            answer.append((d[nums[i]], i))\n",
    "        else:\n",
    "            d[target - nums[i]] = i\n",
    "    return answer\n",
    "    \n",
    "nums = [1,2,4,3,5]\n",
    "target = 5\n",
    "two_sum_fast(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "TWO_SUM_TESTS_DATA = [\n",
    "    (([2, 7, 11, 15], 9), [(0, 1)]),\n",
    "]\n",
    "\n",
    "test_problem_13(two_sum_fast, TWO_SUM_TESTS_DATA)"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}