pract3.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Практическое занятие №3\n",
    "\n",
    "*П.Н. Советов, РТУ МИРЭА*"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Модули"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.1.** (уровень сложности: простейший)\n",
    "\n",
    "Напишите код, состоящий из двух модулей, для получения следующего сообщения об ошибке:\n",
    "\n",
    "```\n",
    "AttributeError: partially initialized module '...' has no attribute '...' (most likely due to a circular import)\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.2.** (уровень сложности: простейший)\n",
    "\n",
    "Как вы думаете, модуль загружается один раз или же загружается каждый раз при очередном импорте? Докажите правильность вашей гипотезы примером кода."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.3.** (уровень сложности: простейший)\n",
    "\n",
    "Предположим, мы хотим изменить значение глобальной переменной модуля, но так, чтобы новое значение отразилось на всех пользователях этого модуля. К чему приведет следующий код? Что можно предложить взамен?\n",
    "\n",
    "```Python\n",
    "from some_module import GLOBAL_VAR\n",
    "GLOBAL_VAR = 42\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.4.** (уровень сложности: простейший)\n",
    "\n",
    "Неконтролируемый импорт с помощью *, как известно, в Питоне не поощряется. Попробуйте сделать его контролируемым со стороны модуля. Использование звездочки не должно приводить к импорту всех глобальных имен вашего модуля."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.5.** (уровень сложности: низкий)\n",
    "\n",
    "Напишите функцию load_config(filename) для загрузки скрипта на Питоне в виде программируемого конфигурационного формата. Приведите плюсы и минусы подходов с использованием импорта и прямого выполнения кода."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.6.** (уровень сложности: средний)\n",
    "\n",
    "Создайте учебный пакет, состоящий из нескольких модулей и JSON-файла. Получите дистрибутив, готовый для установки с помощью pip. Проверьте результат установки в виртуальном окружении."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Все дальнейшие задачи делаются в Jupyter-блокноте с использованием библиотеки Matplotlib.**"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Процедурная графика"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.1.** (уровень сложности: средний)\n",
    "\n",
    "Создайте генератор случайных спрайтов 5x5 пикселей. Используйте свойство симметрии. Вывод реализуйте с помощью функции imshow.\n",
    "\n",
    "Пример работы генератора показан ниже.\n",
    "\n",
    "![](data/sprite1.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.2.** (уровень сложности: средний)\n",
    "\n",
    "Создайте генератор карт спрайтов. Пример работы этого генератора показан ниже.\n",
    "\n",
    "\n",
    "![](data/sprite2.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.3.** (уровень сложности: высокий)\n",
    "\n",
    "Реализуйте генератор случайных спрайтов NxM. Используйте различные свойства симметрии. Добавьте цвета.\n",
    "\n",
    "Пример работы этого генератора показан ниже.\n",
    "\n",
    "\n",
    "![](data/sprite3.png)\n",
    "\n",
    "Использовалась палитра из PICO-8:\n",
    "\n",
    "```\n",
    "1D2B53\n",
    "7E2553\n",
    "008751\n",
    "AB5236\n",
    "5F574F\n",
    "C2C3C7\n",
    "FFF1E8\n",
    "FF004D\n",
    "FFA300\n",
    "FFEC27\n",
    "00E436\n",
    "29ADFF\n",
    "83769C\n",
    "FF77A8\n",
    "FFCCAA\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.4.** (уровень сложности: высокий)\n",
    "\n",
    "Слышали ли вы об играх с процедурно сгенерированными вселенными? Оказывается, у современной Elite Dangerous есть далекий предок – игра Elite 1984 года. В Elite была впечатляющая по тем временам 3d графика и целых 8 галактик для исследования, каждая из которых содержала 256 солнечных систем. Удивительно, но все это работало на 8-битном компьютере, а код игры составлял микроскопические 32 Кбайт.\n",
    "\n",
    "Изобразите легендарную первую галактику из игры Elite. Для этого потребуется портировать алгоритм процедурной генерации, приведенный далее на C/C++. Обратите внимание, [этот код](http://www.iancgbell.clara.net/elite/text/) написан в низкоуровневом стиле, поскольку был получен из оригинальной игры, которая, в свою очередь, была написана на языке ассемблера. Вам необходимо при портировании следовать хорошему стилю написания программ на Питоне.\n",
    "\n",
    "Каждая галактика в игре генерируется на основе всего трех 16-битных чисел w0, w1 и w2. Для первой галактики это 0x5A4A, 0x0248 и 0xB753. Имена звезд генерируются с помощью массива слогов.\n",
    "\n",
    "```C\n",
    "char pairs[] = \"..LEXEGEZACEBISO\"\n",
    "\"USESARMAINDIREA.\"\n",
    "\"ERATENBERALAVETI\"\n",
    "\"EDORQUANTEISRION\"; /* Dots should be nullprint characters */\n",
    "\n",
    "typedef struct\n",
    "{\n",
    " uint x;\n",
    " uint y; /* One byte unsigned */\n",
    " uint economy; /* These two are actually only 0-7 */\n",
    " uint govtype;\n",
    " uint techlev; /* 0-16 i think */\n",
    " uint population; /* One byte */\n",
    " uint productivity; /* Two byte */\n",
    " uint radius; /* Two byte (not used by game at all) */\n",
    " fastseedtype goatsoupseed;\n",
    " char name[12];\n",
    "} plansys;\n",
    "\n",
    "void tweakseed(seedtype *s)\n",
    "{\n",
    " uint16 temp;\n",
    " temp = ((*s).w0) + ((*s).w1) + ((*s).w2); /* 2 byte aritmetic */\n",
    " (*s).w0 = (*s).w1;\n",
    " (*s).w1 = (*s).w2;\n",
    " (*s).w2 = temp;\n",
    "}\n",
    "\n",
    "/**-Generate system info from seed **/\n",
    "\n",
    "plansys makesystem(seedtype *s)\n",
    "{\n",
    " plansys thissys;\n",
    " uint pair1, pair2, pair3, pair4;\n",
    " uint16 longnameflag = ((*s).w0) & 64;\n",
    "\n",
    " thissys.x = (((*s).w1) >> 8);\n",
    " thissys.y = (((*s).w0) >> 8);\n",
    "\n",
    " thissys.govtype = ((((*s).w1) >> 3) & 7); /* bits 3,4 &5 of w1 */\n",
    "\n",
    " thissys.economy = ((((*s).w0) >> 8) & 7); /* bits 8,9 &A of w0 */\n",
    " if (thissys.govtype <= 1)\n",
    " {\n",
    " thissys.economy = ((thissys.economy) | 2);\n",
    " }\n",
    "\n",
    " thissys.techlev = ((((*s).w1) >> 8) & 3) + ((thissys.economy) ^ 7);\n",
    " thissys.techlev += ((thissys.govtype) >> 1);\n",
    " if (((thissys.govtype) & 1) == 1) thissys.techlev += 1;\n",
    " /* C simulation of 6502's LSR then ADC */\n",
    "\n",
    " thissys.population = 4 * (thissys.techlev) + (thissys.economy);\n",
    " thissys.population += (thissys.govtype) + 1;\n",
    "\n",
    " thissys.productivity = (((thissys.economy) ^ 7) + 3)*((thissys.govtype) + 4);\n",
    " thissys.productivity *= (thissys.population) * 8;\n",
    "\n",
    " thissys.radius = 256 * (((((*s).w2) >> 8) & 15) + 11) + thissys.x;\n",
    "\n",
    " thissys.goatsoupseed.a = (*s).w1 & 0xFF;;\n",
    " thissys.goatsoupseed.b = (*s).w1 >> 8;\n",
    " thissys.goatsoupseed.c = (*s).w2 & 0xFF;\n",
    " thissys.goatsoupseed.d = (*s).w2 >> 8;\n",
    "\n",
    " pair1 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);\n",
    " pair2 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);\n",
    " pair3 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);\n",
    " pair4 = 2 * ((((*s).w2) >> 8) & 31); tweakseed(s);\n",
    " /* Always four iterations of random number */\n",
    "\n",
    " (thissys.name)[0] = pairs[pair1];\n",
    " (thissys.name)[1] = pairs[pair1 + 1];\n",
    " (thissys.name)[2] = pairs[pair2];\n",
    " (thissys.name)[3] = pairs[pair2 + 1];\n",
    " (thissys.name)[4] = pairs[pair3];\n",
    " (thissys.name)[5] = pairs[pair3 + 1];\n",
    "\n",
    " if (longnameflag) /* bit 6 of ORIGINAL w0 flags a four-pair name */\n",
    " {\n",
    " (thissys.name)[6] = pairs[pair4];\n",
    " (thissys.name)[7] = pairs[pair4 + 1];\n",
    " (thissys.name)[8] = 0;\n",
    " }\n",
    " else (thissys.name)[6] = 0;\n",
    " stripout(thissys.name, '.');\n",
    "\n",
    " return thissys;\n",
    "}\n",
    "```\n",
    "\n",
    "Описание первой галактики можно найти [здесь](https://wiki.alioth.net/index.php/Oolite_planet_list/Galaxy_1).\n",
    "\n",
    "Ниже показан пример визуализации первой галактики.\n",
    "\n",
    "![](data/galaxy.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.5.** (уровень сложности: высокий)\n",
    "\n",
    "Создайте генератор растений с помощью алгоритма освоения пространства (space colonization algorithm). Этот алгоритм описан в [статье](http://algorithmicbotany.org/papers/colonization.egwnp2007.large.pdf) 2007 года и позволяет моделировать различные природные явления: корни и ветви деревьев, сети рек и дорог и так далее.\n",
    "\n",
    "Основная идея алгоритма состоит в том, чтобы разместить в некоторой области случайным образом точки притяжения. К этим точкам на каждой итерации тянутся узлы моделируемого растения или дерева. В процессе создаются ветки, а точки поглощаются.\n",
    "\n",
    "Алгоритм содержит следующие шаги.\n",
    "\n",
    "1. Создание N случайных точек притяжения, а также одного или нескольких начальных узлов дерева.\n",
    "2. Поглощение ближайших точек притяжения – то есть тех точек, которые находятся к узлам дерева ближе, чем расстояние $d_k$.\n",
    "3. Нахождение для каждой точки притяжения ближайшего к ней узла дерева $v$ на дистанции, не превышающей $d_i$. Для каждого $v$ формируется множество $S(v)$, которое может содержать несколько точек притяжения.\n",
    "4. Если $S(v)$ не пусто, то формируется очередной узел $v'$ на расстоянии $D$ и создается новый сегмент $(v, v')$ с помощью следующих формул:\n",
    "$$\n",
    "v' = v + \\hat{n}D, \\hat{n} = \\frac{\\vec{n}}{\\lVert\\vec{n}\\rVert},\\vec{n} = \\sum_{s \\in S(v)} \\frac{s - v}{\\lVert s - v \\rVert}\n",
    "$$\n",
    "5. Переход на шаг 2, пока не исчерпано заданное число шагов."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для изображения сегментов используйте LineCollection из Matplotlib.\n",
    "\n",
    "Ниже приведен пример сгенерированного растения.\n",
    "\n",
    "![](data/plant1.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Растения могут расти совместно:\n",
    "\n",
    "![](data/plant2.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.6.** (уровень сложности: высокий)\n",
    "\n",
    "Создайте генератор деревьев на основе алгоритма освоения пространства. Деревья должны иметь ствол и листья. Примеры автоматически сгенерированных деревьев показаны далее:\n",
    "\n",
    "![](data/tree1.png)\n",
    "\n",
    "![](data/tree2.png)\n",
    "\n",
    "![](data/tree3.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.7.** (уровень сложности: низкий)\n",
    "\n",
    "Реализуйте функцию, которая по имени графического файла возвращает двумерный массив с помощью списков Питона, содержащий RGB-значения картинки. Эта функция понадобится для решения остальных задач этого раздела."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.8.** (уровень сложности: средний)\n",
    "\n",
    "Диаграммы Вороного находят широкое применение не только в математике, но и, к примеру, в архитектуре, а также в процедурной графике. Названы эти диаграммы в честь русского математика [Георгия Феодосьевича Вороного](https://www.mathnet.ru/links/bd2cf5586728b0e7a7393c5d7cc7b23d/cheb698.pdf). Для создания диаграммы Вороного необходимо выбрать множество точек и разбить плоскость (n-мерный случай рассматривать не будем) на области, для каждой из которых только одна из выбранных точек окажется ближайшей.\n",
    "\n",
    "Мы используем диаграммы Вороного для реализации фильтра изображения. Результат фильтрации может напоминать нарисованную кистью картину или мозаику. Для получения результата необходимо выбрать N случайных точек исходного изображения и построить по ним диаграмму. \n",
    "\n",
    "Существуют различные алгоритмы построения диаграмм Вороного, но мы воспользуемся самым примитивным подходом – просто последуем определению и переберем все координаты изображения-результата на предмет расстояния до случайно выбранных точек исходного изображения.\n",
    "\n",
    "Ниже показано исходное изображение:\n",
    "\n",
    "![](data/winter1.jpg)\n",
    "\n",
    "Результат фильтрации для N = 500:\n",
    "\n",
    "![](data/winter2.png)\n",
    "\n",
    "Результат фильтрации для N = 2000:\n",
    "\n",
    "![](data/winter3.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.9.** (уровень сложности: хакер)\n",
    "\n",
    "Ускорьте фильтрацию с помощью диаграмм Вороного не меня принципиально алгоритм и не используя сторонние библиотеки."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.10.** (уровень сложности: средний)\n",
    "\n",
    "Реализуйте простой [алгоритм](https://github.com/s-macke/VoxelSpace) трехмерной визуализации воксельных ландшафтов на основе текстуры и карты высот.\n",
    "\n",
    "Исходные данные: [текстура](data/texture.png), [карта высот](data/heightmap.png).\n",
    "\n",
    "Идея алгоритма заключается в послойном сканировании, одна горизонтальная линия за другой, значений из текстуры с учетом дистанции от камеры, и размещении на экране каждой точки слоя в виде столбца, высота которого извлекается из карты высот, а цвет – из текстуры.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Изобразите на текстуре область обзора, охватываемого камерой. Для этого потребуется знать координаты камеры (x, y), ширину зкрана (screen_width) и глубину обзора (z):\n",
    "\n",
    "![](data/voxel_info.png)\n",
    "\n",
    "Сканирование начинайте от наиболее удаленного от камеры слоя.\n",
    "\n",
    "Пример (x = 500, y = 900, screen_width = 64, z = 400):\n",
    "\n",
    "![](data/voxel1.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.11.** (уровень сложности: средний)\n",
    "\n",
    "Изобразите текстуру в трехмерном пространстве, используя за основу алгоритм, реализованный в предыдущей задаче. Вам потребуется написать функцию для изображения вертикальных линий. Как и ранее, используйте алгоритм художника – то есть начинайте рисовать от наиболее отдаленных слоев. Цвет линии извлекается из текстуры, а высота текстуры масштабируется с учетом z и переменной, задающей положение горизонта (horizon).\n",
    "\n",
    "Пример:\n",
    "\n",
    "![](data/voxel2.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.12.** (уровень сложности: средний)\n",
    "\n",
    "Изобразите трехмерный ландшафт с использованием доработанного алгоритма из предыдущей задачи. Теперь необходимо задавать высоту вертикальных линий, учитывая карту высот.\n",
    "\n",
    "Пример:\n",
    "\n",
    "![](data/voxel3.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.13.** (уровень сложности: высокий)\n",
    "\n",
    "Ускорьте визуализацию трехмерного ландшафта из предыдущей задачи. Идея: начинайте рисование от ближайшего слоя и храните текущую строку со значениями высот, чтобы не перерисовывать то, что находится за пределами видимости."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.14.** (уровень сложности: высокий)\n",
    "\n",
    "Создайте генератор текстур и карт высот. Для этого можно, к примеру, использовать метод фрактального шума из практического занятия №1.\n",
    "\n",
    "Простой пример:\n",
    "\n",
    "![](data/voxel4.jpg)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.15.** (уровень сложности: хакер)\n",
    "\n",
    "Реализуйте анимацию полета по трехмерному ландшафту, добейтесь приемлемой частоты кадров в секунду."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Инфографика"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проанализируйте данные, полученные от ЦАП. Для этого можно воспользоваться приведенным ниже кодом.\n",
    "\n",
    "```Python\n",
    "import csv\n",
    "import datetime\n",
    "\n",
    "\n",
    "def parse_time(text):\n",
    "    return datetime.datetime.strptime(text, '%Y-%m-%d %H:%M:%S.%f')\n",
    "\n",
    "\n",
    "def load_csv(filename):\n",
    "    with open(filename, encoding='utf8') as f:\n",
    "        return list(csv.reader(f, delimiter=','))\n",
    "\n",
    "\n",
    "# Сообщения, присланные в ЦАП.\n",
    "# id, task, variant, group, time\n",
    "messages = load_csv('messages.csv')\n",
    "\n",
    "# Результаты проверок сообщений, присланных в ЦАП.\n",
    "# id, message, time, status\n",
    "checks = load_csv('checks.csv')\n",
    "\n",
    "# Состояния задач ЦАП.\n",
    "# task, variant, group, time, status, achievements\n",
    "statuses = load_csv('statuses.csv')\n",
    "\n",
    "# Таблица соответствия номеров групп и их названий.\n",
    "# id, title\n",
    "groups = load_csv('groups.csv')\n",
    "\n",
    "# О статусах см. https://github.com/kispython-ru/dta/blob/main/webapp/models.py#L44-L50\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С помощью графиков ответьте на следующие вопросы.\n",
    "\n",
    "**3.1.** (уровень сложности: средний)\n",
    "\n",
    "Как по дням недели распределяется активность студентов?\n",
    "\n",
    "**3.2.** (уровень сложности: средний)\n",
    "\n",
    "Как по времени суток распределяется активность студентов?\n",
    "\n",
    "**3.3.** (уровень сложности: средний)\n",
    "\n",
    "Сколько сообщений в среднем студенты отправляют по каждой задаче?\n",
    "\n",
    "**3.4.** (уровень сложности: высокий)\n",
    "\n",
    "Как за период с начала семестра менялась активность студентов по каждой из задач?\n",
    "\n",
    "**3.5.** (уровень сложности: средний)\n",
    "\n",
    "В каких группах было отправлено больше всего сообщений?\n",
    "\n",
    "**3.6.** (уровень сложности: средний)\n",
    "\n",
    "В каких группах было получено больше всего правильных решений? \n",
    "\n",
    "**3.7.** (уровень сложности: средний)\n",
    "\n",
    "Какие задачи оказались самыми легкими, самыми сложными?\n",
    "\n",
    "**3.8.** (уровень сложности: средний)\n",
    "\n",
    "Студенты каких групп заработали больше всего достижений? \n",
    "\n",
    "**3.9.** (уровень сложности: средний)\n",
    "\n",
    "Кто находится на первых 10 местах в рейтинге студентов?\n",
    "\n",
    "**3.10.** (уровень сложности: средний)\n",
    "\n",
    "В каких группах студенты чаще решают задачи различными способами?\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проанализируйте [базу данных](https://github.com/Newbilius/Old-Games_DOS_Game_Gauntlet/blob/master/GAMES.csv) старых компьютерных игр.\n",
    "\n",
    "С помощью графиков ответьте на следующие вопросы:\n",
    "\n",
    "**3.11.** (уровень сложности: средний)\n",
    "\n",
    "Какие годы были самыми популярными с точки зрения выхода игр?\n",
    "\n",
    "**3.12.** (уровень сложности: средний)\n",
    "\n",
    "Какие жанры были популярны в различные периоды времени?"
   ]
  }
 ],
 "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
 },
 "nbformat": 4,
 "nbformat_minor": 2
}