05 - Data Structures and Oddities/05 - Data Structures and Oddities.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/fmipython/PythonCourse2022/blob/dsa/05%20-%20Data%20Structures%20and%20Algorithms/05%20-%20Data%20Structures%20and%20Algorithms.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2Kd6KbO8zF1H"
      },
      "source": [
        "# Data Structures & Oddities"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NdKxeSrJzF1J"
      },
      "source": [
        "Структурите от данни са класове и обекти с интерфейс чрез който ги използваме, като се абстрахираме от имплементацията им.\n",
        "\n",
        "Алгоритмите са генерализирани процедури (парчета код/функции) които решават даден проблем (изпълняват дадена задача).\n",
        "\n",
        "Oddities са модули на Python, които нямат място в друга тема, но са интересни за решаването на проблеми."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z8oEt0InzF1J"
      },
      "source": [
        "## Защо?\n",
        "\n",
        "Структурите от данни и алгоритми:\n",
        "\n",
        "- Се използват често (по-простите от тях: List/Dict/Sort)\n",
        "- Подпомагат разбирането на други езици за програмиране (e.g. JavaScript обектите са Dict)\n",
        "- Са основа на по-сложни системи и приложения (e.g. Приоритетната опашка може да се реализира чрез запазване на опашката в база данни)\n",
        "- Са ключови за Google-style интервютата\n",
        "\n",
        "![https://i.imgur.com/dVcLsFl.png](https://i.imgur.com/dVcLsFl.png)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PXQ77lsLzF1K"
      },
      "source": [
        "## 3.. 2.. 1.. Go"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Licg8RzRzF1K"
      },
      "source": [
        "## Сложност на алгоритми\n",
        "\n",
        "https://www.bigocheatsheet.com/\n",
        "\n",
        "За оценка на сложност (бързина) на алгоритми използваме нотацията \"Big O\" $O(...)$.\n",
        "\n",
        "Сложността оценяваме спрямо размера на входа, като най-често използваме $n$, за да обозначим размера на входа.\n",
        "\n",
        "Примери за $n$:\n",
        "- За list K: $n = len(K)$\n",
        "- За str K: $n = len(K)$\n",
        "- За int K: $n = bytes\\;of\\;K = log_{10}(K) \\approxeq log_2(K)$ (но обикновено int казваме че има константен размер $O(1)$)\n",
        "\n",
        "Най-важните сложности са:\n",
        "- Constant $O(1)$\n",
        "- Linear $O(n)$\n",
        "- Linearithmic $O(n \\times log(n))$\n",
        "- Quadratic $O(n^2)$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "nux-fG88zF1K"
      },
      "outputs": [],
      "source": [
        "# O(1)\n",
        "def constant(x):\n",
        "    return x + 1\n",
        "\n",
        "# O(n)\n",
        "def linear(arr):  # O(n x 1) = O(n)\n",
        "    for x in arr:  # O(n)\n",
        "        print(x)  # O(1)\n",
        "\n",
        "# O(n * log n)\n",
        "def linearithmic(arr):\n",
        "    logi = 1\n",
        "    while logi < len(arr):  # O(log n)\n",
        "        # iterations = len(arr) = 2 ^ logi -> solve for logi -> logi = log(len(arr))\n",
        "        logi *= 2\n",
        "        linear(arr)\n",
        "\n",
        "# O(n * log n)\n",
        "def linearithmic2(arr):\n",
        "    arr.sort()  # O(n * log n)\n",
        "\n",
        "# O (n^2)\n",
        "def quadratic(arr):  # O(n * n * 1) = O(n^2)\n",
        "    for row in range(len(arr)):  # O(n)\n",
        "        for column in range(len(arr)):  # O(n)\n",
        "            print(arr[row][column])  # O(1)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GSnbwdz6zF1L"
      },
      "source": [
        "## Str\n",
        "\n",
        "`str` е поредица от символи. Ще разгледаме:\n",
        "\n",
        "- [str](https://docs.python.org/3/library/stdtypes.html#text-sequence-type-str) методи и\n",
        "- [string](https://docs.python.org/3/library/string.html) често употребявани константи\n",
        "\n",
        "Стринговете в Python са immutable -> Повечето операции са $O(n)$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "9NzRjZ1gzF1L",
        "outputId": "4aa82ca9-c6be-49eb-d8e0-43e6cbcdd4ad"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "🐍 is awesomeͤͤͤͤͤ\n"
          ]
        }
      ],
      "source": [
        "# Python speaks   UTF-8 :) https://en.wikipedia.org/wiki/UTF-8\n",
        "s = '🐍 is awesomeͤͤͤͤͤ'\n",
        "print(s)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "a6_gJy59zF1M",
        "outputId": "805d21e6-7e09-4820-e8ca-1ec12cd5fc3e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "🐍 is awesomeͤͤͤͤͤ -> b'\\xf0\\x9f\\x90\\x8d is awesome\\xcd\\xa4\\xcd\\xa4\\xcd\\xa4\\xcd\\xa4\\xcd\\xa4'\n",
            "От байтове може да се върнем в стринг: 🐍 is awesomeͤͤͤͤͤ\n",
            "🐍 = 🐍\n",
            "b'' е просто списък от uint8: 🐍\n",
            "Дължината на 🐍 e:  4\n",
            "['c', 'o', 'o', 'l', ' ', '🐍']\n"
          ]
        }
      ],
      "source": [
        "s = '🐍 is awesomeͤͤͤͤͤ'\n",
        "# .encode() Конвертира стринг до байтове.\n",
        "# Някой байтове не могат да се представят със символ от азбуката\n",
        "# и използват Hexadecimal Escape Sequence\n",
        "\n",
        "# Често се използва при работа с файлове -\n",
        "# понякога четем и пишем байтове вместо стрингове\n",
        "encoded = s.encode('utf-8')\n",
        "print(f'{s} -> {encoded}')\n",
        "print('От байтове може да се върнем в стринг:', encoded.decode())\n",
        "# 🐍 = \\xf0\\x9f\\x90\\x8d\n",
        "# сложи символ отгоре = '\\xcd'\n",
        "# какво да се сложи отгоре = '\\xa4'\n",
        "\n",
        "# = 🐍 Поредица от байтове се индикира с b''\n",
        "print('🐍 =', b'\\xf0\\x9f\\x90\\x8d'.decode())\n",
        "print(\"b'' е просто списък от uint8:\", bytes(\n",
        "    [0xf0, 0x9f, 0x90, 0x8d]).decode())\n",
        "print('Дължината на 🐍 e: ', len(b'\\xf0\\x9f\\x90\\x8d'))  # len(\\xYY) = 1 byte\n",
        "\n",
        "# Итерирането по стринг работи чрез итериране по символи, не по байтове\n",
        "print([x for x in 'cool 🐍'])\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "5I2cVz7izF1M",
        "outputId": "b7b531d1-6aaf-4512-881b-6f811f7d9701"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Форматирането работи! 🐍 * 🐍 = 🐍²\n"
          ]
        }
      ],
      "source": [
        "print('Форматирането работи! {0} * {1} = {2}'.format('🐍', '🐍', '🐍²'))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "kIUM7zqFzF1M",
        "outputId": "921a041d-a738-41a7-d48f-84bd2adc046d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{букви} = alphabetic\n",
            "{числа} = digit\n",
            "{числа, букви} = alpha-numeric\n",
            "{малки букви} = lowercase\n",
            "{големи букви} = uppercase\n",
            "{празни символи} = space\n"
          ]
        }
      ],
      "source": [
        "if 'самобукви'.isalpha():\n",
        "    print('{букви} = alphabetic')\n",
        "\n",
        "# Можем ли да конвертираме стринга до int?\n",
        "if '1232367457'.isdigit():\n",
        "    print('{числа} = digit')\n",
        "\n",
        "# Бърза проверка дали работим с дума или изречение (изречението има паузи и символи)\n",
        "if '1283912873andLetters'.isalnum():\n",
        "    print('{числа, букви} = alpha-numeric')\n",
        "\n",
        "# Трябва ли да пишем код който разбира от главни букви?\n",
        "if 'малкибукви'.islower():\n",
        "    print('{малки букви} = lowercase')\n",
        "\n",
        "if 'ГОЛЕМИБУКВИ'.isupper():\n",
        "    print('{големи букви} = uppercase')\n",
        "\n",
        "# Използваме при разбиване на стрингове - if space : do X else do Y\n",
        "if '\\t\\n  '.isspace():\n",
        "    print('{празни символи} = space')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "id": "dzPiAk2qzF1M",
        "outputId": "6317fbce-b2d0-427a-c49a-c747e6aca0e6"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "s започва с '🐍 is'\n",
            "is е на индекс 2\n",
            "'e' се среща 2 пъти\n"
          ]
        }
      ],
      "source": [
        "s = '🐍 is awesomeͤͤͤͤͤ'\n",
        "\n",
        "if s.endswith('e'):\n",
        "    print('s завършва на e')  # eͤͤͤ != e\n",
        "\n",
        "if s.startswith('🐍 is'):\n",
        "    print(\"s започва с '🐍 is'\")\n",
        "\n",
        "print('is е на индекс', s.find('is'))  # Индекс по символ, не по байт\n",
        "\n",
        "print(\"'e' се среща\", s.count('e'), 'пъти')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "id": "1mX6oiDNzF1N",
        "outputId": "66113e54-20f3-4986-c00d-1553fab0d221"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "🐍 is awesomeͤͤͤͤͤ\n",
            "Не винаги субституциите работят както ни се иска: 🐍 is много лесен курсͤͤͤͤͤ\n",
            "Но може да сработят с regex: 🐍 is бЪрЗ\n",
            "Може да направим всички символи голем: 🐍 IS AWESOMEͤͤͤͤͤ\n",
            "или малки: THICC -> thicc\n",
            "Да разчистим празните символи '    нещо ми духа '-> 'нещо ми духа'\n"
          ]
        }
      ],
      "source": [
        "import re\n",
        "\n",
        "s = '🐍 is awesomeͤͤͤͤͤ'\n",
        "print(s)\n",
        "\n",
        "print('Не винаги субституциите работят както ни се иска:',\n",
        "      s.replace('awesome', 'много лесен курс'))\n",
        "\n",
        "print('Но може да сработят с regex:', re.sub(r'awesome.*', 'бЪрЗ', s))\n",
        "\n",
        "print('Може да направим всички символи големи:', s.upper())\n",
        "\n",
        "# Често използваме за да оеднаквим символите, A = a и няма защо\n",
        "# да ги третираме различно\n",
        "print('или малки:', 'THICC ->', 'THICC'.lower())\n",
        "\n",
        "# Ако някой въведе \"me@mail.com  \" то очевидно няма спейс в края на мейл\n",
        "# -> strip() -> \"me@mail.com\"\n",
        "print(\"Да разчистим празните символи '    нещо ми духа '-> '\" +\n",
        "      '    нещо ми духа  '.strip() + \"'\")\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "id": "FH_z464vzF1N",
        "outputId": "a43e7c9f-f360-4ebd-caf8-00ac89102dbe"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Удобно е да принтираме списъци: 1, 2, 3, 4, worldwide\n",
            "или да разбиваме стринг на елементи: ['fmi', 'poluchi', 'li?']\n",
            "['kude', 'sym', 'az', 'kude', 'si', 'ti', '']\n"
          ]
        }
      ],
      "source": [
        "# Много подпомага дебъгването и не оставя запетая след последния елемент!!\n",
        "import re\n",
        "print('Удобно е да принтираме списъци:',\n",
        "      ', '.join(['1', '2', '3', '4', 'worldwide']))\n",
        "# При разбиване на стрингове\n",
        "# (данни, които знаем че саразделени с някакъв символ)\n",
        "print('или да разбиваме стринг на елементи:', 'fmi:poluchi:li?'.split(':'))\n",
        "\n",
        "# за по-сложни разбивания - regex (:\n",
        "print(re.split(r',|:|\\?', 'kude:sym,az?kude:si,ti?'))\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-qbF2WBDzF1N"
      },
      "source": [
        "Библиотеката `string` предоставя някои удобни константи"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "id": "TA9KZy4izF1N",
        "outputId": "d05e1b5e-a4d2-4b40-a3e1-2d9aac083c03"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "all letters: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ\n",
            "all lowercase: abcdefghijklmnopqrstuvwxyz\n",
            "all digits as a string: 0123456789\n",
            "all symbols: !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~\n",
            "all whitespaces:  \t\n",
            "\u000b\f b' \\t\\n\\r\\x0b\\x0c'\n"
          ]
        }
      ],
      "source": [
        "import string\n",
        "\n",
        "# Вместо да хардкодваме \"abcdef...\"\n",
        "print('all letters:', string.ascii_letters)\n",
        "print('all lowercase:', string.ascii_lowercase)\n",
        "print('all digits as a string:', string.digits)\n",
        "print('all symbols:', string.punctuation)\n",
        "print('all whitespaces:', string.whitespace, string.whitespace.encode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hPR3kNeRzF1N"
      },
      "source": [
        "## Int\n",
        "\n",
        "Python няма ограничение за големината на int (C++ long long има ограничение $2^{63}-1$). Но операциите с големи числа са бавни - не са $O(1)$, а $O(log(number)) = O(number\\;of\\;digits)$\n",
        "\n",
        "Когато стойността надвиши $2^{63}-1$ числата се обръщат в BigInt.\n",
        "\n",
        "[https://www.codementor.io/@arpitbhayani/how-python-implements-super-long-integers-12icwon5vk](https://www.codementor.io/@arpitbhayani/how-python-implements-super-long-integers-12icwon5vk)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "id": "mf9yvoxGzF1N",
        "outputId": "28e28bd1-27e0-4deb-a8c6-6fbb49eab706"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "CPU times: user 4.23 s, sys: 22.9 ms, total: 4.25 s\n",
            "Wall time: 4.27 s\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "\n",
        "result = 1\n",
        "for x in range(1, 100000):\n",
        "    result *= x\n",
        "# Същият код на C++ минава за total: 0.001 s.\n",
        "# Но не връща верен отговор :)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "id": "TOrAxN5IzF1O",
        "outputId": "ec0f4682-a6ad-481c-9d59-655253684106"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "int is 28 bytes\n",
            "10^1000 is 468 bytes\n",
            "float is 24 bytes\n"
          ]
        }
      ],
      "source": [
        "import sys\n",
        "\n",
        "print('int is {0} bytes'.format(sys.getsizeof(int(1))))\n",
        "print('10^1000 is {0} bytes'.format(sys.getsizeof(int(10**1000))))\n",
        "print('float is {0} bytes'.format(sys.getsizeof(float(1))))\n",
        "# float има прецизност като double в C++ (~14 знака след запетаята)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "id": "GbzUmc7hzF1O",
        "outputId": "0e4ef276-07e2-42c6-cb4e-217cd767748e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3.1428571428571428571428571428571428571428571428571428571\n"
          ]
        }
      ],
      "source": [
        "# За по голяма прицизност може да използваме `decimal` модула\n",
        "# По дефолт има прецизност 28 знака след запетаята,\n",
        "# но може да му дадем повече :)\n",
        "from decimal import *\n",
        "getcontext().prec = 56\n",
        "print(Decimal(22) / Decimal(7))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "id": "iY3Aoh_AzF1O",
        "outputId": "e42cb94c-e999-4f4c-ac49-9690ed2b21ea"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Стринг -> int: 42\n",
            "Конвертиране от други бройни системи, освен base10: 255\n",
            "Премахване на знаците след десетичната запетая -5 5\n",
            "Абсолютна стойност(-5) = 5\n"
          ]
        }
      ],
      "source": [
        "# Начин на използване\n",
        "\n",
        "print('Стринг -> int:', int('42'))\n",
        "print('Конвертиране от други бройни системи, освен base10:', int('ff', 16))\n",
        "print('Премахване на знаците след десетичната запетая', int(-5.2), int(5.2))\n",
        "print('Абсолютна стойност(-5) =', abs(-5))\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W7Z5ODCuzF1O"
      },
      "source": [
        "## Math"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "id": "Z0L60_J2zF1O",
        "outputId": "83e6efc9-05d4-4be7-c32f-0f815e77522c"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Закръгляне на горе 2.2 -> 3\n",
            "Закръгляне на долу 2.7 -> 2\n",
            "Преброяване на битовете на числото 257 = 9\n",
            "Преброяване на цифрите на числото 14532 = 5\n",
            "Най-голям общ делител на 35 и 15 = 5\n",
            "Можем да смятаме inverse елемента по модул 15^-1 mod 26 = 7\n",
            "N choose K -> 10 choose 2 = 45\n"
          ]
        }
      ],
      "source": [
        "import math\n",
        "\n",
        "print('Закръгляне нагоре 2.2 ->', math.ceil(2.2))\n",
        "print('Закръгляне надолу 2.7 ->', math.floor(2.7))\n",
        "\n",
        "# Може да правим побитово итериране на  числото\n",
        "print('Преброяване на битовете на числото 257 =', math.ceil(math.log2(257)))\n",
        "# Полезно при построяване на Trie/radix sort/заделяне на hashmap\n",
        "print('Преброяване на цифрите на числото 14532 =', math.ceil(math.log10(14532)))\n",
        "\n",
        "# Математически важни функции\n",
        "print('Най-голям общ делител на 35 и 15 =', math.gcd(35, 15))\n",
        "print('Можем да смятаме inverse елемента по модул 15^-1 mod 26 =', pow(15, -1, 26))\n",
        "\n",
        "# Комбинаторика (често се среща в задачи, но има и други)\n",
        "print('N choose K -> 10 choose 2 =', math.comb(10, 2))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "id": "uL01Ei-WzF1O",
        "outputId": "b4b42f5c-b116-4c60-8bb4-13854956d2e2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Not a Number = nan\n",
            "Infinity = inf\n",
            "-Infinity = -inf\n",
            "π =  3.141592653589793\n",
            "e =  2.718281828459045\n"
          ]
        }
      ],
      "source": [
        "# Специални стойности на float:\n",
        "# Not a Number (полезно като дъно на стек)\n",
        "print('Not a Number =', math.nan)\n",
        "# Infinity (полезно като последен елемент на масив,\n",
        "# нещо като терминираща нула в C++)\n",
        "print('Infinity =', math.inf)\n",
        "# -Infinity\n",
        "print('-Infinity =', -math.inf)\n",
        "\n",
        "# Константи\n",
        "print('π = ', math.pi)\n",
        "print('e = ', math.e)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eDkYa_dKzF1O"
      },
      "source": [
        "`math` модулът има още много функции на които няма да се спираме, защото не се използват често:\n",
        "- Тригонометрични функции\n",
        "- Хиперболични функции\n",
        "- Гама функция\n",
        "- Конвертиране между градуси и радиани\n",
        "- Други"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pNaUcmFzzF1O"
      },
      "source": [
        "## List\n",
        "\n",
        "Саморазширяващ се списък/масив от елементи. Въпреки името list, структурата е динамичен масив, а не свързан списък."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "id": "MKB8-uuVzF1O",
        "outputId": "3ca4f6db-2b9b-4323-d984-dc8b281250f4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Списък с 10 елемента: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
            "Празен списък: []\n",
            "До момента имаме: [-2, -1, 1]\n",
            "Може да обърнем списъка [1, -1, -2]\n",
            "И да го сортираме [-2, -1, 1]\n",
            "pop премахва последния елемент и го връща [-2, -1] 1\n"
          ]
        }
      ],
      "source": [
        "arr = [0] * 10  # инициализиране на списък с 10 елемента O(n)\n",
        "print('Списък с 10 елемента:', arr)\n",
        "\n",
        "arr = list()  # празен списък O(1)\n",
        "arr.clear()  # O(1) еквивалентно на ' = list()'\n",
        "print('Празен списък:', arr)\n",
        "\n",
        "# O(1*) за разлика от конкатенацията на стрингове ('abc' + 'd') която е O(n)\n",
        "arr.append(1)\n",
        "arr.insert(0, -1)  # O(n)\n",
        "arr = [-2] + arr  # O(n) еквивалентно на горното АКО елементите НЕ СА list\n",
        "print('До момента имаме:', arr)\n",
        "\n",
        "arr.reverse()  # O(n)\n",
        "print('Може да обърнем списъка', arr)\n",
        "\n",
        "arr.sort()  # O(n * log n)\n",
        "print('И да го сортираме', arr)\n",
        "\n",
        "last_element = arr.pop()  # O(1)\n",
        "print('pop премахва последния елемент и го връща', arr, last_element)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KthpYgh0zF1O"
      },
      "source": [
        "Примери с често използвани техники върху `list`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "id": "6PyJwoVMzF1P",
        "outputId": "941c7277-0dcd-47a4-f6b5-c7ec4fc159fb"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "daddy elon\n",
            "elon daddy\n",
            "tuples = [(1, 'daddy'), (2, 'elon')], tuples_copy = []\n"
          ]
        }
      ],
      "source": [
        "# Сортиране на списък с обекти\n",
        "tuples = [(2, 'elon'), (1, 'daddy')]\n",
        "\n",
        "# Ако вместо tuples имаме обекти използваме obj.field, вместо x[1]\n",
        "tuples.sort(key=lambda x: (x[1]))\n",
        "\n",
        "# ламбда функцията връща tuple от елементи в каквато последователност\n",
        "# трябва да се сравняват.\n",
        "# Ако 0-левия елемент е един и същ, пробвай 1вия.\n",
        "# Ако първият елемент е един и същ, пробвай 2рия и тн.\n",
        "print(' '.join(list(x[1] for x in tuples)))\n",
        "\n",
        "# Обръщане на списък\n",
        "reversed_tuples = tuples[::-1]  # създава нов списък\n",
        "print(' '.join(list(x[1] for x in reversed_tuples)))\n",
        "\n",
        "# Копиране на списък\n",
        "tuples_copy = tuples[::]\n",
        "tuples_copy.clear()\n",
        "print(f'{tuples = }, {tuples_copy = }')\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LZNSMZRfzF1P"
      },
      "source": [
        "## Array \n",
        "\n",
        "`array` предоставя по-ефективно използване на паметта от `list`. Повече прилича на стандартните масиви в други езици. Добавянето на елемент в края на `array` е $O(1)$.\n",
        "\n",
        "Има същите функционалности като `list`.\n",
        "\n",
        "При инициализиране трябва да окажем типа на елементите в списъка.\n",
        "\n",
        "Ако се е стигнало до използване на по-оптимизирани структури в Python най-добре да използваме някоя библиотека като `numpy`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 18,
      "metadata": {
        "id": "OpkE2MKCzF1P"
      },
      "outputs": [],
      "source": [
        "%%capture\n",
        "# %%capture is a jupyter instruction to hide output\n",
        "from array import array\n",
        "\n",
        "array('l')  # array<32 bit int>\n",
        "array('u', 'hello \\u2641')  # array<unicode character>\n",
        "array('d', [1.0, 2.0, 3.14])  # array<double>\n",
        "array('I', [1, 2, 3])  # array<unsigned 16 bit int>\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HXxOPJuXzF1P"
      },
      "source": [
        "## Dict\n",
        "\n",
        "`dict` е питонската имплементация на Hash-Table. Повечето операции с `dict` са $O(1)$. Изключение правят операциите за обработка на всички елементи, които са $O(n)$.\n",
        "\n",
        "Елементите на `dict` са `key`-`value` (ключ - стойност). Ключът задължително трябва да е от тип, който може да се хешира, стойността може да е всякаква.\n",
        "\n",
        "Забележка: Казваме, че операциите са $O(1)$, но всъщност зависят от размера на ключа. Обикновено ключовете са малки по размер в паметта и за това на повечето места в литературата се казва че операциите са $O(1)$, но ако ключовете ни са стрингове с дължина 100,000 символа, то сложността на операциите не е точно $O(1)$ :)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "metadata": {
        "id": "J8SJEN0KzF1P",
        "outputId": "41300286-73d2-45e5-eacf-dfb7e8aba81a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "dict с 1 елемент my_dict = {'is big': 'not'}\n",
            "празен dict след като изтрихме ключа \"is big\" my_dict = {}\n"
          ]
        },
        {
          "ename": "KeyError",
          "evalue": "'non-existent key'",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
            "Cell \u001b[0;32mIn [19], line 10\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[39mprint\u001b[39m(\u001b[39m'\u001b[39m\u001b[39mпразен dict след като изтрихме ключа \u001b[39m\u001b[39m\"\u001b[39m\u001b[39mis big\u001b[39m\u001b[39m\"\u001b[39m\u001b[39m'\u001b[39m, \u001b[39mf\u001b[39m\u001b[39m'\u001b[39m\u001b[39m{\u001b[39;00mmy_dict \u001b[39m= }\u001b[39;00m\u001b[39m'\u001b[39m)\n\u001b[1;32m      8\u001b[0m \u001b[39m# Ако се опитаме да достъпим или изтрием ключ който не\u001b[39;00m\n\u001b[1;32m      9\u001b[0m \u001b[39m# съществува ще гръмнем с KeyError\u001b[39;00m\n\u001b[0;32m---> 10\u001b[0m \u001b[39mdel\u001b[39;00m my_dict[\u001b[39m'\u001b[39m\u001b[39mnon-existent key\u001b[39m\u001b[39m'\u001b[39m]\n",
            "\u001b[0;31mKeyError\u001b[0m: 'non-existent key'"
          ]
        }
      ],
      "source": [
        "my_dict = {}  # Инициализираме празен dict\n",
        "my_dict = dict()  # dict() == {}\n",
        "\n",
        "my_dict['is big'] = 'not'\n",
        "print('dict с 1 елемент', f'{my_dict = }')\n",
        "del my_dict['is big']  # del изтрива елемент\n",
        "print('празен dict след като изтрихме ключа \"is big\"', f'{my_dict = }')\n",
        "# Ако се опитаме да достъпим или изтрием ключ който не\n",
        "# съществува ще гръмнем с KeyError\n",
        "del my_dict['non-existent key']\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 20,
      "metadata": {
        "id": "7x5tjpYIzF1P",
        "outputId": "868365b6-d5b8-4fa7-cef7-c33ec4ab8579"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "for x in dict: ['Gosho na pochivka', 'Gosho na fmi']\n",
            "for x in dict.keys(): ['Gosho na pochivka', 'Gosho na fmi']\n",
            "for x in dict.values(): [25, 11001]\n",
            "for x in dict.items(): [('Gosho na pochivka', 25), ('Gosho na fmi', 11001)]\n"
          ]
        }
      ],
      "source": [
        "# Итериране по dict\n",
        "person_age = {\n",
        "    'Gosho na pochivka': 25,\n",
        "    'Gosho na fmi': 11001,\n",
        "}\n",
        "\n",
        "result = []\n",
        "for x in person_age:  # == .keys()\n",
        "    result.append(x)\n",
        "print('for x in dict:', result)\n",
        "\n",
        "result = []\n",
        "for x in person_age.keys():\n",
        "    result.append(x)\n",
        "print('for x in dict.keys():', result)\n",
        "\n",
        "result = []\n",
        "for x in person_age.values():\n",
        "    result.append(x)\n",
        "print('for x in dict.values():', result)\n",
        "\n",
        "result = []\n",
        "for x in person_age.items():\n",
        "    result.append(x)\n",
        "print('for x in dict.items():', result)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "metadata": {
        "id": "C8arl9izzF1P",
        "outputId": "66e74d21-de7c-4e87-f850-aece0b17a6b5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{'ami': 'nali ne mojelo da se promenq e bai xy*', 'pari': 'nali ne mojelo da se promenq e bai xy*', 'nema': 'nali ne mojelo da se promenq e bai xy*'}\n"
          ]
        },
        {
          "ename": "RuntimeError",
          "evalue": "dictionary changed size during iteration",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mRuntimeError\u001b[0m                              Traceback (most recent call last)",
            "Cell \u001b[0;32mIn [21], line 13\u001b[0m\n\u001b[1;32m      9\u001b[0m     palindromes[x] \u001b[39m=\u001b[39m \u001b[39m'\u001b[39m\u001b[39mnali ne mojelo da se promenq e bai xy*\u001b[39m\u001b[39m'\u001b[39m\n\u001b[1;32m     11\u001b[0m \u001b[39mprint\u001b[39m(palindromes)\n\u001b[0;32m---> 13\u001b[0m \u001b[39mfor\u001b[39;00m x \u001b[39min\u001b[39;00m palindromes:\n\u001b[1;32m     14\u001b[0m     \u001b[39mdel\u001b[39;00m palindromes[x]\n",
            "\u001b[0;31mRuntimeError\u001b[0m: dictionary changed size during iteration"
          ]
        }
      ],
      "source": [
        "# По време на итериране не е позволено да променяме dict\n",
        "palindromes = {\n",
        "    'ami': 'ima',\n",
        "    'pari': 'irap',\n",
        "    'nema': 'amen',\n",
        "}\n",
        "\n",
        "for x in palindromes:\n",
        "    palindromes[x] = 'nali ne mojelo da se promenq e bai xy*'\n",
        "\n",
        "print(palindromes)\n",
        "\n",
        "for x in palindromes:\n",
        "    del palindromes[x]  # промяна върху ключовете не работи :(\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 22,
      "metadata": {
        "id": "P1InGHRuzF1P",
        "outputId": "81caf4e7-651f-4db1-e5a9-dcac0dd895e3"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "въпреки грешката на предишната стъпка изтрихме 1 ключ (на рандъм) {'pari': 'nali ne mojelo da se promenq e bai xy*', 'nema': 'nali ne mojelo da se promenq e bai xy*'}\n",
            "{'nema': 'shte si napravq moi dict togava'}\n"
          ]
        }
      ],
      "source": [
        "print('въпреки грешката на предишната стъпка изтрихме 1 ключ (на рандъм)', palindromes)\n",
        "\n",
        "# Тъй като не може да променяме dict докато итерираме ще трябва да създадем нов\n",
        "changed = {k: 'shte si napravq moi dict togava'\n",
        "           for k, _ in palindromes.items() if k != 'pari'}\n",
        "print(changed)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача\n",
        "\n",
        "my_list = [1,2,3,4,5]\n",
        "my_dict = {1:'a', 2:'b', 3:'c', 4:'d', 5:'e'}\n",
        "\n",
        "# Коя операция е по-бърза\n",
        "if 4 in my_list:\n",
        "    print('list')\n",
        "if 4 in my_dict:\n",
        "    print('dict')\n",
        "\n",
        "\"\"\"Изпълни клетката за хинт\"\"\"\n",
        "import base64\n",
        "print(base64.b64decode(\n",
        "    '0J7Qv9C10YDQsNGC0L7RgNGK0YIgaW4g0LLRitGA'\n",
        "    '0YXRgyBsaXN0INC1IE8obiksINCwINCy0YrRgNGF'\n",
        "    '0YMgZGljdCDQtSBPKDEqKQ=='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VBlkx81zzF1P"
      },
      "source": [
        "### Defaultdict\n",
        "\n",
        "`defaultdict` живее в модула `collections`. Има същата функционалност като `dict`, но при инициализация трябва да окажем от какъв тип ще са стойностите. При достъпване на ключ, който не съществува, ще се създаде ключа и стойност - дефолтен обект от типа, който задаваме при инициализация.\n",
        "\n",
        "Обикновено го използваме за удобство - не е нужно да проверяваме дали стойността зад някой ключ е инициализирана."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 23,
      "metadata": {
        "id": "PlRGD077zF1P",
        "outputId": "71e49b9e-c17c-4444-a87d-7950b5f59ffe"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "defaultdict(<class 'list'>, {})\n",
            "дори само с достъпване на ключа създаваме дефолтен обект defaultdict(<class 'list'>, {'what': []})\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "defaultdict(list,\n",
              "            {'t': [0, 11],\n",
              "             'h': [1],\n",
              "             'i': [2, 5, 13],\n",
              "             's': [3, 6, 10],\n",
              "             ' ': [4, 7, 9],\n",
              "             'a': [8],\n",
              "             'r': [12],\n",
              "             'n': [14],\n",
              "             'g': [15]})"
            ]
          },
          "execution_count": 23,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from collections import defaultdict\n",
        "\n",
        "my_default_dict = defaultdict(list)\n",
        "print(my_default_dict)\n",
        "my_default_dict['what']\n",
        "print('дори само с достъпване на ключа създаваме дефолтен обект', my_default_dict)\n",
        "\n",
        "del my_default_dict['what']\n",
        "for index, char in enumerate('this is a string'):\n",
        "    my_default_dict[char].append(index)  # Това ще изгърми с нормален dict\n",
        "\n",
        "my_default_dict\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача (advanced)\n",
        "# Как може да имплементираме Trie чрез defaultdict\n",
        "\n",
        "import base64\n",
        "print(base64.b64decode(\n",
        "    'ZGVmIHRyaWUoKToKICAgIHJldHVybi'\n",
        "    'BkZWZhdWx0ZGljdCh0cmllKQo='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-hyut4oQzF1P"
      },
      "source": [
        "### Counter\n",
        "\n",
        "`Counter` е още един под-клас на `dict`. При инициализация може да се подаде колекция (или друг обект който може да се итерира и елементите му могат да се хешират), която бива итерирана и елементите ѝ се преброяват.\n",
        "Елементите на колекцията стават ключове, а стойностите са колко пъти даден елемент е срещнат в колекцията."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 24,
      "metadata": {
        "id": "i0pJSfYAzF1P",
        "outputId": "ade45845-db14-4bf2-8ff2-806e0e1e9b60"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "Counter({'s': 3,\n",
              "         't': 6,\n",
              "         'r': 2,\n",
              "         'i': 5,\n",
              "         'n': 3,\n",
              "         'g': 1,\n",
              "         ' ': 6,\n",
              "         \"'\": 2,\n",
              "         'a': 2,\n",
              "         'c': 2,\n",
              "         'o': 2,\n",
              "         'l': 3,\n",
              "         'e': 3,\n",
              "         ',': 1,\n",
              "         'b': 2,\n",
              "         'u': 1})"
            ]
          },
          "execution_count": 24,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "from collections import Counter\n",
        "\n",
        "Counter('string isn\\'t a collection, but it\\'s iterable')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача\n",
        "# Напишете функция която извежда най-често срещаните букви на даден стринг\n",
        "\n",
        "import base64\n",
        "print(base64.b64decode(\n",
        "    'ZGVmIGNvdW50KHMpOgogICAgY291bnRzID0gbGl'\n",
        "    'zdChDb3VudGVyKHMpLml0ZW1zKCkpCiAgICBjb3'\n",
        "    'VudHMuc29ydChrZXk9bGFtYmRhIHg6IC14WzFdK'\n",
        "    'QogICAgcHJpbnQoY291bnRzKQo='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yXg-HT7DzF1P"
      },
      "source": [
        "## Set\n",
        "\n",
        "`set` е `dict`, който има само ключове, стойностите не ни интересуват. Добавяне/премахване/проверка дали елемент е в сет-а се случва за $O(1)$\n",
        "\n",
        "`set` се използва по-рядко от `dict`, и основно за да намерим уникалните елементи на колекция."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 25,
      "metadata": {
        "id": "0QoSD9_jzF1P",
        "outputId": "70bfb791-edfa-4b6a-944f-c88ab483e624"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "инициализация от колекция {1, 2, 3}\n",
            "елемент, който вече е в сета няма да се добави отново {1, 2, 3}\n",
            "Може да обединим 2 сета {1, 2, 3, 4}\n",
            "Може да вземем само общите елементи {2, 3}\n",
            "Може да вземем елементите които не са общи {1, 4}\n",
            "Може да проверим дали даден елемент е в сета: 5 in [1,2,3]? False\n"
          ]
        }
      ],
      "source": [
        "uniques = set()  # няма по-кратък начин за инициализране на сет, както {} за dict\n",
        "# Може директно да го инициализираме от колекция\n",
        "uniques = set([1, 2, 3, 3, 3, 3, 3, 3])\n",
        "print('инициализация от колекция', uniques)\n",
        "\n",
        "uniques.add(1)  # добавяме елемент\n",
        "print('елемент, който вече е в сета няма да се добави отново', uniques)\n",
        "\n",
        "print('Може да обединим 2 сета', set([1, 2, 3]).union(set([2, 3, 4])))\n",
        "print('Може да вземем само общите елементи', set([1, 2, 3]) & set([2, 3, 4]))\n",
        "print('Може да вземем елементите които не са общи',\n",
        "      set([1, 2, 3]) ^ set([2, 3, 4]))\n",
        "print('Може да проверим дали даден елемент е в сета: 5 in [1,2,3]?', 5 in set(\n",
        "    [1, 2, 3]))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "hhJGLERvzF1Q",
        "outputId": "57c172c2-5f05-4b67-8f0a-3c5340eb93f1"
      },
      "outputs": [],
      "source": [
        "# Задача: колко различни букви са използвани в следния стринг\n",
        "# 'The quick brown fox jumps over the lazy dog'\n",
        "\n",
        "import base64\n",
        "print(base64.b64decode(\n",
        "    'bGVuKHNldCgKICAgICdUaGUgcXVpY2sgYnJvd24gZm9'\n",
        "    '4IGp1bXBzIG92ZXIgdGhlIGxhenkgZG9nJwogICAgLm'\n",
        "    'xvd2VyKCkKICAgIC5yZXBsYWNlKCcgJywgJycpCikpC'\n",
        "    'g=='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8cmvUbtzzF1Q"
      },
      "source": [
        "### Frozenset\n",
        "\n",
        "`frozenset` = immutable `set`. Immutability носи плюсове и минуси:\n",
        "- (+) може да хешираме сета (да го използваме като ключ в `dict` или да го добавим в друг `set`)\n",
        "- (-) не може да го променяме (да добавяме/премахваме елементи)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 26,
      "metadata": {
        "id": "ripUGPf6zF1Q",
        "outputId": "fe88ce8e-e667-4f5c-acc2-279ec0896f95"
      },
      "outputs": [
        {
          "ename": "TypeError",
          "evalue": "unhashable type: 'set'",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "Cell \u001b[0;32mIn [26], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m my_dict \u001b[39m=\u001b[39m {\n\u001b[1;32m      2\u001b[0m     \u001b[39mset\u001b[39m([\u001b[39m1\u001b[39m, \u001b[39m2\u001b[39m, \u001b[39m3\u001b[39m]): \u001b[39m'\u001b[39m\u001b[39msets are unhashable, trust me\u001b[39m\u001b[39m'\u001b[39m,\n\u001b[1;32m      3\u001b[0m }\n",
            "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'set'"
          ]
        }
      ],
      "source": [
        "my_dict = {\n",
        "    set([1, 2, 3]): 'sets are unhashable, trust me',\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 27,
      "metadata": {
        "id": "QAFHk515zF1Q",
        "outputId": "085a88f1-150b-401b-8428-eb2a6621ce03"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{frozenset({1, 2, 3}): 'my password',\n",
              " frozenset({'a',\n",
              "            'c',\n",
              "            'e',\n",
              "            'h',\n",
              "            'r',\n",
              "            's',\n",
              "            't'}): 'ако подадем string, ще конструираме set от буквите'}"
            ]
          },
          "execution_count": 27,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "numbers = set([1, 2, 3])\n",
        "\n",
        "my_dict = {\n",
        "    frozenset(numbers): 'my password',\n",
        "    frozenset('characters'): 'ако подадем string, ще конструираме set от буквите'\n",
        "}\n",
        "my_dict\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PKVd59WqzF1Q"
      },
      "source": [
        "## Stack\n",
        "\n",
        "`stack` (стак/стек) е LIFO (Last In First Out) структура, която ни позволява бърз достъп до последния добавен елемент. В Python няма клас `Stack`, защото `list` има всички необходими методи.\n",
        "\n",
        "![](https://i.imgur.com/IDr4JQL.png)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 28,
      "metadata": {
        "id": "3EL0w27_zF1Q",
        "outputId": "61dbbe92-0091-4692-d65f-7616029cb216"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Сумата на първите 10 елемента е:  945\n"
          ]
        }
      ],
      "source": [
        "stack = []\n",
        "for x in range(100):\n",
        "    stack.append(x)\n",
        "\n",
        "first10 = 0\n",
        "for i in range(10):\n",
        "    first10 += stack.pop()  # Достъп до последния елемент е О(1)\n",
        "\n",
        "print('Сумата на първите 10 елемента е: ', first10)  # sum(100 до 90) = 945\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача\n",
        "# Имплементирайте клас, който поддържа следните операции\n",
        "# - O(1) push: добавя нов елемент в стека\n",
        "# - O(1) топ: връща последния вкаран елемент\n",
        "# - O(1) pop: премахва последния вкаран елемент\n",
        "# - O(1) get_min: връща минималният елемент от всички в стека\n",
        "\n",
        "print(base64.b64decode(\n",
        "    'Y2xhc3MgTWluU3RhY2s6CiAgICBkZWYgX19pbml0X18oc2VsZik6CiAgIC'\n",
        "    'AgICAgc2VsZi5kYXRhID0gW10KICAgICAgICBzZWxmLm1pbnMgPSBbXQoKI'\n",
        "    'CAgIGRlZiBwdXNoKHNlbGYsIHg6IGludCkgLT4gTm9uZToKICAgICAgICBz'\n",
        "    'ZWxmLmRhdGEuYXBwZW5kKHgpCiAgICAgICAgaWYgbGVuKHNlbGYubWlucyk'\n",
        "    'gPiAwOgogICAgICAgICAgICBzZWxmLm1pbnMuYXBwZW5kKG1pbihzZWxmLm'\n",
        "    '1pbnNbLTFdLCB4KSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBzZWxmL'\n",
        "    'm1pbnMuYXBwZW5kKHgpCgogICAgZGVmIHBvcChzZWxmKSAtPiBOb25lOgog'\n",
        "    'ICAgICAgIHNlbGYuZGF0YS5wb3AoKQogICAgICAgIHNlbGYubWlucy5wb3A'\n",
        "    'oKQoKICAgIGRlZiB0b3Aoc2VsZikgLT4gaW50OgogICAgICAgIHJldHVybi'\n",
        "    'BzZWxmLmRhdGFbLTFdCgogICAgZGVmIGdldF9taW4oc2VsZikgLT4gaW50O'\n",
        "    'gogICAgICAgIHJldHVybiBzZWxmLm1pbnNbLTFdCg=='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MEmPVw2mzF1Q"
      },
      "source": [
        "## Queue\n",
        "\n",
        "`queue` е thread-safe имплементация на опашка (FIFO). Може да я създадем с ограничен размер `Queue(maxsize=42)` - ако се напълни и се пробваме да добавим нов елемент ще се блокира нишката. `maxsize=0` означава че няма лимит и ще се разширява докато имаме памет.\n",
        "\n",
        "Ако работим в multithreaded среда, то операциите като `qsize()`, `empty()`, `full()` и повечето други нямат гаранции, че връщат винаги точен резултат. Резултатът е близък до точен, но няма гаранция.\n",
        "\n",
        "Пример: Ако имаме опашка която е пълна и от 1 нишка извикаме `full()` докато се изпълнява `full` може някоя друга нишка да извика `get()` и да премахне елемент - съответно ще получим `True` когато трябва да е `False`.\n",
        "\n",
        "![](https://i.imgur.com/c8rMyYo.png)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 29,
      "metadata": {
        "id": "PBdncs9bzF1Q",
        "outputId": "91b0a543-6f66-424a-9eb4-8202f1d6961a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Елементите ги борим с qsize:  100\n",
            "Сумата на всички елементи е:  4950\n",
            "Сумата на първите 10 елемента е:  45\n"
          ]
        }
      ],
      "source": [
        "import queue\n",
        "\n",
        "que = queue.Queue()\n",
        "for x in range(100):\n",
        "    que.put(x)\n",
        "\n",
        "print('Елементите ги борим с qsize: ', que.qsize())\n",
        "\n",
        "total = 0\n",
        "while not que.empty():  # Работим на 1 нишка така че това е детерминистично\n",
        "    total += que.get()\n",
        "\n",
        "print('Сумата на всички елементи е: ', total)\n",
        "\n",
        "for x in range(100):\n",
        "    que.put(x)\n",
        "\n",
        "first10 = 0\n",
        "for i in range(10):\n",
        "    first10 += que.get()\n",
        "\n",
        "print('Сумата на първите 10 елемента е: ', first10)  # sum(1 до 10) = 45\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YxmJ5wyNzF1Q"
      },
      "source": [
        "## PriorityQueue\n",
        "\n",
        "Какво правим ако искаме опашка, но елементите да са поддедени по някакъв приоритет, не по реда в който ги добавяме? - тадаа `PriorityQueue` 🎉\n",
        "\n",
        "`PriorityQueue` предоставя добавяне/премахване на елемент за $O(logn)$ и достъп до най-малкия елемент за $O(1)$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 30,
      "metadata": {
        "id": "Z78Go_J9zF1Q",
        "outputId": "db33e9ad-db0d-46eb-8bb5-2081205b66d6"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Разбъркваме числата с random.shuffle() [1, 9, 7, 4, 10, 2, 6, 3, 5, 8]\n",
            "Данните не са подредени в реда в който ги добавяме, но 1 винаги е в началото: [1, 3, 2, 4, 8, 7, 6, 9, 5, 10]\n",
            "Приоритетната опашка връща елементите от най-малък към най-голям [1, 2, 3]\n"
          ]
        }
      ],
      "source": [
        "import queue\n",
        "import random\n",
        "\n",
        "numbers = list(range(1, 11))  # [1, 2, ... 10]\n",
        "random.shuffle(numbers)\n",
        "print('Разбъркваме числата с random.shuffle()', numbers)\n",
        "\n",
        "que = queue.PriorityQueue()\n",
        "for x in numbers:\n",
        "    que.put(x)\n",
        "print('Данните не са подредени в реда в който ги добавяме, но 1 винаги е в началото:',\n",
        "      que.queue)\n",
        "\n",
        "top3 = []\n",
        "for i in range(3):\n",
        "    top3.append(que.get())\n",
        "\n",
        "print('Приоритетната опашка връща елементите от най-малък към най-голям', top3)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6KrM-XAHzF1Q"
      },
      "source": [
        "За съжаление не е възможно да използваме custom функция за сравнение за да направим Max Heap.\n",
        "\n",
        "Има 2 начина да решим такава задача, единият е да създаваме клас, който да имплементира `__lt__`/`__gt__`, и `__eq__`.\n",
        "Вторият ще разгледаме в следващата клетка.\n",
        "\n",
        "But you know - if you like it hard I won't stop you - https://stackoverflow.com/questions/57487170/is-it-possible-to-pass-a-comparator-to-a-priorityqueue-in-python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача\n",
        "# Как може да използваме вградения клас PriorityQueue като Max Heap, вместо Min Heap\n",
        "\n",
        "print(base64.b64decode(\n",
        "    '0JDQutC+INC40LzQsNC80LUg0YfQuNGB0LvQsNGC0LAgW'\n",
        "    'zEsMiwzLDQsNV0g0LrQvtC1INC1INC90LDQuS3QvNCw0L'\n",
        "    'vQutC+0YLQvj8g0JDQvNC4INCw0LrQviDQuNC80LDQvNC'\n",
        "    '1IFstMSwtMiwtMywtNCwtNV0/Cg=='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rSpC10dgzF1Q"
      },
      "source": [
        "## heapq\n",
        "\n",
        "`heapq` предоставя основните методи за работа с приоритетни опашки поотделно. Тоест, не е нужно да ползваме цялата функционалност на `PriorityQueue`, а може да използваме само 1 от методите - например `heapq.heapify`.\n",
        "\n",
        "tl;dr как работи приоритетна опашка?\n",
        "\n",
        "1. Ковертираме произволен масив до `heapq.heapify()` $O(n)$\n",
        "2. Ако искаме да добавим елемент използваме `heapq.heappush()` $O(log n)$\n",
        "3. Ако искаме да извадим елемент използваме `heapq.heappop()` $O(log n)$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 31,
      "metadata": {
        "id": "0drKc_aLzF1Q",
        "outputId": "9ae57aed-c157-4285-fced-3bbda3bd167a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Разбъркваме числата с random.shuffle() [4, 2, 9, 5, 3, 8, 1, 7, 10, 6]\n",
            "Данните не са подредени в реда в който ги вкарваме, но 1 винаги е в началото: [1, 2, 4, 5, 3, 8, 9, 7, 10, 6]\n",
            "0 винаги е в началото: [0, 1, 4, 5, 2, 8, 9, 7, 10, 6, 3]\n",
            "Приоритетната опашка връща елементите от най-малък към най-голям [0, 1, 2]\n"
          ]
        }
      ],
      "source": [
        "import heapq\n",
        "import random\n",
        "\n",
        "numbers = list(range(1, 11))  # [1, 2, ... 10]\n",
        "random.shuffle(numbers)\n",
        "print('Разбъркваме числата с random.shuffle()', numbers)\n",
        "\n",
        "heapq.heapify(numbers)  # по-бързо от добавянето на елементи 1 по 1\n",
        "print('Данните не са подредени в реда в който ги вкарваме, но 1 винаги е в началото:',\n",
        "      numbers)\n",
        "\n",
        "# Добавянето на нов по-малък елемент ще го постави в началото\n",
        "heapq.heappush(numbers, 0)\n",
        "print('0 винаги е в началото:', numbers)\n",
        "\n",
        "top3 = []\n",
        "for i in range(3):\n",
        "    top3.append(heapq.heappop(numbers))\n",
        "\n",
        "print('Приоритетната опашка връща елементите от най-малък към най-голям', top3)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IyXpdxAdzF1R"
      },
      "source": [
        "## deque\n",
        "\n",
        "Ако ни трябва опашка + стек, тоест искаме $O(1*)$ за добавяне/премахване на елемент в началото използваме `deque`. Обикновено се имплементира върху Circular Array."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 32,
      "metadata": {
        "id": "Dm1D3f04zF1R",
        "outputId": "4af53349-fe0f-4a4b-d469-bc3bee4b833d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "deque(['опашка ли съм', '¿?', 'ʞǝꓕɔ иѵи'])\n",
            "deque(['у лево', 'опашка ли съм', '¿?', 'ʞǝꓕɔ иѵи', 'у десно', 'у десно (1)'])\n",
            "последният елемент за О(1): у десно (1)\n",
            "първият елемент за О(1): у лево\n"
          ]
        }
      ],
      "source": [
        "from collections import deque\n",
        "\n",
        "deq = deque(['опашка ли съм', 'ʞǝꓕɔ иѵи'])\n",
        "deq.insert(1, '¿?')  # Добавянето на елемент на произволна позиция е О(n)\n",
        "print(deq)\n",
        "\n",
        "deq.append('у десно')\n",
        "deq.append('у десно (1)')\n",
        "deq.appendleft('у лево')\n",
        "\n",
        "print(deq)\n",
        "print('последният елемент за О(1):', deq.pop())\n",
        "print('първият елемент за О(1):', deq.popleft())\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Интересно приложение на deque е имплементирането на round robin\n",
        "def roundrobin(*iterables):\n",
        "    \"roundrobin('ABC', 'D', 'EF') --> A D E B F C\"\n",
        "    iterators = deque(map(iter, iterables))\n",
        "    while iterators:\n",
        "        try:\n",
        "            while True:\n",
        "                yield next(iterators[0])\n",
        "                iterators.rotate(-1)\n",
        "        except StopIteration:\n",
        "            iterators.popleft()\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача\n",
        "# Имаме следната имплементация на BFS. Как може да я обърнем до DFS?\n",
        "\n",
        "from collections import deque\n",
        "\n",
        "graph = {\n",
        "    'A': ['B', 'C'],\n",
        "    'B': ['D', 'E'],\n",
        "    'C': ['F'],\n",
        "    'D': [],\n",
        "    'E': ['F'],\n",
        "    'F': []\n",
        "}\n",
        "\n",
        "def bfs(graph, start):\n",
        "  visited = set()\n",
        "  que = deque()\n",
        "  visited.add(start)\n",
        "  que.append(start)\n",
        "\n",
        "  while que:\n",
        "    s = que.popleft()\n",
        "    print(s, end=\" \")\n",
        "\n",
        "    for neighbor in graph[s]:\n",
        "      if neighbor not in visited:\n",
        "        visited.add(neighbor)\n",
        "        que.append(neighbor)\n",
        "\n",
        "print(base64.b64decode('0JfQsNC80LXQvdGP0LzQsCBkZXF1ZS5wb3BsZWZ0KCk'\n",
        "  'g0YEgZGVxdWUucG9wKCk='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0P3NxiWOzF1R"
      },
      "source": [
        "## Algorithms & Oddities"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dG3g0AKkzF1R"
      },
      "source": [
        "## Binary Search\n",
        "\n",
        "Бързо ($O(logn)$) търсене в сортиран масив.\n",
        "\n",
        "`bisect_left` = кой е първият индекс на който може да поставим елемента, за да се запази подредбата?\n",
        "\n",
        "`bisect_right` = кой е последният индекс на който може да поставим елемента, за да се запази подредбата?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 34,
      "metadata": {
        "id": "9PrnmyTAzF1R",
        "outputId": "c2c22288-cb7c-4164-b567-0ee5a883c066"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Ако елемента съществува, връща индекса на първото срещане 3\n",
            "Ако елемента съществува, връща първия индекс след последното срещане 7\n",
            "Ако елемента не съществува, връща индекса на първото срещане 7\n",
            "Ако елемента не съществува, връща първия индекс след последното срещане 7\n"
          ]
        }
      ],
      "source": [
        "import bisect\n",
        "numbers = [0, 1, 2, 4, 4, 4, 4, 7, 8, 9]\n",
        "#          0  1  2  3  4  5  6  7  8  9\n",
        "\n",
        "print('Ако елемента съществува, връща индекса на първото срещане',\n",
        "      bisect.bisect_left(numbers, 4))\n",
        "print('Ако елемента съществува, връща първия индекс след последното срещане',\n",
        "      bisect.bisect_right(numbers, 4))\n",
        "\n",
        "print('Ако елемента не съществува, връща индекса на първото срещане',\n",
        "      bisect.bisect_left(numbers, 5))\n",
        "print('Ако елемента не съществува, връща първия индекс след последното срещане',\n",
        "      bisect.bisect_right(numbers, 5))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Задача\n",
        "# В сортиран list от числа, напишете функция, която намира броя на срещанията на някое число\n",
        "\n",
        "print(base64.b64decode('ZGVmIGNvdW50X29jY3VycmVuY2VzKGhh'\n",
        "    'eXN0YWNrLCBuZWVkbGUpOgogICAgYmlzZWN0LmJpc2VjdF9yaWd'\n",
        "    'odChoYXlzdGFjaywgbmVlZGxlKSAtIGJpc2VjdC5iaXNlY3RfbG'\n",
        "    'VmdChoYXlzdGFjaywgbmVlZGxlKQo='.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JdbHLN-vzF1R"
      },
      "source": [
        "## Copy & Deepcopy\n",
        "\n",
        "Python подава аргументите на функциите по референция, така че може да ги променяме. Това не е винаги желаното поведение, така че Python предоставя 2 метода за копиране да обекти.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 35,
      "metadata": {
        "id": "jFZnn7iYzF1R",
        "outputId": "9cd9041b-9439-4086-9d5f-7f9cb6e78db1"
      },
      "outputs": [],
      "source": [
        "from copy import copy, deepcopy\n",
        "\n",
        "def reset_tree():\n",
        "    return {\n",
        "        'value': 'parent',\n",
        "        'child': {\n",
        "            'value': 'child',\n",
        "        }\n",
        "    }\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 36,
      "metadata": {
        "id": "OjCgPKXIzF1R",
        "outputId": "0cca6dbd-d4df-4a38-df52-c3487a886e4d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{'value': 'parent', 'child': {'value': 'super child'}}\n",
            "{'value': 'parent', 'child': {'value': 'super child'}}\n",
            "Когато подаваме елемент по референция във функцията работим със същия елемент\n",
            "id(tree) = 4399790912 == id(same) = 4399790912\n"
          ]
        }
      ],
      "source": [
        "def level_up(root):\n",
        "    tree = root  # Това не прави нищо, само преименува променливата\n",
        "    tree['child']['value'] = 'super child'\n",
        "    return tree\n",
        "\n",
        "tree = reset_tree()\n",
        "same = level_up(tree)\n",
        "print(tree)\n",
        "print(same)\n",
        "print('Когато подаваме елемент по референция във функцията работим със същия елемент')\n",
        "print(f'{id(tree) = } == {id(same) = }')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 37,
      "metadata": {
        "id": "LM0uxCQFzF1R",
        "outputId": "bbdb6f4e-571d-40d5-9555-7cfa2f1d6ba2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{'value': 'parent', 'child': {'value': 'super child'}}\n",
            "{'value': 'parent', 'child': {'value': 'super child'}}\n",
            "(shallow) copy копира обекта, но не копира обектите в него\n",
            "id(tree) = 4698146048 != id(same_but_different_but_same) = 4698275328\n"
          ]
        }
      ],
      "source": [
        "def level_up_swallow(root):\n",
        "    tree = copy(root)\n",
        "    tree['child']['value'] = 'super child'\n",
        "    return tree\n",
        "\n",
        "tree = reset_tree()\n",
        "same_but_different_but_same = level_up_swallow(tree)\n",
        "print(tree)\n",
        "print(same_but_different_but_same)\n",
        "print('(shallow) copy копира обекта, но не копира обектите в него')\n",
        "print(f'{id(tree) = } != {id(same_but_different_but_same) = }')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "id": "QLfpNwqIzF1R",
        "outputId": "ebada9ae-fc96-4be7-9252-cbf7cba6950c"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{'value': 'parent', 'child': {'value': 'child'}}\n",
            "{'value': 'parent', 'child': {'value': 'super child'}}\n",
            "deepcopy създава копие, на обекта и рекурсивно на обектите в него\n",
            "id(tree) = 4698416960 != id(different) = 4698412800\n"
          ]
        }
      ],
      "source": [
        "def level_up_deep(root):\n",
        "    tree = deepcopy(root)\n",
        "    tree['child']['value'] = 'super child'\n",
        "    return tree\n",
        "\n",
        "tree = reset_tree()\n",
        "different = level_up_deep(tree)\n",
        "print(tree)\n",
        "print(different)\n",
        "print('deepcopy създава копие, на обекта и рекурсивно на обектите в него')\n",
        "print(f'{id(tree) = } != {id(different) = }')\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HtN8DmN4zF1R"
      },
      "source": [
        "## Random\n",
        "\n",
        "`random` модулът предоставя методи за избиране на случаен елемент, случайно число, случайни битове и тн.\n",
        "\n",
        "Обикновено се използва за тестове (генериране на вход/изход).\n",
        "\n",
        "За криптографски задачи (криптиране на данни, пароли, генериране на токени и тн), не трябва да се\n",
        "използва `random`, а `secrets` модула. За да не навлизаме в разликите, нека да кажем че `secrets` генерира\n",
        "по-рандъм изход от `random` модула :)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 39,
      "metadata": {
        "id": "1DFr1a4tzF1R",
        "outputId": "da58b8ea-9315-4ddc-e852-ac052abd97b4"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "82"
            ]
          },
          "execution_count": 39,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "import random\n",
        "\n",
        "# random модулът може да приеме начална стойност, която се използва\n",
        "# в рандъм алгоритмите, за да върне детерминистичен изход.\n",
        "# Обикновено се използва за да може даден експеримент/тест да се репродуцира\n",
        "random.seed(42)\n",
        "\n",
        "# Това е рандъм число, но заради seed = 42, винаги ще върне 82 в този notebook\n",
        "random.randint(1, 100)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 40,
      "metadata": {
        "id": "MLRuPTQPzF1R",
        "outputId": "05345c4d-cb72-45a6-cbad-e25f1a8aff0c"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "рандъм float 0.11133106816568039\n",
            "randint [0,1]: 1\n",
            "randrange [0,1) не е много рандъм: 0\n",
            "Епа кот дойде: fuck\n",
            "Понякога рандъм изборът не е много рандъм ['boiko']\n",
            "shuffle: [8, 3, 6, 7, 1, 4, 5, 10, 9, 2]\n",
            "Избор на 2 елемента без повторения: [7, 9]\n"
          ]
        }
      ],
      "source": [
        "import random\n",
        "\n",
        "print('рандъм float', random.random())\n",
        "\n",
        "print('randint [0,1]:', random.randint(0, 1))\n",
        "# Някои методи в random работят със затворени, някой с отворени интервали.\n",
        "# Добре е да се провери преди използването им\n",
        "print('randrange [0,1) не е много рандъм:', random.randrange(0, 1))\n",
        "# randrange(a,b) = randint(a,b-1)\n",
        "\n",
        "# Ако имаме колекция от елементи може да използваме choice, за да изберем произволен\n",
        "# Алтернативният метод е да използваме random.randrange(0, len(collection))\n",
        "print('Епа кот дойде:', random.choice(['fuck', 'marry', 'kill']))\n",
        "\n",
        "# Може да задаваме и тежести - 50% ще е първият елемент, 25% втория и 25% третия\n",
        "print('Понякога рандъм изборът не е много рандъм',\n",
        "      random.choices(\n",
        "          ['boiko', 'pak boiko', 'totally not boiko'],\n",
        "          weights=[2, 1, 1]\n",
        "      ))\n",
        "\n",
        "# Понякога трябва да разбъркаме някяква колекция. Например преди да правим quicksort\n",
        "numbers = list(range(1, 11))\n",
        "random.shuffle(numbers)\n",
        "print('shuffle:', numbers)\n",
        "\n",
        "# При експерименти или когато имаме много данни искаме да изберем произволна подгрупа\n",
        "print('Избор на 2 елемента без повторения:', random.sample(numbers, 2))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 41,
      "metadata": {
        "id": "7J2UO4pHzF1R"
      },
      "outputs": [],
      "source": [
        "%%capture\n",
        "import random\n",
        "# За пълнота трябва да споменем, че random модулът има имплементация на\n",
        "# повечето видови разпределения от статистиката, но няма да навлизаме в подробности\n",
        "\n",
        "\n",
        "random.uniform(1, 10)\n",
        "random.gauss(1, 2)\n",
        "random.expovariate(1)\n",
        "random.gammavariate(10, 1)\n",
        "random.normalvariate(5, 1)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sd0g4NQszF1S"
      },
      "source": [
        "## Itertools\n",
        "\n",
        "`itertools` модулът предоставя методи улесняващи итерацията по елементи и често използвани конструкции. Вече сме виждали някой подобни функции като `map`/`filter`.\n",
        "\n",
        "Функциите са доста и улесняват писането на цикли и особено вложени цикли, но понякога отнема повече време да намерим правилната функция от колкото да напишем кода от 0.\n",
        "\n",
        "Целият списък е [тук](https://docs.python.org/3/library/itertools.html) като има разширение на стандартната библиотека от [more-itertools](https://pypi.org/project/more-itertools/) пакета."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 42,
      "metadata": {
        "id": "cXgD4DjCzF1S",
        "outputId": "d2787697-2474-4d6d-e411-e61d0ed50290"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "A, B, C, A, B, C, A, B, C, A, \n",
            "f,i,r,s,t, ,s,e,c,o,n,d,\n",
            "[-20, -10, 20, 15]\n",
            "['c', 'co', 'con', 'cons', 'const', 'constr', 'constru', 'construc', 'construct']\n",
            "[('A', 'B'), ('A', 'C'), ('B', 'C')]\n",
            "[(1, 5), (5, 7), (7, 10)]\n",
            "[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]\n",
            "[(1, 'A'), (1, 'B'), (1, 'C'), (2, 'A'), (2, 'B'), (2, 'C'), (3, 'A'), (3, 'B'), (3, 'C')]\n"
          ]
        }
      ],
      "source": [
        "import itertools\n",
        "\n",
        "# Итератор, който се връща в началото на списъка като се изчерпи.\n",
        "# Наподобява Ring Buffer\n",
        "cycle = itertools.cycle('ABC')\n",
        "for _ in range(10):\n",
        "    print(next(cycle), end=', ')\n",
        "print()\n",
        "\n",
        "# Итератор, който обединява няколко итератора/колекции\n",
        "# Може да го използваме за да flatten-нем списък от списъци\n",
        "for x in itertools.chain('first', ' ', 'second'):\n",
        "    print(x, end=',')\n",
        "print()\n",
        "\n",
        "# Към всеки елемент от списъка се прибавя сумата на всички предишни елементи\n",
        "print(list(itertools.accumulate([-20, +10, +30, -5])))\n",
        "# Може да го използваме за да генерираме всички префикси на дума\n",
        "print(list(itertools.accumulate('construct')))\n",
        "\n",
        "# Генериране на всички уникални двойки. Еквивалентно на 2 вложени цикъла\n",
        "print(list(itertools.combinations('ABC', 2)))\n",
        "\n",
        "# Генериране на всички съседни двойки\n",
        "print(list(itertools.pairwise([1, 5, 7, 10])))\n",
        "\n",
        "# Всички пермутации\n",
        "print(list(itertools.permutations([0, 1, 2])))\n",
        "\n",
        "# A x B - декартово произведение\n",
        "print(list(itertools.product([1, 2, 3], 'ABC')))\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rzETnlzbzF1S"
      },
      "source": [
        "## Functools\n",
        "\n",
        "`functools` предоставя фунцкии от по-висок ред - декоратори и помощни функции. Концепциите в модула са доста сложни така че ще разгледаме само по-често използваните. В темата за функционално се разлеглежда един от основните методи - `reduce`.\n",
        "\n",
        "Друг интересен пример е `functools.singledispatch` декоратора, който ни позволява да overload-ваме функции базирано на типа на първият им аргумент. Тъй като това не работи за функции с повече от 1 аргумент които да overload-нем, няма да му отделяме време. But it exists!"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 43,
      "metadata": {
        "id": "-KWVLg8PzF1S",
        "outputId": "80f3330b-9aed-4f27-b498-e438d82aa5ca"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "CPU times: user 19.8 s, sys: 92 ms, total: 19.9 s\n",
            "Wall time: 20 s\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "165580141"
            ]
          },
          "execution_count": 43,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "%%time\n",
        "import functools\n",
        "\n",
        "# Нека си дефинираме наивна рекурсивна функция\n",
        "def fibonacci(n):\n",
        "    if n in [0, 1]:\n",
        "        return 1\n",
        "    return fibonacci(n - 1) + fibonacci(n - 2)\n",
        "\n",
        "\n",
        "# Имаме O(2 ^ 40) извиквания на фунцкии :(\n",
        "fibonacci(40)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 44,
      "metadata": {
        "id": "pNOMXw3OzF1S",
        "outputId": "2c1ea9a3-14c0-4689-cfeb-51285a31fba6"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "CPU times: user 62 µs, sys: 89 µs, total: 151 µs\n",
            "Wall time: 155 µs\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "16130531424904581415797907386349"
            ]
          },
          "execution_count": 44,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "%%time\n",
        "import functools\n",
        "\n",
        "# Mоже да я забързаме ако кешираме извикванията\n",
        "# Така няма да правим едно и също изчисление 2 пъти\n",
        "\n",
        "\n",
        "@functools.lru_cache(maxsize=150)\n",
        "def fibonacci(n):\n",
        "    if n in [0, 1]:\n",
        "        return 1\n",
        "    return fibonacci(n - 1) + fibonacci(n - 2)\n",
        "\n",
        "\n",
        "fibonacci(40)\n",
        "fibonacci(150)\n",
        "# Дори fib(150) което с наивната рекурсия няма да приключи\n",
        "# никога минава за под 1ms\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 45,
      "metadata": {
        "id": "Z3Y8HXnAzF1S"
      },
      "outputs": [],
      "source": [
        "# Ако имаме клас, за който искаме да имплементираме сравнение\n",
        "# Може да имплементираме само __lt__ и __eq__ и останалите методи\n",
        "# ще се имплементират за нас\n",
        "# Защото понякога имплементирането им просто не е тривиално ...\n",
        "\n",
        "import functools\n",
        "\n",
        "@functools.total_ordering  # ще имплементира __gt__, __le__, и тн.\n",
        "class Point:\n",
        "    def __init__(self, x, y):\n",
        "        self.x = x\n",
        "        self.y = y\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        return self.x == other.x and self.y == other.y\n",
        "\n",
        "    def __lt__(self, other):\n",
        "        # Имплементира Z-order curve подредба на точките\n",
        "        most_significant_dim = 'x'\n",
        "        if self.less_msb(self.x ^ other.x, self.y ^ other.y):\n",
        "            msd = 'y'\n",
        "\n",
        "        if most_significant_dim == 'x':\n",
        "            return self.x < other.x\n",
        "        else:\n",
        "            return self.y < other.y\n",
        "\n",
        "    def less_msb(self, x, y):\n",
        "        return x < y and x < (x ^ y)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JZQDIiqHzF1S"
      },
      "source": [
        "## CSV\n",
        "\n",
        "Python предоставя няколко модула за работа с данни сериализирани под различен формат. Един от тези модули е за работа с CSV файлове (coma-separated values). Ще разгледаме само пример за парсене на такъв файл, но модулът има много различни функционалности и опции."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 46,
      "metadata": {
        "id": "17WMKgJWzF1S",
        "outputId": "10d906eb-26ba-413e-d75a-caeb75781185"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0 : ['Lyubo', '21', 'Sofia']\n",
            "1 : ['Alex', '22', 'Sofia']\n",
            "2 : ['Ivan', '49', 'Ne Sofia']\n"
          ]
        }
      ],
      "source": [
        "import csv\n",
        "from io import StringIO\n",
        "\n",
        "contents = StringIO(  # == string stream\n",
        "    '''Lyubo,21,Sofia\n",
        "Alex,22,Sofia\n",
        "Ivan,49,\"Ne Sofia\"\n",
        "''')\n",
        "\n",
        "reader = csv.reader(contents)\n",
        "for index, row in enumerate(reader):\n",
        "    print(index, ':', row)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BglS5GcMzF1S"
      },
      "source": [
        "## JSON\n",
        "\n",
        "Друг популярен формат на данни е JSON ... Разбира се в Python има модул `json`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 47,
      "metadata": {
        "id": "d-6CT6sRzF1S",
        "outputId": "30cd58d4-a207-4511-c06a-99fbe40afab1"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "От стринг конструирахме dict, който може да използваме: ['baz', None, 1.0, 2]\n",
            "Обратната операция на сериализиране е удобна за принтене на дебъг съобщения\n",
            "{\n",
            "    \"foo\": {\n",
            "        \"bar\": [\n",
            "            \"baz\",\n",
            "            null,\n",
            "            1.0,\n",
            "            2\n",
            "        ]\n",
            "    }\n",
            "}\n"
          ]
        }
      ],
      "source": [
        "import json\n",
        "\n",
        "my_dict = json.loads('{\"foo\": {\"bar\":[\"baz\", null, 1.0, 2]}}')\n",
        "print('От стринг конструирахме dict, който може да използваме:',\n",
        "      my_dict['foo']['bar'])\n",
        "\n",
        "print('Обратната операция на сериализиране е удобна за принтене на дебъг съобщения')\n",
        "print(json.dumps(my_dict, sort_keys=True, indent=4))\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i4-oHcA7zF1S"
      },
      "source": [
        "## Regex\n",
        "\n",
        "Regex или още регулярни изрази са стрингове, които описват някакъв патърн, който може да използваме за търсене в обикновени стрингове.\n",
        "\n",
        "`regex` може да запълни материала за цял курс, но ще се опитаме да разгледаме само често използвани примери, без да навлизаме в подробности.\n",
        "\n",
        "Писането на регулярни изрази обикновено е трудоемка задача, за това препоръчваме инструменти като [regexr](https://regexr.com/), които изпълняват regex в реално време и имат обяснение защо даден стринг е match-нал."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 48,
      "metadata": {
        "id": "-LZL1e38zF1S",
        "outputId": "ea9bfe31-22eb-4d87-960e-f2518ac3a3e4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "(16, 19)\n",
            "Следва ли стринга този патърн? True\n",
            "Намери всички срещания: ['ninja', 'noooinja', 'ninja', 'nwvi9ew9ninja']\n",
            "Разбиване на стринг на всяко срещане на патърн: ['', 'tree', 'forest', 'voice', '']\n",
            "Субституция на патърн в стринг: -NINJA-tree-NINJA-forest-NINJA-voice-NINJA-\n"
          ]
        }
      ],
      "source": [
        "import re\n",
        "\n",
        "# == (.start(), .end())\n",
        "print(re.search(r'123', '458971985719285712324953928572').span())\n",
        "\n",
        "ninjas = 'ninjatreenoooinjaforestninjavoicenwvi9ew9ninja'\n",
        "\n",
        "print('Следва ли стринга този патърн?',\n",
        "      re.match(r'.*ninja$', ninjas) is not None)\n",
        "\n",
        "print('Намери всички срещания:',\n",
        "      re.findall(r'n.*?a', ninjas))\n",
        "\n",
        "print('Разбиване на стринг на всяко срещане на патърн:',\n",
        "      re.split(r'n.*?a', ninjas))\n",
        "\n",
        "print('Субституция на патърн в стринг:',\n",
        "      re.sub(r'n.*?a', '-NINJA-', ninjas))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 49,
      "metadata": {
        "id": "txrotfUmzF1S",
        "outputId": "04d4bc7d-0fe4-495d-b9ed-dc4fdc564e39"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "\n"
          ]
        }
      ],
      "source": [
        "# Hint helper\n",
        "import base64\n",
        "\n",
        "print(base64.b64encode(''.encode()).decode())\n",
        "print(base64.b64decode(''.encode()).decode())\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Допълнителни задачи\n",
        "\n",
        "- https://leetcode.com/problems/find-the-town-judge/ ([solution](https://github.com/luchev/interview-preparation/blob/master/leetcode/997.%20Find%20the%20Town%20Judge/1.py))\n",
        "- https://leetcode.com/problems/number-of-islands/ ([solution](https://github.com/luchev/interview-preparation/blob/master/leetcode/200.%20Number%20of%20Islands/1.py))\n",
        "- https://leetcode.com/problems/network-delay-time/ ([solution](https://github.com/luchev/interview-preparation/blob/master/leetcode/743.%20Network%20Delay%20Time/1.py))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "include_colab_link": true,
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.10.6 64-bit",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.10.7"
    },
    "orig_nbformat": 4,
    "vscode": {
      "interpreter": {
        "hash": "b0fa6594d8f4cbf19f97940f81e996739fb7646882a419484c72d19e05852a7e"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}