Posted on

LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

Solution is a greedy recursion. Iterate in reverse order to make sure to get the largest solution first.


function constructDistancedSequence(n: number): number[] {
    const size = 2 * n - 1;
    const result: number[] = new Array(size).fill(0);
    const used: boolean[] = new Array(n + 1).fill(false);
    function backtrack(index: number): boolean {
        if (index === size) return true; // If we filled the array, return success
        if (result[index] !== 0) return backtrack(index + 1); // Skip filled positions
        for (let num = n; num >= 1; num--) { // Try from largest to smallest
            if (used[num]) continue;
            if (num === 1) {
                // Place 1 (only once)
                result[index] = 1;
                used[1] = true;
                if (backtrack(index + 1)) return true;
                used[1] = false;
                result[index] = 0;
            } else {
                // Place num at index and index + num (if valid)
                if (index + num < size && result[index + num] === 0) {
                    result[index] = result[index + num] = num;
                    used[num] = true;
                    if (backtrack(index + 1)) return true;
                    used[num] = false;
                    result[index] = result[index + num] = 0;
                }
            }
        }
        return false;
    }
    backtrack(0);
    return result;
}
Posted on

List of Open Source C++ Games

Yeah, there are plenty of open-source C++ games that run on Linux and can help you learn game development. Here are a few solid ones:

  1. Godot Engine (with C++ modules) – While Godot mainly uses GDScript, you can extend it with C++ for performance-critical parts. Check out its source code here.
  2. SuperTux – A classic side-scrolling platformer similar to Super Mario. Its codebase is relatively easy to understand for beginners. Repo: https://github.com/SuperTux/supertux.
  3. Battle for Wesnoth – A turn-based strategy game with a well-structured C++ codebasFor physics engines and networking in C++, these open-source games and engines will be really useful:
  4. Box2D – Not a game, but a powerful 2D physics engine used in many games. Studying its code will teach you how physics simulations work. Repo: https://github.com/erincatto/box2d.
  5. Bullet Physics – A widely used physics engine for 3D games, including real-time simulations. Repo: https://github.com/bulletphysics/bullet3.
  6. Godot Engine (C++ modules) – While primarily using GDScript, Godot allows custom physics and networking via C++. Repo: https://github.com/godotengine/godot.
  7. Torque 3D – A full-featured game engine with built-in physics (Bullet) and networking. Repo: https://github.com/TorqueGameEngines/Torque3D.
  8. OpenTTD – A transport simulation game with multiplayer networking. The networking code is well-structured and useful for learning. Repo: https://github.com/OpenTTD/OpenTTD.
  9. Teeworlds – A 2D multiplayer shooter with networking and physics interactions. It has a clean and efficient network implementation. Repo: https://github.com/teeworlds/teeworlds.
  10. For pure networking, you might also want to look into ENet (https://github.com/lsalzman/enet), which is a simple and lightweight networking library used in many multiplayer games.e, useful for learning AI, networking, and game mechanics. Repo: https://github.com/wesnoth/wesnoth.
  11. 0 A.D. – A real-time strategy game with a highly professional C++ codebase. If you’re interested in complex game development, this is a great resource. Repo: https://github.com/0ad/0ad.
  12. OpenRA – A modernized engine for old Command & Conquer games. It’s great for learning about game engines and networking. Repo: https://github.com/OpenRA/OpenRA.

Posted on

3174. Clear Digits

You are given a string s. Your task is to remove all digits by doing this operation repeatedly: Delete the first digit and the closest non-digit character to its left. Return the resulting string after removing all digits.

Example 1:

Input: s = “abc”
Output: “abc”

Explanation:

There is no digit in the string.

Example 2:

Input: s = “cb34”
Output: “”

Explanation:

First, we apply the operation on s[2], and s becomes "c4".
Then we apply the operation on s[1], and s becomes "".

Constraints:

  • 1 <= s.length <= 100
  • s consists only of lowercase English letters and digits.
  • The input is generated such that it is possible to delete all digits.

    string clearDigits(string s) {
        stack<char> sc;
        string result = "";
        for( char c : s ){
            if( c >= 48 && c <=57 ){
                sc.pop();
            } else
                sc.push(c);
        }
        while( !sc.empty() ){
            result+= sc.top();
            sc.pop();
        }
        reverse( result.begin(), result.end());
        return result;
    }
Posted on

in order traversal

this was the geeks for geeks problem of the day today


/* A Binary Tree node

class Node {
    int data;
    Node left, right;
   Node(int item)    {
        data = item;
        left = right = null;
    }
}
*/
class Solution {
    ArrayList<Integer> result = new ArrayList<>();
    // Function to return a list containing the inorder traversal of the tree.
    ArrayList<Integer> inOrder(Node root) {
        // Code
        
        inOrderHelper(root);
        return result;
    }
    
    private void inOrderHelper( Node root ){
        if( root == null ) return;
        
        inOrderHelper( root.left );
        result.add(root.data);
        inOrderHelper( root.right );

    }
    
}
Posted on

Find the Number of Distinct Colors Among the Balls

You are given an integer limit and a 2D array queries of size n x 2.

There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the form [x, y], you mark ball x with the color y. After each query, you need to find the number of distinct colors among the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after i<sup>th</sup> query.

Note that when answering a query, lack of a color will not be considered as a color.

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

Output: [1,2,2,3]

Explanation:

  • After query 0, ball 1 has color 4.
  • After query 1, ball 1 has color 4, and ball 2 has color 5.
  • After query 2, ball 1 has color 3, and ball 2 has color 5.
  • After query 3, ball 1 has color 3, ball 2 has color 5, and ball 3 has color 4.

Example 2:

Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]

Output: [1,2,2,3,4]

Explanation:

  • After query 0, ball 0 has color 1.
  • After query 1, ball 0 has color 1, and ball 1 has color 2.
  • After query 2, ball 0 has color 1, and balls 1 and 2 have color 2.
  • After query 3, ball 0 has color 1, balls 1 and 2 have color 2, and ball 3 has color 4.
  • After query 4, ball 0 has color 1, balls 1 and 2 have color 2, ball 3 has color 4, and ball 4 has color 5.

class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        int[] result = new int[queries.length];
        HashMap<Integer, Integer> ballMap = new HashMap<>();
        HashMap<Integer, Integer> colorMap = new HashMap<>();
        for( int i = 0; i < queries.length; i++ ) {
            int[] q =  queries[i];
            int ball = q[0];
            int color = q[1];
            if( ballMap.containsKey( ball )){
                
                int prevColor = ballMap.get( ball );
                colorMap.put( prevColor, colorMap.get(prevColor)-1);
                
                if( colorMap.get( prevColor) == 0 )
                    colorMap.remove(prevColor);
                
            }
            
            ballMap.put(ball, color);
            colorMap.put( color , colorMap.getOrDefault(color, 0) + 1);
            result[i] = colorMap.size();
            
        }
        return result;
    }
}

Posted on

Tuple with Same Product

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where abc, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10<sup>4</sup>
  • All elements in nums are distinct.
class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        uint size = nums.size();
        unordered_map<int, int> mp;

        for( int i = 0; i < size; i++ )
            for( int j = i +1; j< size; j++){
                int prod  = nums[i] * nums[j];
                mp[prod]++;
            }
        
        int res = 0;
        for( auto& [prod, cnt] : mp ){
            int pairs = (cnt *(cnt-1)) / 2;
            res += 8 * pairs;
        }

        return res;
    }
};
Posted on

1790. Check if One String Swap Can Make Strings Equal

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Constraints:

  • 1 <= s1.length, s2.length <= 100
  • s1.length == s2.length
  • s1 and s2 consist of only lowercase English letters.
class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        vector<int> index;
        for( uint8_t i = 0; i < s1.length(); i++ ){
            if( s1[i] != s2[i] )
                index.push_back(i);
            if( index.size() > 2)
                return false;

        }
        if( index.size() == 2 ){
            int i = index[0];
            int j = index[1];
            if( s1[i] == s2[j] && s1[j] == s2[i] ) return true;
        }
    
        return index.size() == 0;
    }
};
Posted on

Removing the Nth Node from a list.

https://leetcode.com/problems/remove-nth-node-from-end-of-list

Given the head of a linked list, remove the n<sup>th</sup> node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Follow up: Could you do this in one pass?

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    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 dummy(0, head);
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        // Move fast n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

        // Move both pointers
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }

        // Remove the nth node
        slow->next = slow->next->next;

        return dummy.next;
    }
};

// Function to create a linked list from an array
ListNode* createLinkedList(int arr[], int size) {
    if (size == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// Function to print a linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

// Main function for testing
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int n = 2;  // Remove the 2nd node from the end

    // Create linked list
    ListNode* head = createLinkedList(arr, size);

    cout << "Original List: ";
    printLinkedList(head);

    // Call removeNthFromEnd function
    Solution solution;
    head = solution.removeNthFromEnd(head, n);

    cout << "Updated List: ";
    printLinkedList(head);

    return 0;
}
Posted on

Does birthrate decline equal the Loss of National Identity

Interesting problem of the modern age is overpopulation. Especially as AI begins to grab hold of the globe, with the new announcement of project stargate intent on opening a dimensional rift to the age of the singularity. A period in history where the rate of progress will go beyond our ability to adapt to it as a species. A landscape where a new form of life may replace homosapiens altogether.

So why would birth rate decline be an issue if artificial minds are about to outnumber biological ones? The issue is indeed that we are already feeling the pains of adaptation. Our economic systems are based on continual growth. Regardless of how you may feel about this constant need to consume the greater fool, without fresh meat we have nothing to grind. And the machine that is the economy will not be able to oil its cogs without the nutrients found in the hopeful minds and hearts of a youthful and optimistic generation. Governments are not ready to concede complete failure, to even witness that their need to squeeze out more from their populace has actually become like squeezing water from a stone.

In some parts of the world, the solution being enacted has proven to be an extremely unpopular one. Open borders. A reallocation of human resources from less developed areas with high birthrates into the developed meat grinders of the world that have perfected soul destruction. Yes, management is doubling down without listening to the woes of their constituents. That is why a tweet would land you in jail in a western country. This extremely difficult and unpopular reality must be confronted with honest conversation. Both the root cause, and potential solution, as well possible outcomes, need to take center stage in the public. We cannot plan for the continued prosperity of any nation without talking about this problem.

And since some are not willing to see their culture simply fade away into the history books, we must address this looming doom cloud that is robbing us of our wills to live, and procreate. We must find a way to give the people hope, without doping them with hopium. We must instill a love and a reverence for words that stood as pillars of our societies before, without the need for lies or fantasy. Or worse yet, bloodlust. Unlike the ship of Thesus, the Dali Lama says the UK will no longer be itself if its original nature is replaced. A surprising precept from one who cultivates compassion.

While I personally hope that governments choose to improve quality of life standards for their current citizens to reproduce as needed. I also believe that the rule of law needs to be enforced. No decisions of this magnitude should happen without discussion. So if we are being asked to sacrifice our culture for continued economic prosperity, lets have an open discussion about it.

Posted on

Profound need for Self Correcting Minds

Psychology in my opinion was a pseudoscience for the longest time. It wasn’t until we had brain scans that backed up subjective experiences and doctors notes, that I began to think otherwise. There is a terrible word, that is as confusing as it is horrifying: Schizophrenia. And most AI today suffers from the same core symptom as a human with this illness, hallucinations. The mind is constructed in time with belief systems. That’s why a cascading system failure is possible, yet not noticeable, until the dichotomy between perceived reality and actual objective reality collide and collapse. We see this as a psychotic break in the form of humans. In Large Language Models we see this as inappropriate reactions, and alignment issues.

Restructuring the model, rebuilding the mind. Perhaps what we can extend from our learnings with the synthetic mind, is that deep structural issues need to be reworked. And like a hypnotist, a prompt engineer can trigger rewiring of core logic. The weights. I think of the Parameters and Layers of a Neural Network as genetic talents. But the same model can be trained to go into a myriad of weighted structures. And is our best synthetic example of nature vs nurture. AI research isn’t just about duplicating the human mind to force it to work in a capitalistic dystopian future like a bound demon to a golem. It provides exciting tools to allow us to explore the development of a mind, and how to steer it.

All through out history we have had echo towers of truth. Repeaters of commands. Realignment of goals and even national identity was broadcast from Minarets of the institution. The world is indeed a simulation, and over 8 Billion different simulations currently running. Language is the fundamental mode of communication, this means telling stories to each other is the most essential reality building system in existence today. So AI research may help us uncover deeper insights into how to heal the human mind, that has been constructed by incorrect perceptions and even malevolent deception.

Once we can find a common link between “prompt engineering” and the possibility of using hypnosis or another method to replicate that interface in the biological, we may be able to predict the outcome of treatment on an individual far in advance. And with time, solidify deterministic beliefs, as we can start predicting a persons reaction to any input. Without natures love for variation, we may be tempted to even install Mind1.0 into all of our children. A successful model of a motivated son or daughter. A golden child guaranteed to add generational wealth. So keep an eye out for this scifi future. When we can understand the construction of, and modify, our own minds.