DEV Community: Akash Jadhav

Private

Akash Jadhav — Thu, 28 Nov 2024 05:10:32 +0000

1> Medium To Hard (Graph-Based DP with memoization)
Problem Description

Frankenstein, the alchemist, is on a quest to brew the elixir of life. In his attempts, he combines various ingredients and potions, but he has yet to succeed. Every time he brews something, he meticulously notes down the ingredients and their combinations.

For instance, when he combines "snakefangs" and "wolfbane", he discovers the "awakening" potion, and he records the recipe as:

awakening = snakefangs + wolfbane

Similarly, when three ingredients are required, he notes the recipe as:

thunderstorm = rain + wind + lightning

In general, the recipe would follow this format:

Potion 1 = Ingredient 1 + Ingredient 2
Potion 2 = Ingredient 1 + Ingredient 2 + Ingredient 3
Potion 3 = Ingredient 1 + Ingredient 2 + Ingredient 3 + Ingredient 4
and so on...

Each recipe requires magical orbs to brew. The number of magical orbs needed is equal to the number of ingredients minus one. If a potion is made from several ingredients, the total magical orbs required are the sum of orbs required for each ingredient.

An ingredient can either be an item or a potion. Items are already available, while potions are brewed from ingredients, possibly other potions. In his notes, Frankenstein always lists the result as a potion.

The problem is that sometimes the same potion can be brewed with different recipes, some requiring fewer magical orbs. Given a potion and Frankenstein's notes, you need to determine the minimum number of magical orbs required to brew that potion.

Constraints:

(0 < N < 20) (N is the number of recipes)

Input:

The first line contains an integer (N) representing the number of recipes.
The next (N) lines contain strings representing the recipes in the format: PotionName=Ingredient1+Ingredient2+...+IngredientN.
The last line contains the name of the potion that Frankenstein needs to brew.

Output:

Print a single integer representing the minimum number of magical orbs required to brew the given potion.

Examples:

Example 1:

Input:

4
awakening=snakefangs+wolfbane
veritaserum=snakefangs+awakening
dragontonic=snakefangs+velarin
dragontonic=awakening+veritaserum
dragontonic

Output:

Explanation:
In this example, there are two ways to brew dragontonic:

dragontonic = awakening + veritaserum:
- Brewing awakening requires 1 orb, and brewing veritaserum requires 1 orb.
- Total orbs required = 1 + 1 = 2 orbs.
dragontonic = snakefangs + velarin:
- Brewing snakefangs and velarin requires no orbs, as they are both ingredients.
- Total orbs required = 1 orb.

Thus, the minimum orbs required is 1.

Example 2:

Input:

6
oculus=thunderbrew+jellfish
felix=thunderbrew+pumpkin
wigenweld=thunderbrew+ladybug
wigenweld=oculus+felix
thunderbrew=pumpkin+firefly
maxima=pumpkin+ladybug
wigenweld

Output:

Explanation:
To brew wigenweld with the minimum number of magical orbs:

First, brew thunderbrew, which requires 1 orb.
Then, brew wigenweld using thunderbrew + ladybug, requiring 1 more orb.

Thus, the total orbs required is 2.

Answer

import java.util.*;
public class PotionBrewer {

    private static Map<String, List<List<String>>> potionRecipes = new HashMap<>();
    private static Map<String, Integer> potionMemo = new HashMap<>();

    public static void main(String[] args) {
        Scanner inputScanner = new Scanner(System.in);
        int recipeCount = inputScanner.nextInt();
        inputScanner.nextLine(); // Consume the newline

        for (int i = 0; i < recipeCount; i++) {
            String recipeLine = inputScanner.nextLine();
            String[] potionParts = recipeLine.split("=");
            String resultingPotion = potionParts[0];
            String[] requiredIngredients = potionParts[1].split("\\+");

            potionRecipes.putIfAbsent(resultingPotion, new ArrayList<>());
            potionRecipes.get(resultingPotion).add(Arrays.asList(requiredIngredients));
        }

        String targetPotion = inputScanner.nextLine();
        inputScanner.close();

        int minimumOrbs = calculateMinimumOrbs(targetPotion);
        System.out.print(minimumOrbs);
    }

    private static int calculateMinimumOrbs(String potion) {
        if (!potionRecipes.containsKey(potion)) {
            return 0; // Base ingredient requires no orbs
        }

        if (potionMemo.containsKey(potion)) {
            return potionMemo.get(potion);
        }

        int minimumOrbsRequired = Integer.MAX_VALUE;

        for (List<String> recipe : potionRecipes.get(potion)) {
            int currentOrbsRequired = recipe.size() - 1; // Orbs required for this recipe
            for (String ingredient : recipe) {
                currentOrbsRequired += calculateMinimumOrbs(ingredient); // Add orbs for sub-ingredients
            }
            minimumOrbsRequired = Math.min(minimumOrbsRequired, currentOrbsRequired);
        }

        potionMemo.put(potion, minimumOrbsRequired);
        return minimumOrbsRequired;
    };
};

2> Easy To Medium (Greedy/string)

Here's a clean version of the problem statement:

Problem: JustifyWords

Problem Description:

Given a list of K words and two integers N and M, you are tasked with arranging the words into N lines following these rules:

Each line can contain no more than M characters.
Each word should appear entirely on one line.
If multiple words are on a line, they should be separated by a single space.

The goal is to determine the maximum number of words that can be arranged within the N lines of length M.

Constraints:

(0 < K < 25)
(0 < N < 10)
(0 < M < 10)
Words will contain only lowercase alphabets.

Input:

The first line consists of an integer K, representing the total number of words.
The next K lines each consist of one word.
The last line consists of two space-separated integers N and M, representing the number of lines and the maximum number of characters per line, respectively.

Output:

Print a single integer denoting the maximum number of words that can be arranged into the N lines.

Time Limit: 1 second

Examples:

Example 1:

Input:

8
i
hello
how
going
u
whatsapp
help
hmm
5 5

Output:

Explanation:

We have 8 words to arrange in 5 lines, each having a maximum of 5 characters.

One way to arrange the words to fit the maximum number of words is:

how_i
going
u_hmm
help_
hello_

Here, 7 words can be fitted. There could be other valid combinations, but we are interested in the maximum number of words that can be accommodated.

Example 2:

Input:

6
a
is
b
be
it
a
5 4

Output:

Explanation:

We have 6 words to arrange in 5 lines, each with a maximum of 4 characters. One possible arrangement is:

a_is
b_be
it_a
____

Here, all 6 words can fit, and that is the maximum possible arrangement.

Answer

#include<bits/stdc++.h>
using namespace std;

int K, N, M;
vector<string> words;
int maxCnt = 0;

void backtrack(int i, vector<int> &lines, int cnt, const vector<string> &w) {
    if(static_cast<size_t>(i) == w.size()) { // Cast i to size_t for comparison
        if(cnt > maxCnt) 
            maxCnt = cnt;
        return;
    }
    if(cnt + (static_cast<int>(w.size()) - i) <= maxCnt) return; // Cast w.size() to int
    for(int j = 0; j < N; j++) {
        if(lines[j] == 0) {
            lines[j] = w[i].size();
            backtrack(i + 1, lines, cnt + 1, w);
            lines[j] = 0;
            break;
        } else {
            if(lines[j] + 1 + static_cast<int>(w[i].size()) <= M) { // Cast w[i].size() to int
                lines[j] += 1 + w[i].size();
                backtrack(i + 1, lines, cnt + 1, w);
                lines[j] -= 1 + w[i].size();
            }
        }
    }
    backtrack(i + 1, lines, cnt, w);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> K;
    words.resize(K);
    for(auto &s: words) cin >> s;
    cin >> N >> M;
    vector<string> valid;
    for(auto &s: words) 
        if(static_cast<int>(s.size()) <= M) // Cast s.size() to int
            valid.push_back(s);
    sort(valid.begin(), valid.end(), [&](const string &a, const string &b) -> bool {
        if(a.size() != b.size()) return a.size() > b.size();
        return a < b;
    });
    vector<int> lines(N, 0);
    backtrack(0, lines, 0, valid);
    cout << maxCnt;
}

3> Hard (Graph)
BusCount

Problem Description

As the Transportation In-Charge of a reputed company, your responsibility is to ensure that buses are available for every employee and that they arrive on time.

Since pandemic restrictions have been lifted, but not completely, the number of people allowed on buses is still limited. Employees have started visiting the office regularly.

You are given an M x M matrix, which represents the distance between each location. The value in the i-th row and j-th column represents the distance between the i-th place and the j-th place. Assume that all locations are connected by roads and that the first location is the office. The distance between the i-th place and the j-th place is the same as the distance between the j-th place and the i-th place. The top-left element of this matrix (0, 0) is the office location.

The number of people boarding the bus at each location is known a priori and is part of the input.

Given the number of people that a bus can accommodate at one time (post restrictions), determine the number of buses required to pick up all employees. A bus can start from any location but must take only the shortest path from that location to the office. The bus can pick up employees at locations along its route. Assume that there is only one shortest route between the office and each remaining location.

Constraints

( 1 < M < 12 )
( 0 \leq \text{Distance between locations} \leq 300 )
( 0 \leq \text{Total number of employees} \leq 500 )

Input

First line consists of a single integer ( M ), representing the number of locations including the office.
Next ( M ) lines consist of ( M ) integers separated by space, representing the distance matrix.
Next line consists of ( M-1 ) space-separated integers, representing the number of employees boarding at each corresponding location.
Last line consists of an integer representing the number of people that can travel in the bus at one time.

Output

Print a single integer representing the minimum number of buses required to pick up all employees.

Time Limit (secs)

1

Examples

Example 1

Input

Output

Explanation

The below diagram represents the above input.

Based on the input, there are four locations, which we can denote as 0, 1, 2, and 3. The first location is the office, represented as (0).

The shortest paths between each location and the office are:

Location 1 → Office
Location 2 → Office
Location 3 → Location 2 → Office

The number of buses required will be 4:

One bus from Location 1
Two buses from Location 2
One bus from Location 3

The two buses start from Location 2. One bus picks up a full load from Location 2 and heads to the office, and the remaining two people board the bus coming from Location 3.

Example 2

Input

5  
0 10 10 60 60  
10 0 30 10 10  
10 30 0 30 30  
60 10 30 0 30  
60 10 30 30 0  
15 15 15 15  
25

Output

Explanation

For this example, the following diagram (not shown) would depict only the shortest path from each location to the office. Three buses will originate from locations 2, 3, and 4 respectively. The buses starting from locations 3 and 4 will need to travel through location 1. Since they have enough seats to pick up the employees from location 1, three buses are sufficient. Therefore, the output is 3.

Answer

import java.util.*; 

public class Main { 
    static int[][] distances; 
    static int[] employees; 
    static int M, busCapacity; 
    static List<Integer>[] shortestPaths; 
    static int[][] nextNode; 

    public static void main(String[] args) { 
        Scanner scanner = new Scanner(System.in); 

        // Read input 
        M = scanner.nextInt(); 
        distances = new int[M][M]; 

        // Read distance matrix 
        for (int i = 0; i < M; i++) { 
            for (int j = 0; j < M; j++) { 
                distances[i][j] = scanner.nextInt(); 
            } 
        } 

        // Read employees at each location (excluding office) 
        employees = new int[M]; 
        for (int i = 1; i < M; i++) { 
            employees[i] = scanner.nextInt(); 
        } 

        // Read bus capacity 
        busCapacity = scanner.nextInt(); 

        // Calculate result 
        int result = solve(); 
        System.out.println(result); 
    } 

    static int solve() { 
        // Find all shortest paths using Floyd-Warshall 
        int[][] dist = floydWarshall(); 
        findShortestPaths(); 

        // Calculate required buses using greedy approach 
        return calculateRequiredBuses(); 
    } 

    static int[][] floydWarshall() { 
        int[][] dist = new int[M][M]; 
        nextNode = new int[M][M]; 

        // Initialize distances and next array 
        for (int i = 0; i < M; i++) { 
            for (int j = 0; j < M; j++) { 
                dist[i][j] = distances[i][j]; 
                if (distances[i][j] != 0) { 
                    nextNode[i][j] = j; 
                } else { 
                    nextNode[i][j] = -1; 
                } 
            } 
        } 

        // Floyd-Warshall algorithm 
        for (int k = 0; k < M; k++) { 
            for (int i = 0; i < M; i++) { 
                for (int j = 0; j < M; j++) { 
                    if (dist[i][k] != 0 && dist[k][j] != 0 &&  
                        (dist[i][j] == 0 || dist[i][k] + dist[k][j] < dist[i][j])) { 
                        dist[i][j] = dist[i][k] + dist[k][j]; 
                        nextNode[i][j] = nextNode[i][k]; 
                    } 
                } 
            } 
        } 
        return dist; 
    } 

    static void findShortestPaths() { 
        shortestPaths = new List[M]; 
        for (int i = 0; i < M; i++) { 
            shortestPaths[i] = new ArrayList<>(); 
            if (i != 0) { // Skip office 
                int current = i; 
                while (current != 0) { 
                    shortestPaths[i].add(current); 
                    current = nextNode[current][0]; 
                } 
                shortestPaths[i].add(0); // Add office 
            } 
        } 
    } 

    static int calculateRequiredBuses() { 
        int totalBuses = 0; 
        int[] remainingEmployees = Arrays.copyOf(employees, employees.length); 

        // Process locations in order of distance from office (farthest first) 
        List<Integer> locations = new ArrayList<>(); 
        for (int i = 1; i < M; i++) { 
            locations.add(i); 
        } 
        locations.sort((a, b) -> shortestPaths[b].size() - shortestPaths[a].size()); 

        for (int location : locations) { 
            while (remainingEmployees[location] > 0) { 
                // Start a new bus 
                totalBuses++; 
                int capacity = busCapacity; 

                // Pick up employees along the path 
                for (int stop : shortestPaths[location]) { 
                    int canPickup = Math.min(remainingEmployees[stop], capacity); 
                    remainingEmployees[stop] -= canPickup; 
                    capacity -= canPickup; 
                } 
            } 
        } 

        return totalBuses; 
    } 
}

4> Medium (2d Matrix)

Block Extraction

Problem Description

Aarya is playing with LEGO bricks, each a one-unit square. She connects the bricks to form various shapes, creating what is known as a block. Thus, a block is an amalgamation of bricks in four possible directions: top, bottom, left, and right.

Each such block she created is assigned a unique identity number. Using the blocks she created, Aarya assembled a matrix with dimensions ( N \times M ). This matrix is positioned upright on the ground. Now, Aarya wants to pick up the block numbered ( K ) from the matrix, starting from the top. The rules to pick up the desired block are as follows:

A block can be easily removed only if there are no other blocks on top of it.
It is guaranteed that there are no empty spaces within the matrix.
If block ( K ) is partially inside block ( L ) and can't be picked directly from the top, she will need to remove block ( L ).

A careful look at the matrix tells us that apart from block ( K ), all other blocks will need to be removed to pick block ( K ).

To collect a block, we need to understand it as collecting all blocks with the same identity. A block numbered ( K ) may span across multiple rows. To pick up all blocks with identity ( K ), Aarya needs to remove all blocks stacked above any occurrence of ( K ).

Input:

The first line consists of two space-separated integers, denoting ( N ) and ( M ) (the number of rows and columns of the matrix).
The next ( N ) lines consist of ( M ) space-separated integers denoting the front view of the matrix assembled by Aarya.
The last line consists of an integer ( K ), denoting the identity number of the block which Aarya wants to pick up, from the top of the matrix.

Output:

Print a single integer denoting the number of blocks she needs to remove to pick up the block with identity ( K ).

Examples

Example 1:

Input:

Output:

Explanation:

The matrix is 5 rows and 5 columns.
It is composed of blocks with identities 1, 2, 3, 4, 5, 6, 7, 8, and 9.
Aarya wishes to collect all blocks with identity 1. Block 1 spans across 3 rows (rows 3, 4, and 5).
To collect block 1, we must remove all blocks stacked above it.
The blocks to be removed are 2, 3, 4, 5, 7, 8, and 9, resulting in 7 blocks being removed.

Example 2:

Input:

Output:

Explanation:

The matrix is 6 rows and 3 columns, composed of blocks with identities 1, 2, 3, 4, 5, 6, and 7.
Aarya wishes to collect all blocks with identity 6. Block 6 appears in row 5.
To collect block 6, we must remove all blocks stacked above it. These are blocks 1, 2, and 3.
Therefore, the number of blocks to be removed is 3.

Example 3:

Input:

4 6
1 1 6 6 6 7
2 3 3 3 8 3
3 3 5 3 3 3
4 9 9 14 14 14
5

Output:

Explanation:

The matrix is 4 rows and 6 columns.
It is composed of blocks with identities 1, 2, 3, 5, 6, 7, 8, 9, and 14.
Aarya wishes to collect all blocks with identity 5. Block 5 appears in the third row.
To collect block 5, we must remove all the blocks stacked above it. These are blocks numbered 1, 2, 3, 6, 7, and 8.
Therefore, the number of blocks to be removed is 6.

Constraints:

( 0 \leq ) number of blocks ( \leq 500 )
( 1 \leq N, M \leq 50 )
A block will never be fully enclosed by another block, meaning it won't be surrounded on all four sides.

This concludes the complete problem statement with three examples. Let me know if anything else is required!

How To Deploy a json-server on render

Akash Jadhav — Fri, 15 Nov 2024 12:15:22 +0000

A short step by step by step guide to creating a JSON-DB server and deploying it on render
json-server is a tool for creating mock REST API fast! To get started, ensure you have the following requirements:

NodeJS (npm)
Let's get started!

On an empty folder, initiate a nodejs application by running the following on your terminal/CMD:

npm init -y

Once that is complete, you install the following packages:
`
json-server

json-serve

cors
`

npm install json-server json-serve cors

After the installation, create a new file: index.js. This is the entry point for the json-serve. Add the following inside the file:

`
const jsonServer = require("json-server"); // importing json-server library
const server = jsonServer.create();
const router = jsonServer.router("db.json");
const middlewares = jsonServer.defaults();
const port = process.env.PORT || 3001; // you can use any port number here; i chose to use 3001

server.use(middlewares);
server.use(router);

server.listen(port);
`
In the code above, a server has been created that will be fetching and updating data from a json file, db.json

In the project root, create a new file: db.json and add the following:

{ "feedback": [ { "id": 1, "rating": 10, "user_name": "Tony Stark", "text": "You are the ironman of this world" }, { "id": 2, "rating": 9, "user_name": "Bruce Wayne", "text": "You are the batman of this world" }, { "id": 3, "rating": 8, "user_name": "Peter Parker", "text": "You are the spiderman of this world" } ] }
The mock server is ready to run, but let's add some scripts in package.json:

Update the "scripts" to:

"scripts": { "start": "node index.js" },
Deploy On Render :-
Go To Site :- https://dashboard.render.com/

Select Web Services

Connect with Github

Go to Github create new repo

Clone this repo and create all files and installation of json-server all are mentioned in above.

push all the code on Github

Go To Render And Select Github Repo where push all json-server code

Click on create Web Service Button below

and wait few minutes for progress and enjoy

Hopefully this article useful for you , happy coding! || Like this article ♥

Changes to Replit's Starter Plan: Announced Friday

Akash Jadhav — Sat, 31 Aug 2024 04:08:17 +0000

replit some upcoming changes to your Starter plan:

What's Changing?

Number of Repls: The Starter plan will now have a limit of 3 Repls. To access unlimited* Repls, consider upgrading to the Core plan.
Collaboration Limits: The Starter plan allows 1 collaborator per account. The Core plan allows up to 3 collaborators, while the Teams plan provides access for your entire organization.
Storage Retention: Repls on the Starter plan may be deleted after 1 year of inactivity.
Deployments:
- Starter plan users can deploy a single static site without needing a credit card (with a 1 GiB outbound data transfer limit). This update will roll out in the next few weeks.
- Autoscale, Reserved VM, and Scheduled Deployments will now require a Core account. If you currently use these features, you'll receive a separate email with further details.
Development:
- Development Time: The Starter plan will be limited to 600 development minutes per month. To remove this limitation, consider upgrading to the Core plan.
- Outbound Data Transfer: The Starter plan will have a new outbound data transfer limit of 1 GiB.
- Development Storage: The storage limit on the Starter plan will change to 2 GiBs.

These changes will take effect fully on August 26th.