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

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

2270. Number of Ways to Split Array

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        // Keep track of sum of elements on left and right sides
        long long leftSum = 0, rightSum = 0;

        // Initially all elements are on right side
        for (int num : nums) {
            rightSum += num;
        }

        int count = 0;
        // Try each possible split position
        for (int i = 0; i < nums.size() - 1; i++) {
            // Move current element from right to left side
            leftSum += nums[i];
            rightSum -= nums[i];

            // Check if this creates a valid split
            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
};

You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

  • The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
  • There is at least one element to the right of i. That is, 0 <= i < n - 1.

Return the number of valid splits in nums.

Example 1:

Input: nums = [10,4,-8,7]
Output: 2
Explanation: 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
- Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
- Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

Example 2:

Input: nums = [2,3,1,0]
Output: 2
Explanation: 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
- Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

Constraints:

  • 2 <= nums.length <= 10<sup>5</sup>
  • -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

Posted on

Subarrays with sum K

Given an unsorted array of integers, find the number of continuous subarrays having sum exactly equal to a given number k.

Examples:

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.
Input: arr = [9, 4, 20, 3, 10, 5], k = 33
Output: 2
Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.
Input: arr = [1, 3, 5], k = 0
Output: 0 Explaination: No subarray with 0 sum.

Constraints:

  • 1 ≤ arr.size() ≤ 105
  • -103 ≤ arr[i] ≤ 103
  • -107 ≤ k ≤ 107
class Solution {
  public:
    int countSubarrays(vector<int> &arr, int k) {

    // unordered_map to store prefix sums frequencies
    unordered_map<int, int> prefixSums;
  
    int res = 0;
    int currSum = 0;

    for (int i = 0; i < arr.size(); i++) {
        
        // Add current element to sum so far.
        currSum += arr[i];

        // If currSum is equal to desired sum, then a new
        // subarray is found. So increase count of subarrays.
        if (currSum == k)
            res++;

        // Check if the difference exists in the prefixSums map.
        if (prefixSums.find(currSum - k) != prefixSums.end())
            res += prefixSums[currSum - k];

        // Add currSum to the set of prefix sums.
        prefixSums[currSum]++;
    }

    return res;

    }
};

Posted on

1678. Goal Parser Interpretation

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G""()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G""()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser‘s interpretation of command.

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"
class Solution {
public:
    string interpret(string command) {
        string result = "";
        for(int i=0; i<command.size(); i++){
            if(command[i] == 'G') result += "G";
            else if(command[i] == '(' && command[i+1] == ')') {
                result += "o";
                i++;
            }
            else if(command[i] == '(' && command.substr(i,4) == "(al)"){
                result += "al";
                i += 3;
            }
        }
        return result;
    }
};

Posted on

2559. Count Vowel Strings in Ranges

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [l<sub>i</sub>, r<sub>i</sub>] asks us to find the number of strings present in the range l<sub>i</sub> to r<sub>i</sub> (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the ith query.

Note that the vowel letters are 'a''e''i''o', and 'u'.

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].
class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        vector<int> prefixSum(words.size()+1,0);
        vector<int> result;

        function<bool(char)> isVowel = [](char ch)->bool{
            if( ch == 'a' || ch == 'e' || ch =='i' || ch == 'o' || ch=='u'){
                return true;
            }

            return false;
        };

        int index = 1;
        for( string str:words){
            if( isVowel(str.front()) && isVowel(str.back()) ){
                prefixSum[index] = prefixSum[index-1]+1;
            } else
                prefixSum[index] = prefixSum[index-1];

            index++;
        }
 

        for( auto q: queries ){
          result.push_back( prefixSum[q[1]+1] - prefixSum[q[0]] );
        }

        return result;
    }
};
Posted on

1030. Matrix Cells in Distance Order

You are given four integers rowcolsrCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.

The distance between two cells (r<sub>1</sub>, c<sub>1</sub>) and (r<sub>2</sub>, c<sub>2</sub>) is |r<sub>1</sub> - r<sub>2</sub>| + |c<sub>1</sub> - c<sub>2</sub>|.

Example 1:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

class Solution {
public:

    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {

        queue<pair<int,int>> q;        
        vector<vector<int>> result;

        vector<vector<bool>> visited( rows , vector<bool>(cols, false));        
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        q.push({rCenter, cCenter});
        visited[rCenter][cCenter] = true;

        while( !q.empty() ){
            int size = q.size();
            while(size > 0){
                auto [currentRow, currentCol] = q.front();              
                result.push_back({currentRow, currentCol});

                q.pop();
                for (auto [dr, dc] : directions) {
                    int newRow = currentRow + dr;
                    int newCol = currentCol + dc;


                    if( newRow >= 0 && newRow < rows && newCol >=0 && newCol < cols 
                        && !visited[newRow][newCol]){                        
                        q.push({newRow,newCol});
                        visited[newRow][newCol] = true;
                    }
                }
                size--;
            }

        }
        return result;
        
    }
};