pract5.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Практическое занятие №5\n",
    "\n",
    "*П.Н. Советов, РТУ МИРЭА*"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Многие задачи из этого блокнота решать удобнее в парном составе: один студент занимается написанием кода программы и пытается внести в код такие ошибки, которые будет сложно выявить с помощью тестов другому студенту.\n",
    "\n",
    "Далее потребуется несколько программ, содержащих ошибки. Если в задаче явно не указана программа для тестирования, то используется одна из следующих программ:\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Сортировка."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bucketsort(arr, k):\n",
    "    counts = [0] * k\n",
    "    for x in arr:\n",
    "        counts[x] += 1\n",
    "\n",
    "    sorted_arr = []\n",
    "    for i in range(k):\n",
    "        sorted_arr.extend([i] * counts[i])\n",
    "\n",
    "    return sorted_arr\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Бинарный поиск."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(arr, x):\n",
    "    left = 0\n",
    "    right = len(arr) \n",
    "    while left <= right:\n",
    "        mid = round((left + right) / 2)\n",
    "        if arr[mid] == x:\n",
    "            return mid\n",
    "        if arr[mid] < x:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid           \n",
    "    return -1\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Вычисление расстояния между точками."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    return ((x2 + x1)**2 - (y2 + y1)**2) ** 0.25"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Определение типа треугольника."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def triangle_type(x1, y1, x2, y2, x3, y3):\n",
    "    a = distance(x1, y1, x2, y2)\n",
    "    b = distance(x2, y2, x3, y3)\n",
    "    c = distance(x3, y3, x1, y1)\n",
    "    if a == b == c:\n",
    "        return \"равнобедренный\"\n",
    "    elif a == b or a == c or b == c:\n",
    "        return \"равносторонний\"\n",
    "    elif a != b != c:\n",
    "        return \"разносторонний\"\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Сжатие и расжатие данных по методу RLE."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def encode_rle(data):\n",
    "    encoded = bytes()\n",
    "    count = 0\n",
    "    last_char = data[-1]\n",
    "    for i in range(1, len(data) + 1):\n",
    "        if data[i] == last_char:\n",
    "            count += 1\n",
    "        else:\n",
    "            encoded.append(data[i])\n",
    "            encoded.append(count)\n",
    "            count = 1\n",
    "            last_char = data[i]\n",
    "    encoded.append(count)\n",
    "    encoded.append(last_char)\n",
    "    return bytes(encoded)\n",
    "\n",
    "def decode_rle(data):\n",
    "    decoded = bytes()\n",
    "    i = 1\n",
    "    while i < len(data):\n",
    "        count = data[i - 1]\n",
    "        char = data[i]\n",
    "        decoded.extend([char]*count)\n",
    "        i += 1\n",
    "    return bytes(decoded)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. Банковский счет."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BankAccount:\n",
    "    def __init__(self, account_number, balance=0):\n",
    "        self.account_number = account_number\n",
    "        self.balance = balance\n",
    "\n",
    "    def deposit(self, amount):\n",
    "        self.balance += amount\n",
    "        return f\"{amount} средств успешно зачислены на счет {self.account_number}\"\n",
    "\n",
    "    def withdraw(self, amount):\n",
    "        self.balance -= amount\n",
    "        return f\"{amount} средств успешно сняты с счета {self.account_number}\"\n",
    "\n",
    "    def check_balance(self):\n",
    "        return f\"Баланс счета {self.account_number}: {self.balance}\""
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. Банковский счет с использованием базы данных."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sqlite3\n",
    "\n",
    "class BankAccount:\n",
    "    def __init__(self, account_number):\n",
    "        self.account_number = account_number\n",
    "        self.conn = sqlite3.connect('bank.db')\n",
    "        self.cursor = self.conn.cursor()\n",
    "        self.cursor.execute(\n",
    "            \"CREATE TABLE IF NOT EXISTS accounts (account_number INTEGER PRIMARY KEY, balance REAL)\")\n",
    "        self.conn.commit()\n",
    "\n",
    "    def deposit(self, amount):\n",
    "        self.cursor.execute(\n",
    "            \"UPDATE accounts SET balance = balance + ? WHERE account_number = ?\", (amount, self.account_number))\n",
    "        self.conn.commit()\n",
    "        return f\"{amount} средств успешно зачислены на счет {self.account_number}\"\n",
    "\n",
    "    def withdraw(self, amount):\n",
    "        self.cursor.execute(\n",
    "            \"SELECT balance FROM accounts WHERE account_number = ?\", (self.account_number,))\n",
    "        balance = self.cursor.fetchone()[0]\n",
    "        self.cursor.execute(\n",
    "            \"UPDATE accounts SET balance = balance - ? WHERE account_number = ?\", (amount, self.account_number))\n",
    "        self.conn.commit()\n",
    "        return f\"{amount} средств успешно сняты с счета {self.account_number}\"\n",
    "\n",
    "    def check_balance(self):\n",
    "        self.cursor.execute(\n",
    "            \"SELECT balance FROM accounts WHERE account_number = ?\", (self.account_number,))\n",
    "        balance = self.cursor.fetchone()[0]\n",
    "        return f\"Баланс счета {self.account_number}: {balance}\"\n",
    "\n",
    "    def close_account(self):\n",
    "        self.cursor.execute(\n",
    "            \"DELETE FROM accounts WHERE account_number = ?\", (self.account_number,))\n",
    "        self.conn.commit()\n",
    "        return f\"Счет {self.account_number} закрыт\"\n",
    "\n",
    "    def create_account(self, balance):\n",
    "        self.cursor.execute(\n",
    "            \"INSERT INTO accounts (account_number, balance) VALUES (?, ?)\", (self.account_number, balance))\n",
    "        self.conn.commit()\n",
    "        return f\"Счет {self.account_number} успешно создан\""
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Вводные задачи"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.1.** (уровень сложности: низкий)\n",
    "\n",
    "Исправьте функцию distance. Добавьте документацию к функции в виде docstring-строки. Укажите примеры в формате doctest. Примеры должны охватывать граничные случаи. Протестируйте программу с помощью вызова модуля doctest. Перенесите примеры в отдельный файл и снова протестируйте программу."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.2.** (уровень сложности: высокий)\n",
    "\n",
    "Добавьте к функции сортировки тестирование на случайных данных. Исправьте ошибки в функции.\n",
    "\n",
    "Напишите к функции сортировки отдельную функцию-спецификацию в виде набора assert'ов.  Спецификация должна исчерпывающим образом описывать задачу сортировки (без привлечения готовых функций сортировки), иными словами – для **общего случая** нельзя придумать такое искажение кода сортировки, которое будет принято спецификацией."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1.3.** (уровень сложности: средний)\n",
    "\n",
    "Реализуйте конструкцию raises с помощью менеджера контекста в духе таковой из pytest.\n",
    "\n",
    "Пример использования:\n",
    "\n",
    "```Python\n",
    "with raises(MealyError) as e:\n",
    "    ...\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Библиотеки pytest и coverage"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.1.** (уровень сложности: средний)\n",
    "\n",
    "Научитесь работать с модулем pytest. Выберите одну из программ, содержащих ошибки. Создайте отдельный файл для тестирования, в который поместите тестирующие функции (не менее двух). Упростите код с помощью добавления fixture-функций. Добавьте параметризацию."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.2.** (уровень сложности: средний)\n",
    "\n",
    "Выберите одну из программ, содержащих ошибки. Добавьте туда ввод со стороны пользователя. Добавьте макетный код для тестирования, с учетом такого ввода."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2.2.** (уровень сложности: средний)\n",
    "\n",
    "Научитесь работать с модулем coverage. Выберите одну из программ, содержащих ошибки. Получите статистику по покрытию операторов. Получите статистику по покрытию ветвей. Найдите случай, когда покрытие ветвей отличается от покрытия операторов. Постарайтесь изменить код исходной программы так, чтобы затруднить получение 100% покрытия. Найдите простой пример ошибки в выбранной программе, при полученном 100% покрытии. Реализуйте вывод статистики о покрытии в HTML-представлении с демонстрацией покрытия по строкам программы."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Мутационное тестирование"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Прототип системы мутационного тестирования приведен ниже. Попробуйте разобраться в том, как работает этот код. Вам поможет документация к модулю ast.\n",
    "\n",
    "Функция `mut_test` принимает на вход тестируемую функцию и функцию, осуществляющую тестирование с помощью `assert`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from collections import defaultdict\n",
    "import inspect\n",
    "import ast\n",
    "\n",
    "\n",
    "class Mutator(ast.NodeTransformer):\n",
    "    def visit_Constant(self, node):\n",
    "        # TODO\n",
    "        return node\n",
    "\n",
    "\n",
    "def mutate_code(src):\n",
    "    tree = ast.parse(src)\n",
    "    Mutator().visit(tree)\n",
    "    return ast.unparse(tree)\n",
    "\n",
    "\n",
    "def make_mutants(func, size):\n",
    "    mutant = src = ast.unparse(ast.parse(inspect.getsource(func)))\n",
    "    mutants = [src]\n",
    "    while len(mutants) < size + 1:\n",
    "        while mutant in mutants:\n",
    "            mutant = mutate_code(src)\n",
    "        mutants.append(mutant)\n",
    "    return mutants[1:]\n",
    "\n",
    "\n",
    "def mut_test(func, test, size=20):\n",
    "    survived = []\n",
    "    mutants = make_mutants(func, size)\n",
    "    for mutant in mutants:\n",
    "        try:\n",
    "            exec(mutant, globals())\n",
    "            test()\n",
    "            survived.append(mutant)\n",
    "        except:\n",
    "            pass\n",
    "    return survived\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3.1.** (уровень сложности: средний)\n",
    "\n",
    "Выберите одну из программ, содержащих ошибки. Доработайте код мутационного тестирования так, чтобы генерировались программы-мутанты со случайными константами. Покажите, что при 100% покрытии тестами мутационное тестирование в состоянии находить ошибки."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3.2.** (уровень сложности: средний)\n",
    "\n",
    "Добавьте к системе мутационного тестирования генерацию случайных бинарных операций. Проверьте результат на сортировке. Постарайтесь генерировать программы-мутанты, которые «выживают» после большинства assert'ов."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Контракты"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.1.** (уровень сложности: средний)\n",
    "\n",
    "Изучите работу с модулем deal. Для тестирования контрактов используйте pytest. Выберите одну из программ, содержащих ошибки. Добавьте к программе контракты `pre`, `post`, `ensure`, `raises`, `reason`, `has`."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.2.** (уровень сложности: средний)\n",
    "\n",
    "Перепишите класс банковского счета (6) с использованием контрактного программирования и, в частности, инвариантов класса. Продемонстрируйте, что реализованные инварианты класса действительно позволяют выявлять ошибки."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.3.** (уровень сложности: высокий)\n",
    "\n",
    "Реализуйте контракт, выполнение которого `deal` проверяет статически. Какие ограничения имеют статически проверяемые контракты?"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Тестирование на основе свойств"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.1.** (уровень сложности: средний)\n",
    "\n",
    "Научитесь работать с библиотекой hypothesis. Протестируйте функцию distance."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.2.** (уровень сложности: средний)\n",
    "\n",
    "Реализуйте тестирование функций для RLE."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.3.** (уровень сложности: высокий)\n",
    "\n",
    "Реализуйте тестирование для деревьев выражений из предыдущей практики, для одного из «посетителей».\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.4.** (уровень сложности: высокий)\n",
    "\n",
    "Используйте тестирование по модели для проверки реализации банковского счета (7)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Формальная верификация"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Формальная верификация головоломок из компьютерных игр\n",
    "\n",
    "Одной из важных проблем, стоящих перед разработчиком компьютерных игр, является создание интересных головоломок, в которых отсутствуют тупиковые состояния (состояния, из которых нельзя достичь цели).\n",
    "\n",
    "Формальную верификацию проведем следующим образом:\n",
    "\n",
    "1. Реализовать игровую ситуацию в виде некоторого количества локаций с указанием перечня возможных действий в каждой из них.\n",
    "1. Сгенерировать по реализованной игровой ситуации граф всех возможных игровых состояний, в котором ребра задают переходы из состояние в состояние.\n",
    "1. Проанализировать граф состояний на предмет проверяемого игрового свойства.\n",
    "\n",
    "Рассмотрим следующую игровую ситуацию из [PuzzleGraph](https://runevision.itch.io/puzzlegraph):\n",
    "\n",
    "![](data/puzzlegraph.png)\n",
    "\n",
    "Здесь Goal означает целевое состояние, а состояние с двумя зелеными кругами обозначает старт. Справа от стартового состояния используется специальное ребро, по которому позволяется двигаться только в одну сторону, вправо.\n",
    "\n",
    "Ниже приведено описание рассмотренной игровой ситуации на Питоне:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Функция перехода из комнаты в комнату\n",
    "def go(room):\n",
    "    def func(state):\n",
    "        return dict(state, room=room)\n",
    "    return func\n",
    "\n",
    "\n",
    "# Структура игры. Комнаты и допустимые в них действия\n",
    "game = {\n",
    "    'room0': dict(\n",
    "        left=go('room1'),\n",
    "        up=go('room2'),\n",
    "        right=go('room3')\n",
    "    ),\n",
    "    'room1': dict(\n",
    "        up=go('room2'),\n",
    "        right=go('room0')\n",
    "    ),\n",
    "    'room2': dict(\n",
    "    ),\n",
    "    'room3': dict(\n",
    "        up=go('room4'),\n",
    "        right=go('room5')\n",
    "    ),\n",
    "    'room4': dict(\n",
    "        down=go('room3'),\n",
    "        right=go('room5')\n",
    "    ),\n",
    "    'room5': dict(\n",
    "        up=go('room4'),\n",
    "        left=go('room3')\n",
    "    )\n",
    "}\n",
    "\n",
    "# Стартовое состояние\n",
    "START_STATE = dict(room='room0')\n",
    "\n",
    "\n",
    "def is_goal_state(state):\n",
    "    '''\n",
    "    Проверить, является ли состояние целевым.\n",
    "    '''\n",
    "    return state['room'] == 'room2'\n",
    "\n",
    "\n",
    "def get_current_room(state):\n",
    "    '''\n",
    "    Выдать комнату, в которой находится игрок.\n",
    "    '''\n",
    "    return state['room']"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6.1.** (уровень сложности: средний)\n",
    "\n",
    "Реализовать функцию `make_model`, которая по структуре игры и стартовому состоянию строит граф всех возможных состояний.\n",
    "\n",
    "**6.2.** (уровень сложности: высокий)\n",
    "\n",
    "Реализовать функцию `find_dead_ends`, которая выдает список тупиковых узлов графа. Вспомните тупиковые ситуации из известных вам компьютерных игр, где, иной раз, для дальнейшего прохождения нужно прибегать к старому сохранению или вводу специальных системных команд, и все потому, что был потерян важный для дальнейшего прохождения предмет или не совершено требуемое действие.\n",
    "\n",
    "**6.3.** (уровень сложности: высокий)\n",
    "\n",
    "Добавьте в одну из комнат room3-room5 рычаг, нажатие на который делает односторонний переход из room0 в room3 двусторонним.\n",
    "\n",
    "**6.4.** (уровень сложности: высокий)\n",
    "\n",
    "Придумайте минимальную игровую ситуацию, при которой будет наблюдаться комбинаторный взрыв для графа состояний.\n",
    "\n",
    "Простой вариант функции печати графа в формате GraphViz:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_dot(graph, start_key):\n",
    "    dead_ends = [] # find_dead_ends(graph) TODO\n",
    "    print('digraph {')\n",
    "    graph_keys = list(graph.keys())\n",
    "    for x in graph:\n",
    "        n = graph_keys.index(x)\n",
    "        if x == start_key:\n",
    "            print(f'n{n} [style=\"filled\",fillcolor=\"dodgerblue\",shape=\"circle\"]')\n",
    "        elif is_goal_state(x):\n",
    "            print(f'n{n} [style=\"filled\",fillcolor=\"green\",shape=\"circle\"]')\n",
    "        elif x in dead_ends:\n",
    "            print(f'n{n} [style=\"filled\",fillcolor=\"red\",shape=\"circle\"]')\n",
    "        else:\n",
    "            print(f'n{n} [shape=\"circle\"]')\n",
    "    for x in graph:\n",
    "        n1 = graph_keys.index(x)\n",
    "        for y in graph[x]:\n",
    "            n2 = graph_keys.index(y)\n",
    "            print(f'n{n1} -> n{n2}')\n",
    "    print('}')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вот как выглядит вывод функции print_dot:\n",
    "    \n",
    "![](data/game.svg)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вывод для пункта 4 с рычагом:\n",
    "    \n",
    "![](data/puzzlegraph2.svg)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть простая игра The Teeny Tiny Mansion (TTTM), описание которой приведено [здесь](data/tttm.txt). В этой игре имеется 2 персонажа (Алиса и Боб), которыми можно поочередно управлять, 4 комнаты, 3 двери и 3 ключа. Персонажи могут брать ключи и передавать их друг другу. Целью является привести Алису в красную комнату, а Боба — в голубую комнату.\n",
    "\n",
    "В качестве стартового состояния используйте:\n",
    "\n",
    "```Python\n",
    "\n",
    "START_STATE = dict(\n",
    "    player='alice',\n",
    "    alice_room='west room',\n",
    "    bob_room='east room',\n",
    "    red_key='east room',\n",
    "    blue_key='west room',\n",
    "    green_key='east room'\n",
    ")\n",
    "```\n",
    "\n",
    "**6.5.** (уровень сложности: высокий)\n",
    "\n",
    "Реализовать все пункты предыдущей задачи для TTTM.\n",
    "\n",
    "**6.6.** (уровень сложности: высокий)\n",
    "\n",
    "Реализовать функцию подсчета кратчайшего числа шагов, за которые игру можно успешно завершить.\n",
    "\n",
    "**6.7.** (уровень сложности: хакер)\n",
    "\n",
    "Провести верификацию для общего случая: Алиса, Боб и 3 ключа случайно располагаются в западной и восточной комнатах.\n",
    "\n",
    "Пример вывода графа состояний:\n",
    "\n",
    "![](data/tttm.svg)"
   ]
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}