{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "956275e8-e4e6-4a03-afe5-31eca1c3272b",
   "metadata": {},
   "source": [
    "# Testing possible algorithms to solve MDHVRPTW"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "234feb6e-4c52-443c-a3d6-6da8e903dd5c",
   "metadata": {
    "tags": []
   },
   "source": [
    "Travelling salesman problem\n",
    "\n",
    "TSP es *casi* MDHVRPTW (*Multi-Depot Heterogeneous VRP with Time Windows) *del profe* pero:\n",
    "- Solo 1 camion\n",
    "- Todos los ciudades (aka. almacenes pequeños) tienen al menos 1 pedido\n",
    "- Capacidad infinita (1 solo tipo de vehiculo)\n",
    "- Sin ventanas de tiempo (aka. plazos de entrega)\n",
    "- Solo 1 deposito\n",
    "- No hay entregas parciales\n",
    "  - Relajar la restriccion de que la demanda de los \"customers\" debe ser satisfecha al 100% por\n",
    "    un solo camion.  Entonces, si un \"customer\" requiere 8 paquetes,  se le puede entregar solo 5,\n",
    "    y quedan pendientes 3.  **Esto modifica la solucion,  ahora es una lista donde los nodos a visitar\n",
    "    ya no son unicos**.  Se debe terminar la solucion cuando ya no hayan pedidos pendientes (paquetes por entregar > 0).\n",
    "- No hay \"trasvaces\"\n",
    "  - F\n",
    "\n",
    "Cambios identificados, necesarios para adaptar el TSP a nuestro caso:\n",
    "- Tramos no conectados -> distancia grande entre ellos\n",
    "- Distancias no son euclidianas, usar \"geodistance\"\n",
    "- [...]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ce403ac-eb32-4f74-ae8d-41cb70fe4a20",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Posibilidades\n",
    "\n",
    "Una manera de implementar \n",
    "\n",
    "- [scikit-opt](https://github.com/guofei9987/scikit-opt)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98fe5cbb-4fb3-478b-b22f-c14a0408e638",
   "metadata": {
    "tags": []
   },
   "source": [
    "## NetworkX to find all_pairs_shortest_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b854709-fe5c-4c5a-8a05-b2e438c92a1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "G = nx.Graph()\n",
    "G.add_edge(1, 2)  # default edge data=1\n",
    "G.add_edge(2, 3, weight=0.9)  # specify edge data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44bf2120-1e55-4c1d-b806-3e66227483a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "G.add_edge('y', 'x', function=math.cos)\n",
    "G.add_node(math.cos)  # any hashable can be a node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ed6d6e2-921a-4376-8f8e-c6731385d561",
   "metadata": {},
   "outputs": [],
   "source": [
    "elist = [(1, 2), (2, 3), (1, 4), (4, 2)]\n",
    "G.add_edges_from(elist)\n",
    "elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]\n",
    "G.add_weighted_edges_from(elist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16aad098-3702-4d81-889b-3dc8b3e46ca7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "#G = nx.cubical_graph()\n",
    "subax1 = plt.subplot(121)\n",
    "nx.draw(G)   # default spring_layout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cc6e56b-3dcf-45fe-9127-0cd63f01ccec",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(G.adj)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bad6e2e8-cff5-4a7d-9e3f-f37bae5dff2d",
   "metadata": {},
   "source": [
    "## Pre-processing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22af16ef-7df6-49c8-8e55-157069c03830",
   "metadata": {},
   "source": [
    "La data del profe es muy tedioso de leer.  Formato raro.  Pasar primero a csv.\n",
    "\n",
    "Distancia entre nodos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "db46bd0b-46c7-4125-bfff-33205c578e27",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'/home/mitsuo/docs/courses/2022-1/INF226_DP1/project/code/DP_project/test'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%pwd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b87961d0-f9b4-417e-9138-3db1b0a36d2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "import csv\n",
    "import math\n",
    "import random\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "aeca1be3-1394-4ae1-b488-6abe8bd1e808",
   "metadata": {},
   "outputs": [],
   "source": [
    "def degreesToRadians(degrees):\n",
    "    return degrees * math.pi / 180\n",
    "\n",
    "def distanceInKmBetweenEarthCoordinates(lat1, lon1, lat2, lon2):\n",
    "    earthRadiusKm = 6371        # Avg. radius\n",
    "\n",
    "    dLat = degreesToRadians(lat2-lat1)\n",
    "    dLon = degreesToRadians(lon2-lon1)\n",
    "\n",
    "    lat1 = degreesToRadians(lat1)\n",
    "    lat2 = degreesToRadians(lat2)\n",
    "\n",
    "    a = math.sin(dLat/2) * math.sin(dLat/2) \\\n",
    "      + math.sin(dLon/2) * math.sin(dLon/2) * math.cos(lat1) * math.cos(lat2)\n",
    "    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a));\n",
    "    return earthRadiusKm * c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "80a0fef2-ae25-40e3-94ab-e3d07b9b60c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"\"\"\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    lat : float\n",
    "        Latitud (angulo de los Paralelos) en grados sexagesimales\n",
    "    lon : float\n",
    "        Longitud (angulo de los Meridianos) en grados sexagesimales\n",
    "    x : float\n",
    "        Aproximacion local, en Km respecto (\"Lima\": -12.04591952,-77.03049615  (lat, long))\n",
    "        x = (longitud - (-77.03049615)) * (pi / 180) * earthRadiusKm\n",
    "    y : float\n",
    "        Aproximacion local, en Km respecto (\"Lima\")\n",
    "        y = (latitud - (-12.04591952)) * (pi / 180) * earthRadiusKm\n",
    "    demand : float\n",
    "        Cantidad de paquetes  (facil cambiar a int)\n",
    "    *_time : float\n",
    "        Cantidades de tiempo en minutos\n",
    "    \n",
    "    Notes\n",
    "    -----\n",
    "    Web Mercator projection (BAD):\n",
    "    \n",
    "        x = floor(256 / (2 * math.pi) * 2**(zoom_level) * (lon + math.pi))\n",
    "        y = floor(265 / (2 * math.pi) * 2**(zoom_level) * (math.pi - math.ln(math.tan( math.pi / 4 + lat / 2 ))))\n",
    "        \n",
    "        x = R * lon\n",
    "        y = R * ln(tan(pi/4 + lat/2)\n",
    "    \n",
    "    Both `lon` and `lat` in radians.\n",
    "    \n",
    "    \"Lima\": -12.04591952,-77.03049615  (lat, long)\n",
    "    \"\"\"\n",
    "    def __init__(self, id:  int, ubigeo, lat, lon, is_depot,\n",
    "                 demand, ready_time, due_time, service_time):\n",
    "        super()\n",
    "        self.id = id\n",
    "        self.ubigeo = ubigeo\n",
    "\n",
    "        if is_depot:\n",
    "            self.is_depot = True\n",
    "        else:\n",
    "            self.is_depot = False\n",
    "    \n",
    "        earthRadiusKm = 6371        # Avg. radius\n",
    "        zoom_level = 1\n",
    "        lima_lat = (-12.04591952)\n",
    "        lima_lon = (-77.03049615)\n",
    "        \n",
    "        self.lat = lat\n",
    "        self.lon = lon\n",
    "        self.x = (lon - lima_lon) * (math.pi / 180) * earthRadiusKm\n",
    "        self.y = (lat - lima_lat) * (math.pi / 180) * earthRadiusKm\n",
    "        #self.lat *= (math.pi / 180)\n",
    "        #self.lon *= (math.pi / 180)\n",
    "        #self.x = 256 / (2 * math.pi) * 2**(zoom_level) * (self.lon + math.pi)\n",
    "        #self.y = 256 / (2 * math.pi) * 2**(zoom_level) * (math.pi - math.log(math.tan( math.pi / 4 + self.lat / 2 )))\n",
    "        self.x = round(self.x, 3)\n",
    "        self.y = round(self.y, 3)\n",
    "        self.demand = demand\n",
    "        self.ready_time = 0 #ready_time\n",
    "        self.due_time = due_time\n",
    "        self.service_time = service_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "fd72a504-3538-4b43-9e90-bef4299ca83d",
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = []\n",
    "\n",
    "with open('data/VRPTW_python/inf226.oficinas_mod.csv', newline='') as csvfile:\n",
    "    orders = csv.reader(csvfile)\n",
    "    count = 1\n",
    "    id = 0\n",
    "    for row in orders:\n",
    "        if count >= 2:\n",
    "            ubigeo, dept, prov, latitud, longitud, region_natural, is_depot = row[:7]\n",
    "            demand, ready_time, due_time, service_time = row[7:]\n",
    "            nodes.append(Node(\n",
    "                id, ubigeo, float(latitud), float(longitud), int(is_depot),\n",
    "                #int(100 * random.random()), 0, int(5000 + 500 * (1.5 - random.random())), service_time=60\n",
    "                demand=float(demand), ready_time=0, due_time=float(due_time), service_time=60\n",
    "            ))\n",
    "            id += 1\n",
    "        count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8a9cb3eb-d434-44de-a179-01464ba7bbf8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'id': 34, 'ubigeo': '040101', 'is_depot': True, 'lat': -16.39881421, 'lon': -71.537019649, 'x': 610.847, 'y': -484.02, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n",
      "{'id': 122, 'ubigeo': '130101', 'is_depot': True, 'lat': -8.11176389, 'lon': -79.02868652, 'x': -222.189, 'y': 437.458, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n",
      "{'id': 134, 'ubigeo': '150101', 'is_depot': True, 'lat': -12.04591952, 'lon': -77.03049615, 'x': 0.0, 'y': 0.0, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n"
     ]
    }
   ],
   "source": [
    "for node in nodes:\n",
    "    if node.is_depot:\n",
    "        print(node.__dict__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "79fcde2d-d0df-4cca-8334-3ffd7a0da997",
   "metadata": {},
   "outputs": [],
   "source": [
    "node_num = len(nodes)\n",
    "\n",
    "tramos = []\n",
    "with open('../data/inf226.tramos.v.2.0.csv', newline='') as f:\n",
    "    rows = csv.reader(f)\n",
    "    count = 1\n",
    "    for row in rows:\n",
    "        if count >= 2:\n",
    "            tramos.append([row[0], row[1]])\n",
    "        count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "945de058-6fc3-44c1-8d59-227064323bae",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7008\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[['010201', '010301'],\n",
       " ['010301', '010201'],\n",
       " ['010201', '010401'],\n",
       " ['010401', '010201'],\n",
       " ['010201', '010501']]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(len(tramos))\n",
    "tramos[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "e6895a35-ff22-48a1-88a8-ceb8344f36cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "node_dist_mat = np.zeros((node_num, node_num))\n",
    "\n",
    "nodes_d = dict(zip([n.ubigeo for n in nodes], nodes))\n",
    "for ubigeo1, ubigeo2 in tramos:\n",
    "    #if ubigeo1 in nodes_d.keys() and ubigeo2 in nodes_d.keys():\n",
    "    id1 = nodes_d[ubigeo1].id\n",
    "    id2 = nodes_d[ubigeo2].id\n",
    "    n1 = nodes[id1]\n",
    "    n2 = nodes[id2]\n",
    "    node_dist_mat[id1][id2] = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "b971e3b3-cea5-43b8-9c57-5bbb83180ee6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(196, 196)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "node_dist_mat.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "abc75da4-fed7-493e-ae9d-f5daba33c693",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0.   ,  86.349,   0.   , 137.864],\n",
       "       [ 86.349,   0.   ,   0.   , 146.07 ],\n",
       "       [  0.   ,   0.   ,   0.   ,   0.   ],\n",
       "       [137.864, 146.07 ,   0.   ,   0.   ]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "node_dist_mat[:4, :4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "e818c9bb-28cb-475d-b8b5-98dfe4d11f91",
   "metadata": {},
   "outputs": [],
   "source": [
    "# depots are '040101', '130101', '150101'\n",
    "\n",
    "depots = []\n",
    "customers = []\n",
    "for n in nodes:\n",
    "    if n.is_depot:\n",
    "        depots.append(n)\n",
    "    else:\n",
    "        customers.append(n)\n",
    "depots_customers = depots + customers\n",
    "\n",
    "with open('data/VRPTW_python/pedidosperu195.txt', 'w', newline='') as csvfile:\n",
    "    spamwriter = csv.writer(csvfile, delimiter=' ', quoting=csv.QUOTE_MINIMAL)\n",
    "    i = 0\n",
    "    for node in depots_customers:\n",
    "        spamwriter.writerow([\n",
    "            #node.id,\n",
    "            i,\n",
    "            node.x, node.y,\n",
    "            node.demand, node.ready_time, node.due_time, node.service_time\n",
    "        ])\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cf94976-9003-4b9a-a600-ad9b48d3e60e",
   "metadata": {},
   "source": [
    "### Transformar a matriz conexa de nodos \"customer\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac9f4ce7-7f54-4d26-9bbf-75252f083046",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in nodes[:5]:\n",
    "    print(n.__dict__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3f18eaf-a962-454f-99d4-67bf71067e39",
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "for n in nodes:\n",
    "    if n.demand:\n",
    "        print(n.__dict__)\n",
    "        count += 1\n",
    "count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4308a3df-27ca-4910-bff3-1302c8fb589d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14d8d583-7766-421b-96cc-ec95ad9604e6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f85c9cab",
   "metadata": {},
   "outputs": [],
   "source": [
    "#node_dist_mat = np.zeros((node_num, node_num))\n",
    "elist = []\n",
    "\n",
    "nodes_d = dict(zip([n.ubigeo for n in nodes], nodes))\n",
    "for ubigeo1, ubigeo2 in tramos:\n",
    "    #if ubigeo1 in nodes_d.keys() and ubigeo2 in nodes_d.keys():\n",
    "    id1 = nodes_d[ubigeo1].id\n",
    "    id2 = nodes_d[ubigeo2].id\n",
    "    n1 = nodes[id1]\n",
    "    n2 = nodes[id2]\n",
    "    #node_dist_mat[id1][id2] = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)\n",
    "    dist = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)\n",
    "    elist.append((ubigeo1, ubigeo2, dist))\n",
    "    \n",
    "G = nx.Graph()\n",
    "G.add_weighted_edges_from(elist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3c522d4",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(len(list(nodes_d)))\n",
    "print(len(list(G.nodes)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86771f42",
   "metadata": {},
   "outputs": [],
   "source": [
    "G['010201']['010301']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "001a04b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "node_dist_mat[nodes_d['010201'].id, nodes_d['010301'].id]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71e54f4d",
   "metadata": {},
   "outputs": [],
   "source": [
    "G['010201']['250301']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ebe3cdc",
   "metadata": {},
   "outputs": [],
   "source": [
    "path1 = nx.shortest_path(G, source='010201', target='250301', weight='weight')\n",
    "path1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cca62d40",
   "metadata": {},
   "outputs": [],
   "source": [
    "path2 = nx.shortest_path(G, source='010201', target='250301')\n",
    "path2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "756f1845",
   "metadata": {},
   "outputs": [],
   "source": [
    "l1, l2 = 0, 0\n",
    "for i in range(len(path1)):\n",
    "    if i == 0:\n",
    "        continue\n",
    "    l1 += G[path1[i-1]][path1[i]]['weight']\n",
    "    l2 += G[path2[i-1]][path2[i]]['weight']\n",
    "print(l1, l2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e124757",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# https://stackoverflow.com/a/63169428/7498073\n",
    "H = nx.subgraph(G, path1)\n",
    "nx.draw(H, with_labels=True, font_weight='bold', node_color='lightblue', node_size=500)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c5ded33b",
   "metadata": {},
   "outputs": [],
   "source": [
    "len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))\n",
    "#for node, (dist, path) in len_path:\n",
    "#    print(f\"{node}: {dist} [{path}]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3361d460",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(len_path['010201'][0]['250301'])\n",
    "print(len_path['010201'][1]['250301'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba3d4ae7-c6b5-484a-a1b4-0f6ffe1890b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "help(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "596bf42a-3600-4446-a904-a4e9080d2f2b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "132bea6b-c50c-4406-8e2f-2279a87e9cbf",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf5cac1d-9ae4-4423-ab96-48728c14fa01",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00f4cd39-c093-4397-ae96-cb3ae2a433c6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ff3f7473-6418-4f4a-828f-172f2996ba54",
   "metadata": {},
   "source": [
    "## Pruebitas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6956f235-0401-4a67-8ed2-d2b3fd07b3bf",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ab3843c-faba-46a0-9f7b-97897430ba67",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e45dd91b-fc32-4da3-a340-d3dc888b1335",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fdfcaa8-9000-48d7-b3ab-4d2f2efc2bcc",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}