harpoonix / gr-affable Goto Github PK

Repository for Hello FOSS 2022, a month long institute-wide Open Source Contributive Event along the lines of Hacktoberfest. The "Hello World" of open source contributions!

C++ 96.34% Shell 3.66%

algorithms-and-data-structures graph-algorithms huffman-coding rsa-encryption hacktoberfest

gr-affable's People

Contributors

Stargazers

Watchers

Forkers

sanyam-7 ryuusama09 saksham-gupta-off shrey371 dgibn sanuraagm heisenbergscat03 shasss447 nihalat anoushkadey12 faiz1729 dangercomix07 aadi2323 sabitak27 vamshikasutar nachoduke shreyganatra tirthomania pranjalanimesh sarthakbarwal the-real-anish srishti-badaya 23-ryan harshitag1 rohanchoudhary21 prekshu dh-gntr manishroylearning iris-agape noobcoder45 ananyachinmaya arushibansal963 raj9571 lvl9sandipan vivek-108 arnavpandey03 shounakd56 aasthasancheti-2805 aastha8901 aquoza lastmarble amitjha2403 preetham2324 anonymousagarwal sharvild11 pranjal-01 vidhan9503 eragon2995 vibhu234 parthp3 rohitkangoni aaryansharma abhi7230 rakshith-2100 harshagarwal2k02 koushik62 ru0110 sumitladdha333 kamalkant21 kunalr33 sridhar-singapakula aadishsethiya ishenlong im-akshat predatorcoder007 cs50-i statawat4 soumyadeepj ramnarayan-choudhary agarwalumang aizenmirio sfoorti12 hpk-iitb prathamchandra-18 abhi-kedare qraunak madhuri343 agnipratimnag haibatullahakhunzada mukul0610 its-me-harsh-anand harsha200050041 kandarpsolanki all7en abhijit424515 shambhavii13 atishay25 mohitkoley pranavyatnalkar udaygohil gamechaser782 rahul0082 atharvatambat durgesh-17 deekshithlenka krishnagaggar ablazesamurai shiveshcodes

gr-affable's Issues

Extracting frequency of each character into a compressed string

Go to Communication/Huffman Codes/huffman.cpp, there is a problem in calculating the frequency of each character in the given string. Can you fix it?
$data$ is the compressed string which has each character if given string one time and $freq[i]$ has the frequency of character at $data[i]$.

Inefficient and wrong implementation for tunnel traversal

Gr-affable/Bellman-Ford/Tunnel/tunnel.cpp

Lines 17 to 32 in 9a88309

 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); 

 } 

 }

A simple Brute force search kind of algorithm is being used here which is inefficient and has high time complexity
It does not take into account the fact that we can go through the same tunnel several times!
May get stuck into a loop. For example, $n = 6$ and tunnels are $1\rightarrow3$, $3\rightarrow5$, $5\rightarrow4$, $4\rightarrow1$.
As given in Instructions, the idea is to use Bellman Ford algorithm here. Can you do it?

Merge the PRs :D

You guys do realise that PRs must be merged for them to be considered as successful contributions 😄

Type mismatch in vector.push_back

Gr-affable/Strongly Connected/stronglyConnected.cpp

Lines 39 to 40 in 2949077

 graph[x].push_back(y,i); // An error has been thrown 

 graph[y].push_back(x,i); // Can you figure it out ?

There seems to be a type mismatch between the argument passed to push_back and the arguments it expects. Can you find the problem and fix it?

Incorrect output

Gr-affable/Sorting and Searching/Auction/auction.cpp

Lines 34 to 53 in 3845733

 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; 

 }

There seems a problem somewhere here. The code is not providing the desired output for sample testcase given. Solve this issue, if you can
(Hint - It is just one word)

Redundant Loop

Gr-affable/Symphony/subarray_sum.cpp

Lines 11 to 16 in 3845733

 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);

We don't need to calculate the sum of the subarray again when the end shifts from j to j+1. We can simply add array[j+1] to the previous sum.
Saves computation.

Improper input method

Gr-affable/Bellman-Ford/Tunnel/tunnel.cpp

Lines 8 to 14 in 9a88309

 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]; 

 }

start end end represent starting and ending node of a tunnel and thus constitute an edge together as a pair. Here, inputs of there values are being taken into two separate arrays, which may cause error. Shouldn't it be better to make a pair of them?

harpoonix / gr-affable Goto Github PK

gr-affable's People

Contributors

Stargazers

Watchers

Forkers

gr-affable's Issues

Extracting frequency of each character into a compressed string

Inefficient and wrong implementation for tunnel traversal

Merge the PRs :D

Type mismatch in vector.push_back

Incorrect output

Redundant Loop

Improper input method

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	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);
	}
	}

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

	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);

	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];
	}