Inefficient and wrong implementation for tunnel traversal

Gr-Affable | Hello FOSS 2022

Welcome to Gr-Affable, a project on DSA and Graph Theory under Hello FOSS 2022 !

Here, We explore algorithms with special emphasis on Graph Theory.

Many programming problems can be solved by modeling them as a Graph problem and using appropriate graph algorithm. There are many clever and efficient graph algorithms that can resolve difficult problems effectively. We will get to know about these Algorithms while solving the problems here.

We embark upon a rather ambitious journey - to design algorithms for a self-driving car! How does your car move when given the map of a city? What routes does it take? Code your way out of the traffic on the city streets!

Guidelines

Take any input/output format you see fit, if the problem doesn't mentions it. This is not an autograded lab ;)
Explore various problems that are provided here, think on there implementation. Try to solve them first. If you can think of a better solution, do implement it. We have provided some hints and ideas to start with
Some of the problems have a code for it. Try to see if that code works. If not, do contribute to that code and make it more efficient. Begin your journey -

Sorting and Searching
Symphony (Algorithmic Time Complexity)
Grid Ways (Basic Dynamic Programming)
Dijkstra
Bellman Ford
Maze (Application of BFS)
Surplus (Tree Algorithms)
Closest Points (Divide and Conquer)
Check Paths (Directed Graphs)
Communication (Huffman Coding and RSA Encryption)
Diwali (Optimised Backtracking)
Strongly Connected

The order is in no way strict. If you feel puzzled by a problem, feel free to approach the next one, or have a look at the other problems.

Clone, Commit and Push

After you have forked this repo, go to your fork, and click on the Code drop down button. Copy the link of your fork, which would look like https://github.com/username/Gr-affable.git. Make a new folder on your device, open a powershell terminal in that folder or right click and select Git bash here. Then run git clone https://github.com/username/Gr-affable.git.

This will make a copy of your fork on your device, and now you can start coding files in the IDE of your choice. A few handy commands -

git add filename will add the file to the staging area, which means the file is now being tracked by version control. Do this before commiting the file.
git commit will commit your changes (adding a new file, commiting modified files etc.) to your local repository.
git push To push local committed changes on your device to the forked repository hosted on github.
git pull To get the changes made in your fork synced with the copy on your device. For example, if you make some changes to your fork (adding new files, modifying files) directly github.com, then you can get those changes to apply to the repo on your device.

A simpler way to add new files to your fork is by navigating to the desired folder and using the Add files button, then upload any files you want. To get the changes on your local device, run git pull.

Sync your fork and create pull requests

Whenever there are some changes in the central repo (harpoonix/Gr-affable), they DO NOT apply directly to your fork. To get the changes from the upstream repository (harpoonix/Gr-affable) into your fork, simply click Sync Fork and Update branch. Now you've got the updates from the main repo into your own.

Once you've created some files and want to contribute, you can use the Contribute option to create a pull request.

Here is an example image that demonstrates some of these.

Files to commit

If you have solved a particular question and want to contribute your work, make a file called username_question.cpp or something like that. Say you want to add your attempt to the SPFA algorithm implementation, or the naive Bellman Ford implementation. Maybe you have solved the question Bellman-Ford/Tunnels.

In the folder, add a file called username_tunnel.cpp, or username_spfa.cpp or something like that. This allows us to accept submissions of multiple people, while keeping the challenge open for others.

Created with ❤️ by WnCC

	for(int i = 0; i < m; i++){
	if(start[i] == first){
	int sum = tunnel[i];
	int dest = end[i];
	while(dest!=last){
	for(int j = 0; j < m; j++){
	if(start[j] == dest){
	sum += tunnel[j];
	dest = end[j];
	break;
	}
	}
	}
	score.push_back(sum);
	}
	}

	long long int *tunnel = new long long int[m];
	int *start = new int[m];
	int *end = new int[m];
	vector<int> score;
	for(int i = 0; i < m; i++){
	cin >> start[i] >> end[i] >> tunnel[i];
	}

	for(int i = 0; i < m; i++){

	int boughtIndex = getMinIndex(price); // Index with minimum price
	for(int j = 0; j < n; j++){
	if(price[j] > price[boughtIndex] && !bought[boughtIndex] && price[j] <= customer[i]){
	boughtIndex = j;
	}
	}

	// Now boughtIndex variable has the index of the
	// price which is maximum among all those prices
	// that are below the maximum price as told by customer

	if(!bought[boughtIndex]){ // Sold it to customer, if not bought already by someone else
	bought[boughtIndex] = true;
	customer[i] = price[boughtIndex];
	}
	else { // else give -1 to customer
	customer[i] = -1;
	}

	for (int j=i; j<n; j++) {
	int sum_of_this_subarray = 0;
	for (int k=i; k<=j; k++) {
	sum_of_this_subarray += array[k];
	}
	best_sum = max(best_sum, sum_of_this_subarray);

	graph[x].push_back(y,i); // An error has been thrown
	graph[y].push_back(x,i); // Can you figure it out ?

harpoonix / gr-affable Goto Github PK

gr-affable's Introduction

Gr-Affable | Hello FOSS 2022

Guidelines

Clone, Commit and Push

Sync your fork and create pull requests

Files to commit

gr-affable's People

Contributors

Stargazers

Watchers

Forkers

gr-affable's Issues

Recommend Projects

Recommend Topics

Recommend Org