How to solve - Efficiently

[Script Coder]

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 

[ETAkoG1T]

Can you write some example output for your input, I don't quite understand the problem. And can you post your old code?

[ne555]

> 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.

[Disch]

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:

// 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 

[Script Coder]

@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

[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 :)

#include "stdafx.h"
#include <iostream>

const int maximum = 100000;


int main()
{
	using namespace 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;
	
	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;
}

[nathan10]

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.

[ETAkoG1T]

My program don't work D:

[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!

#include "stdafx.h"
#include <iostream>

const int maximum = 100000;


int main()
{
	using namespace 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;
	cin.clear();
	cin.ignore(1);
	cin.get();
	cin.get();
	return 0;
}

[JLBorges]

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]

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.

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:

// 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:

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.

This is about as efficient as it can get.

[ETAkoG1T]

Disch that is cool, I found it out the hard way :P But I figured it out and this was my solution:

Line 45::  if(arr[i+1] != -1 && arr[i+1] != -2)
			{
				arr[i + 1] = -2;
				i++;
			}

[Script Coder]

Thanks Disch

[D80DSL3A]

May I still throw mine in?
I think it follows Dischs approach and it gives correct values for the 2 cases considered.

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<R; ++i)
    {
        pos = ripePos[i];
        lo = (pos-D) < (hi+1) ? (hi+1) : (pos-D);
        hi = (pos+D) > (N-1) ? N-1 : (pos+D);
        count += hi-lo+1;
    }

    cout << "count = " << count << endl;
    return 0;
}

[ETAkoG1T]

I edited mine a bit to show it how many of the apples are riped and green at the end :) enjoy,

#include "stdafx.h"
#include <iostream>

const int maximum = 100000;


int main()
{
	using namespace 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