pract2.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Практическое занятие №2\n",
    "\n",
    "*П.Н. Советов, РТУ МИРЭА*"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Форматирование кода"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Приведите примеры кода, которые соответствуют нарушениям PEP 8. Для проверки используйте библиотеку [pycodestyle](https://github.com/PyCQA/pycodestyle) или ЦАП.\n",
    "\n",
    "**1.1.** (уровень сложности: простейший)\n",
    "\n",
    "E211 whitespace before '('\n",
    "\n",
    "**1.2.** (уровень сложности: простейший)\n",
    "\n",
    "E225 missing whitespace around operator\n",
    "\n",
    "**1.3.** (уровень сложности: простейший)\n",
    "\n",
    "E231 missing whitespace after ','\n",
    "\n",
    "**1.4.** (уровень сложности: простейший)\n",
    "\n",
    "E251 unexpected spaces around keyword / parameter equals\n",
    "\n",
    "**1.5.** (уровень сложности: простейший)\n",
    "\n",
    "E302 expected 2 blank lines, found 1\n",
    "\n",
    "**1.6.** (уровень сложности: простейший)\n",
    "\n",
    "E701 multiple statements on one line (colon)\n",
    "\n",
    "**1.7.** (уровень сложности: простейший)\n",
    "\n",
    "E702 multiple statements on one line (semicolon)\n",
    "\n",
    "**1.8.** (уровень сложности: простейший)\n",
    "\n",
    "E711 comparison to None should be 'if cond is None:'\n",
    "\n",
    "**1.9.** (уровень сложности: простейший)\n",
    "\n",
    "E712 comparison to True should be 'if cond is True:' or 'if cond:'"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Некоторые особенности языка"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.1.** (уровень сложности: низкий)\n",
    "\n",
    "Объясните, что это за код. Это Питон?\n",
    "\n",
    "```[0xfor _ in 'abc']```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.2.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте функцию, которая принимает только именованные аргументы. При передаче позиционного аргумента Питон должен выдать ошибку. В тело функции для этого никаких проверок добавлять нельзя."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.3.** (уровень сложности: низкий)\n",
    "\n",
    "Странные результаты приведены ниже. Как такое возможно?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True False\n"
     ]
    }
   ],
   "source": [
    "a = 1\n",
    "b = 1\n",
    "c = 300000 # проверено в Python 3.11\n",
    "d = 300000\n",
    "print(a is b, c is d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True True False\n"
     ]
    }
   ],
   "source": [
    "a, b = 'py', 'py'\n",
    "c = ''.join(['p', 'y'])\n",
    "print(a is b, a == c, a is c)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.4.** (уровень сложности: средний)\n",
    "\n",
    "В следующем фрагменте по индексу i выбирается одна из трех строк. Сократите код во второй строке до 19 символов без использования функций и методов."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'much'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = 0\n",
    "['much','code','wow'][i] # 24 символа"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Однострочники\n",
    "\n",
    "Напишите программы-однострочники для следующих задач. Начните с наивных решений и постепенно двигайтесь в сторону решений кратких и изящных. Старайтесь попутно создавать автоматические тесты на случайных входных данных.\n",
    "\n",
    "Определитесь, в каких случаях решение-однострочник является предпочтительным, а в каких – нет."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3.1.** (уровень сложности: низкий)\n",
    "\n",
    "Преобразовать элементы списка s из строковой в числовую форму.\n",
    "\n",
    "**3.2.** (уровень сложности: низкий)\n",
    "\n",
    "Подсчитать количество различных элементов в последовательности s.\n",
    "\n",
    "**3.3.** (уровень сложности: простейший)\n",
    "\n",
    "Обратить последовательность s без использования функций.\n",
    "\n",
    "**3.4.** (уровень сложности: низкий)\n",
    "\n",
    "Выдать список индексов, на которых найден элемент x в последовательности s.\n",
    "\n",
    "**3.5.** (уровень сложности: низкий)\n",
    "\n",
    "Сложить элементы списка s с четными индексами.\n",
    "\n",
    "**3.6.** (уровень сложности: низкий)\n",
    "\n",
    "Найти строку максимальной длины в списке строк s.\n",
    "\n",
    "**3.7.** (уровень сложности: низкий)\n",
    "\n",
    "Проверить, относится ли число к числам харшад (делящиеся нацело на сумму своих цифр).\n",
    "\n",
    "**3.8.** (уровень сложности: низкий)\n",
    "\n",
    "Сгенерировать случайную текстовую строку с заданным максимальным размером.\n",
    "\n",
    "**3.9.** (уровень сложности: средний)\n",
    "\n",
    "Реализовать функцию-однострочник для RLE-сжатия. Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> rle_encode('ABBCCCDEF')\n",
    "[('A', 1), ('B', 2), ('C', 3), ('D', 1), ('E', 1), ('F', 1)]\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Ассорти из небольших задач"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.1.** (уровень сложности: низкий)\n",
    "\n",
    "Напишите функцию generate_groups(), которая компактно генерирует (а не просто выдает готовый) список всех названий групп в том виде, который используется на сайте ЦАП.\n",
    "\n",
    "```Python\n",
    "['ИВБО-01-21', 'ИВБО-02-21', 'ИВБО-03-21', 'ИВБО-04-21', 'ИВБО-05-21', 'ИВБО-06-21', 'ИВБО-07-21', 'ИВБО-08-21', 'ИКБО-01-21', 'ИКБО-02-21', ...]\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.2.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте свою версию print(). Постарайтесь использовать максимум возможностей настоящей print(). Для вывода используйте функцию sys.stdout.write()."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.3.** (уровень сложности: средний)\n",
    "\n",
    "Вы получили зашифрованное сообщение и теперь предстоит его расшифровать:\n",
    "\n",
    "```\n",
    "E3238557 6204A1F8 E6537611 174E5747\n",
    "5D954DA8 8C2DFE97 2911CB4C 2CB7C66B\n",
    "E7F185A0 C7E3FA40 42419867 374044DF\n",
    "2519F07D 5A0C24D4 F4A960C5 31159418\n",
    "F2768EC7 AEAF14CF 071B2C95 C9F22699\n",
    "FFB06F41 2AC90051 A53F035D 830601A7\n",
    "EB475702 183BAA6F 12626744 9B75A72F\n",
    "8DBFBFEC 73C1A46E FFB06F41 2AC90051\n",
    "97C5E4E9 B1C26A21 DD4A3463 6B71162F\n",
    "8C075668 7975D565 6D95A700 7272E637\n",
    "```\n",
    "\n",
    "Известно, что для зашифрования использовался алгоритм TEA. Известен также ключ зашифрования/расшифрования:\n",
    "\n",
    "```\n",
    "k = [0, 4, 5, 1]\n",
    "```\n",
    "\n",
    "Имеется и функция на C/C++ для расшифровки данных (v – слова данных, k – ключ):\n",
    "\n",
    "```C\n",
    "void decrypt(uint32_t v[2], const uint32_t k[4]) {\n",
    "    uint32_t v0 = v[0], v1 = v[1], sum = 0xC6EF3720, i;\n",
    "    uint32_t delta = 0x9E3779B9;\n",
    "    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];\n",
    "    for (i = 0; i < 32; i++) {\n",
    "        v1 -= ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);\n",
    "        v0 -= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);\n",
    "        sum -= delta;\n",
    "    }\n",
    "    v[0] = v0; v[1] = v1;\n",
    "}\n",
    "```\n",
    "\n",
    "Остается перевести функцию decrypt на Питон и узнать, что же содержится в зашифрованном сообщении!"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Редакционное расстояние"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.1.** (уровень сложности: низкий)\n",
    "\n",
    "Редакционное расстояние Хэмминга определяет минимальное число позиций, в которых нужно произвести замену символов, чтобы получить из одной последовательности длины n другую последовательность той же длины.\n",
    "\n",
    "Реализуйте функцию вычисления расстояния Хэмминга для двух чисел, на уровне замен бит.\n",
    "\n",
    "Реализуйте сначала наивную версию, а затем придумайте, как изящно написать функцию в виде однострочника с использованием средств современного Питона.\n",
    "\n",
    "Примеры работы функции:\n",
    "\n",
    "```Python\n",
    ">>> ham_dist(0b10, 0b11)\n",
    "1\n",
    ">>> ham_dist(0b1100, 0b0011)\n",
    "4\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.2.** (уровень сложности: средний)\n",
    "\n",
    "Простейшим вариантом кода с коррекцией ошибок является код с повторением. В рассматриваемом далее случае каждый передаваемый бит со значением 1/0 представляется тройкой бит 111/000.\n",
    "\n",
    "Примеры:\n",
    "\n",
    "```Python\n",
    ">>> bin(encode_val(4, 3, 0b1011))\n",
    "'0b111000111111'\n",
    ">>> bin(decode_val(4, 3, 0b111_000_111_111))\n",
    "'0b1011'\n",
    "```\n",
    "\n",
    "Если два исходных значения отличаются лишь в одном бите, то их закодированные варианты имеют расстояние Хэмминга равное 3:\n",
    "\n",
    "```Python\n",
    ">>> ham_dist(encode_val(4, 3, 0b1001), encode_val(4, 3, 0b1000))\n",
    "3\n",
    "```\n",
    "\n",
    "Это позволяет автоматически исправлять внесенные помехи в данные в зависимости от того значения, которое является преобладающим в тройке бит.\n",
    "\n",
    "```Python\n",
    "bin(decode_val(4, 3, 0b110_010_011_101))\n",
    "'0b1011'\n",
    "```\n",
    "\n",
    "Задача состоит в том, чтобы корректно декодировать и откорректировать следующее текстовое сообщение. Известно, что каждое значение в исходной последовательности является 8-битным.\n",
    "\n",
    "```Python\n",
    "[815608, 2064837, 2093080, 2063879, 196608, 2067983, 10457031, 1830912, 2067455, 2093116, 1044928, 2064407, 6262776, 2027968, 4423680, 2068231, 2068474, 1999352, 1019903, 2093113, 2068439, 2064455, 1831360, 1936903, 2067967, 2068456]\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.3.** (уровень сложности: низкий)\n",
    "\n",
    "Советский и российский математик Владимир Иосифович Левенштейн в 1965 г. [предложил](https://www.mathnet.ru/links/5544b02ca719f9e5e3bf19cbd811dae2/dan31411.pdf) свой вариант редакционного расстояния. В расстоянии Левенштейна учитываются не только замены символов, но также операции вставки и удаления. То есть, в отличие от расстояния Хэмминга, с помощью расстояния Левенштейна можно сравнивать последовательности с разными длинами.\n",
    "\n",
    "Расстояние Левенштейна можно определить с помощью рекуррентной формулы (за формулировку спасибо Горчакову А.В.):\n",
    "\n",
    "$$\n",
    "f\\left(\\mathbf{a}, \\mathbf{b}, i, j\\right)=\\left\\{\n",
    "    {\\begin{array}\n",
    "        {llcl}\n",
    "        \\max\\left(i, j\\right),&&&i=0\\ или\\ j=0\\\\\n",
    "        f(\\mathbf{a}, \\mathbf{b}, i-1, j-1),&&&a_{i-1}=b_{j-1}\\\\\n",
    "        1 + \\min\\left(\n",
    "            f\\left(\\mathbf{a}, \\mathbf{b}, i, j-1\\right),\n",
    "            f\\left(\\mathbf{a}, \\mathbf{b}, i-1,j\\right),\n",
    "            f\\left(\\mathbf{a}, \\mathbf{b}, i-1,j-1\\right)\n",
    "        \\right),&&&иначе\n",
    "    \\end{array}\n",
    "}\\right.\n",
    "$$\n",
    "\n",
    "где $\\mathbf{a}$ и $\\mathbf{b}$ — сравниваемые последовательности символов, например, строки;  \n",
    "$i$ и $j$ — индексы последовательностей;  \n",
    "$a_{i-1}$ — $(i-1)$-й символ в строке $\\mathbf{a}$;  \n",
    "$b_{j-1}$ — $(j-1)$-й символ в строке $\\mathbf{b}$.\n",
    "\n",
    "Реализуйте функцию вычисления расстояния Левенштейна.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> lev_dist('столб', 'слон')\n",
    "3\n",
    "```\n",
    "\n",
    "Для ускорения работы реализованной функции используйте «волшебный» декоратор «cache»:\n",
    "\n",
    "```Python\n",
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def lev_dist(...):\n",
    "    ...\n",
    "```\n",
    "\n",
    "**5.4.** (уровень сложности: средний)\n",
    "\n",
    "Реализованная функция вычисления расстояния Левенштейна дает только миниальное число операций. Было бы полезно узнать, какие именно операции произведены над исходной строкой.\n",
    "\n",
    "Например:\n",
    "\n",
    "```Python\n",
    ">>> lev_dist_ops('столб', 'слон')\n",
    "['замена', 'удаление', 'замена']\n",
    "```\n",
    "\n",
    "Реализуйте функцию lev_dist_ops.\n",
    "\n",
    "**5.5.** (уровень сложности: средний)\n",
    "\n",
    "С использованием функции расстояния Левенштейна можно получить последовательность команд редактирования, которые превращают исходную последовательность в результат. Это может помочь компактно хранить данные – для измененной версии файла мы храним только команды, которые производят эти изменения. В этой задаче необходимо сгенерировать код на Питоне, который из исходного списка создает список-результат с помощью минимального числа операций вставки, замены и удаления.\n",
    "\n",
    "Например:\n",
    "\n",
    "```Python\n",
    ">>> print('\\n'.join(lev_dist_gen('достаток', 'остаточный')))\n",
    "x[7] = y[9]\n",
    "x.insert(7, y[8])\n",
    "x.insert(7, y[7])\n",
    "x.insert(7, y[6])\n",
    "del x[0]\n",
    "```\n",
    "\n",
    "Обязательно добавьте тестирование на случайных данных для функции lev_dist_gen."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.6.** (уровень сложности: средний)\n",
    "\n",
    "Реализуйте простую систему проверки орфографии с помощью функции вычисления расстояния Левенштейна. Для работы потребуется [словарь русских слов с указанием частот встречаемости](data/words.txt).\n",
    "\n",
    "Воспользуйтесь следующим методом:\n",
    "\n",
    "1. Если слово найдено в словаре, то возвращаем его.\n",
    "1. Если слово найдено среди словарных слов с расстоянием Левенштейна **равным 1**, то возвращаем самое популярное среди найденных слов.\n",
    "1. Если слово найдено среди словарных слов с расстоянием Левенштейна **равным 2**, то возвращаем самое популярное среди найденных слов.\n",
    "1. Если слово не найдено в словаре, то возвращаем его.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> spell('помоему я напесал усё правильна')\n",
    "по-моему я написал всё правильно\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.7.** (уровень сложности: высокий)\n",
    "\n",
    "Доработайте систему проверки орфографии с помощью модифицированной функции расстояния Левенштейна, в которой учитываются:\n",
    "\n",
    "* Замены сходных по написанию английских букв на русские.\n",
    "* Перестановки пар соседних символов."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Генераторы текстов"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6.1.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте генератор докладов по цифровой экономике. Данные для генерации извлекаются из таблицы:\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "<th>1</th>\n",
    "<th>2</th>\n",
    "<th>3</th>\n",
    "<th>4</th>\n",
    "<th>5</th>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Коллеги,</td>\n",
    "<td>парадигма цифровой экономики</td>\n",
    "<td>открывает новые возможности для</td>\n",
    "<td>дальнейшего углубления</td>\n",
    "<td>знаний и компетенций.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>В то же время,</td>\n",
    "<td>контекст цифровой трансформации</td>\n",
    "<td>выдвигает новые требования</td>\n",
    "<td>бюджетного финансирования</td>\n",
    "<td>непроверенных гипотез.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Однако,</td>\n",
    "<td>диджитализация бизнес-процессов</td>\n",
    "<td>несёт в себе риски</td>\n",
    "<td>синергетического эффекта</td>\n",
    "<td>волатильных активов.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Тем не менее,</td>\n",
    "<td>прагматичный подход к цифровым платформам</td>\n",
    "<td>расширяет горизонты</td>\n",
    "<td>компрометации конфиденциальных</td>\n",
    "<td>опасных экспериментов.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Следовательно,</td>\n",
    "<td>совокупность сквозных технологий</td>\n",
    "<td>заставляет искать варианты</td>\n",
    "<td>универсальной коммодитизации</td>\n",
    "<td>государственно-частных партнёрств.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Соответственно,</td>\n",
    "<td>программа прорывных исследований</td>\n",
    "<td>не оставляет шанса для</td>\n",
    "<td>несанкционированной кастомизации</td>\n",
    "<td>цифровых следов граждан.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Вместе с тем,</td>\n",
    "<td>ускорение блокчейн-транзакций</td>\n",
    "<td>повышает вероятность</td>\n",
    "<td>нормативного регулирования</td>\n",
    "<td>нежелательных последствий.</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>С другой стороны,</td>\n",
    "<td>экспоненциальный рост Big Data</td>\n",
    "<td>обостряет проблему</td>\n",
    "<td>практического применения</td>\n",
    "<td>внезапных открытий.</td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Придумайте способ автоматизировать извлечение данных таблицы из этого документа.\n",
    "\n",
    "Доклад должен иметь корректное начало и несколько абзацев текста.\n",
    "\n",
    "Пример доклада показан ниже:\n",
    "\n",
    "```\n",
    "Коллеги, совокупность сквозных технологий повышает вероятность нормативного регулирования опасных экспериментов. С другой стороны, совокупность сквозных технологий несёт в себе риски нормативного регулирования внезапных открытий. Тем не менее, совокупность сквозных технологий открывает новые возможности несанкционированной кастомизации опасных экспериментов. \n",
    "\n",
    "Тем не менее, парадигма цифровой экономики открывает новые возможности практического применения цифровых следов граждан. Соответственно, совокупность сквозных технологий открывает новые возможности универсальной коммодитизации волатильных активов. Следовательно, программа прорывных исследований несёт в себе риски практического применения государственно-частных партнёрств. \n",
    "\n",
    "Следовательно, ускорение блокчейн-транзакций расширяет горизонты универсальной коммодитизации знаний и компетенций. Вместе с тем, прагматичный подход к цифровым платформам не оставляет шанса для нормативного регулирования непроверенных гипотез. Следовательно, прагматичный подход к цифровым платформам повышает вероятность бюджетного финансирования волатильных активов.\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6.2.** (уровень сложности: ученый)\n",
    "\n",
    "Придумайте и реализуйте алгоритм автоматического построения подобных таблиц на основе произвольного входного текста."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6.3.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте генератор случайных данных ФИО. Список распространенных имен можно скачать из интернета. Фамилии необходимо генерировать самостоятельно – так, чтобы результат оказался не менее реалистичным, чем в примере ниже. Впрочем, можете попробовать генерировать и имена.\n",
    "\n",
    "Примеры работы генератора:\n",
    "\n",
    "```\n",
    "Данил А. Фуций\n",
    "Роман Д. Фецачли\n",
    "Лев Ц. Шолодяк\n",
    "Ильдар Ц. Тачасяк\n",
    "Николай Р. Мугодич\n",
    "Данила И. Табян\n",
    "Семен Л. Черев\n",
    "Самир Д. Тифомский\n",
    "Тамерлан О. Гузянц\n",
    "Святослав И. Набян\n",
    "Герман З. Семидяк\n",
    "Тамерлан К. Башко\n",
    "Назар Ш. Кунарий\n",
    "Степан Е. Гидский\n",
    "Леонид Н. Сабин\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6.4.** (уровень сложности: средний)\n",
    "\n",
    "Реализуйте простую языковую модель. Обучение модели производится на входном тексте с указанием длины префикса – глубины «памяти» модели. Для каждого префикса, извлеченного из текста, определяется частота встречаемости следуемого за префиксом символа. Более строго говоря, языковая модель основана на применении марковских цепей заданного порядка.\n",
    "\n",
    "Например, если текстом является «На дворе трава, на траве дрова», а префикс выбран длины 2:\n",
    "\n",
    "```Python\n",
    "{' д': {'в': 1, 'р': 1},\n",
    " ' н': {'а': 1},\n",
    " ' т': {'р': 2},\n",
    " ', ': {'н': 1},\n",
    " 'На': {' ': 1},\n",
    " 'а ': {'д': 1, 'т': 1},\n",
    " 'а,': {' ': 1},\n",
    " 'ав': {'а': 1, 'е': 1},\n",
    " 'ва': {',': 1},\n",
    " 'ве': {' ': 1},\n",
    " 'во': {'р': 1},\n",
    " 'дв': {'о': 1},\n",
    " 'др': {'о': 1},\n",
    " 'е ': {'д': 1, 'т': 1},\n",
    " 'на': {' ': 1},\n",
    " 'ов': {'а': 1},\n",
    " 'ор': {'е': 1},\n",
    " 'ра': {'в': 2},\n",
    " 'ре': {' ': 1},\n",
    " 'ро': {'в': 1},\n",
    " 'тр': {'а': 2}}\n",
    "```\n",
    "\n",
    "Если же для того же текста выбрать префикс длины 4, то модель выглядит следующим образом:\n",
    "\n",
    "```Python\n",
    "{' дво': {'р': 1},\n",
    " ' дро': {'в': 1},\n",
    " ' на ': {'т': 1},\n",
    " ' тра': {'в': 2},\n",
    " ', на': {' ': 1},\n",
    " 'На д': {'в': 1},\n",
    " 'а дв': {'о': 1},\n",
    " 'а тр': {'а': 1},\n",
    " 'а, н': {'а': 1},\n",
    " 'ава,': {' ': 1},\n",
    " 'аве ': {'д': 1},\n",
    " 'ва, ': {'н': 1},\n",
    " 'ве д': {'р': 1},\n",
    " 'воре': {' ': 1},\n",
    " 'двор': {'е': 1},\n",
    " 'дров': {'а': 1},\n",
    " 'е др': {'о': 1},\n",
    " 'е тр': {'а': 1},\n",
    " 'на т': {'р': 1},\n",
    " 'оре ': {'т': 1},\n",
    " 'рава': {',': 1},\n",
    " 'раве': {' ': 1},\n",
    " 'ре т': {'р': 1},\n",
    " 'трав': {'а': 1, 'е': 1}}\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Далее по модели необходимо генерировать текст заданной длины:\n",
    "\n",
    "1. Очередной символ генерируется с использованием существующего префикса. По префиксу случайно выбирается следующий за ним символ с учетом частот встречаемости. Этот символ и добавляется к результату. Случайный выбор должен быть взвешенным, см. на этот счет функцию в стандартной библиотеке Питона.\n",
    "1. Далее из префикса удаляется самый старый символ, а в конец префикса добавляется только что случайно выбранный символ."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для тестирования генератора можно использовать тексты [стихотворных произведений Пушкина](data/pushkin.txt)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример использования генератора для префикса длины 2:\n",
    "\n",
    "```\n",
    "ней то бов, чесно мит\n",
    "Душоктям.\n",
    "Безовамирать я продна людоходволишь иход,\n",
    "Алединесвятвосиютсятномн в днасть\n",
    "И подин\n",
    "При негиных был на.\n",
    "А сласы поэтоних и скому безда: оне вой обого стяк, зан.\n",
    "О бесни це мнезорошладом: «Ость,\n",
    "Добоже счальцаризна\n",
    "Кого страв туп; опустой пииныхая, обколегкорывет.\n",
    "Придалоник?..\n",
    "Мы вый в столоных\n",
    "Со своночью взордце.\n",
    "Болье.\n",
    "Препа\n",
    "Сразарных шветхаяснебашипя не прет онье\n",
    "Походит винуждеж ной несь –\n",
    "От лее, суг мой онью я ней,\n",
    "И друговольковел ждуша вны:\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример использования генератора для префикса длины 5:\n",
    "\n",
    "```\n",
    "Вздыхала, как нежный?\n",
    "Мария!\n",
    "Опомнишь: в страданью крымских годованья\n",
    "Стоная мгла недели Петрова,\n",
    "И тихий солнце кровью\n",
    "Спасти не пила,\n",
    "Чтоб с неволе сводом туманен лунный стар и хлад;\n",
    "Вставался.\n",
    "Глядит на солнце подымался он удалился.\n",
    "Все флаги в горько волен,\n",
    "Когда молю: не ела,\n",
    "Когда на месте вдруг,\n",
    "Турецкой ранки,\n",
    "А мы поедем;\n",
    "Принесла таинственный набег опять узы стране робко сядем.\n",
    "Удивлена,\n",
    "Ужасный\n",
    "В младой меркнет бездна!\n",
    "Дон Гуан вам\n",
    "Шутишь?\n",
    "Лепорелло\n",
    "Ай, ай!..\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример использования генератора для префикса длины 10:\n",
    "\n",
    "```\n",
    "С тех пор, как умерла княжна,\n",
    "Свершилось и ее страданье,\n",
    "Где крепко с Вольностью святой\n",
    "Законов мощных сочетанье;\n",
    "Где всем простерт их твердый щит,\n",
    "Где сжатый верными руками\n",
    "Граждан над равными главами\n",
    "Их меч без выбора скользит\n",
    "И преступленью не причастна;\n",
    "Я знаю: не твоя вина…\n",
    "Итак, послушай: я прекрасна;\n",
    "Во всем гареме ты одна\n",
    "Могла б еще мне быть умней!\n",
    "Но узнаю по всем приметам\n",
    "Болезнь любви в душе моей угасла не совсем;\n",
    "Но пусть она вас больше не тревожит;\n",
    "Я не хочу печалить вас\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. Движок для текстовых игр\n",
    "\n",
    "**7.1.** (уровень сложности: средний)\n",
    "\n",
    "Мир простейших текстовых игр (книг-игр, Choose Your Own Adventure) состоит из множества комнат.\n",
    "\n",
    "Каждая комната содержит:\n",
    "\n",
    "* название,\n",
    "* метку для перехода в эту комнату,\n",
    "* описание комнаты,\n",
    "* список действий со стороны игрока, приводящих к выводу сообщения и переходу в другую комнату по ее метке.\n",
    "\n",
    "В рассматриваемом движке для описания игрового мира используется подмножество формата Markdown.\n",
    "\n",
    "[Вот простейшая игра](data/game.md), реализованная таким образом.\n",
    "\n",
    "Задача состоит в реализации разбора указанного формата, а также в реализации игрового процесса в режиме терминала. Разбор необходимо осуществлять построчно, с помощью регулярных выражений.\n",
    "\n",
    "Ниже показан пример сеанса игры:\n",
    "\n",
    "```\n",
    "Начало лабиринта\n",
    "\n",
    "Вы в начале лабиринта. Сможете ли из него выбраться?\n",
    "\n",
    "1. Проход на запад.\n",
    "\n",
    "> 1\n",
    "\n",
    "...\n",
    "\n",
    "Комната №2\n",
    "\n",
    "Вы находитесь в комнате №2.\n",
    "\n",
    "1. Проход на запад.\n",
    "2. Проход на восток.\n",
    "\n",
    "> 1\n",
    "\n",
    "...\n",
    "\n",
    "Комната №3\n",
    "\n",
    "Вы находитесь в комнате №3.\n",
    "\n",
    "1. Проход на север.\n",
    "2. Проход на восток.\n",
    "\n",
    "> \n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7.2.** (уровень сложности: средний)\n",
    "\n",
    "Изобразите граф игрового мира с помощью генерации кода на языке Dot – представления инструмента Graphviz.\n",
    "\n",
    "Пример вывода графа для [game.md](data/game.md):\n",
    "\n",
    "![](data/game_md.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7.3.** (уровень сложности: высокий)\n",
    "\n",
    "Переработайте игровой движок таким образом, чтобы поддерживалась генерация html-проекта для игры в Web. Поддержите также вывод графики в формате игрового мира."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7.4.** (уровень сложности: высокий)\n",
    "\n",
    "Реализуйте инструмент для автоматической проверки игрового мира на наличие тупиков – мест, из которых нельзя добраться до завершения игры."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. Утилиты командной строки"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.1.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте аналог команды ls с помощью стандартной библиотеки Питона. Реализованная команда должна работать и в Windows, и в Linux. Поддержите как можно больше ключей ls. Для разбора аргументов командной строки используйте модуль [argparse](https://docs.python.org/3/library/argparse.html)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.2.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте утилиту командной строки, формирующую дерево каталогов и файлов с учетом произвольной вложенности и начиная с заданного пути. Результат должен быть выдан в виде текста в формате Graphviz."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8.3.** (уровень сложности: средний)\n",
    "\n",
    "Реализуйте утилиту командной строки, которая преобразует в Markdown-файле обычные кавычки в кавычки-елочки с учетом их парности. Внутри блоков кода кавычки необходимо оставлять без изменений. Если утилита была запущена без аргументов, то необходимо обрабатывать стандартный ввод."
   ]
  }
 ],
 "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.1"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "61dfe9c682d93c0afd147a4694a60871cd02680c76d00a06359d9b0f9ffcab18"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}