{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a1dff6b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import csv\n",
    "import matplotlib.pyplot as plt\n",
    "from statistics import mean\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "66bfd079",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Builder.Builder import TextFileMazeBuilder\n",
    "from Core.Benchmark import RunBenchmark\n",
    "from MazeSolver.Solver import MazeSolver\n",
    "from Observer_Command.ConsoleView import ConsoleView\n",
    "from Strategies.BFS import BFS\n",
    "from Strategies.DFS import DFS\n",
    "from Strategies.AStar import AStar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "50c7010d",
   "metadata": {},
   "outputs": [],
   "source": [
    "builder = TextFileMazeBuilder()\n",
    "\n",
    "mazes = {\n",
    "    \"small\": builder.build_from_file(\"Mazes/small.txt\"),\n",
    "    \"medium\": builder.build_from_file(\"Mazes/medium.txt\"),\n",
    "    \"large\": builder.build_from_file(\"Mazes/large.txt\"),\n",
    "    \"empty\": builder.build_from_file(\"Mazes/empty.txt\"),\n",
    "    \"no_exit\": builder.build_from_file(\"Mazes/no_exit.txt\"),\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7326fe7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "strategies = {\n",
    "    \"BFS\": BFS(),\n",
    "    \"DFS\": DFS(),\n",
    "    \"A*\": AStar()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8d47b4cf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Лабиринт: small\n",
      "Testing BFS\n",
      "BFS: time=0.21313328579708468 ms | visited=58.0 | path_len=15.0\n",
      "Testing DFS\n",
      "DFS: time=0.0768381428965118 ms | visited=31.0 | path_len=19.0\n",
      "Testing A*\n",
      "A*: time=0.2827478572596322 ms | visited=57.0 | path_len=15.0\n",
      "Лабиринт: medium\n",
      "Testing BFS\n",
      "BFS: time=5.220513428477196 ms | visited=1263.0 | path_len=173.0\n",
      "Testing DFS\n",
      "DFS: time=4.18784342861857 ms | visited=1229.0 | path_len=173.0\n",
      "Testing A*\n",
      "A*: time=4.219951571420617 ms | visited=806.0 | path_len=173.0\n",
      "Лабиринт: large\n",
      "Testing BFS\n",
      "BFS: time=11.833781999874711 ms | visited=3918.0 | path_len=269.0\n",
      "Testing DFS\n",
      "DFS: time=5.629428999977141 ms | visited=1905.0 | path_len=269.0\n",
      "Testing A*\n",
      "A*: time=10.02670385716036 ms | visited=2040.0 | path_len=269.0\n",
      "Лабиринт: empty\n",
      "Testing BFS\n",
      "BFS: time=0.19871557131929357 ms | visited=64.0 | path_len=15.0\n",
      "Testing DFS\n",
      "DFS: time=0.13947814282541263 ms | visited=64.0 | path_len=29.0\n",
      "Testing A*\n",
      "A*: time=0.28600042846197277 ms | visited=63.0 | path_len=15.0\n",
      "Лабиринт: no_exit\n",
      "Testing BFS\n",
      "BFS: time=0.18080571427552578 ms | visited=58.0 | path_len=0.0\n",
      "Testing DFS\n",
      "DFS: time=0.19448514272621 ms | visited=58.0 | path_len=0.0\n",
      "Testing A*\n"
     ]
    },
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'x'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[5], line 19\u001b[0m\n\u001b[1;32m     16\u001b[0m solver \u001b[38;5;241m=\u001b[39m MazeSolver(maze, strategy)\n\u001b[1;32m     18\u001b[0m start_time \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mperf_counter()\n\u001b[0;32m---> 19\u001b[0m stats, path \u001b[38;5;241m=\u001b[39m \u001b[43msolver\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43msolve\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     20\u001b[0m end_time \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mperf_counter()\n\u001b[1;32m     22\u001b[0m elapsed_ms \u001b[38;5;241m=\u001b[39m (end_time \u001b[38;5;241m-\u001b[39m start_time) \u001b[38;5;241m*\u001b[39m \u001b[38;5;241m1000\u001b[39m\n",
      "File \u001b[0;32m~/2026-rff_mp/pomelovsd/ExitMaze/MazeSolver/Solver.py:16\u001b[0m, in \u001b[0;36mMazeSolver.solve\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21msolve\u001b[39m(\u001b[38;5;28mself\u001b[39m):\n\u001b[1;32m     14\u001b[0m     start \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mperf_counter()\n\u001b[0;32m---> 16\u001b[0m     path, visited \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mstrategy\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mfindPath\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mmaze\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mmaze\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mstart\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mmaze\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mexit\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     18\u001b[0m     end \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mperf_counter()\n\u001b[1;32m     20\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m SearchStats((end\u001b[38;5;241m-\u001b[39mstart)\u001b[38;5;241m*\u001b[39m\u001b[38;5;241m1000\u001b[39m, visited, \u001b[38;5;28mlen\u001b[39m(path)), path\n",
      "File \u001b[0;32m~/2026-rff_mp/pomelovsd/ExitMaze/Strategies/AStar.py:33\u001b[0m, in \u001b[0;36mAStar.findPath\u001b[0;34m(self, maze, start, exit)\u001b[0m\n\u001b[1;32m     31\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m n \u001b[38;5;129;01mnot\u001b[39;00m \u001b[38;5;129;01min\u001b[39;00m g \u001b[38;5;129;01mor\u001b[39;00m tentative \u001b[38;5;241m<\u001b[39m g[n]:\n\u001b[1;32m     32\u001b[0m     g[n] \u001b[38;5;241m=\u001b[39m tentative\n\u001b[0;32m---> 33\u001b[0m     priority \u001b[38;5;241m=\u001b[39m tentative \u001b[38;5;241m+\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mheuristic\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mexit\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     34\u001b[0m     heapq\u001b[38;5;241m.\u001b[39mheappush(heap, (priority, counter, n))\n\u001b[1;32m     35\u001b[0m     counter \u001b[38;5;241m+\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m1\u001b[39m\n",
      "File \u001b[0;32m~/2026-rff_mp/pomelovsd/ExitMaze/Strategies/AStar.py:8\u001b[0m, in \u001b[0;36mAStar.heuristic\u001b[0;34m(self, a, b)\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mheuristic\u001b[39m(\u001b[38;5;28mself\u001b[39m, a, b):\n\u001b[0;32m----> 8\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28mabs\u001b[39m(a\u001b[38;5;241m.\u001b[39mx \u001b[38;5;241m-\u001b[39m \u001b[43mb\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mx\u001b[49m) \u001b[38;5;241m+\u001b[39m \u001b[38;5;28mabs\u001b[39m(a\u001b[38;5;241m.\u001b[39my \u001b[38;5;241m-\u001b[39m b\u001b[38;5;241m.\u001b[39my)\n",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'x'"
     ]
    }
   ],
   "source": [
    "results = []\n",
    "\n",
    "N = 7\n",
    "\n",
    "for maze_name, maze in mazes.items():\n",
    "    print(f\"Лабиринт: {maze_name}\")\n",
    "\n",
    "    for strategy_name, strategy in strategies.items():\n",
    "        total_time = 0\n",
    "        total_visited = 0\n",
    "        total_path_len = 0\n",
    "\n",
    "        print(f\"Testing {strategy_name}\")\n",
    "\n",
    "        for _ in range(N):\n",
    "            solver = MazeSolver(maze, strategy)\n",
    "\n",
    "            start_time = time.perf_counter()\n",
    "            stats, path = solver.solve()\n",
    "            end_time = time.perf_counter()\n",
    "\n",
    "            elapsed_ms = (end_time - start_time) * 1000\n",
    "\n",
    "            total_time += elapsed_ms\n",
    "            total_visited += stats.visited_cells       \n",
    "            total_path_len += len(path)                \n",
    "\n",
    "        avg_time = total_time / N\n",
    "        avg_visited = total_visited / N\n",
    "        avg_path_len = total_path_len / N\n",
    "\n",
    "        results.append({\n",
    "            \"maze\": maze_name,\n",
    "            \"strategy\": strategy_name,\n",
    "            \"time_ms\": round(avg_time, 3),\n",
    "            \"visited_cells\": int(avg_visited),         \n",
    "            \"path_length\": int(avg_path_len),          \n",
    "        })\n",
    "\n",
    "        print(\n",
    "            f\"{strategy_name}: \"\n",
    "            f\"time={avg_time} ms | \"\n",
    "            f\"visited={avg_visited} | \"\n",
    "            f\"path_len={avg_path_len}\"\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "347cb7be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "CSV saved: results.csv\n"
     ]
    }
   ],
   "source": [
    "csv_file = \"results.csv\"\n",
    "\n",
    "with open(csv_file, \"w\", newline=\"\", encoding=\"utf-8\") as file:\n",
    "\n",
    "    writer = csv.writer(file)\n",
    "\n",
    "    writer.writerow([\n",
    "        \"maze\",\n",
    "        \"strategy\",\n",
    "        \"time_ms\",\n",
    "        \"visited_cells\",\n",
    "        \"path_length\"\n",
    "    ])\n",
    "\n",
    "    for row in results:\n",
    "        writer.writerow([\n",
    "            row[\"maze\"],\n",
    "            row[\"strategy\"],\n",
    "            row[\"time_ms\"],\n",
    "            row[\"visited_cells\"],\n",
    "            row[\"path_length\"]\n",
    "        ])\n",
    "\n",
    "print(f\"\\nCSV saved: {csv_file}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b6fb0b0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Результаты:\n",
      "small | BFS | 0.029 ms | 17 visited \n",
      "small | DFS | 0.018 ms | 14 visited \n",
      "small | A* | 0.033 ms | 16 visited \n",
      "medium | BFS | 0.018 ms | 10 visited \n",
      "medium | DFS | 0.019 ms | 10 visited \n",
      "medium | A* | 0.024 ms | 10 visited \n",
      "large | BFS | 0.292 ms | 198 visited \n",
      "large | DFS | 0.201 ms | 198 visited \n",
      "large | A* | 0.277 ms | 198 visited \n",
      "empty | BFS | 0.014 ms | 10 visited \n",
      "empty | DFS | 0.015 ms | 10 visited \n",
      "empty | A* | 0.021 ms | 9 visited \n",
      "no_exit | BFS | 0.007 ms | 1 visited \n",
      "no_exit | DFS | 0.006 ms | 1 visited \n",
      "no_exit | A* | 0.006 ms | 1 visited \n"
     ]
    }
   ],
   "source": [
    "\n",
    "print(\"Результаты:\")\n",
    "\n",
    "for row in results:\n",
    "\n",
    "    print(\n",
    "        f\"{row['maze']} | \"\n",
    "        f\"{row['strategy']} | \"\n",
    "        f\"{row['time_ms']} ms | \"\n",
    "        f\"{row['visited_cells']} visited \"\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95a41c2e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 117492 characters]",
      "text/plain": [
       "<Figure size 1200x1400 with 3 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "maze_names = [\"small\", \"medium\", \"large\", \"empty\", \"no_exit\"]\n",
    "strategies = [\"BFS\", \"DFS\", \"A*\"]\n",
    "\n",
    "colors = {\"BFS\": \"#EEDC82\", \"DFS\": \"#88D94C\", \"A*\": \"#FF43A4\"}\n",
    "\n",
    "# Подготовим данные для графиков\n",
    "time_data = {maze: {s: None for s in strategies} for maze in maze_names}\n",
    "visited_data = {maze: {s: None for s in strategies} for maze in maze_names}\n",
    "path_data = {maze: {s: None for s in strategies} for maze in maze_names}\n",
    "\n",
    "for row in results:\n",
    "    maze = row[\"maze\"]\n",
    "    strat = row[\"strategy\"]\n",
    "    time_data[maze][strat] = row[\"time_ms\"]\n",
    "    visited_data[maze][strat] = row[\"visited_cells\"]\n",
    "    path_data[maze][strat] = row[\"path_length\"]\n",
    "\n",
    "fig, (ax1, ax2, ax3) = plt.subplots(3, 1, figsize=(12, 14))\n",
    "\n",
    "x = np.arange(len(maze_names))\n",
    "width = 0.25  \n",
    "multiplier = 0\n",
    "\n",
    "for strategy in strategies:\n",
    "    values = [time_data[maze][strategy] for maze in maze_names]\n",
    "    offset = width * multiplier\n",
    "    ax1.bar(x + offset, values, width, label=strategy, color=colors[strategy])\n",
    "    multiplier += 1\n",
    "\n",
    "ax1.set_xticks(x + width, maze_names)\n",
    "ax1.set_ylabel(\"Время (мс)\")\n",
    "ax1.set_title(\"Сравнение времени выполнения алгоритмов\")\n",
    "ax1.legend()\n",
    "ax1.grid(axis='y', alpha=0.5, linestyle='--')\n",
    "\n",
    "multiplier = 0\n",
    "for strategy in strategies:\n",
    "    values = [visited_data[maze][strategy] for maze in maze_names]\n",
    "    offset = width * multiplier\n",
    "    ax2.bar(x + offset, values, width, label=strategy, color=colors[strategy])\n",
    "    multiplier += 1\n",
    "\n",
    "ax2.set_xticks(x + width, maze_names)\n",
    "ax2.set_ylabel(\"Количество исследованных клеток\")\n",
    "ax2.set_title(\"Сравнение количества исследованных клеток\")\n",
    "ax2.legend()\n",
    "ax2.grid(axis='y', alpha=0.5, linestyle='--')\n",
    "\n",
    "multiplier = 0\n",
    "for strategy in strategies:\n",
    "    values = [path_data[maze][strategy] for maze in maze_names]\n",
    "    offset = width * multiplier\n",
    "    ax3.bar(x + offset, values, width, label=strategy, color=colors[strategy])\n",
    "    multiplier += 1\n",
    "\n",
    "ax3.set_xticks(x + width, maze_names)\n",
    "ax3.set_ylabel(\"Длина пути\")\n",
    "ax3.set_title(\"Сравнение длины найденного пути\")\n",
    "ax3.legend()\n",
    "ax3.grid(axis='y', alpha=0.5, linestyle='--')\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.savefig('analysis.png')\n",
    "plt.show()"
   ]
  }
 ],
 "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
