Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the twentytwenty domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in C:\inetpub\wwwroot\blogs\wp-includes\functions.php on line 6121
Programming – Page 3 – Club TechKnowHow!
Categories
Data Structures & Algorithms Java

Dynamic Connectivity Problem

What is Dynamic Connectivity?

In computing and graph, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of graph.

Dynamic Connectivity Problem

Given a set of N objects.

  • Union command: connect two objects.
  • Find/connected query: is there a path connecting the two objects?

Q. Is there a path connecting p and q?

Source: Algorithm by Robert Sedgewick

 

 

 

 

 

 

 

Union Find Data Type

The goal is to design an efficient data structure for union-find with two commands, union and connected. It can be implemented by two different algorithms, Quick Find and Quick Union.

Quick Find

This quick find algorithm is called eager algorithm to solve dynamic connectivity problem. The data structure includes an Integer array id[] of length N and we consider p and q  to be connected iff they have the same id.

for (int i = 0; i < n; i++)          
     id[i] = i;               //set id of each object to itself

Union

To merge components containing p and q, change all entries whose id equals id[p] to id[q].

int pid = id[p];
int qid = id[p];
for (int i = 0; i < id.length; i++)
    if(id[i] == pid)
        id[i] = qid;

Connected

Check if p and q have the same id.

return id[p] == id[q];

Java Implementation

public class QF
{
    public int[] id;
    
    public QF(int n)
    {
        id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i]=i;
        }
    }
    
    public void union (int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++) {
            
            if(id[i] == pid) {
                id[i] = qid;
            }
        }
    }
    
    public boolean connected (int p, int q)
    {
        return id[p] == id[q];
    }
}

Quick Union

It’s an algorithm for solving the dynamic connectivity problem, also called “lazy approach”.

for (int i = 0; i < n; i++)
    parent[i] = i;      //set parent of object at index i

Root

while (i != id[i]) 
  i = id[i];
return i;

Union

To merge components containing p and q, set the id of p’s root to the id of q’s root.

 int i = root(p);
 int j = root(q);
 id[i] = j;

Connected

Check if p and q have same root.

return root(p) == root(q);

Java Implementation 

public class QuickUnionUF
{
    private int[] id;
    public QuickUnionUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++) 
            id[i] = i;
    }
    public int root(int i)
    {
        while (i != id[i]) i = id[i];
        return i;
    }
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

 

 

Categories
Programming Python

Integrating OpenCV with a Tkinter GUI in Python

OpenCV is a pretty handy tool while working with image processing and computer vision. It’s a large open-source library which can be accessed in a variety of programming languages, including Python. It has also been used for video analysis and real-world applications like CCTV footage analysis. 
OpenCV can be easily installed via the command console, to be used in various capacities while programming in Python.

To use the various packages included in OpenCV, we can install it using pip, via the command,

pip install opencv-python

PIL (Python Imaging Library) is another useful open-source library which supports opening and using various image formats. By installing PIL as well, we can further improve our ability to integrate OpenCV packages in out programs.
We can install PIL using the command:

pip install Pillow

A simple GUI utilizing tkinter is in general, more user-friendly and simpler to use. Hence, we can integrate OpenCV based programs with a tkinter GUI for easier access of end product.
Tkinter can be installed with the command,

pip install tk

To demonstrate, we can create a Python program which utilizes an OpenCV package to open the user’s webcam. The user can then get the RGB codes of various regions in the captured feed via a tkinter GUI.

To begin, we have to import the various packages to be used, from OpenCV, Tkinter and PIL

import cv2
from tkinter import *
from PIL import Image, ImageTk

VideoCapture() is the function in package cv2 which can open a camera for video capturing, whereas the cvtColor() function converts the colourspace of the image provided. Here the first frame from the video feed is provided to be converted to RGB. 

vc = cv2.VideoCapture(0)
cv2image= cv2.cvtColor(vc.read()[1],cv2.COLOR_BGR2RGB)

In the GUI, buttons and labels are created to facilitate turning on the camera with user’s permission, and displaying the pixel data when any region in the video feed is clicked.

window = Tk()
window.title("Video feed")
window.geometry("1200x700")
button = Button(window,text="Click to open camera")
button.grid(row=0, column=0)
label = Label(window, height=500, width=650, text="Video feed here")
label.grid(row=1, column=1, columnspan=1)
label_pix1 = Label(window, height=5, width=30, text="Pixel Location: ")
label_pix1.grid(row=2, column=0)
label_pix2 = Label(window, height=5, width=30, text="Pixel colour scheme (RGB): ")
label_pix2.grid(row=2, column=1)
label_pix3 = Label(window, height=5, width=30, text="Pixel colour scheme (HexCode): ")
label_pix3.grid(row=2, column=3)

Two functions are created to implement these roles.
Show_frames() displays the video feed from the webcam.
At a set interval, a frame from the webcam feed is set as a PhotoImage object (from the PIL package) and updated in the GUI.

def show_frames():
      global cv2image
      cv2image = cv2.cvtColor(vc.read()[1],cv2.COLOR_BGR2RGB)
      img = Image.fromarray(cv2image)

      imgtk = ImageTk.PhotoImage(image = img)
      label.imgtk = imgtk
      label.configure(image=imgtk)
      label.after(20, show_frames)

Pixel_colour() updates the information regarding the clicked pixel, every time a new pixel is clicked in the video feed. Also, the pixel data is printed onto the console.

def pixelcolour(pix):
    print("Pixel location")
    print (pix.x, pix.y)
    label_pix1.config(text=f"Pixel Location: ({pix.x}, {pix.y})")
    print("RGB colour")
    print (cv2image[pix.x, pix.y])
    label_pix2.config(text=f"Pixel colour scheme (RGB): {cv2image[pix.x, pix.y]}")
    print("Hex colour")
    bgr_list = cv2image[pix.x, pix.y].tolist()
    hex_str="#"
    for i in reversed(bgr_list):
         hex_str+=f"{hex(i)[2:]}"
    print(hex_str)
    label_pix3.config(text=f"Pixel colour scheme (RGB): {hex_str}")

Setting the function to the button and the label in the GUI, and setting the mainloop for the window,

button.config(command=show_frames)
label.bind("<Button-1>", pixelcolour)
window.mainloop()

Running the program, a window is opened with a clickable button, which opens up the user’s webcam.
Click anywhere in the video feed et voila! Data about the selected pixel is displayed, which includes its position and colour scheme in RGB.

Working demonstration wherein python program opens webcam. Clicking anywhere will provide the pixels location in colour scheme in Hex code and RGB

Categories
C++ Programming

Cooler than KnapSack

Familiarizing oneself with Design and Analysis of Algorithms this semester, one of the problems my professor keeps talking about is the KnapSack Problem.

In the presented problem we have N items where each item has some profit and weight associated with it and also given a bag with capacity W, and profits associated with them being P. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible. 

The constraint here is we can either put an item completely into the bag or cannot put it at all.

While the popular knapsack problem might deal with maximizing profit in a completely legal way, we borrow inspiration from data miners and contemplate robbing. Just that it is money instead of data and totally hypothetical of course.

We consider that every house on a street has a specific amount of money. Now, our constraint here is that adjacent houses are no-goes.

To minimize space complexity we keep tabs on the values of previous index prev and previous-to-previous index prev2 and we can calculate the value for current index cur.

class Solution 
{
public:
    int rob(vector<int>& A) {
        int prev2 = 0, prev = 0, cur = 0;
        for(auto i : A) {
            cur = max(prev, i + prev2); //here we compare the prev value and the sum of the alternate houses
            prev2 = prev; 
            prev = cur;
        }
        return cur;
    }
};

Now, if we were to add an additional constraint of the first and the last house being adjacent to each other – hence creating more of a cyclic system – we make further changes.

public:
int rob(vector<int>nums)
{
  int n=nums.size();
  if (n<2)
    return n ? nums[0]:0;
  return max(robber (nums, 0,n-2), robber (nums,1,n-1));
}
private:
int robber(vector<int>nums, int l, int r)
{
  int prev2 = 0, prev = 0, cur = 0;
  for (auto i : A)
  {
    int cur = max(prev, i + prev2)
    prev2 = prev; 
    prev = cur;
  }
  return cur;
}

Here, we divide the problem into parts and compute the maximum separately. Once by including the first house and excluding the last house, and again by excluding the first house and including the last house and finding its maximum.

Categories
Programming Python

RESTful APIs

The concept of APIs is pretty fascinating when starting to code, because it allows us to integrate stuff into our projects which we would not want to develop ourselves. An API in short is just an interface for software applications to communicate. Its like the WhatsApp for applications. Let us assume you have an e-commerce application and you want to enable payments you can simply use the RazorPay API or PayTM API. Now lets dive deeper into how these APIs work, how to integrate them into out applications and by the end of this article you would have the working knowledge on how to create your own RESTful API.

What is a RESTful API?

A REST API is a way for computer programs to talk to each other over the internet. It follows certain rules to perform actions like getting data, adding new information, updating, or deleting. This is done typically using HTTP requests. There are multiple HTTP requests but we shall discuss GET, POST, PUT & DELETE as these are the ones which are most commonly used.

Now recently I was brushing up my matplotlib and wanted to plot 4 graphs in real-time and all 4 of them would be running on separate threads. For this i wanted data which would keep changing every second. For this I used the ‘Where the ISS at?’ API. This API provides you with the following information about the ISS(International Space Station) every second.

{
    "name": "iss",
    "id": 25544,
    "latitude": 50.11496269845,
    "longitude": 118.07900427317,
    "altitude": 408.05526028199,
    "velocity": 27635.971970874,
    "visibility": "daylight",
    "footprint": 4446.1877699772,
    "timestamp": 1364069476,
    "daynum": 2456375.3411574,
    "solar_lat": 1.3327003598631,
    "solar_lon": 238.78610691196,
    "units": "kilometers"
}

This API allows you to only GET the data, however this seems like a pretty basic example which showcases how these kinds of APIs work.

Where are RESTful APIs used?

In simple words a RESTful API allows CRUD based operations on a database. CRUD stands for CREATE, RETRIEVE, UPDATE, DELETE. Assume you have a Todo Application, in it you would be required to perform CRUD operations on the Todos. For this we can setup a RESTful API using which our web application or mobile application can send HTTP requests to perform the operations.

How do you send HTTP Requests?

To send HTTP requests, you typically use a programming language or a tool that supports HTTP communication. Here’s a brief overview:

If you are using python you are required to import the requests library.

import requests

response = requests.get("__endpoint_of_the_api_you_are_trying_to_hit__")  # the url is also called the endpoint of the API
print(response.body)

If you are using javascript you can directly use the fetch function.

fetch("__endpoint_of_the_api_youre_trying_to_hit__")
  .then(response => response.json())
  .then(data => console.log(data))
  .catch(error => console.error('Error:', error));

If you don’t know what json is, think of it as something which serves as a common data format for exchanging structured information between web servers and clients. Apart from json XML is also used for similar purposes.

How to create a RESTful API in python?

We will be using the Django framework to create a REST API in python. Let us go over the step by step approach on how to do this.

Install Django and initializing the project

Install django using the pip install django command in the terminal. It is generally advised to create a virtual environment first and then install all the dependancies.
After installing django we must create a project using the django-admin startproject myProjectYou can change the name of the project to whatever you like.
Now we must run the command pip install djangorestframework , it allows us to seamlessly create a REST API.

Navigate to the settings.py file in your project directory, in our case it is myProject. Inside it add rest_framework to the list of installed apps like so.

# myProject/settings.py

INSTALLED_APPS = [
    # other installed apps
    # add the line below to your code
    'rest_framework', 
]

Now create an app using the command python manage.py startapp api.

Creating a Model for the Data

We will now create a model of the data we are trying to store. Let us make a model for a Todo App.

# api/models.py

from django.db import models

class Todo(models.Model):
    title = models.CharField(max_length=50)
    desc = models.CharField(max_length=200)
    isDone = models.BooleanField(default=False)
    date = models.DateTimeField(auto_now_add=True)

    def __str__(self):
        return self.title

We will also have to migrate this model to the database which by default is sqlite in django. You can change it to use a different one if you like. Run python manage.py makemigrations and then python manage.py migrate to do so. If you later make changes to the models by updating existing models or by adding new models just run python manage.py migrate after making changes.

Creating a serializer

In Django, a serializer is essential for converting complex data types, such as querysets or model instances, into Python data types that can be easily rendered into JSON for API responses. Create a serializers.py file in the api folder and change its content to match the following.

# api/serializers.py

from rest_framework import serializers
from .models import Todo

class TodoSerializer(serializers.ModelSerializer):
    class Meta:
        model = Todo
        fields = '__all__'

Creating Views for Get, Create, Update, and Delete

We will create two views: TodoGetCreate for listing and creating Todo items, and TodoUpdateDelete for retrieving, updating, and deleting individual Todo items. This specifies the model (Todo) and serializer (TodoSerializer) to use for these views, streamlining the implementation of CRUD (Create, Read, Update, Delete) operations for the Todo API.

# api/views.py

from django.shortcuts import render
from rest_framework import generics
from .models import Todo
from .serializers import TodoSerializer

class TodoGetCreate(generics.ListCreateAPIView):
    queryset = Todo.objects.all()
    serializer_class = TodoSerializer

class TodoUpdateDelete(generics.RetrieveUpdateDestroyAPIView):
    queryset = Todo.objects.all()
    serializer_class = TodoSerializer

 Creating urls for the Views

We will create two paths: TodoGetCreate for listing and creating Todo items, and TodoUpdateDelete for handling individual Todo items’ retrieval, updating, and deletion based on their primary key.

# api/urls.py

from django.urls import path
from .views import TodoGetCreate, TodoUpdateDelete

urlpatterns = [
    path('', TodoGetCreate.as_view()),
    path('<int:pk>', TodoUpdateDelete.as_view()), 
]

 Note doing just this won’t work as the paths for the project are being used from the urls.pywhich lies in the myProject directory. We will have to include the api.urls in the main urls.py.

# myProject/urls.py

from django.contrib import admin
from django.urls import include, path

urlpatterns = [
    path('admin/', admin.site.urls),
    path('', include('api.urls')),
]

Running the application

Run python manage.py runserver to test it out. You should be able to see it working at http://127.0.0.1:8000/ .

 

 

 

 

Categories
Bash

Bash Scripting

BASH stands for Bourne Again Shell. It is based on bourne shell and is mostly compatible with it features.

Shells act as an intermediary between users and their operating systems, interpreting commands. Shells allow batch command execution and interactive command input, while they are not necessary for program execution. Consider a shell as a way to interact with your system, enabling you to carry out commands, launch programs, and automate difficult processes. The well-known shell BASH is merely a tool for running scripts and commands; it has nothing to do with managing files or configuring an operating system.

In its interactive mode, BASH is frequently linked to command lines and prompts. But when scripts are executed, it can also function in a non-interactive manner. Files with lists of commands that can be used to automate tasks are called scripts. These commands are often run in a consecutive manner. Learn the fundamentals of interactive shells first; you can then combine them in scripts.

A script is basically a sequence of commands in a file. Bash reads the file and processes the commands in order. It moves on to the next command only when the current one has ended.

At first #!/bin/bash is added this header is called an interpreter directive (hashbang, shebang).  It specifies that /bin/bash is to be used as the interpreter when the file is used as the executable in a command.

Declaring some values to variable name:

name="Kanhaiya"

To call out the name ‘Kanhaiya’ we need to use the function echo:

echo $name                  #output->Kanhaiya 
echo "hi my name is $name"  #output->hi my name is Kanhaiya 
echo 'hi my name is $name'  #output->hi my name is $name

Editing the name:

echo “${name/K/k}”     #output->kanhaiya
echo “${name:0:2}”     #output->ka
echo “${name,}”        #output->ram (1st letter lowercase)
echo “${name,,}”       #output->ram (all lowercase)
echo “${name^}”        #output->Kanhaiya (1st letter uppercase)
echo “${name^^}”       #output->KANHAIYA (all uppercase)

File conditions

In Bash, file conditions are checks or tests that you can perform on files or directories. Some common file conditions include

  • [[-e file]]    #exists
  • [[-r file]]    #readable
  • [[-h file]]   #symlink
  • [[-d file]]   #directory
  • [[-w file]]  #writable
  • [[-s file]]   #size is >0 bytes
  • [[-f file]]   #file
  • [[-x file]]  #executable

Chaining multiple commands or tests using && or ||

function comand1 || function comand2

if [condition1] && [condition2]; then
	#execute if true
elif [condition3] || [condition4]; then
	#execute if true
else
	#execute if all above false
fi

Arrays

Arrays are used to store multiple pieces of data in one variable, which can then be extracted by using an index. Most commonly notated as var[index_position]. Arrays use indexing meaning that each item in an array stands for a number. In the array [‘car’, ‘train’, ‘bike’, ‘bus’] each item has a corresponding index. All indexes start at position 0.

Fruits=('Apple' 'Banana' 'Orange')
Fruits[0]="Apple"
Fruits[1]="Banana"
Fruits[2]="Orange"

echo "${Fruits[0]}"                     # Element #0
echo "${Fruits[-1]}"                    # Last element
echo "${Fruits[@]}"                     # All elements, space-separated
echo "${#Fruits[@]}"                    # Number of elements
echo "${#Fruits}"                       # String length of the 1st element
echo "${#Fruits[3]}"                    # String length of the Nth element
echo "${Fruits[@]:3:2}"                 # Range (from position 3, length 2)
echo "${!Fruits[@]}"                    # Keys of all elements, space-separated
Fruits=("${Fruits[@]}" "Watermelon")    # Push
Fruits+=('Watermelon')                  # Also Push
Fruits=( "${Fruits[@]/Ap*/}" )          # Remove by regex match
unset Fruits[2]                         # Remove one item
Fruits=("${Fruits[@]}")                 # Duplicate
Fruits=("${Fruits[@]}" "${Veggies[@]}") # Concatenate
lines=(`cat "logfile"`)                 # Read from file