DEV Community: DHDucky

DILI #15: More Lit Codes with LeetCodes !!!!

DHDucky — Fri, 22 Sep 2023 16:57:25 +0000

WASSAPPPPP! I have decided doing LeetCodes is too LIT 🔥🔥🔥! So here's some more problems that I found interesting!

Problem #1: 3 Sum

This problem in a way is easier than it's predecessor: 2 Sum. Because the answer doesn't require the index, but rather digits in the array that sum to 0. So, I instantly thought of sorting the array, and just do a "selective bruteforcing" using the Two Pointer Technique.

We need to meet the requirement: a + b + c = 0. So, by choose the first digit as "a" and increment the left pointer by one when the sum is negative, and reduce the right pointer by one when the sum is positive - as the array is sorted. With this we can quickly find all the sets that sums to 0.

Though, we can make it BETTER 💪💪💪! If the 2 digits adjacent to each other are the same, we would just be repeating what we were doing in the last iteration. So that's a loss of time! And if that sums to 0 as well, the output array would have 2 of the same answers, and that is said by the problem designer to be exclude. So we need to skip to the next index whenever that happens.
Source Code:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int head = 0;
        int n = nums.size();
        vector<vector<int>> ans;

        if(n < 3) return ans;
        for(int i = 0; i < n - 2; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i - 1] == nums[i]) continue;

            int left = i + 1;
            int right = n - 1;
            while(left < right){
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else{
                    ans.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1])
                        left++;
                    left++;
                    while (left < right && nums[right] == nums[right - 1])
                        right--;
                    right--;
                }
            }
        }
        return ans;
    }
};

Problem #2: Find Minimum in Rotated Sorted Array

This problem baffled me when I first read it,... until I reached the "O(log n)" line. To find "target" digit in an array in O(log n), I instantly thought of Binary Search,... or you can see it as the headline in NeetCode:).

Anyways, as the array is already sorted in ascending order but "rotated", it's just Binary Search with a twist. The act of rotating is just splitting the array into 2 ascending subarrays. So, knowing whether we are in the left ascending part or the right ascending part would be a great help. So, how should we know ? Well, if our "middle" digit is larger than our leftmost digit in the array, we must be in the left part. And if not, we on the right part.

The end goal is to find the smallest digit in that array, so where is it abstractly. Well, it should be in the right part as the array is rotated! So, if we're on the left part, we would want to move right to reach our smallest digit, else we would want to move left to go to the smallest digit in our right side.

Source Code:

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int ans = nums[0];

        while(left <= right){
            if(nums[left] < nums[right]){
                ans = min(ans, nums[left]);
                break;
            }

            int mid = (left + right)/2;
            ans = min(ans,nums[mid]);
            if(nums[mid] >= nums[left]){
                left = mid + 1;
            }
            else right = mid - 1;
        }
        return ans;
    }
};

That's all the time I have for today! Only two, I know, how lazy of me! But these two puzzles really bring out the beauty of 2 of the most staple techniques in programming. I had time to do the second part of Problem #2 which instead of finding the smallest number, I need to search for a target number. It's a great problem to help you learn how to ultilized the thing you know, Problem #2, and also how to split bigger problem into smaller ones! And that's it! Have a great week until next time!

REFERENCES:
LeetCode
NeetCode

DILI #14: I lied....

DHDucky — Fri, 15 Sep 2023 18:14:05 +0000

Apprently the week after holiday is quite a busy week, for me at least. So, I couldn't keep my promise on the note-taking app as I couldn't really find time.... But as a compensation, let's do some LeetCodes!!!!

Problem 1: Longest Repeating Character Replacement

Solving this problem was not hard (as the method to this was spoiled on NeetCode). Using the sliding windows technique, I couold solve this quite neatly. Also, because it only required me to give the length of the longest substring with repeating letters after the replacement, I didn't need actually modify the string; I only need to keep track of the certain variables like: number of the most repeated digit in the window(maxCount) and the two positions of the window(left and right).

And when this condition is satisfied: right - left + 1 - maxCount = k, that is a candidate for our final result. Finally, I just need to see if that candidate is longer than the last repeatedy until the window ends.

Soure Code:

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26);
        int maxCount = 0;

        int l = 0;
        int r = 0;
        int res = 0;

        while(r < s.size()){
            count[s[r] - 'A']++;
            maxCount = max(maxCount, count[s[r] - 'A']);
            if(r - l + 1 - maxCount > k){
                count[s[l] - 'A']--;
                l++;
            }
            res = max(res, r - l + 1);
            r++;
        }
        return res;
    }
};

Problem 2: Pacific Atlantic Water Flow

This was another fun problem. But different from last time, the only help I had was it was a problem using Graph. Thanks NeetCode. Anyways. This problem give you a 2-D grid with each cells are mountains of an island and the value is the height.

Given that it's gonna rain, and water flow from mountains with higher heights to lower or equal heights, which mountain or cell has water that can make it to both the Pacific Ocean and the Atlantic Ocean. Look at the image below.

So, working from a cell and see if it's gonna reach both ocean is not gonna get you anywhere. Believe me, I tried. It's gonna take an excessive amount of time. So, let works backwards and start from the oceans. And the water logic will just literally flow backwards as in our waterway will flow from low-height mountains to high-height mountains.

From the image, the North and West is touching Pacific, while South and East is touching Atlantic. So we just need to navigate paths from those cells using DFS and keep track of what cells are visited. Which ever cells are visited by both the "Pacific path" and the "Atlantic path" is the cell we are looking far.

Source Code:

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<int>> res;

        vector<vector<bool>> pac(m, vector<bool> (n));
        vector<vector<bool>> atl(m, vector<bool> (n));

        for(int i = 0; i < m; i++){
            dfs(heights,pac,i,0,m,n);
            dfs(heights,atl,i,n-1,m,n);
        }
        for(int j = 0; j < n; j++){
            dfs(heights,pac,0,j,m,n);
            dfs(heights,atl,m-1,j,m,n);
        }
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(pac[i][j] && atl[i][j]){
                    res.push_back({i,j});
                }
            }
        }
        return res;
    }
private:
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int i, int j, int m, int n){
        visited[i][j] = true;
        if(i > 0 && !visited[i-1][j] && heights[i-1][j] >= heights[i][j])
            dfs(heights, visited, i-1,j,m,n);
        if(i < m-1 && !visited[i+1][j] && heights[i+1][j] >= heights[i][j])
            dfs(heights, visited, i+1,j,m,n);
        if(j > 0 && !visited[i][j-1] && heights[i][j-1] >= heights[i][j])
            dfs(heights, visited, i,j-1,m,n);
        if(j < n-1 && !visited[i][j+1] && heights[i][j+1] >= heights[i][j])
            dfs(heights, visited, i,j+1,m,n);
    }
};

Are 2 problems all I've done? No, I've done at least like 3... But those 2 are most fascinating to me of how different thought processes they needed. One is to find when to move the window and how to make the best of each evaluation and one is working backwards.

With that, I shall conclude today's week blog. As always, all advices are welcomed. Cya next week! Peace!

REFERENCES:
LeetCode... that's it!

DILI #13: Logging off Holiday. Logging in Back to work.

DHDucky — Fri, 08 Sep 2023 15:14:18 +0000

As you can see, last week, I did not post anything and yes, based on the title of this blog, I was on holiday. But it is justifiable, because it's my country's Independence Day. But less on that and more on today's topic: Authentication, aka Login and Logout.

The library I'm going to use to help me with this is fstream, which can create files, write information to files, and read information from files. With this, I can create a login system which create a file that stores the registration. Then, the login system will check if the username and password entered by the user match the usernames and passwords in the file. If they do, the user will be logged in. Otherwise, the user will be prompted to enter their username and password again.

This code will create the file and open it to store the infomations and I can even designated the location and the name of the file:

ofstream file;
file.open("d:\\CODES AND STUFFS\\SnakeGame\\" + username + ".txt");

And to store user's inputs into the file, it's similar to cin but with "file" keyword:

file << username << endl << password;
file.close();

After, it just a matter of matching the file's data with user's login's input:

bool Login()
{
    string username, password, checkUN, checkPW;
    cout << "Enter username: "; cin >> username;
    cout << "Enter password: "; cin >> password;

    ifstream read("d:\\CODES AND STUFFS\\SnakeGame\\"  + username + ".txt");
    getline(read, checkUN);
    getline(read, checkPW);

    if(checkUN == username && checkPW == password){
        return true;
    }
    else return false;

}

With this a simple authentication system is created. And the only left to do is add this to your desired project. Mine is my first game: Snakes. Check my GitHub.

With this, more can be done like a note-taking app that can save your data and can only be accessed by you given correct authentication. I might post a blog about this by the middle of next week as a replacement for the missed last week's blog.

As always, all advices about anything are welcome. See you in about 3-4 days!

REFERENCES:
GeeksforGeeks
Help with visualizing

DILI #12: Snakes

DHDucky — Fri, 25 Aug 2023 06:50:16 +0000

Today's blog will be primarily about a classic game that I was able to program, Snake. With the implementation of one of the data structure, Queue, in the previous post, I was able to program it. Though it's a simple-looking game, the programming part was not simple. As many functions were needed and I have to make sure no human logic errors would occur.

1. Logic:
I used Queue as a way to keep track of the Snake's coordinates. So, for each frame of movement, the coordinate at the front of the Queue(tail of the Snake) is Dequeued and the coordinate at the tail of the Queue (front of the Snake) will Enqueue whatever the next inputted coordinates is. And put that in a loop and Bam! We are done with the movement.

And in the Snake game, whenever you eat a fruit, your size increases. So, I did just that as well. Everytime the next cell's coordinate match with the fruit's coordinate, I simply don't Dequeue and move on from there.

2. Future ideas:
I'm thinking off adding a few power-ups or increase the difficulty over time like double the point power-up or an extra life power-up. But those seem kinda dull, so I'm hoping to get some recommendations.

3. Source Code:

The Queue:

#include <iostream>

using namespace std;

class Node {
    friend class Snake;

    private:
        int xpos, ypos;
        Node *nextNode;
};

class Snake {
    private:
        Node *front, *rear;

    public:
        Snake() {
            front = new Node();
            rear = new Node();
            front = NULL;
            rear = NULL;
        }

        void enqueue(int x, int y) {
            Node* newNode = new Node();
            newNode->xpos = x;
            newNode->ypos = y;
            newNode->nextNode = NULL;

            if (rear == NULL) {
                rear = newNode;
                front = newNode;
            }
            else {
                rear->nextNode = newNode;
                rear = newNode;
            }
        }

        void dequeue(int& x, int& y) { // It will directly put data in given variables
            if (!(this->isEmpty())) {
                x = front->xpos;
                y = front->ypos;

                Node *temp = front;
                front = front->nextNode;

                delete temp;

                if(this->isEmpty())
                    rear = NULL;
            }
            else cout << "Queue is Empty.\n";
        }

        void getFront(int& x, int& y) { // only return the node data from front of queue
            if (!(this->isEmpty())) {
                x = front->xpos;
                y = front->ypos;
            }

            else cout << "Queue is empty.\n";
        }

        bool isEmpty() {
            return (front == NULL);
        }
};

The Game:

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <map>
#include <time.h>
#include <windows.h>
#include "Snake.cpp"

using namespace std;

//VARIABLES
map<int, map<int, char> > frame;

float speed = 10.0;

int i, j;

int width = 50, height = 20;

Snake snake;

int headX, headY;

int bodyX, bodyY;

int fruitX, fruitY;

char head = '\351';
char bodyPart = 'o';
char fruit = '\242';


int score;

bool gameOver;

bool direction; // 0 means vertical, 1 means horizontal
bool whichward; // In vertical: 0 means right 1 means left.
                // In horizontal: 0 means up and 1 means down

//FUNCTION DECLARATION
void setUp(); // Settings
void addBody(); // Increase size when eat fruit
void update(); // Update the movement using queue
void generateFruit(); // Generate the fruit
void changeDirection(char dir); // Input of movement
void moveHead(); // Do the movement
void printMap(); // UI

//MAIN FUNCTION
int main() {

    setUp();
    generateFruit();

    do {
        update();
        if (_kbhit()) {
            changeDirection(_getch());
        }
    } while(gameOver == false);

    cout << "Game Over.\n\n";

    system("pause");
    return 0;
}

void setUp() {
    score = 0;

    for(i = 0; i < width; i++)
        frame[0][i] = '\262';
    for(i = 1; i < height - 1; i++){
        frame[i][0] = '\262';
        for(j = 1; j < width - 1; j++)
            frame[i][j] = ' ';
        frame[i][j] = '\262';
    }

    for(i = 0; i < width; i++)
        frame[height-1][i] = '\262';



    srand(time(NULL));
    headX = rand() % (width - 5);
    headY = rand() % (height - 5);

    frame[headY][headX] = head;

    snake.enqueue(headX - 2, headY);
    frame[headY][headX - 2] = bodyPart;
    snake.enqueue(headX - 1, headY);
    frame[headY][headX - 1] = bodyPart;

    printMap();

    direction = 0;
    whichward = 0;

    gameOver = false;

    Sleep(1000/speed);
}

void addBody() {
    moveHead();

    printMap();

    Sleep(1000/speed);
}

void update() {
    moveHead();

    snake.dequeue(bodyX,bodyY);
    frame[bodyY][bodyX] = ' ';

    printMap();
    Sleep(1000/speed);
}

void generateFruit() {
    fruitX = rand() % width;
    fruitY = rand() % height;
    if(frame[fruitY][fruitX] == ' ')
        frame[fruitY][fruitX] = fruit;
    else generateFruit();
 }

void changeDirection(char dir) {
    if((dir == 'w' || dir == 's') && direction == 0){
        if(dir == 'w')
            whichward = 0;
        else
            whichward = 1;
        direction = 1;
    }
    else if((dir == 'a' || dir == 'd') && direction == 1){
        if(dir == 'a')
            whichward = 1;
        else
            whichward = 0;
        direction = 0;
    }
}

void moveHead() {
    snake.enqueue(headX, headY);
    frame[headY][headX] = bodyPart;
    if(direction == 0 && whichward == 0)
        headX++;
    if(direction == 0 && whichward == 1)
        headX--;
    if(direction == 1 && whichward == 0)
        headY--;
    if(direction == 1 && whichward == 1)
        headY++;

    if(headX == fruitX && headY == fruitY){
        score++;
        addBody();
        generateFruit();
    }
    if(frame[headY][headX] == '\262'
        || frame[headY][headX] == bodyPart)
        gameOver = true;

    frame[headY][headX] = head;
}

void printMap() {
    system("cls");
    for(i = 0; i < height; i++) {
        for(j = 0; j < width; j++) {
                cout << frame[i][j];
            }
        if (i == 10)
            cout << "    Score: " << score;
        cout << endl;
    }
}

P.S: I used map in the code as well though I have not learnt it. But it's mostly use for the drawing of the grid so it's not important. Maybe I'll learn it next week.

REFERENCES:
Codebytes for the Queue Logic
NVitanovic for the general Format of the Code

DILI #11: Stack and Queue

DHDucky — Fri, 18 Aug 2023 15:20:46 +0000

Stack and queue are two of the most fundamental and literal data structures in computer science. As they work how they sound like.They are both linear data structures, but they differ in the way that elements are added and removed.

1. STACK:
a) Definition:

A stack is a Last In First Out (LIFO) data structure. This means that the last element added to the stack is the first element to be removed. A stack is a stack. Like a stack of book or a stack of unwashed dishes that your mom told you to do but you are too lazy and you ended up get your butt whooped. Anyways, when you add a book to the pile, you put it on top of the other books. When you remove a book from the pile, you take the top book off (if you're a normal person and not a psychopath and just take it from the middle).

b) The Code:

To use stack you can either use STL(Standard Template Library) by doing

#include <stack>

or if you're an overachiever, you can do it the hard way using class.

#include <iostream>
class MyStack {
    private:
        vector<int> data;               // store elements
    public:
        /** Insert an element into the stack. */
        void push(int x) {
            data.push_back(x);
        }
        /** Checks whether the queue is empty or not. */
        bool isEmpty() {
            return data.empty();
        }
        /** Get the top item from the queue. */
        int top() {
            return data.back();
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        bool pop() {
            if (isEmpty()) {
                return false;
            }
            data.pop_back();
            return true;
   }
};

c) The Reverse Polish Notation:

In Rverse Polish Notation, or how I like to call it: The Indonesian Notation, the operands are pushed onto a stack, and the operators are applied to the top two operands on the stack. The result of the operation is then pushed back onto the stack.

For example, the expression 3 + 4 * 5 in RPN would be written as 3 4 5 * +. The operands 3 and 4 are pushed onto the stack, and then the operator * is applied to them. The result, 12, is then pushed back onto the stack. The operator + is then applied to 12 and 5, and the final result, 17, is the output of the expression.

RPN is a very efficient notation for evaluating mathematical expressions. This is because the order of operations is implicit in the notation, so there is no need to use parentheses to group the operands.

CODE:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int n = tokens.size();
        for(int i = 0; i < n; i++){
            if(tokens.size() > 1 || isdigit(tokens[i]) st.push(stoi(tokens[i]));
            else{
                int x2 = st.top();
                st.pop();
                int x1 = st.top();
                st.pop();
                switch(tokens[i]){
                    case '+': x1 = x1 + x2; break;
                    case '-': x1 = x1 - x2; break;
                    case '*': x1 = x1 * x2; break;
                    case '/': x1 = x1 / x2; break;
                }
                st.push(x1);
            }
        }
        return st.top();
    }
};

2. QUEUE
a) Definition

A queue is a First In First Out (FIFO) data structure. This means that the first element added to the queue is the first element to be removed. A queue can be visualized as a line of people waiting to buy tickets. So, literally a queue, the first person in line is the first person to get a ticket and the person that arrived later will be at the end of the queue. Now you can tell your kids that computers know manners so you should too!

b) The Code:

Not much to say:

The Lazy way:

#include <queue>

The Asian way:

class MyQueue {
    private:
        // store elements
        vector<int> data;       
        // a pointer to indicate the start position
        int p_start;            
    public:
        MyQueue() {p_start = 0;}
        /** Insert an element into the queue. Return true if the operation is successful. */
        bool enQueue(int x) {
            data.push_back(x);
            return true;
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        bool deQueue() {
            if (isEmpty()) {
                return false;
            }
            p_start++;
            return true;
        };
        /** Get the front item from the queue. */
        int Front() {
            return data[p_start];
        };
        /** Checks whether the queue is empty or not. */
        bool isEmpty()  {
            return p_start >= data.size();
        }
};

Though the Asian way looks more impressive, it's inefficient. As, you Dequeue, the space before it is left empty. So, if given a limited space or a fixed-queue, we are screwed.

FYI: To enter a queue is Enqueue and to be off a queue is Dequeue

c) Circular Queue:

Though not as interesting at the Polish up there, this is a neat concept as well, a circular queue. It ultilized the wasted space left by the Asian way of making a queue in a fixed space. For a better visualizations, you can check it out on Leetcodes.

CODE:

class MyCircularQueue {
private:
    vector<int> data;
    int head = 0;
    int tail = 0;
public:
    MyCircularQueue(int k): data(k){}

    bool enQueue(int value) {
        if(isFull()) return false;
        data[(head + tail++) % data.size()] = value;
        return true;
    }

    bool deQueue() {
        if(isEmpty()) return false;
        head = (head + 1) % data.size();
        tail--;
        return true;
    }

    int Front() {
        if(isEmpty()) return -1;
        return data[head];
    }

    int Rear() {
        if(isEmpty()) return -1;
        return data[(head + tail - 1) % data.size()];
    }

    bool isEmpty() {
        return !tail;
    }

    bool isFull() {
        return tail == data.size();
    }
};

REFERENCES:
LeetCode
Stack at GeeksforGeeks
Queue at GeeksforGeeks

DILI #10: A Classic In Programming

DHDucky — Fri, 11 Aug 2023 16:49:36 +0000

HARE - TORTOISE ALGORITHM

Also known as Floyd’s cycle finding algorithm, is a literal classic in Linked List. Using a simple technique of one fast moving pointer (the hare) and one slow moving one (the tortoise), one can see if there's a loop or not in a given Linked List. Also, it has an interesting property that will wow-ed any of you like how it wow-ed me.

Because in a singly Linked List, you can only traverse like one-way road, many pointers are needed. For example, a simple program to reverse a linked list needs up to 3 pointers to navigate and reverse it:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode* forw = cur->next;
            cur->next = prev;
            prev = cur;
            cur = forw;
        }
    return prev;
    }

};

The above was a small exercise in Leetcode. Anyways, that is to show most Linked List problems require multiple pointers and Floyd's Hare and Tortoise algorithm also follows suit.

The algorithm starts by moving the two pointers to the first node of the linked list. The slow pointer then moves one node at a time, while the fast pointer moves two nodes at a time. If the linked list does not contain a cycle, the fast pointer will eventually reach the end of the list and stop. However, if the linked list does contain a cycle, the fast pointer will eventually catch up to the slow pointer. Or the hare will eventually catch up to the tortoise.

But the crazy part comes later, Floyd's algorithm's property can pinpoint the start of cycle/loop. The start of the cycle can be found by moving the tortoise to the start, then move both tortoise and the hare, who's still at the meeting point, until they both meet again. That point is the start of the cycle. NOW THAT'S COOL, IS IT NOT?

Let's declare some variables:

X: the distance from the start of Linked List to the start of cycle.
Y: the distance from the start of the cycle to the meeting point.
C: one full trip around the cycle.
t: the amount of time the tortoise loops.
h: the amount of time the hare loops.

With that, we can say:

The tortoise traveled a distance of X + Y + t*C.
The hare traveled a distance of X + Y + h*C.

But because the hare is twice as fast as the tortoise, it would travel double the distance given the same time. So we have the equation:

X + Y + t*C = 2(X + Y + h*C)

After simplification, we have:

X + Y = (t + h)*C or X = (t + h)*C - Y.

But going a full round trip any number of time is equal to going a full round trip one time or just think trigonometrically. So we have X = C - Y.

So, the distance from the start of Linked List to the start of cycle will equals to the meeting point to the start of the cycle. Hence, we have the claim above. Very neat!

REFERENCES:
GeeksforGeeks
LeetCode

DILI #9: Linked Lists

DHDucky — Fri, 04 Aug 2023 16:28:29 +0000

Linked lists, a powerful data structure that can be used for a variety of tasks. They are a better choice than arrays for storing data that is not known in advance, and are also efficient for performing operations such as insertion and deletion. For reference, this is a perfect illustration of an array and a linked list.

To describe what is happening, a linked list is a linear data structure in which each element, called a node, contains data and a pointer to the next node in the list. The first node in the list is called the head, and the last node is called the tail.

Linked lists are a dynamic data structure(remember Vectors?), which means that they can grow and shrink as needed. This makes them ideal for storing data that is not known in advance, such as the results of a search query.

There are primarily 2 types: singly and doubly linked lists. Singly can only access the next node as such:

And doubly linked lists can access both the previous and the next nodes as such:

With that, here's an example of a linked list:

struct Node {
  int data;
  Node* next;
};

Node* head = nullptr;
Node* tail = nullptr;

void insert(int data) {
  Node* newNode = new Node();
  newNode->data = data;
  newNode->next = nullptr;

  if (head == nullptr) {
    head = newNode;
    tail = newNode;
  } else {
    tail->next = newNode;
    tail = newNode;
  }
}

void printList() {
  Node* current = head;
  while (current != nullptr) {
    cout << current->data << " ";
    current = current->next;
  }
}

int main() {
  insert(10);
  insert(20);
  insert(30);

  printList();

  return 0;
}

This code creates a linked list with three nodes, and then prints the list to the console.

Anyways, there are a variety of other things you can do as well:

Inserting a node
Deleting a node
Searching for a node
Traversing the list
Reversing the list
Sorting the list These operations can be implemented using pointers and can be done recursively or iteratively.

For example, given the set up above, this is a program which would insert a new node at a given ith index:

 void addAtIndex(int index, int val) {
        // Return if invalid index
        if (index>size || index < 0) {
            return;
        }
        Node* current= head;
        Node* new_node = new Node(val);
        // index == 0 implies insert at head
        // Considered separately as we need to update head
        if (index == 0) {
            new_node->next = current;
            // Update head
            head = new_node;
        }
        else {
            // Run loop till index-1 as we need to insert node at index
            for(int i=0;i<index-1;++i) {
                current= current->next;
            }
            /* 
                current --> current->next
                            /
                        new_node

                current    current->next
                      \      /
                        new_node           

            */            
            new_node->next = current->next;
            current->next = new_node;
        }
        // Increase size whenever we insert node
        size++;
    }

Similarly, you can do the deletion as well.

Learning linked lists in C++ is like learning how to ride a unicycle. It's a pain in the *ss at first, but once you get the hang of it, you'll be glad you did.

Just kidding, linked lists are actually pretty cool. They're a powerful data structure that can be used for a variety of tasks. If you're interested in learning more about linked lists, I encourage you to check out the resources that I have listed down below in the references.

And who knows, maybe you'll even learn how to ride a unicycle along the way.

REFERENCES:
GeeksforGeeks
LeetCode
William Fiset on YT

DILI #8: This is BS.

DHDucky — Fri, 28 Jul 2023 16:10:59 +0000

Today, I will talk about BS. You've guessed it, it's Binary Search! Opposed to its more nonsensical cousin, BS is a really efficient and most definitely sensible algorithm to find an item from a sorted array or vector.

For starters, I did not do a good job covering array and just jumped to doing a problem. So, here we go. An array is like a list of items where you can store many of same type of data in one array. Imagine going into a supermarket, there are different sections for meats, vegetables, fruitsa and etc. Each of those sections is an array and they're storing something of their own types. So, a "meat" array can only store "meat" and nothing else but "meat".

The same thing also applies to vector but the only key difference is an array size/length has to be established beforehand. Whereas a vector size/length can grow or shrink dependent on the type of "meat" you took or put back.

That should brief the basics of array and vector. Now, we need to talk BS. BS works by dividing a sorted list in half repeatedly until you've reached the desired result. For example, try playing the higher lower number game. I will think of a number in a range and you can try to guess it. The most efficient way to do it every single time is to guess the halfway point. And everytime, we will get closer and closer to the answer by a half. And to put this in code, Here's a step-by-step description of using binary search to play the game above:

Let min = 1 and max = n.
Calculate the average.
If you guessed it, yay!.
If I say higher, set your min to that halfway point.
If I say lower, set your max to that halfway point.
Then rinse and repeat from step 2.

This is the simplest form of BS:

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main() {
  int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
   cout << "Not found";
  else
    cout << result;
  return 0;
}

With this, you can find the item in your list most efficiently. Just sort the array or vector and BS your way to the answer. With BS-ing in your skillset, you can make everyone gasped of how amazing you are!

REFERENCES:
GeeksforGeeks

DILI #7: Classes - something Marxists does not understand!

DHDucky — Fri, 21 Jul 2023 14:40:41 +0000

Moving on from the usual programming which is called Procedural Progarmming, where the code runs step by step from top down through fucntions, I have mistakenly made my first step into OOP (Object-Oriented Programming). You see what I did there? Mistakenly and OOP! Anyways, OOP is usually said to be based on the "real world" with objects (hence the name) that contains datas and attributes and can interact with the real world. There are many new concepts that are introduced, but the most popular ones seemed to fly right over the Marxists' heads, classes.

If the Marxists have read a bit about struct, they might have an easier time understanding classes. For them, surely they read OOP backwards. ...Ahem...they are similar as class can be used to replace struct in all cases:

struct DateStruct
{
    int year {};
    int month {};
    int day {};
};

class DateClass
{
public:
    int year {};
    int month {};
    int day {};
};

But the other way around can be met with some issues as structure is unable to have functions in them but class can.

class DateClass
{
public:
    int year {};
    int month {};
    int day {};

    void print() // defines a member function named print()
    {
        std::cout << year << '/' << month << '/' << day;
    }
};

The function of course can be accesed through the "." operators like in struct.

int main()
{
    DateClass today { 2023, 7, 14 };

    today.m_day = 21; // use member selection operator to select a member variable of the class
    today.print(); // use member selection operator to call a member function of the class

    return 0;
}

This prints:

2023/7/21

I'm sure you should have noticed the "public:" keyword there right below class. It's an access specifier that say the members of those in the class is public, meaning it can be accesed by functions outside of the class itself. By default, struct is public and class is private. Meaning if your code exclude that "public" keyword in class, only the functions or whatever inside that class can accessed it. Hence, why it presents.

Typically, class members/objects are private so that no direct change can be made to them and actions/functions are made public. Consider the following program:

#include <iostream>

class DateClass // members are private by default
{
    int m_month {}; // private by default, can only be accessed by other members
    int m_day {}; // private by default, can only be accessed by other members
    int m_year {}; // private by default, can only be accessed by other members

public:
    void setDate(int month, int day, int year)
    {
        m_month = month;
        m_day = day;
        m_year = year;
    }

    void print()
    {
        std::cout << m_month << '/' << m_day << '/' << m_year;
    }

    // Note the addition of this function
    void copyFrom(const DateClass& d)
    {
        // Note that we can access the private members of d directly
        m_month = d.m_month;
        m_day = d.m_day;
        m_year = d.m_year;
    }
};

int main()
{
    DateClass date;
    date.setDate(10, 14, 2020); // okay, because setDate() is public

    DateClass copy {};
    copy.copyFrom(date); // okay, because copyFrom() is public
    copy.print();
    std::cout << '\n';

    return 0;
}

This also shows that any function that is within the class can access both privately and publicly.

In conclusion, classes are like struct but are more classy and can do way more things. It's also quite fun to mess about with, unlike in real life.

P.S: Y'all SHALL give me some advices on blog-writing and programming. (I got tired of politely asking)

*REFERENCE: *
Chapter 13.1 - 13.4
GeeksforGeeks

DILI #6.5(Recursive Sudoku)

DHDucky — Fri, 14 Jul 2023 15:21:02 +0000

SUDOKU

It's a classic puzzle game that can be seen on your local newspaper. For those who (somehow) do not know the rules, it is as follow: Fill in the grid with digits 1-9 one each in each row, column and 3x3 box. The rules are that simple, yet sometimes, it can be mind-bogglingly hard to solve any of them. So, I came up with a plan ... just bruteforce it. If we can just try each number individually and checked if that number breaks the rule, we will reach the solution ... eventually.

But a human doing that is not quite possible. As there are 10^21 ways to arrange the digits in the Sudoku grid, that would take a very long time. So, after taking a sneak peak at Recursion, I got a "slave" to do it for me, the computer:

#include <iostream>

using namespace std;

bool checkValid(int grid[9][9], int row, int col, int val)
{
    for (int i = 0; i < 9; i++){
        if (grid[i][col] == val)
            return false;
    }

    for (int i = 0; i < 9; i++){
        if (grid[row][i] == val)
            return false;
    }
    int rowBox = row - row % 3;
    int colBox = col - col % 3;
    int temp1 = rowBox + 3;
    int temp2 = colBox + 3;
    for (int i = 0; rowBox < temp1; rowBox++)
        for (int j = 0; colBox < temp2; colBox++)
            if (grid[rowBox][colBox] == val)
                return false;
    return true;
}

bool Solve(int grid[9][9], int row, int col)
{
    if (row == 8 && col == 9) return true;
    if (col == 9){
        row++;
        col = 0;
    }

    if (grid[row][col] != 0)
        return Solve(grid, row, col + 1);

    for (int i = 1; i <= 9; i++){
        if (checkValid(grid,row,col,i)){
            grid[row][col] = i;
            if (Solve(grid,row,col+1)) return true;
        }
        grid[row][col] = 0;
    }
    return false;
}

int main()
{
    int grid[9][9];
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            cin >> grid[i][j];

    if (Solve(grid,0,0)){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++)
                cout << grid[i][j]<<" ";
                cout << endl;
        }
    }
    return 0;
}

Though this can only find the first solution that pops up, it's already beter than me in term of Sudoku-solving capabilities. By using a concept that uses Recursion called Backtracking, it will go through all combination and retrace its footsteps when a number it tries break the rules. Fairly straightforward, I would say!

However, it cannot guarantee that that would be the only possible solution. I have tried to reverse the order of checking from 1->9 to 9->1, but to put both of them into the same algorithm does not seem to work properly and that can only also bring the maximum amount of solutions to 2. Although, I can check for the "uniqueness" of a Sudoku, where it can only be called a Sudoku puzzle when there is only one unique solution, I would have to do that ... manually... by changing the order of number-checked by hand and see if the 2 grids are different. That is very dull as the ultimate goal of an algorithm is to do it in one go. I've got a few ideas using vectors but the bugs bugged me so here I am, asking for help.

P.S: Also, my 3x3-box-checking codes in checkValid() seemed bad so I need some advices on that.

REFERENCE:
GeeksforGeeks
Good'ol Indian Man on YT
SUDOKU YT CHANNEL THAT GOT ME TO WRITE THIS

DILI #6

DHDucky — Fri, 07 Jul 2023 09:04:24 +0000

TREES(PART 1)

The trees I'm refering to are not those you see in the park with roots and leaves ... well these also have roots and leaves but it's not that kind of tree...You know what I mean. The trees I'm talking about are Binary Trees, Tertiary Trees and n-ary Trees. For example:

There are many applications for it, or that at least what the website said, like for sorting and searching or like how you see how the files in your folder or arrange with one file containing the others. For now, I have not learn that far but I know the basics. Like all the properties like how the maximum number of nodes there can be on a Binary Tree of height N is 2^N or in an n-ary Tree is n^N. But those are just things you can find on the Internet so here is the link to all of them.

Different from an array or a vector which are linear and can be access through indexing, a node on a tree can ony be access through other nodes or sequential and need to be "Traversed". There are generally 2 Tree Traversal algorithms:

Depth-First Search (DFS) Algorithms, which can be further catergorised into 3 more:

Preorder Traversal (current-left-right)
Inorder Traversal (left-current-right)
Postorder Traversal (left-right-current)

Breadth-First Search (BFS) Algorithms for now I can only find one which is Level Order Traversal(left-to-right, level-by-level)

Ultilizing the tree up there, these are examples for each Traversal that can help you get comfortable with them:

Pre-order Traversal of the above tree: 1-2-4-5-3-6-7
In-order Traversal of the above tree: 4-2-5-1-6-3-7
Post-order Traversal of the above tree: 4-5-2-6-7-3-1
Level-order Traversal of the above tree: 1-2-3-4-5-6-7

Now for the more technical part, how do you create a tree? There are no Tree data type so you can only manually create it via struct or class:

// Use any below method to implement Nodes of tree

// Method 1: Using "struct" to make
// user-define data type
struct node {
    int data;
    struct node* left;
    struct node* right;
};

// Method 2: Using "class" to make
// user-define data type
class Node {
public:
    int data;
    Node* left;
    Node* right;
};

But for actual programmes to be done, something more needs to be added. The NULL:

class Node {
public:
    int data;
    Node* left;
    Node* right;
    // Val is the key or the value that
    // has to be added to the data part
    Node(int val)
    {
        data = val;
        // Left and right child for node
        // will be initialized to null
        left = NULL;
        right = NULL;
    }
};

With the NULL, our Traversal Algorithms can know when to stop and check other branches of the Trees. For the 3s in DFS, all can be done using Recursion and only differs by the order of which we checked the current, left and right nodes so I'll let you figure out the other 2s and only do Preorder:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> nodes;
        preorder(root, nodes);
        return nodes;
    }
private:
    void preorder(TreeNode* root, vector<int>& nodes) {
        if (!root) {
            return;
        }
        nodes.push_back(root -> val);
        preorder(root -> left, nodes);
        preorder(root -> right, nodes);
    }
};

Just with a bit of shuffling you can get the other 2 quite simply. For BFS, it can be done iteratively but that introduces a new concept called "queue" so I will lay that off for now. I think that's enough for now. Anymore will be too much for you and me.

As always, any advices on coding or blog writing are much appreciated!

REFERENCE:
GeeksforGeeks
Alex's help with class 'cus I forgot to learn that

DILI #5

DHDucky — Fri, 30 Jun 2023 14:48:10 +0000

RECURSION

Have you ever gone into a mirror maze and got absolutely flabbergasted by an infinte amount of you getting smaller and smaller. That's my friend is Recursion ... or at least how I visualize it after some productive time in a cafe with a friend.

Similar to what you see in the mirror maze, smaller yous that keep going as far as the eyes can see, in coding in general, Recursion or recursive functions divide a big problem to smaller sub-problems that can be easily sovled. For example, problems like Tower of Hanoi or more mathematical like calculating Factorials or The Fibbonacci sequence.

But how is it different from Iterations like for loops or while loops? Well in a sense, I feel like whatever can be done via Recursion can be using Iterations and vice versa (I'm not copying geeksorgeeks.com, I have paraphrased it). It just that you have to evaluate which method is better given certain scenarios. For example, Recursion make your code looks simpler but simplicity is hard to achieve as it is quite a handful to wrap your head around. Problems like I mentioned above if dissect carefully with the use of Recursion, the problem becomes quite neat and can be hard to use Iterations. So, I would recommend using Iterations for small works like calculations and Recursion for more abstract works. Like calculating a factorial:

Using Iterations:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans = 1;
    for (int i = 2; i <=n; i++){
        ans = ans * i;
    }
    cout << ans;
    return 0;
}

Or if you are a pro with using Recursion (like ... ahem ...me):

#include <iostream>

using namespace std;

int factorial (int n)
{
    if (n == 1) return 1;
    return n * factorial(n-1);
}

int main()
{
    int n;
    cin >> n;
    cout << factorial(n);
    return 0;
}

And for the Finale, as I'm a Vietnamese, it would be a shame not to try to code Tower of Hanoi:

#include <iostream>

using namespace std;

void towerOfHanoi(int n, int& cnt, char a, char b, char c)
{
    if (n == 1) {
        cout << a << " --> " << c <<endl;
        cnt++;
    }
    else {
        towerOfHanoi (n-1,cnt,a,c,b);
        towerOfHanoi (1,cnt,a,b,c); 
        towerOfHanoi (n-1,cnt,b,a,c);
    }
}

int main()
{
    int n;
    cin >> n;
    char a = 'A';
    char b = 'B';
    char c = 'C';
    int cnt = 0;
    towerOfHanoi(n,cnt,a,b,c);
    cout << "It is done in " << cnt << " steps";
    return 0;
}

You can try the code and have this on your side when your friends challenge you to play Tower of Hanoi. To briefly explain how the code works, I did the Tower of Hanoi backwards and changed the Start (char a), Middle (char b), and Goal (char c) for everytime the biggest piece at the time is move to the intial Goal. This is a picture that helped me and hopefully you as well.

As always, any advices on coding, blog-writing and recommendations on what to learn are all much appreciated by me. Hope y'all have a nice day!

REFERENCE:
GeeksforGeeks
Alex