Showing posts with label Data Structures and Algorithms. Show all posts
Showing posts with label Data Structures and Algorithms. Show all posts

Game of Life program in C# | Game of Life Problem in C#

 Conway's Game of Life is a classic cellular automaton that simulates the evolution of a grid of cells over discrete time steps. The rules of the game are simple: each cell can be either alive or dead, and the state of a cell in the next generation depends on the states of its neighboring cells. The rules are as follows:

  1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by overpopulation.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Here's a basic implementation of Conway's Game of Life in C#:

using System;

class Program
{
    static int GridWidth = 20;
    static int GridHeight = 20;
    static bool[,] currentGeneration = new bool[GridWidth, GridHeight];
    static bool[,] nextGeneration = new bool[GridWidth, GridHeight];
    static Random random = new Random();

    static void Main(string[] args)
    {
        InitializeGrid();
        Console.CursorVisible = false;

        while (true)
        {
            Console.Clear();
            DisplayGrid();
            UpdateGrid();
            System.Threading.Thread.Sleep(100); // Adjust the delay
//to control the speed.
        }
    }

    static void InitializeGrid()
    {
        for (int x = 0; x < GridWidth; x++)
        {
            for (int y = 0; y < GridHeight; y++)
            {
                currentGeneration[x, y] = random.Next(2) == 0;
            }
        }
    }

    static void DisplayGrid()
    {
        for (int y = 0; y < GridHeight; y++)
        {
            for (int x = 0; x < GridWidth; x++)
            {
                Console.Write(currentGeneration[x, y] ? "█" : " ");
            }
            Console.WriteLine();
        }
    }

    static void UpdateGrid()
    {
        for (int x = 0; x < GridWidth; x++)
        {
            for (int y = 0; y < GridHeight; y++)
            {
                int liveNeighbors = CountLiveNeighbors(x, y);

                if (currentGeneration[x, y])
                {
                    // Apply the rules for live cells.
                    nextGeneration[x, y] = liveNeighbors == 2 || liveNeighbors == 3;
                }
                else
                {
                    // Apply the rules for dead cells.
                    nextGeneration[x, y] = liveNeighbors == 3;
                }
            }
        }

        // Swap current and next generation grids.
        bool[,] temp = currentGeneration;
        currentGeneration = nextGeneration;
        nextGeneration = temp;
    }

    static int CountLiveNeighbors(int x, int y)
    {
        int count = 0;

        for (int dx = -1; dx <= 1; dx++)
        {
            for (int dy = -1; dy <= 1; dy++)
            {
                if (dx == 0 && dy == 0)
                    continue;

                int nx = x + dx;
                int ny = y + dy;

                if (nx >= 0 && nx < GridWidth && ny >= 0 && ny < GridHeight &&
currentGeneration[nx, ny])
                {
                    count++;
                }
            }
        }

        return count;
    }
}

This code creates a console application that simulates Conway's Game of Life. You can adjust the GridWidth and GridHeight variables to change the size of the grid, and the delay in the game loop to control the speed of the simulation.


The provided C# implementation of Conway's Game of Life is quite straightforward, and its time complexity is already quite efficient for a basic implementation. The time complexity for this implementation is O(N^2) in terms of the grid size, where N is GridWidth or GridHeight. This is because for each cell in the grid, you update its state based on the states of its neighbors, and you iterate through the entire grid.

To improve time complexity significantly, you could consider parallelizing the computation using multi-threading or taking advantage of GPU processing, but this would make the code more complex and is not suitable for a basic example.

If you need to handle very large grids or require even more efficiency, you might want to look into more advanced techniques, such as using sparse data structures like HashLife or other optimizations specific to Conway's Game of Life.

In summary, while the given implementation can be optimized in various ways, the time complexity for a basic implementation is already quite efficient for smaller grid sizes. For larger or more efficient implementations, you would need to explore advanced techniques beyond the scope of this basic example.




-----------------------------------------------

Find the Longest Common Prefix in C#

In this article, we will see the longest common prefix in C#

Problem Description

Write a function to find the longest common prefix string amongst all the arrays of strings in C#.

If there is no any common prefix then return an empty string "".

The solution to finding the Longest Common Prefix

Input Example

Example 1

Let the set of strings be { "flower", "flight", "fly", "flow" };

The longest common prefix here is "fl"

Example 2

Let the set of strings be {"dot", "dog", "donkey", "door", "cat" } there is no common prefix here so the longest common prefix is "", which means, an empty string.

Since there is no common prefix at all. 

To find the longest common prefix of a given set of strings in C#, you can use the following algorithm:

  1. Initialize a variable prefix to an empty string.
  2. If the input array is empty, return the empty string.
  3. Sort the input array in lexicographic order.
  4. Iterate over the characters in the first string in the sorted array.
  5. For each character, compare it to the corresponding character in the other strings in the array. If any of the characters don't match, return the current prefix.
  6. If all the characters match, append the current character to the prefix.
  7. Return the prefix.

Here is the C# code that implements this algorithm:

public class LongestCommonPrefix {
    public static string LongestCommonPrefixFun(string[] input) {
        if (input.Length == 0) {
            return "";
        }
        Array.Sort(input);
        string prefix = "";
        for (int i = 0; i < input[0].Length; i++) {
            char c = input[0][i];
            for (int j = 1; j < input.Length; j++) {
                if (i >= input[j].Length || input[j][i] != c) {
                    return prefix;
                }
            }
            prefix += c;
        }
        return prefix;
    }
}
C#

You can call this method with an array of strings as an argument, like this:

string[] input = { "flower", "flight", "fly", "flow" };
string result = LongestCommonPrefix.LongestCommonPrefixFun(input);
Console.WriteLine("Longest Common Prefix is- " + result); // Output: "fl"
C#

This code will output "fl", which is the longest common prefix of the input strings "flower""flight", "flow", and "flight".


Output





-----------------------------------------------------

Job Sequencing Problem in C#

  In this article we will discuss the Job sequencing problem in C#, we will achieve it using a greedy approach algorithm.

Problem statement

The job sequencing problem is a common problem that contains assigning a set of jobs to a set of machines, where each job has a deadline and a profit, and we have to get the maximum profit before the job deadline.

Given an array of jobs where each job has its deadline and profit. And Profit can get only if the job is finished before the job deadline also every job takes a single unit of time, so the minimum possible deadline for any job is 1 so we have to get the maximum profit before the job deadline.

For example,

JobIDDeadlineProfit
1390
2120
3230
4125
5215

Output

JobID:-> 4,3,1

C# code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JobsSequencingProblemInCSharp {
    public class Jobs {
        public int JobsID {
            get;
            set;
        }
        public int Deadline {
            get;
            set;
        }
        public int Profit {
            get;
            set;
        }
    }
    public class JobsSequencingProblem {
        public static void JobsSequencing() {
            List < Jobs > Jobs = new List < Jobs > () {
                new Jobs {
                    JobsID = 1, Deadline = 3, Profit = 90
                },
                new Jobs {
                    JobsID = 2, Deadline = 1, Profit = 20
                },
                new Jobs {
                    JobsID = 3, Deadline = 2, Profit = 30
                },
                new Jobs {
                    JobsID = 4, Deadline = 1, Profit = 25
                },
                new Jobs {
                    JobsID = 5, Deadline = 2, Profit = 15
                }
            };
            // Sort Jobs in the decreasing order of profit
            Jobs = Jobs.OrderByDescending(j => j.Profit).ToList();
            // Determine the maximum deadline of job
            int maxDeadline = Jobs.Max(j => j.Deadline);
            // Initialize the slots array
            int[] slots = new int[maxDeadline];
            foreach(Jobs Job in Jobs) {
                int slot = -1;
                for (int i = Job.Deadline - 1; i >= 0; i--) {
                    if (slots[i] == 0) {
                        slot = i;
                        break;
                    }
                }
                // If the slot is available, assign the Jobs to that slot
                if (slot != -1) {
                    slots[slot] = Job.JobsID;
                }
            }
            Console.WriteLine("Selected Jobs:");
            for (int i = 0; i < maxDeadline; i++) {
                if (slots[i] != 0) {
                    Console.WriteLine("Jobs " + slots[i]);
                }
            }
        }
    }
}
Public static void Main(string[] args) {
    JobsSequencingProblem.JobsSequencing();
    Console.ReadLine();
}
C#

Problem Explanation

This implementation is done by the greedy approach; we start by sorting the jobs in the decreasing order of the profit and then we determine the maximum deadline of the job then we initialize an array of slots with a length equal to the maximum deadline.

And then we iterate through each job and find the latest available slot for that job by starting from its deadline and going backward until we find an empty slot. If we find an available slot, we assign the job to that slot. If we don't find an available slot, we skip the job.

Finally, we print the selected jobs by iterating through the slots array and printing the job ID for each non-zero slot.

 



------------------------------------------