### How to solve - Efficiently I have solved this problem:
 Suppose you have a row of N tomatoes, of which R are red. After each day, the unripe neighbors of each red tomato become red. Write a program that determines the number of red tomatoes after D days.

But I use a very inefficient method, what would be the most efficient way to solve this problem?

EDIT:
Example input:
 ```Enter number of tomatoes N: 10 Enter number of Ripe Tomatoes R: 3 Enter number of days D: 2 Enter position of Tomatoes in ascending order: 1 8 9 ```
Last edited on closed account (ETAkoG1T)
Can you write some example output for your input, I don't quite understand the problem. And can you post your old code? > what would be the most efficient way to solve this problem?
O(r)

After D days, a red tomato creates 2*D+1 red tomatoes.
You just need to subtract the overlapping parts. Since the ripe tomatoes are already in ascending order, this makes it simple. Just make a vector of the ripe tomatoes, loop through it, making sure not to count the same tomato twice.

My approach, untested:
 ``123456789101112131415`` ``````// assuming tomato position is zero based int highest_pos = -1; int count = 0; for(int ripepos : vector_of_ripe_positions) { int first = std::max( highest_pos+1, ripepos - days ); int last = std::min( ripepos + days, number_of_tomatoes - 1 ); count += (last - first) + 1; highest_pos = last; } // count is the number of ripe tomatoes after 'days' days `````` @Filiprei

Example output
 `8`

Explanation

Starting array
R G G G G G G R R G

Day 1
R R G G G G R R R R

Day 2
R R R G G R R R R R

How I did it:
I solved it by simulation, which is in inefficient when N reaches higher values
Last edited on closed account (ETAkoG1T)
I tried with your example it worked, and with some bigger numbers. I am just a beginner so there might be better approaches. I don't know if it works with bigger numbers because I don't know the answer. I am sure you'll figure it out. And one last thing about my program is that you don't have to enter the number of ripe tomatoes :)

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970`` ``````#include "stdafx.h" #include const int maximum = 100000; int main() { using namespace std; int n; cout << "Tomatoes: "; cin >> n; int arr[maximum]; arr = -1; int i = 0; while(i < n) { arr[i+1] = i; i++; } int max = i - 1; cout << "Enter days: "; int days; cin >> days; cout << "Enter position of Tomatoes(q to quit): "; int order; while(cin >> order) { arr[order] = -2; cout << "Enter another position(q to quit): "; } int x = 0; while(x < days) { i = 1; while(arr[i] != -1) { if(arr[i] == -2) { if(i-1 > 0) { arr[i - 1] = -2; } if(i+1 < maximum-1) { arr[i + 1] = -2; } } i++; } x++; } i = 1; int count = 0; arr[max] = -1; while(arr[i] != -1) { if(arr[i] == -2) count++; i++; } cout << "\nTotal: " << count; cin.clear(); cin.ignore(1); cin.get(); cin.get(); return 0; } ``````
Last edited on It seems to me that an array is the way to go. It will yield whether a tomato is ripe or not and the tomato's position.

Days would pass in a loop. In each iteration, test if a tomato is ripe or not. If it is ripe, then test if its neighbor is ripe or not. If the neighbor is not ripe, then ripen it. At the end of each loop, count the number of ripe tomatoes.

The flaw I see in this approach, (that I am too lazy to solve right now), is when an unripe tomato is sandwiched between two ripe tomatoes. That tomato may be double counted. closed account (ETAkoG1T)
My program don't work D: closed account (ETAkoG1T)
I think it works now, can't confirm it, but I have tried with some low numbers and stuff. :) Hope you like it. It is really fast!
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970`` ``````#include "stdafx.h" #include const int maximum = 100000; int main() { using namespace std; int n; cout << "Tomatoes: "; cin >> n; int arr[maximum]; arr = -1; int i = 0; while(i < n) { arr[i+1] = i; i++; } int max = i + 1; arr[max] = -1; cout << "Enter days: "; int days; cin >> days; cout << "Enter position of Tomatoes(q to quit): "; int order; while(cin >> order) { arr[order] = -2; cout << "Enter another position(q to quit): "; } int x = 0; while(x < days) { i = 1; while(arr[i] != -1) { if(arr[i] == -2) { if(arr[i-1] != -1) { arr[i - 1] = -2; } if(arr[i+1] != -1 && arr[i+1] != -2) { arr[i + 1] = -2; i++; } } i++; } x++; } i = 1; int count = 0; arr[max] = -1; while(arr[i] != -1) { if(arr[i] == -2) count++; i++; } cout << "\nTotal: " << count << "\nMax: " << max - 1; cin.clear(); cin.ignore(1); cin.get(); cin.get(); return 0; }``````
Last edited on 1. Let us say that the gap (number of unripe tomatoes) between two ripe tomatoes is G. 2. Each day, G will reduce by two. 3. In D days, the gap will reduce by `std::min( D*2, G )` 4. To start with there are R+1 gaps

Take it up from there.

(This is just a different way of phrasing what ne555 said). nathan10 wrote:
Disch is an established programmer, however I can't follow his suggestion.

The idea is, each ripe tomato will create other ripe tomatoes D places away from it.

 ``1234`` ``````assuming D=2 G G G R G G G G G R G R G G G <- initial setup G r r R r r G r r R r R r r G <- tomatoes that eventually become ripe``````

So really, all you have to do is loop through the known ripe tomatoes, and total the surrounding tomatoes. The thing that makes it tricky is, you dont want to count the same tomato twice.

The code again for reference:
 ``123456789101112131415161718`` ``````// assuming tomato position is zero based int highest_pos = -1; int count = 0; for(int ripepos : vector_of_ripe_positions) { int first = std::max( highest_pos+1, ripepos - days ); int last = std::min( ripepos + days, number_of_tomatoes - 1 ); if(last >= first) // adding this if statement. Only count tomatoes if there are tomatoes to count { count += (last - first) + 1; highest_pos = last; } } // count is the number of ripe tomatoes after 'days' days ``````

Visual explanation of how the logic works:

 ``1234567891011121314151617181920`` ``````first iteration: ripepos = 3 highest_pos = -1 G r r R r r G r r R r R r r G ^ ^ ^ | | | | | last | ripepos first last = 5 first = 1 count += 5. count now is 5 highest_pos = last (5), so we know the last tomato we counted G r r R r r G r r R r R r r G ^ | highest_pos... we counted this tomato and all before it already.``````

 ``1234567891011121314151617181920212223242526`` ``````next iteration: ripepos = 9 highest_pos = 5 highest_pos | v G r r R r r G r r R r R r r G ^ ^ ^ | | | | | last | ripepos first last = 11 first = 7 nothing really new happens here count += 5. count now is 10 highest_pos = last (11): G r r R r r G r r R r R r r G ^ | new highest_pos``````

 ``1234567891011121314151617181920212223242526272829`` ``````last iteration: ripepos = 11 highest_pos = 11 highest_pos | v G r r R r r G r r R r R r r G ^ ^ ^ | | | | | last | first ripepos last = 13 first = 12 This is where highest_pos kicked in. we already counted tomato 11, so highest_pos makes sure we start at at LEAST tomato 12. As you can see, 'first' is 12 as a result of this. This ensures we do not count the same tomato more than once count += 2. count now is 12 highest_pos = last (13): G r r R r r G r r R r R r r G ^ | new highest_pos``````

Final result: count == 12, which is the correct answer.
only had to do 3 loop iterations (= R), even though there were 15 tomatoes.

This is about as efficient as it can get.
Last edited on closed account (ETAkoG1T)
Disch that is cool, I found it out the hard way :P But I figured it out and this was my solution:
 ``12345`` ``````Line 45:: if(arr[i+1] != -1 && arr[i+1] != -2) { arr[i + 1] = -2; i++; }``````
Last edited on Thanks Disch closed account (D80DSL3A)
May I still throw mine in?
I think it follows Dischs approach and it gives correct values for the 2 cases considered.
 ``1234567891011121314151617`` ``````int main() { int N = 15, R = 3, D = 2; int pos=0, lo=0, hi=-1, count=0; int ripePos[] = {3,9,11}; for(int i=0; i (N-1) ? N-1 : (pos+D); count += hi-lo+1; } cout << "count = " << count << endl; return 0; }`````` closed account (ETAkoG1T)
I edited mine a bit to show it how many of the apples are riped and green at the end :) enjoy,
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081`` ``````#include "stdafx.h" #include const int maximum = 100000; int main() { using namespace std; int n; cout << "Tomatoes: "; cin >> n; int arr[maximum]; arr = -1; int i = 0; while(i < n) { arr[i+1] = i; i++; } int max = i + 1; arr[max] = -1; cout << "Enter days: "; int days; cin >> days; cout << "Enter position of Tomatoes(q to quit): "; int order; while(cin >> order) { arr[order] = -2; cout << "Enter another position(q to quit): "; } int x = 0; while(x < days) { i = 1; while(arr[i] != -1) { if(arr[i] == -2) { if(arr[i-1] != -1) { arr[i - 1] = -2; } if(arr[i+1] != -1 && arr[i+1] != -2) { arr[i + 1] = -2; i++; } } i++; } x++; } i = 1; int count = 0; arr[max] = -1; while(arr[i] != -1) { if(arr[i] == -2) count++; i++; } cout << "\nTotal: " << count << "\nMax: " << max - 1 << endl; cout << "A visual way of showing it:\n"; i = 1; while(arr[i] != -1) { if(arr[i] == -2) cout << "R"; else cout << "G"; i++; } cout << endl; cin.clear(); cin.ignore(1); cin.get(); cin.get(); return 0; }``````

OUTPUT:
 ``` Tomatoes: 20 Enter days: 2 Enter position of Tomatoes(q to quit): 5 Enter another position: 17 Enter another position:10 Enter another position:q Total: 15 Max: 20 A visual way of showing it: GGRRRRRRRRRRGGRRRRRG```
Last edited on
Topic archived. No new replies allowed.