code.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "day1 - https://pixeldrain.com/u/ZQfiQV5L"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task1a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_file = open(\"task1a_files/input1a.txt\", \"r\")\n",
    "output_file = open(\"task1a_files/output1a.txt\", \"w\")\n",
    "num_cases = int(input_file.readline())\n",
    "\n",
    "for _ in range(num_cases):\n",
    "    num = int(input_file.readline())\n",
    "    if num % 2 == 0:\n",
    "        output_file.write(f\"{num} is an Even number.\\n\")\n",
    "    else:\n",
    "        output_file.write(f\"{num} is an Odd number.\\n\")\n",
    "\n",
    "input_file.close()\n",
    "output_file.close()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task1b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_file = open(\"task1b_files/input1b.txt\", \"r\")\n",
    "output_file = open(\"task1b_files/output1b.txt\", \"w\")\n",
    "\n",
    "num_cases = int(input_file.readline())\n",
    "\n",
    "for _ in range(num_cases):\n",
    "    expression = input_file.readline().strip().split()\n",
    "    \n",
    "    num1 = int(expression[1])\n",
    "    operator = expression[2]\n",
    "    num2 = int(expression[3])\n",
    "    \n",
    "    if operator == \"+\":\n",
    "        result = num1 + num2\n",
    "    elif operator == \"-\":\n",
    "        result = num1 - num2\n",
    "    elif operator == \"*\":\n",
    "        result = num1 * num2\n",
    "    elif operator == \"/\":\n",
    "        result = num1 / num2\n",
    "    \n",
    "    output_file.write(f\"The result of {' '.join(expression)} is {result}\\n\")\n",
    "\n",
    "input_file.close()\n",
    "output_file.close()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubbleSort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n - 1):\n",
    "        swapped = False  # Track if any swap happens\n",
    "        for j in range(n - 1 - i):\n",
    "            if arr[j] > arr[j + 1]:\n",
    "                arr[j], arr[j + 1] = arr[j + 1], arr[j]\n",
    "                swapped = True  # A swap occurred\n",
    "        if not swapped:\n",
    "            break  # Exit early if no swaps in this pass\n",
    "    return arr\n",
    "\n",
    "# Explanation:\n",
    "# The \"swapped\" flag ensures that the algorithm stops as soon as the array is sorted.\n",
    "# In the best case (already sorted list), the inner loop runs only once, resulting in O(n) complexity.\n",
    "                \n",
    "\n",
    "input_file = open(\"day1_files/task2_files/input2.txt\", \"r\")\n",
    "output_file = open(\"day1_files/task2_files/output2.txt\", \"w\")\n",
    "\n",
    "num_cases = int(input_file.readline())\n",
    "data_to_sort = input_file.readline().split()\n",
    "\n",
    "inted_data_to_sort = []\n",
    "\n",
    "for _ in data_to_sort:\n",
    "    inted_num = int(_)\n",
    "    inted_data_to_sort.append(inted_num)\n",
    "\n",
    "bubbleSort(inted_data_to_sort)\n",
    "\n",
    "for _ in inted_data_to_sort:\n",
    "    output_data = f\"{_}\" + \" \"\n",
    "    output_file.write(output_data)\n",
    "\n",
    "input_file.close()\n",
    "output_file.close()\n",
    "\n",
    "## below code works too, but i dont understand how it works\n",
    "\n",
    "# def countingSort(arr):\n",
    "#     max_val = max(arr)\n",
    "#     min_val = min(arr)\n",
    "#     range_of_elements = max_val - min_val + 1\n",
    "\n",
    "\n",
    "#     count_arr = [0] * range_of_elements\n",
    "#     output_arr = [0] * len(arr)\n",
    "\n",
    "\n",
    "#     for num in arr:\n",
    "#         count_arr[num - min_val] += 1\n",
    "\n",
    "\n",
    "#     for i in range(1, len(count_arr)):\n",
    "#         count_arr[i] += count_arr[i - 1]\n",
    "\n",
    "\n",
    "#     for num in reversed(arr):\n",
    "#         output_arr[count_arr[num - min_val] - 1] = num\n",
    "#         count_arr[num - min_val] -= 1\n",
    "\n",
    "\n",
    "#     for i in range(len(arr)):\n",
    "#         arr[i] = output_arr[i]\n",
    "\n",
    "\n",
    "# input_file = open(\"task2_files/input2.txt\", \"r\")\n",
    "# output_file = open(\"task2_files/output2.txt\", \"w\")\n",
    "\n",
    "# num_cases = int(input_file.readline())\n",
    "# data_to_sort = input_file.readline().split()\n",
    "# inted_data_to_sort = [int(num) for num in data_to_sort]\n",
    "\n",
    "# countingSort(inted_data_to_sort)\n",
    "\n",
    "# for num in inted_data_to_sort:\n",
    "#     output_file.write(f\"{num} \")\n",
    "\n",
    "# input_file.close()\n",
    "# output_file.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def rank_students():\n",
    "\n",
    "    with open(\"files/day1/task3/input3.txt\", \"r\") as infile:\n",
    "\n",
    "        n = int(infile.readline().strip())\n",
    "        \n",
    "        student_ids = list(map(int, infile.readline().strip().split()))\n",
    "        \n",
    "        marks = list(map(int, infile.readline().strip().split()))\n",
    "    \n",
    "    students = list(zip(student_ids, marks))\n",
    "    \n",
    "    students.sort(key=lambda x: (-x[1], x[0]))\n",
    "    \n",
    "    with open(\"files/day1/task3/output3.txt\", \"w\") as outfile:\n",
    "        for student in students:\n",
    "            outfile.write(f\"ID: {student[0]} Mark: {student[1]}\\n\")\n",
    "\n",
    "rank_students()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert_time_to_minutes(time_str):\n",
    "    hours, minutes = map(int, time_str.split(\":\"))\n",
    "    return hours * 60 + minutes\n",
    "\n",
    "def read_and_sort_train_schedule():\n",
    "\n",
    "    with open(\"files/day1/task4/input4.txt\", \"r\") as infile:\n",
    "    \n",
    "        n = int(infile.readline().strip())\n",
    "        \n",
    "    \n",
    "        schedules = []\n",
    "        for i in range(n):\n",
    "            line = infile.readline().strip()\n",
    "            parts = line.split(\" \")\n",
    "            train_name = parts[0]\n",
    "            departure_time_str = parts[-1]\n",
    "            departure_minutes = convert_time_to_minutes(departure_time_str)\n",
    "            \n",
    "           \n",
    "            schedules.append((line, train_name, departure_minutes, i))\n",
    "    \n",
    "    \n",
    "    schedules.sort(key=lambda x: (x[1], -x[2], x[3])) \n",
    "    \n",
    "    \n",
    "    with open(\"files/day1/task4/output4.txt\", \"w\") as outfile:\n",
    "        for schedule in schedules:\n",
    "            outfile.write(schedule[0] + \"\\n\")\n",
    "\n",
    "read_and_sort_train_schedule()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "day2 - https://pixeldrain.com/u/aaBaq2t8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# # Part 1 solution\n",
    "\n",
    "# def two_sum_brute_force(arr, s):\n",
    "#     n = len(arr)\n",
    "#     for i in range(n):\n",
    "#         for j in range(i + 1, n):\n",
    "#             if arr[i] + arr[j] == s:\n",
    "#                 return i + 1, j + 1\n",
    "#     return \"IMPOSSIBLE\"\n",
    "\n",
    "# # Part 2 solution 1\n",
    "\n",
    "# def two_sum_optimized(arr, s):\n",
    "#     index_map = {}\n",
    "#     for i, num in enumerate(arr):\n",
    "#         complement = s - num\n",
    "#         if complement in index_map:\n",
    "#             return index_map[complement] + 1, i + 1 \n",
    "#         index_map[num] = i\n",
    "#     return \"IMPOSSIBLE\"\n",
    "\n",
    "# Part 2 solution 2\n",
    "\n",
    "def two_sum_optimized(arr, s):\n",
    "    index_map = {}\n",
    "    best_pair = None  # To store the lexicographically smallest pair\n",
    "\n",
    "    for i, num in enumerate(arr):\n",
    "        complement = s - num\n",
    "        if complement in index_map:\n",
    "            # Create the current pair (1-based indexing)\n",
    "            current_pair = (index_map[complement] + 1, i + 1)\n",
    "            # Update the best pair if:\n",
    "            # - No best pair exists yet\n",
    "            # - Current pair is lexicographically smaller\n",
    "            if best_pair is None or current_pair < best_pair:\n",
    "                best_pair = current_pair\n",
    "\n",
    "        # Store the first occurrence of `num`\n",
    "        if num not in index_map:\n",
    "            index_map[num] = i\n",
    "\n",
    "    return best_pair if best_pair else \"IMPOSSIBLE\"\n",
    "\n",
    "\n",
    "with open(\"files/day2/task1/input.txt\", \"r\") as infile:\n",
    "    n, s = map(int, infile.readline().split())\n",
    "    arr = list(map(int, infile.readline().split()))\n",
    "\n",
    "result = two_sum_optimized(arr, s)\n",
    "\n",
    "with open(\"files/day2/task1/output.txt\", \"w\") as outfile:\n",
    "    if isinstance(result, str): \n",
    "        outfile.write(result)\n",
    "    else:\n",
    "        outfile.write(\" \".join(map(str, result)))\n",
    "\n",
    "infile.close()\n",
    "outfile.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Part 1 solution 1\n",
    "\n",
    "# Read inputs\n",
    "with open(\"files/day2/task2/input.txt\", \"r\") as infile:\n",
    "    N = int(infile.readline().strip())  # Length of Alice's list\n",
    "    alice_list = list(map(int, infile.readline().split()))\n",
    "    M = int(infile.readline().strip())  # Length of Bob's list\n",
    "    bob_list = list(map(int, infile.readline().split()))\n",
    "\n",
    "# Merge and sort the two lists\n",
    "merged_list = alice_list + bob_list  # Combine the two lists\n",
    "sorted_list = sorted(merged_list)    # Sort the combined list (O(n log n))\n",
    "\n",
    "# Write the output to a file\n",
    "with open(\"files/day2/task2/output.txt\", \"w\") as outfile:\n",
    "    outfile.write(\" \".join(map(str, sorted_list)))\n",
    "\n",
    "infile.close()\n",
    "outfile.close()\n",
    "\n",
    "# Part 1 solution 2\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "day3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "quiz - https://i.postimg.cc/3rk1mQrq/462550973-1219289142489221-433941277243306390-n.jpg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_minimum_team_difference():\n",
    "    # Read input from 'in3.txt'\n",
    "    with open(\"day3_files/quiz/txt3.inp.txt\", \"r\") as infile:\n",
    "        # Number of people\n",
    "        n = int(infile.readline().strip())\n",
    "        \n",
    "        # Strengths of the people (in ascending order)\n",
    "        strengths = list(map(int, infile.readline().strip().split()))\n",
    "    \n",
    "    # Calculate the total sum of strengths\n",
    "    total_sum = sum(strengths)\n",
    "    \n",
    "    # Initialize variables\n",
    "    min_difference = float('inf')\n",
    "    current_sum = 0\n",
    "    \n",
    "    # Iterate through the strengths to find the minimum difference\n",
    "    for i in range(n - 1):  # We stop at n-1 to avoid empty second team\n",
    "        current_sum += strengths[i]\n",
    "        other_sum = total_sum - current_sum\n",
    "        min_difference = min(min_difference, abs(current_sum - other_sum))\n",
    "    \n",
    "    # Write the result to 'out3.txt'\n",
    "    with open(\"day3_files/quiz/23101376.txt\", \"w\") as outfile:\n",
    "        outfile.write(str(min_difference) + \"\\n\")\n",
    "\n",
    "# Call the function to execute the program\n",
    "find_minimum_team_difference()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(a, b):\n",
    "\n",
    "    sorted_list = []\n",
    "\n",
    "    i = j = 0\n",
    "\n",
    "    while i < len(a) and j < len(b):\n",
    "\n",
    "        if a[i] <= b[j]:\n",
    "\n",
    "            sorted_list.append(a[i])\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        else:\n",
    "\n",
    "            sorted_list.append(b[j])\n",
    "\n",
    "            j += 1\n",
    "\n",
    "    sorted_list.extend(a[i:])\n",
    "\n",
    "    sorted_list.extend(b[j:])\n",
    "\n",
    "    return sorted_list\n",
    "\n",
    "def mergeSort(arr):\n",
    "\n",
    "    if len(arr) <= 1:\n",
    "\n",
    "        return arr\n",
    "\n",
    "    mid = len(arr) // 2\n",
    "\n",
    "    a1 = mergeSort(arr[:mid])\n",
    "\n",
    "    a2 = mergeSort(arr[mid:])\n",
    "\n",
    "    return merge(a1, a2)\n",
    "\n",
    "\n",
    "input_file = open(\"day3_files/task1_files/input.txt\", \"r\")\n",
    "input_file.readline()\n",
    "arr = list(map(int, input_file.readline().split()))\n",
    "\n",
    "sorted_arr = mergeSort(arr)\n",
    "\n",
    "output_file = open(\"day3_files/task1_files/output.txt\", \"w\")\n",
    "output_file.write(\" \".join(map(str, sorted_arr)))\n",
    "\n",
    "input_file.close()\n",
    "output_file.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "day4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part a\n",
    "\n",
    "input_file = open(\"files/day4/task1/input.txt\", \"r\")\n",
    "output_file = open(\"files/day4/task1/output.txt\", \"w\")\n",
    "\n",
    "n, m = map(int, input_file.readline().split())\n",
    "n = n + 1\n",
    "\n",
    "adj_matrix = [[0] * n for _ in range(n)]\n",
    "\n",
    "\n",
    "for _ in range(m):\n",
    "    u, v, w = map(int, input_file.readline().split())\n",
    "    adj_matrix[u - 1][v - 1] = w  # Adjust for 1-based indexing\n",
    "\n",
    "\n",
    "for row in adj_matrix:\n",
    "    output_file.write(\" \".join(map(str, row)) + \"\\n\")\n",
    "\n",
    "\n",
    "input_file.close()\n",
    "output_file.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_file = open(\"files/day4/task2/input.txt\", \"r\")\n",
    "output_file = open(\"files/day4/task2/output.txt\", \"w\")\n",
    "\n",
    "node, edge = tuple(map(int, input_file.readline().split()))\n",
    "\n",
    "adj_list = {}\n",
    "\n",
    "for n in range(node+1):\n",
    "    adj_list[n]=[]\n",
    "\n",
    "for i in range(edge):\n",
    "\n",
    "    u, v = tuple(map(int, input_file.readline().split(\" \")))\n",
    "\n",
    "    adj_list[u].append((v))\n",
    "    adj_list[v].append((u))\n",
    "\n",
    "queue=[]\n",
    "visited=[]\n",
    "\n",
    "def bfs(visited, graph, u):\n",
    "\n",
    "    visited.append(u)\n",
    "    queue.append(u)\n",
    "\n",
    "    while len(queue) > 0:\n",
    "\n",
    "        m=queue.pop(0)\n",
    "\n",
    "        output_file.write(str(m) + \" \")\n",
    "        \n",
    "        for i in graph[m]:\n",
    "\n",
    "            if i not in visited:\n",
    "                visited.append(i)\n",
    "                queue.append(i)\n",
    "\n",
    "# print(adj_list)                \n",
    "\n",
    "bfs(visited, adj_list,1)\n",
    "\n",
    "input_file.close()\n",
    "output_file.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "task4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DFS(G,u,visited,stack):\n",
    "  visited[u] = True\n",
    "  stack[u] = True\n",
    "\n",
    "  for v in G[u]:\n",
    "    if not visited[v]:\n",
    "      if DFS(G,v,visited,stack):\n",
    "        return True\n",
    "    elif stack[v]:\n",
    "        return True\n",
    "\n",
    "  stack[u] = False\n",
    "  return False\n",
    "\n",
    "def isCycle(G):\n",
    "  for u in range(len(G)):\n",
    "    if DFS(G,u,visited,stack):\n",
    "      return True\n",
    "\n",
    "  return False\n",
    "\n",
    "# read the file\n",
    "input4 = open(\"input4_5.txt\", \"r\")\n",
    "# generate a output file by running the code\n",
    "output4 = open(\"output4_5.txt\", \"w\")\n",
    "\n",
    "# read the graph info\n",
    "N,M = map(int,input4.readline().split())\n",
    "\n",
    "G = {}\n",
    "for i in range(N+1):\n",
    "  G[i] = []\n",
    "\n",
    "for i in range(M):\n",
    "  n,m = map(int,input4.readline().split())\n",
    "  G[n].append(m)\n",
    "\n",
    "visited = [False] * (N+1)\n",
    "stack = [False] * (N+1)\n",
    "\n",
    "if isCycle(G)==True:\n",
    "  output4.write(\"YES\")\n",
    "else:\n",
    "  output4.write(\"NO\")\n",
    "\n",
    "output4.close()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}