sem05_set_dict/sem05_group01.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Анализ данных на Python\n",
    "\n",
    "### Семинар 5. Множества и словари"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Вопросы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Старая: 0.8 * Min(10, 0.1*МСР + 0.25*БСР + 0.3*КР + 0.35*ДЗ)\n",
    "# Новая:  Min(8, 0.1*МСР + 0.25*БСР + 0.3*КР + 0.35*ДЗ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задача 2 из БСР"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 12 23 34 45 56 67 78 89 100 111 122 133 144 155 166 177 188 199 210 221 232 243 254 265 276 287 298 309 320 331 342 353 364 375 386 397 408 419 430 441 452 463 474 485 496 507 518 529 540 551 562 573 584 595 606 617 628 639 650 661 672 683 694 705 716 727 738 749 760 771 782 793 804 815 826 837 848 859 870 881 892 903 914 925 936 947 958 969 980 991 2 14 26 38 50 62 74 86 98 110 123 135 147 159 171 183 195 207 219 231 244 256 268 280 292 304 316 328 340 352 365 377 389 401 413 425 437 449 461 473 486 498 510 522 534 546 558 570 582 594 607 619 631 643 655 667 679 691 703 715 728 740 752 764 776 788 800 812 824 836 849 861 873 885 897 909 921 933 945 957 970 982 994 3 16 29 42 55 69 82 95 108 121 136 149 162 175 189 202 215 228 241 255 269 282 295 308 322 335 348 361 374 388 402 415 428 442 455 468 481 494 508 521 535 548 561 575 588 601 614 627 641 654 668 681 695 708 721 734 747 761 774 787 801 814 828 841 854 867 880 894 907 920 934 948 961 974 987 1000 4 18 32 47 61 76 91 105 119 134 150 164 179 193 208 223 237 251 266 281 296 311 325 339 355 369 383 398 412 427 443 457 471 487 501 515 530 544 559 574 589 603 618 633 647 662 676 690 706 720 735 750 765 779 794 808 822 838 852 866 882 896 911 926 940 954 968 984 998 5 20 36 52 68 84 101 116 131 148 165 181 197 213 229 246 261 277 293 310 326 343 358 373 391 406 422 438 454 470 488 503 519 536 552 567 583 599 615 632 648 664 680 697 712 729 744 759 777 792 809 825 842 857 874 889 905 922 938 953 971 986 6 22 40 58 75 93 112 128 145 163 182 200 217 235 252 271 288 305 323 341 359 378 394 411 431 447 465 482 500 517 537 554 571 590 608 624 642 659 677 696 713 731 748 767 784 802 819 835 855 872 890 908 927 943 962 978 996 7 25 44 64 83 103 124 141 160 180 201 220 239 259 278 299 317 336 356 376 395 416 434 453 475 492 512 531 550 569 591 610 629 649 669 687 707 725 745 766 785 805 823 844 863 883 901 919 941 960 979 999 8 28 49 71 92 114 137 156 176 198 222 242 263 285 306 329 349 370 392 414 435 458 478 499 523 542 564 585 605 626 651 671 692 714 736 756 778 798 820 843 864 886 906 929 950 972 992 9 31 54 79 102 126 151 172 194 218 245 267 290 314 337 362 384 407 432 456 479 504 526 549 576 597 621 644 666 689 717 739 762 786 810 832 856 878 902 928 951 975 997 10 35 60 87 113 139 167 190 214 240 270 294 319 346 371 399 423 448 476 502 527 555 579 604 634 657 684 709 733 758 789 813 839 865 891 916 942 966 993 11 39 66 96 125 153 184 209 236 264 297 324 351 381 409 439 466 493 524 553 580 611 637 665 698 723 753 780 807 834 868 895 923 952 981 13 43 73 106 138 169 203 230 260 291 327 357 387 420 450 483 513 543 577 609 638 673 701 732 768 796 829 858 888 918 955 985 15 48 81 117 152 186 224 253 286 321 360 393 426 462 495 532 565 598 635 670 702 741 772 806 845 876 912 944 977 17 53 90 129 168 205 247 279 315 354 396 433 469 509 545 586 622 658 699 737 773 816 850 887 930 964 19 59 99 142 185 226 272 307 347 390 436 477 516 560 600 645 685 724 769 811 851 898 935 976 21 65 109 157 204 249 300 338 382 429 480 525 568 616 660 710 754 797 846 893 937 988 24 72 120 173 225 274 330 372 421 472 528 578 625 678 726 781 830 877 931 983 27 80 132 191 248 302 363 410 464 520 581 636 688 746 799 860 913 965 30 88 146 211 273 333 400 451 511 572 640 700 757 821 879 946 33 97 161 233 301 367 440 497 563 630 704 770 833 904 967 37 107 178 257 332 404 484 547 620 693 775 847 917 995 41 118 196 283 366 445 533 602 682 763 853 932 46 130 216 312 403 490 587 663 751 840 939 51 143 238 344 444 539 646 730 827 924 57 158 262 379 489 593 711 803 910 63 174 289 417 538 653 783 884 70 192 318 459 592 719 862 973 77 212 350 505 652 791 949 85 234 385 556 718 871 94 258 424 612 790 959 104 284 467 674 869 115 313 514 742 956 127 345 566 817 140 380 623 899 154 418 686 989 170 460 755 187 506 831 206 557 915 227 613 250 675 275 743 303 818 334 900 368 990 405 446 491 541 596 656 722 795 875 963\n"
     ]
    }
   ],
   "source": [
    "a = list(range(1, 1001))\n",
    "r = []\n",
    "while len(a) > 0:\n",
    "    r += a[::11]\n",
    "    del a[::11]\n",
    "          \n",
    "print(' '.join(map(str, r)))\n",
    "\n",
    "# Примерно одно и то же:\n",
    "# [str(item) for item in r]\n",
    "# map(str, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,3,4,5]\n",
    "a[::2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "del a[::2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задача 4 из БСР"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "a = [list(map(int, input().strip().split())) for _ in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 0, 0, 0], [0, 6, 0, 0], [0, 0, 11, 0], [0, 0, 0, 16]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidates = list(range(1, n**2 + 1))\n",
    "candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 6, 11, 16]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# used = []\n",
    "\n",
    "# for item in a:\n",
    "#     for jtem in item:\n",
    "#         if jtem != 0:\n",
    "#             used.append(jtem)\n",
    "\n",
    "used = [jtem for item in a for jtem in item if jtem != 0]\n",
    "used"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "actual = [ktem for ktem in candidates if ktem not in used]\n",
    "actual"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 0\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        if a[i][j] == 0:\n",
    "            a[i][j] = actual[s]\n",
    "            s += 1\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4\n",
      "5 6 7 8\n",
      "9 10 11 12\n",
      "13 14 15 16\n",
      "\n"
     ]
    }
   ],
   "source": [
    "ans = ''\n",
    "for item in a:\n",
    "    row = ''\n",
    "    for jtem in item:\n",
    "        row += (str(jtem) + ' ')\n",
    "    ans += (row.strip() + '\\n')\n",
    "\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4\n",
      "5 6 7 8\n",
      "9 10 11 12\n",
      "13 14 15 16\n"
     ]
    }
   ],
   "source": [
    "print('\\n'.join([' '.join(map(str, row)) for row in a]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Что такое Хэш-таблица? \n",
    "\n",
    "Вы - продавец в магазине. Когда покупатель что-то у вас покупает, вы проверяете стоимость товара по книге. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = [('яйца', 60), ('чай', 16), ('кофе', 35), ('лён', 20), \n",
    "        ('петрушка', 15), ('торт', 10), ('арбуз', 60), ('йогурт', 35), \n",
    "        ('соя', 20), ('ролтон', 42), ('бобы', 10), ('глаз дракона', 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как найти сколько стоят бобы? Листать книгу, читать в ней каждую строчку до тех пор пока мы не найдём ответ. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "x = 'бобы'\n",
    "\n",
    "# T(n) = O(n)\n",
    "# M(n) = O(1)\n",
    "\n",
    "for item in book:\n",
    "    if item[0] == x:\n",
    "        print(item[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ Если у нас всего $n$ продуктов, сколько действий нам надо будет сделать в худшем случае? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как-то долговато. Давайте попробуем ускориться. Одной из идей ускорения может быть сортировка. Если отсортировать все продукты по их названию, искать будет легче. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('арбуз', 60),\n",
       " ('бобы', 10),\n",
       " ('глаз дракона', 2),\n",
       " ('йогурт', 35),\n",
       " ('кофе', 35),\n",
       " ('лён', 20),\n",
       " ('петрушка', 15),\n",
       " ('ролтон', 42),\n",
       " ('соя', 20),\n",
       " ('торт', 10),\n",
       " ('чай', 16),\n",
       " ('яйца', 60)]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book = sorted(book, key=lambda w: w[0])  # O(n * log n)\n",
    "book"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Будем открывать книгу в середине. Там буква \"п\". Нам нужна буква \"б\", она левее буквы \"п\". Откроем серидну левой части книги, там буква \"й\", нам нужно еще левее, снова откроем середину. Будем так делать до тех пор, пока не найдём бобы. Такая процедура будет работать быстрее, она называется __бинарный поиск.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Попытайтесь на досуге написать такой поиск самостоятельно :) \n",
    "\n",
    "    # ┬─┬ ノ( ゜-゜ノ)       Писать код самому? \n",
    "    \n",
    "    # (╯° □°)╯︵ ┻━┻ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ Если у нас всего $n$ продуктов, сколько действий нам надо будет сделать в худшем случае? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Всё ещё долго. А можно ещё быстрее? Конечно можно. Давайте наймём помощницу по имени Алиса и заставим её выучить всю книгу с продуктами и ценами наизусть. Тогда мы сможем задавать ей вопрос и моментально будем получать ответ на него. Просто чудо, а не помощница! Где бы взять такую... \n",
    "\n",
    "Попробуем создать её из тех структур данных, которые мы уже знаем. А именно: из массивов. Для этого будем использовать __хеш-функцию.__ Хеш-функция - это такая функция, которая на вход получает строку и возвращает число. Они и поможет нам создать свою Алису."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [0]*33 # заведём пустой массив\n",
    "x[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пусть наша хэш-функция возвращает номер первой буквы слова в алфавите. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def simple_hash(x):\n",
    "    alph = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя'\n",
    "    return alph.index(x[0])\n",
    "\n",
    "simple_hash('яйца')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple_hash('бобы')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple_hash('булка') # Коллизия"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Положим в массив $x$ на $32$ позицию цену на яйца. По аналогии сделаем со всеми продуктами и их ценами. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[60,\n",
       " 10,\n",
       " 0,\n",
       " 2,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 35,\n",
       " 35,\n",
       " 20,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 15,\n",
       " 42,\n",
       " 20,\n",
       " 10,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 16,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 60]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for food, price in book:\n",
    "    x[simple_hash(food)] = price\n",
    "    \n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хэщ-функция в нашем примере связывает каждое название с одним индексом. На месте этого индекса в векторе $x$ и лежит нужная цена. __Поздравляю, мы создали свою Алису!__\n",
    "\n",
    "А теперь к нам приходит клиент и спрашивает: \"А сколько стоит торт?\" Мы легко можем ответить на его вопрос: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ind = simple_hash('торт')\n",
    "x[ind]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И мы делаем это моментально, без перебора как в первых двух случаях. \n",
    "\n",
    "__Вопросы:__\n",
    "\n",
    "- Понятное дело, что на практике хеш-функции устроены сложнее, у той функции, которую мы тут использовали есть куча проблем: какие это проблемы? \n",
    "- Как можно попытаться решить эти проблемы? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В python хэш-таблицы реализованы в виде словарей и множеств. Давайте с ними познакомимся. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Множества (set)\n",
    "\n",
    "Мы уже знаем списки и кортежи - упорядоченные структуры, которые могут хранить в себе объекты любых типов, к которым мы можем обратиться по индексу. Теперь поговорим о стуктурах неупорядоченных - множествах и словарях. \n",
    "\n",
    "Множества хранят некоторое количество объектов, но, в отличие от списка, один объект может храниться в множестве не более одного раза. Кроме того, порядок элементов множества произволен, им нельзя управлять.\n",
    "\n",
    "Тип называется set, это же является конструктором типа, т.е. в функцию set можно передать произвольную последовательность, и из этой последовательности будет построено множество:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set()"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = set() # пустое множество\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{5, 10}"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.add(5)\n",
    "x.add(10)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{4, 5, 10}"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = {5, 10, 4, 5, 5, 5, 5} \n",
    "x # все элементы внутри множества уникальные"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'set' object is not subscriptable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[42], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mx\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m]\u001b[49m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'set' object is not subscriptable"
     ]
    }
   ],
   "source": [
    "x[1] # внутри множества нет порядка"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 5, 10, 11]\n",
    "10 in x  # линейный поиск - перебор всех элементов и сравние O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = {1, 5, 10, 11}\n",
    "10 in x # работает моментально за O(1) => берем хэш от 10 и смотрим есть ли на этой позиции в таблице что-нибудь"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Разные операции с множествами:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "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": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{2, 3, 5, 7}\n",
      "{'horse', 'cat', 'dog'}\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": 49,
   "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": 50,
   "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": 51,
   "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",
    "\n",
    "s.remove(1) # удаление элемента\n",
    "s.discard(1) # аналогично, но не будет ошибки, если вдруг такого элемента нет в множестве\n",
    "print(s)\n",
    "\n",
    "x = s.pop() # удаляет и возвращает один произвольный элемент множества (можем сохранить его в переменную)\n",
    "print(s)\n",
    "print(x)\n",
    "\n",
    "s.clear() # очистить\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [4, 5, 7]\n",
    "z = a.pop(0)\n",
    "z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 7]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = {5, 34, 7}\n",
    "z = a.pop()\n",
    "z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{5, 7}"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "set.pop() takes no arguments (1 given)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[76], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43ma\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mpop\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n",
      "\u001b[0;31mTypeError\u001b[0m: set.pop() takes no arguments (1 given)"
     ]
    }
   ],
   "source": [
    "a.pop(1)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "Как мы сокращали арифметические операции раньше (например, +=), так же можно сокращать операции над множествами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "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": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', '3', '4', '5', '1', '2', '1', '2', '7', '3', '\\\\n']"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = input()\n",
    "x.split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', '3', '4', '5', '1', '2', '1', '2', '7', '3', '\\\\n']"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = input()\n",
    "x.strip().split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "print(len(set(input().strip().split())))"
   ]
  },
  {
   "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": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# решение здесь\n",
    "student_1 = 'математика немецкий право'\n",
    "student_2 = 'математика немецкий'\n",
    "student_3 = 'немецкий право математика'\n",
    "\n",
    "len(set(student_1.split()) & set(student_2.split()) & set(student_3.split()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте модифицируем эту задачу, и представим, что только два студента выбирают факультативы, откроются факультативы, которые выбрал, хотя бы один студент. Но затем выясняется, что один из факультативов из списка отменили. Выводить будет через запятую те факультативы, которые откроются.\n",
    "\n",
    "*Пример*  \n",
    "**Ввод:**\n",
    "\n",
    "математика немецкий право  \n",
    "математика английский  \n",
    "право\n",
    "\n",
    "**Вывод:**  \n",
    "математика, немецкий, английский"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# решение здесь"
   ]
  },
  {
   "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=\"200\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = \"aAAbbbb\"  # n камней \n",
    "J = \"aA\"       # m камней \n",
    "\n",
    "# Сколько такой код будет работать по времени?  O(nm)\n",
    "cnt = 0\n",
    "for stone in S:           # перебираю n вариантов\n",
    "    for j_stone in J:         # перебираю m вариантов \n",
    "        if stone == j_stone:\n",
    "            cnt += 1\n",
    "cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Итоговая сложность T(n) = O(nm)\n",
    "# M(n) = O(1)\n",
    "\n",
    "cnt = 0\n",
    "for stone in S:     # O(n)\n",
    "    if stone in J:      # линейный поиск O(m) (тайный цикл)\n",
    "        cnt += 1\n",
    "cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cnt = 0\n",
    "\n",
    "# Итоговая сложность T(n) = O(n + m)\n",
    "# M(n) = O(m)\n",
    "\n",
    "J_set = set(J)  # O(m)\n",
    "\n",
    "# O(n)\n",
    "for stone in S:           # O(n)\n",
    "    if stone in J_set:      # O(1)\n",
    "        cnt += 1\n",
    "cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numJewelsInStones(J, S):\n",
    "    cnt = 0\n",
    "    J_set = set(J)\n",
    "    for stone in S:\n",
    "        if stone in J_set:\n",
    "            cnt += 1\n",
    "    return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "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": 105,
   "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": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import random\n",
    "n_obs = 10**6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist = [random() for _ in range(n_obs)]\n",
    "myset = set(mylist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.22 ms ± 31.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "0.5 in mylist  # список"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "39.8 ns ± 0.0944 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 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": 110,
   "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": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(2, 3): [2, 3]}"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = dict()\n",
    "a[(2,3)] = [2,3] # кортеж может быть ключом, потому что он неизменямый\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "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)",
      "Cell \u001b[0;32mIn[112], line 2\u001b[0m\n\u001b[1;32m      1\u001b[0m b \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mdict\u001b[39m()\n\u001b[0;32m----> 2\u001b[0m \u001b[43mb\u001b[49m\u001b[43m[\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m2\u001b[39;49m\u001b[43m,\u001b[49m\u001b[38;5;241;43m3\u001b[39;49m\u001b[43m]\u001b[49m\u001b[43m]\u001b[49m \u001b[38;5;241m=\u001b[39m [\u001b[38;5;241m2\u001b[39m,\u001b[38;5;241m3\u001b[39m] \u001b[38;5;66;03m# а список уже нет, получим ошибку\u001b[39;00m\n\u001b[1;32m      3\u001b[0m \u001b[38;5;28mprint\u001b[39m(b)\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": 113,
   "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": 114,
   "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": 115,
   "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": 116,
   "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": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d1 == d2 == d3 == d4 # Содержание всех словарей одинаковое"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пустой словарь можно создать двумя способами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "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": 119,
   "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)",
      "Cell \u001b[0;32mIn[119], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43md1\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m]\u001b[49m \u001b[38;5;66;03m# выдаст ошибку во всех случах кроме того, если в вашем словаре вдруг есть ключ 1\u001b[39;00m\n",
      "\u001b[0;31mKeyError\u001b[0m: 1"
     ]
    }
   ],
   "source": [
    "d1[1] # выдаст ошибку во всех случах кроме того, если в вашем словаре вдруг есть ключ 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Но можно обращаться к значению по ключу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'кот': 10, 'и': 100, 'Тейлора': 2}"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "print(d1['кот'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'бобы'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[122], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43md1\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mбобы\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m]\u001b[49m\n",
      "\u001b[0;31mKeyError\u001b[0m: 'бобы'"
     ]
    }
   ],
   "source": [
    "d1['бобы']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d1.get('кот', -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d1.get('бобы', -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно создать новую пару ключ-значение. Для этого просто указываем в квадратных скобках название нового ключа."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "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": 128,
   "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": 129,
   "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": 130,
   "metadata": {
    "scrolled": true
   },
   "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)",
      "Cell \u001b[0;32mIn[130], line 3\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28mprint\u001b[39m(d1\u001b[38;5;241m.\u001b[39mget(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mкот\u001b[39m\u001b[38;5;124m\"\u001b[39m)) \u001b[38;5;66;03m# вернул значение 11\u001b[39;00m\n\u001b[1;32m      2\u001b[0m \u001b[38;5;28mprint\u001b[39m(d1\u001b[38;5;241m.\u001b[39mget(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mктоо\u001b[39m\u001b[38;5;124m\"\u001b[39m)) \u001b[38;5;66;03m# вернут None\u001b[39;00m\n\u001b[0;32m----> 3\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43md1\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mктоо\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m]\u001b[49m) \u001b[38;5;66;03m# ошибка\u001b[39;00m\n",
      "\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": 131,
   "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": 132,
   "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": 133,
   "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": 135,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_values([10, 100, 2])\n",
      "dict_keys(['кот', 'и', 'Тейлора'])\n",
      "dict_items([('кот', 10), ('и', 100), ('Тейлора', 2)])\n"
     ]
    }
   ],
   "source": [
    "d1 = {\"кот\": 10, \"и\": 100, \"Тейлора\": 2}\n",
    "\n",
    "print(d1.values()) # только значения\n",
    "print(d1.keys()) # только ключи\n",
    "print(d1.items()) # только значения"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Пример"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "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": 136,
     "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",
    "list(zip(product, price))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "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": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict = dict(zip(product, price))\n",
    "book_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['яйца', 'чай', 'кофе', 'банан', 'петрушка', 'сода', 'яблочко', 'йогурт', 'соя', 'беозар', 'бобы', 'печень дракона'])"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([60, 16, 35, 20, 15, 10, 60, 35, 20, 42, 10, 2])"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([('яйца', 60), ('чай', 16), ('кофе', 35), ('банан', 20), ('петрушка', 15), ('сода', 10), ('яблочко', 60), ('йогурт', 35), ('соя', 20), ('беозар', 42), ('бобы', 10), ('печень дракона', 2)])"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book_dict.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "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": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 8, 5: 125, 8: 512, 11: 1331, 14: 2744, 17: 4913}"
      ]
     },
     "execution_count": 142,
     "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": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_dict = {'swear' : ['клясться', 'ругаться'], 'dream' : ['спать', 'мечтать']}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "По ключу мы получим значение в виде списка:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['клясться', 'ругаться']"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_dict['swear']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Так как значением является список, можем отдельно обращаться к его элементам:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'клясться'"
      ]
     },
     "execution_count": 145,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_dict['swear'][0] # первый элемент"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можем пойти дальше и создать словарь, где значениями являются словари! Например, представим, что в некотором сообществе проходят выборы, и каждый участник может проголосовать за любое число кандидатов. Данные сохраняются в виде словаря, где ключами являются имена пользователей, а значениями – пары *кандидат-голос*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "votes = {'user1': {'cand1': '+', 'cand2': '-'},\n",
    "         'user2' : {'cand1': 0, 'cand3' : '+'}} # '+' - за, '-' - против, 0 - воздержался"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'user1': {'cand1': '+', 'cand2': '-'}, 'user2': {'cand1': 0, 'cand3': '+'}}"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "По аналогии с вложенными списками по ключам мы сможем обратиться к значению в словаре, который сам является значением в `votes` (да, эту фразу нужно осмыслить):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'+'"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes['user1']['cand1'] # берем значение, соответствующее ключу user1, в нем – ключу cand1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"Объединять словари можно через метод update(). Обратите внимание, что если в словарях есть одинаковые ключи, то они перезапишутся ключами того словаря, который добавляем.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'user1': {'cand1': '+', 'cand2': '-'},\n",
       " 'user2': {'cand1': 0, 'cand3': '+'},\n",
       " 'swear': ['клясться', 'ругаться'],\n",
       " 'dream': ['спать', 'мечтать']}"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes.update(my_dict)\n",
    "votes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "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": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{'hello': 1}\n",
      "{'hello': 2}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'hello': 2, 'world': 1}"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"hello hello world\"\n",
    "\n",
    "dct = dict() # { }\n",
    "\n",
    "for kek in s.split():\n",
    "    print(dct)\n",
    "    if kek in dct:\n",
    "        dct[kek] += 1\n",
    "    else:\n",
    "        dct[kek] = 1\n",
    "dct "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 164,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'h' < 'w'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1103, 1105)"
      ]
     },
     "execution_count": 167,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('я'), ord('ё') "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hello'"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pre_ans = sorted(dct.items(), key=lambda w: w[1], reverse=True)\n",
    "pre_ans[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(x):\n",
    "    return x**2 \n",
    "f(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = lambda x: x**2\n",
    "g(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stats(s):\n",
    "\n",
    "    dct = dict()\n",
    "    for kek in s.split():\n",
    "        if kek in dct:\n",
    "            dct[kek] += 1\n",
    "        else:\n",
    "            dct[kek] = 1\n",
    "\n",
    "    pre_ans = sorted(dct.items(), key=lambda w: w[1], reverse=True)\n",
    "    max_cnt = pre_ans[0][1]\n",
    "    \n",
    "    ans = [ ]\n",
    "    for item in pre_ans:\n",
    "        if item[1] == max_cnt:\n",
    "            ans.append(item[0])\n",
    "        else:\n",
    "            break \n",
    "\n",
    "    if len(ans) == 1:\n",
    "        return ans[0]\n",
    "    else:\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "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": 184,
   "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": "code",
   "execution_count": 185,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hello'"
      ]
     },
     "execution_count": 185,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stats(\"hello hello world\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'b']"
      ]
     },
     "execution_count": 186,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stats(\"a a b b c\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задача 5: сумма двух \n",
    "\n",
    "Дан массив из целых чисел `nums` и ещё одно целое число `target`.  Найдите все такие пары чисел из массива `nums`, которые в сумме дают число `target`. Выведите на экран их индексы. Одно и то же число использовать при подсчёте суммы дважды нельзя. Попытайтесь решить эту задачу максимально эффективно. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def two_sum_fast(nums, target):\n",
    "    \n",
    "    # ┬─┬ ノ( ゜-゜ノ)\n",
    "    \n",
    "    # (╯° □°)╯︵ ┻━┻\n",
    "    \n",
    "    return ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.11.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}