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
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// 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
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 :)
I have not thought deeply about this problem. Disch is an established programmer, however I can't follow his suggestion.
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.
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).
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.
1 2 3 4
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// 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
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.
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
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.
#include "stdafx.h"
#include <iostream>
constint maximum = 100000;
int main()
{
usingnamespace std;
int n;
cout << "Tomatoes: ";
cin >> n;
int arr[maximum];
arr[0] = -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