day-3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Doubly Linked List\n",
    "+ In a doubly linked list, each node points to both the next node and the previous node.\n",
    "+ This allows traversal in both directions (forward and backword)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List is empty.\n",
      "The given key is not in the list.\n",
      "True\n",
      "False\n",
      "40 <-> 30 <-> None\n"
     ]
    }
   ],
   "source": [
    "class DNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "\n",
    "class DoublyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "\n",
    "    def insert_at_beginning(self, data):\n",
    "        new_node = DNode(data)\n",
    "\n",
    "        if self.is_empty():\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            new_node.next = self.head\n",
    "            self.head.prev = new_node\n",
    "            self.head = new_node\n",
    "    \n",
    "    def insert_at_end(self, data):\n",
    "        new_node = DNode(data)\n",
    "\n",
    "        if self.is_empty():\n",
    "            self.head = new_node\n",
    "            return\n",
    "        \n",
    "        current_node = self.head\n",
    "        \n",
    "        while current_node.next:\n",
    "            current_node = current_node.next\n",
    "\n",
    "        current_node.next = new_node\n",
    "        new_node.prev = current_node\n",
    "    \n",
    "\n",
    "    def insert_after_node(self, prev_node_data, data):\n",
    "        new_node = DNode(data)\n",
    "\n",
    "        current_node = self.head\n",
    "\n",
    "        while current_node and current_node.data != prev_node_data:\n",
    "            current_node = current_node.next\n",
    "\n",
    "        if current_node is None:\n",
    "            print(\"The given previous node is not in the list.\")\n",
    "            return\n",
    "\n",
    "        new_node.next = current_node.next\n",
    "        new_node.prev = current_node\n",
    "        current_node.next = new_node\n",
    "\n",
    "        if new_node.next:\n",
    "            new_node.next.prev = new_node\n",
    "    \n",
    "    def delete_node(self, key):\n",
    "\n",
    "        current_node = self.head\n",
    "        \n",
    "        if self.is_empty():\n",
    "            print(\"list is empty\")\n",
    "            return\n",
    "        \n",
    "        # if the node to be deleted is the head node\n",
    "        if current_node.data == key:\n",
    "            if not current_node.next:\n",
    "                self.head = None\n",
    "            else:\n",
    "                self.head = current_node.next\n",
    "                self.head.prev = None\n",
    "            \n",
    "            current_node = None\n",
    "            return\n",
    "        \n",
    "        \n",
    "\n",
    "        while current_node and current_node.data != key:\n",
    "            current_node = current_node.next\n",
    "\n",
    "        if current_node is None:\n",
    "            print(\"The given key is not in the list.\")\n",
    "            return\n",
    "\n",
    "        if current_node.prev:\n",
    "            current_node.next.prev = current_node.prev\n",
    "        \n",
    "        if current_node.next:\n",
    "            current_node.prev.next = current_node.next\n",
    "        \n",
    "        current_node = None\n",
    "\n",
    "    def searchKey(self, key):\n",
    "        current_node = self.head\n",
    "\n",
    "        if self.is_empty():\n",
    "            print(\"list is empty\")\n",
    "            return\n",
    "    \n",
    "        while current_node:\n",
    "            if current_node.data == key:\n",
    "                return True\n",
    "            \n",
    "            current_node = current_node.next\n",
    "\n",
    "        return False\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "    def display(self):\n",
    "        if self.is_empty():\n",
    "            print(\"List is empty.\")\n",
    "            return\n",
    "\n",
    "        current_node = self.head\n",
    "\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\" <-> \")\n",
    "            current_node = current_node.next\n",
    "\n",
    "        print(\"None\")\n",
    "    \n",
    "\n",
    "\n",
    "doublyLinkedList = DoublyLinkedList()\n",
    "\n",
    "doublyLinkedList.display()\n",
    "\n",
    "doublyLinkedList.insert_at_beginning(10)\n",
    "doublyLinkedList.insert_at_beginning(20)\n",
    "doublyLinkedList.insert_at_end(30)\n",
    "\n",
    "doublyLinkedList.insert_after_node(10, 25)\n",
    "\n",
    "doublyLinkedList.delete_node(25)\n",
    "doublyLinkedList.delete_node(40)\n",
    "doublyLinkedList.delete_node(20)\n",
    "doublyLinkedList.delete_node(10)\n",
    "\n",
    "doublyLinkedList.insert_at_beginning(40)\n",
    "print(doublyLinkedList.searchKey(40))\n",
    "print(doublyLinkedList.searchKey(20))\n",
    "\n",
    "doublyLinkedList.display()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problems:\n",
    "\n",
    "##### 1. Reverse a Linked List\n",
    "+ We need to reverse a given singly linked list, which involves changing the direction of the pointers so that each node points to the previous node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List is empty\n",
      "10->20->30->None\n",
      "10\n",
      "<__main__.LinkedList.Node object at 0x000001BDA5176990>\n",
      "20\n",
      "<__main__.LinkedList.Node object at 0x000001BDA52EC410>\n",
      "30\n",
      "None\n",
      "30->20->10->None\n"
     ]
    }
   ],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    class Node:\n",
    "        def __init__(self, data):\n",
    "            self.data = data\n",
    "            self.next = None\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "    \n",
    "    def insert_at_end(self, data):\n",
    "\n",
    "        new_node = self.Node(data)\n",
    "\n",
    "        if self.is_empty():\n",
    "            self.head = new_node\n",
    "            return\n",
    "\n",
    "        current_node = self.head\n",
    "\n",
    "        while current_node.next:\n",
    "            current_node = current_node.next\n",
    "        \n",
    "        current_node.next = new_node\n",
    "\n",
    "    \n",
    "    def reverse_linkedList(self):\n",
    "        prev_node = None\n",
    "        current_node = self.head\n",
    "\n",
    "        while current_node:\n",
    "            next_node = current_node.next\n",
    "            current_node.next = prev_node\n",
    "            prev_node = current_node\n",
    "            current_node = next_node\n",
    "\n",
    "        self.head = prev_node\n",
    "\n",
    "\n",
    "    \n",
    "    def display(self):\n",
    "        current_node = self.head\n",
    "\n",
    "        if self.is_empty():\n",
    "            print(\"List is empty\")\n",
    "            return\n",
    "\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\"->\")\n",
    "            current_node = current_node.next\n",
    "        \n",
    "        print(\"None\")\n",
    "\n",
    "\n",
    "\n",
    "linkedlist = LinkedList()\n",
    "linkedlist.display()\n",
    "\n",
    "linkedlist.insert_at_end(10)\n",
    "linkedlist.insert_at_end(20)\n",
    "linkedlist.insert_at_end(30)\n",
    "\n",
    "linkedlist.display()\n",
    "linkedlist.reverse_linkedList()\n",
    "\n",
    "linkedlist.display()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2. Detect a Cycle in a Linked List\n",
    "To detect a cycle, we can use Floyd's Cycle Detection Algorithm (also known as the Tortoise and Hare algorithm). The idea is to use two pointers: one moves slowly (one step at a time) and the other moves quickly (two steps at a time). If there is a cycle, the two pointers will eventually meet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List is empty\n",
      "10->20->30->None\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    class Node:\n",
    "        def __init__(self, data):\n",
    "            self.data = data\n",
    "            self.next = None\n",
    "\n",
    "    \n",
    "    def insert_at_end(self, data):\n",
    "        new_node = self.Node(data)\n",
    "\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        \n",
    "        current_node = self.head\n",
    "        while current_node.next:\n",
    "            current_node = current_node.next\n",
    "\n",
    "        current_node.next = new_node\n",
    "\n",
    "    \n",
    "    def detect_cycle(self):\n",
    "        slow = self.head\n",
    "        fast = self.head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "            if slow == fast:\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "    \n",
    "    def display(self):\n",
    "        if not self.head:\n",
    "            print(\"List is empty\")\n",
    "            return\n",
    "        \n",
    "        current_node = self.head\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\"->\")\n",
    "            current_node = current_node.next\n",
    "        \n",
    "        print(\"None\")\n",
    "\n",
    "    \n",
    "\n",
    "llist = LinkedList()\n",
    "llist.display()\n",
    "\n",
    "llist.insert_at_end(10)\n",
    "llist.insert_at_end(20)\n",
    "llist.insert_at_end(30)\n",
    "\n",
    "llist.display()\n",
    "# create cycle for testing (30->20)\n",
    "llist.head.next.next.next = llist.head.next\n",
    "print(llist.detect_cycle())\n",
    "\n",
    "# llist.display()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 3. Merge Two Sorted Linked Lists\n",
    "Given two sorted linked lists, we merge them into a single sorted linked list. We compare the nodes from both lists and merge them in sorted order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->6->None\n"
     ]
    }
   ],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    \n",
    "    class Node:\n",
    "        def __init__(self, data):\n",
    "            self.data = data\n",
    "            self.next = None\n",
    "\n",
    "    def insert_at_end(self, data):\n",
    "        new_node = self.Node(data)\n",
    "\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        \n",
    "        current_node = self.head\n",
    "        while current_node.next:\n",
    "            current_node = current_node.next\n",
    "        \n",
    "        current_node.next = new_node\n",
    "\n",
    "    \n",
    "    def display(self):\n",
    "        if not self.head:\n",
    "            print(\"List is empty\")\n",
    "            return\n",
    "\n",
    "        current_node = self.head\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\"->\")\n",
    "            current_node = current_node.next\n",
    "\n",
    "        print(\"None\")\n",
    "\n",
    "\n",
    "def merge_sorted_linkedList(list1, list2):\n",
    "    dummyNode = LinkedList.Node(0)\n",
    "    tail = dummyNode\n",
    "\n",
    "    p1 = list1.head \n",
    "    p2 = list2.head\n",
    "\n",
    "\n",
    "    while p1 and p2:\n",
    "        if p1.data < p2.data:\n",
    "            tail.next = p1\n",
    "            p1 = p1.next\n",
    "        else:\n",
    "            tail.next = p2\n",
    "            p2 = p2.next\n",
    "        \n",
    "        tail = tail.next\n",
    "\n",
    "    \n",
    "    if p1:\n",
    "        tail.next = p1\n",
    "    elif p2:\n",
    "        tail.next = p2\n",
    "    \n",
    "    merged_list = LinkedList()\n",
    "    merged_list.head = dummyNode.next\n",
    "\n",
    "    return merged_list\n",
    "\n",
    "\n",
    "list1 = LinkedList()\n",
    "list1.insert_at_end(1)\n",
    "list1.insert_at_end(3)\n",
    "list1.insert_at_end(5)\n",
    "\n",
    "list2 = LinkedList()\n",
    "list2.insert_at_end(2)\n",
    "list2.insert_at_end(4)\n",
    "list2.insert_at_end(6)\n",
    "\n",
    "merged_list = merge_sorted_linkedList(list1, list2)\n",
    "merged_list.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Trees\n",
    "\n",
    "+ A tree is a non-linear data structure\n",
    "+ Consisting of node connected to edges\n",
    "+ It is a hierarchical structure where,\n",
    "    + Each node contains data\n",
    "    + The root node is the topmost node in the trees\n",
    "    + Each node (excpet the root) has a parent node, and zero or more child nodes.\n",
    "    + Nodes without any children are called leaf nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ The Most common type of tree used in computer science is the **Binary Tree**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Binary Tree\n",
    "+ A binary tree is a tree data structure in which each node has **at most two children**, refered to as the left child and the right child."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Basic Terminology of Binary Tree\n",
    "+ Root: The topmost node in a tree.\n",
    "+ Parent: A node that has one or more children.\n",
    "+ Child: A node that is a descendant of another node.\n",
    "+ Leaf: A node with no children.\n",
    "+ Height: The number of edges from the root to the deepest leaf.\n",
    "+ Depth: The number of edges from the root to a node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. Tree Traversal in binary Tree\n",
    "Tree traversal refers to the process of visiting (checking or updating) each node in a tree data structure, exactly onnce.\n",
    "\n",
    "+ There are several ways to traverse a tree:\n",
    "    + **In-order Traversal**: Visit the left subtree, the root and then the right subtree. **(Left, Root, Right)**\n",
    "    + **Pre-order Traversal**: Visit the root, then the left subtree and then the right subtree. **(Root, Left, Right)**\n",
    "    + **Post-order Traversal**: Visit the left subtree, the right subtree, and then the root.  **(Left, Right, Root)**\n",
    "    \n",
    "    + **Level-order Traversal** (BFS): Visit nodes level by level from left to right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Binary Tree Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In-Order Traversal: \n",
      "4 2 5 1 3 \n",
      "Pre-order Traversal:\n",
      "1 2 4 5 3 \n",
      "Post-order Traversal:\n",
      "4 5 2 3 1 \n",
      "Level-order Traversal:\n",
      "1 2 3 4 5 "
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class BinaryTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "\n",
    "    # In-order Traversal (Left -> Root -> Right)\n",
    "    def in_order_traversal(self, node):\n",
    "        if node:\n",
    "            self.in_order_traversal(node.left)\n",
    "            print(node.data, end=\" \")\n",
    "            self.in_order_traversal(node.right)\n",
    "\n",
    "    # Pre-order Traversal (Root -> Left -> Right)\n",
    "    def pre_order_traversal(self, node):\n",
    "        if node:\n",
    "            print(node.data, end=\" \")\n",
    "            self.pre_order_traversal(node.left)\n",
    "            self.pre_order_traversal(node.right)\n",
    "    \n",
    "    # Post-order Traversal (Left -> Right -> Root)\n",
    "    def post_order_traversal(self, node):\n",
    "        if node:\n",
    "            self.post_order_traversal(node.left)\n",
    "            self.post_order_traversal(node.right)\n",
    "            print(node.data, end=\" \")\n",
    "    \n",
    "    # Level-order Traversal (Breadth-First Search)\n",
    "    def level_order_traversal(self):\n",
    "        if self.root is None:\n",
    "            return\n",
    "\n",
    "        queue = [self.root]\n",
    "        while queue:\n",
    "            current = queue.pop(0)\n",
    "            print(current.data, end=\" \")\n",
    "\n",
    "            if current.left:\n",
    "                queue.append(current.left)\n",
    "            if current.right:\n",
    "                queue.append(current.right)\n",
    "\n",
    "\n",
    "tree = BinaryTree()\n",
    "tree.root = Node(1)\n",
    "tree.root.left = Node(2)\n",
    "tree.root.right = Node(3)\n",
    "tree.root.left.left = Node(4)\n",
    "tree.root.left.right = Node(5)\n",
    "\n",
    "print(\"In-Order Traversal: \")\n",
    "tree.in_order_traversal(tree.root)\n",
    "\n",
    "print(\"\\nPre-order Traversal:\")\n",
    "tree.pre_order_traversal(tree.root)\n",
    "\n",
    "print(\"\\nPost-order Traversal:\")\n",
    "tree.post_order_traversal(tree.root)\n",
    "\n",
    "print(\"\\nLevel-order Traversal:\")\n",
    "tree.level_order_traversal()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Types of Binary Trees\n",
    "+ **Full Binary Tree**: Every node has 0 or 2 children.\n",
    "+ **Complete Binary Tree**: All levels except possibly the last are completely filled, and all nodes are as far left as possible.\n",
    "+ **Perfect Binary Tree**: A tree where all internal nodes has two children and all leaf nodes are at the same level.\n",
    "+ **Balanced Binary Tree**: A binary tree in which the height of the left and right subtrees of any node differ by at most 1.\n",
    "+ **Binary Search Tree (BST)**: A binary tree where for each node, the left subtree contains only nodes with values less than the node, and the right subtree contains only nodes with values greater than the node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Binary Search Tree (BST)\n",
    "+ The value of every node in the left subtree is less than the value of the root.\n",
    "+ The value of every node in the right subtree is greater than the value of the root.\n",
    "+ Both the left and right subtrees must also be binary search trees.\n",
    "\n",
    "##### BST Operations:\n",
    "+ INSERT: Add a node to the BST while maintaining the property of the BST.\n",
    "+ SEARCH: Find a node in the BST.\n",
    "+ DELETE: Remove a node from the BST while maintaining the BST property."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In-order Traversal of the BST:\n",
      "2 3 6 7 8 \n",
      "\n",
      "Search for 40 in BST: \n",
      "Node not found\n",
      "\n",
      "\n",
      "Height of BT\n",
      "2\n",
      "\n",
      "\n",
      " Is Balanced ? \n",
      "True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class BinarySearchTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    def insert(self, data):\n",
    "        if self.root is None:\n",
    "            self.root = Node(data)\n",
    "        else:\n",
    "            self._insert_recursive(self.root, data)\n",
    "\n",
    "    def _insert_recursive(self, node, data):\n",
    "        if data < node.data:\n",
    "            if node.left is None:\n",
    "                node.left = Node(data)\n",
    "            else:\n",
    "                self._insert_recursive(node.left, data)\n",
    "        else:\n",
    "            if node.right is None:\n",
    "                node.right = Node(data)\n",
    "            else:\n",
    "                self._insert_recursive(node.right, data)\n",
    "        \n",
    "\n",
    "    def search(self, data):\n",
    "        return self._search_recursive(self.root,data)\n",
    "    \n",
    "    def _search_recursive(self, node, key):\n",
    "        if node is None or node.data == key:\n",
    "            return node\n",
    "        \n",
    "        if key < node.data:\n",
    "            return self._search_recursive(node.left, key)\n",
    "        \n",
    "        return self._search_recursive(node.right, key)\n",
    "        \n",
    "    \n",
    "\n",
    "    def inorder_traversal(self, node):\n",
    "        if node:\n",
    "            self.inorder_traversal(node.left)\n",
    "            print(node.data, end=\" \")\n",
    "            self.inorder_traversal(node.right)\n",
    "\n",
    "    def find_height_of_BT(self, node):\n",
    "        if node is None:\n",
    "            return -1\n",
    "\n",
    "        left_height = self.find_height_of_BT(node.left)\n",
    "        right_height = self.find_height_of_BT(node.right)\n",
    "        \n",
    "        return 1 + max(left_height, right_height)\n",
    "    \n",
    "    def check_balanced(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        \n",
    "        left_height = self.find_height_of_BT(node.left)\n",
    "        \n",
    "        if left_height == -1:\n",
    "            return -1\n",
    "        \n",
    "        right_height = self.find_height_of_BT(node.right)\n",
    "\n",
    "        if right_height == -1:\n",
    "            return -1\n",
    "        \n",
    "        if abs(left_height - right_height) > 1:\n",
    "            return -1\n",
    "        \n",
    "        return 1 + max(left_height, right_height)\n",
    "\n",
    "    def _is_balanced(self):\n",
    "        return self.check_balanced(self.root) != -1\n",
    "\n",
    "\n",
    "bst = BinarySearchTree()\n",
    "bst.insert(6)\n",
    "bst.insert(2)\n",
    "bst.insert(3)\n",
    "bst.insert(7)\n",
    "bst.insert(8)\n",
    "\n",
    "print(\"In-order Traversal of the BST:\")\n",
    "bst.inorder_traversal(bst.root)\n",
    "\n",
    "print(\"\\n\\nSearch for 40 in BST: \")\n",
    "node = bst.search(40)\n",
    "\n",
    "if node:\n",
    "    print(\"Node found: \", node.data)\n",
    "else:\n",
    "    print(\"Node not found\")\n",
    "\n",
    "print(\"\\n\\nHeight of BT\")\n",
    "print(bst.find_height_of_BT(bst.root))\n",
    "\n",
    "print(\"\\n\\n Is Balanced ? \")\n",
    "print(bst._is_balanced())\n",
    "\n",
    "bst.root.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}