DEV Community: drinkingWater

Singleton in Unreal Engine

drinkingWater — Thu, 03 Nov 2022 13:13:43 +0000

Singleton pattern is a very important pattern for storing states in a game and keep them persistent between levels. Also, to share data between at some point.
*Problem: * In a game I am currently working on, there are some actors called trash. After a certain amount delay if these items aren't pick up, they destroy and increase pollution factor in the world. Now the pollution factor has to be accessed by every trash to send the event if they are destroyed. Also, if scene changes, the pollution factor won't change.

**Solution: **Make a singleton class where all the variables which have to be persistent between levels or scenes.

**Challange: **In unity I used a lot of DontdestroyOnLoad to make a lot of persistent object which is recommended. I could keep multiple singleton classes for different mechanism or work. In unreal however you can work with only one singleton class which is called "Game Instance" here.

**My Approach: **Firstly created a Game Instance from blueprint menu. It's like any other blueprint.

In the project settings I changed the default instance with the new one I created.

In the Game Instance blueprint I created a custom event which will count pollution factor within. For that I also added a variable to store the pollution factor. And also, why not the life span of the trashes. That way I can change the life span for every trash at once. Also, how much trash to spawn at each time.

In the trash I call the event and update the trash count. For that we Get the game instance and cast it to the newly made game instance.

This is how I am implementing singleton for now. This does solve all the singleton related problem for me. But the bad habit of having multiple singleton classes in Unity does irritate me xD.

Back-To-CP: day 10

drinkingWater — Fri, 21 Oct 2022 18:07:39 +0000

21-10-2022

Longest Substring Without Repeating Characters

The problem is quite simple if applied brute force, but the time complexity will be O(n^3). So, the good approach is sliding window. Where we keep two pointers at the beginning and a map to store the frequency of the characters in the array. Right pointer keeps moving forward if doesn't encounter the same character twice. If encountered, left pointer will start from the Right pointer position now. This is achieved by in the frequency map, instead of the actual frequency, the position of right pointer is stored. This allows left to jump directly to right + 1.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int ans = 0;
        map<char, int> hmap;
        int left = 0, right = 0;
        while(right<n){
            if(hmap[s[right]] > 0){
                left = max(hmap[s[right]], left);
            }
            ans = max(ans, right-left + 1);
            hmap[s[right]] = right + 1;
            right++;
        }
        return ans;
    }
};

Back-To-CP: day 3

drinkingWater — Sat, 15 Oct 2022 17:58:25 +0000

15-10-2022

Remove Nth Node From End of List

Another problem that can be solved using two pointers technique.
It can be easily solved if we run a loop and hold all the addresses in an array then just find out the middle point, remove the link between nodes.
But it can be done efficiently using two pointers. Firstly, the fast node is advanced n times, so that the slow pointer will be at the n-1'th position when fast pointer reaches the end.

This however gives an error if the length of the list is equal to n. In which case answer would be null pointer. So, an edge case for checking for list length equal 1 is necessary.

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode *f = head;
        ListNode *s = head;
        for(int i = 0; i < n ; i++){
            f = f->next;
        }
        if(f == nullptr) {
            return head->next;
        }
        while(f->next != nullptr && f != nullptr) {
            s = s->next;
            f = f->next;
        }

        s->next = s->next->next;
        return head;
    }
};

Back-To-CP: day 2

drinkingWater — Fri, 14 Oct 2022 16:47:13 +0000

14-10-2022

Delete the Middle Node of a Linked List

The problem is pretty straightforward. With the given head of a singly linked list, we delete the middle node. The definition of is given as middle = n/2 where n is the length of the list.
Since it's a singly linked list, traversal to black is not possible. So, it's necessary to get to the previous node of middle node or middle - 1.
Since only head is given, a traversal is needed to count the length. Then break the connection.

/**
 * 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* deleteMiddle(ListNode* head) {
        if(head->next == nullptr){
            return nullptr;
        }
        int count = 0;
        ListNode* ptr = head;
        ListNode* ptr2 = head;

        while(ptr != nullptr){
            count++;
            ptr = ptr->next;
        }
        for(int i = 0; i < (count / 2) - 1; i++){
            ptr2 = ptr2->next;
        }

        ptr2->next = ptr2->next->next;
        return head;
    }
};

After accepted I looked for other efficient ways to solve this problem and learnt this new way called Slow pointer Fast pointer
This is a pretty straight forward technic to find middle of a list with unknown size. There is a slow pointer and fast pointer who starts from the beginning. The fast node increments itself twice more than the slow node. As a result, when the fast node already reaches the end, the slow pointer will be at the middle.

With first attempt I ran to an error
runtime error: member access within null pointer of type 'ListNode' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior
for
while(f != nullptr || f->next != nullptr){ f = f->next->next; s = s->next; }
Turns out if I need to check both for pointer to be not null.

On the second attempt I got the same error. Because I initialize fast pointer before and if it was a list with length one, it gives us the error for accessing fast->next->next which doesn't exist.
So, an edge case was necessary.

/**
 * 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* deleteMiddle(ListNode* head) {

        if(head->next == nullptr){
            return 0;
        }

        ListNode *s = head;
        ListNode *f = head->next->next;

        while(f != nullptr && f->next != nullptr){
            f = f->next->next;
            s = s->next;
        }

        s->next = s->next->next;
        return head;
        return head;
    }
};

Reverse String

My approach was simple. Have two pointers at beginning and end. Swap the two pointer and increment and decrement the pointers accordingly.

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0, h = s.size() - 1;
        while(l < h){
            swap(s[l], s[h]);
            l++;
            h--;
        }
    }
};

Back-To-CP Day 1

drinkingWater — Thu, 13 Oct 2022 16:38:21 +0000

13-10-2022

Two Sum II

For the array I used two pointers, one for the beginning of the and one for the end of the array. In a loop I checked if sum of those pointer value greater or less than the target value and decrease end pointer or increase start pointer by 1. Otherwise stop the loop.
Returned a vector containing start pointer + 1 and end pointer + 1 as the index in result supposed to start from 1 and not 0.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
         vector<int> res;
         int l = 0, h = numbers.size() - 1;
         for(int i = 0; i < numbers.size(); i++){
            if(numbers[l] + numbers[h] < target){
                l++;
            }else if(numbers[l] + numbers[h] > target){
                h--;
            }
            else{
                res.push_back(l+1);
                res.push_back(h+1);
                break;              
            }
        }
        return res;
    }
};

Move Zero
The approach is quite easy and solved it with one go. Firstly, I declared a vector. Then checked if the array contains non-zero, append that that vector otherwise counts how many 0s are there. After the counting is done we just append the number of 0s that was connected. At the end I just replaced the given vector with the new vector. Quite Simple and fun.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int> res;
        int cc = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != 0){
                res.push_back(nums[i]);
            }else{
                cc++;
            }
        }
        for(int i = nums.size() - cc; i < nums.size(); i++){
            res.push_back(0);
        }
        nums = res;
    }
};

Starting Problem Solving Again

drinkingWater — Thu, 13 Oct 2022 15:39:10 +0000

I started doing problem solving at the beginning of my first year. Then the corona hit, the lockdown started. Lost all motivation to code and do anything productive. Spent my days playing games and watching animes or web series.
Three years later I have nothing but regrets. Well, and some skills with Unity, digital arts, Illustrator, photoshop and ricing Linux.
So, here I am again, after 3 years, starting competitive programming again, to better myself.
Also starting this blog to record myself.