2
\$\begingroup\$

As a solution to the B. Wet Boxes problem :

B. Wet Boxes

Bob works in a warehouse which contains a large pile of boxes. The position of a box can be described with a pair of integers (x, y). Each box either stands on the ground (y = 0) or stands on top of two boxes with positions (x, y - 1) and (x + 1, y - 1) (see the figure).

Sometimes the contents of a box leak out and the box gets wet. When a box becomes wet, so do the two boxes below it. Given a list of boxes that leak in succession, help Bob count how many dry boxes became wet after each leak. Don't include boxes that were already wet.

My solution is :

#include <stdio.h>
#include <stdlib.h>

static int count;


typedef struct {
    int x;
    int y;
}Box;


Box* push(Box* memptr, int x, int y){
    int i;
    for (i = 0; i < count; i++){
        if ((memptr[i].x == x) && (memptr[i].y == y))
            return memptr;
    }
    count++;
    if (count == 1)
        memptr = (Box*)malloc(sizeof(Box));
    else
        memptr = (Box*)realloc(memptr, sizeof(Box) * count);
    memptr[count - 1].x = x;
    memptr[count - 1].y = y;

    return memptr;
}

Box* find_wet_boxes(Box* memptr, int x, int y){
    if ((x * y) < 0)
        return memptr;
    else {
        memptr = push(memptr, x, y);
        find_wet_boxes(memptr, x, y - 1);
        return find_wet_boxes(memptr, x + 1, y - 1);
    }
}

int main(){
    Box* memptr = NULL;
    // int i;
    memptr = find_wet_boxes(memptr, 1, 3);
    // memptr = find_wet_boxes(memptr, 3, 2);
    // memptr = find_wet_boxes(memptr, 0, 6);
    // memptr = find_wet_boxes(memptr, 1, 1);
    printf("count = %d\n", count);
    return 0;
}

This works fine for each individual box co-ordinates but when I try to run for all the 4 co-ordinates, it gives me time limit exceed error during submission. (Coordinates may be as large as 109. There may be up to 105 leaking boxes. Time limit is 0.7 seconds.) Clearly my algorithm is not good enough. Can someone please give me a better solution for this?

If it the answer is too broad and there could be many solution, then I expect at least one of them which will at least pass the runtime limit test

Possible Solution:

So, a single leaked box covers a smaller triangle of boxes. In short, we maintain a set that contains the vertices of such triangles that have not been covered by any other triangle yet. When a box leaks (i.e., a new triangle is added), we find the vertices of the triangles that are inside the new one, and subtract the area that was first covered by this box and is inside the new triangle. Then we can remove them from the set and insert the new triangle vertex in the set. This results in \$O(n\ \log n)\$ solution (for each new triangle, there can be also two vertices that are not inside the new triangle, but overlap with it: these vertices remain in the set, but that does not change the complexity).

This is the possible solution as quoted by someone but I don't understand how to implement it or will that actually solve the problem.

\$\endgroup\$
  • 2
    \$\begingroup\$ We're OK with reviewing your code and with suggesting a better solution. However, "Can someone please give me a better solution for this?" is a little bit too direct, especially when you've included a suggested strategy and stated that you don't know how to implement it. \$\endgroup\$ – 200_success Jan 14 '16 at 9:28
  • \$\begingroup\$ @200_success Actually I think there is hardly a better solution for this. I may skip the recursion and implement it using a loop but I don't think it would help anyway. Moreover, I don't think even the solution proposed could even solve the runtime exceed problem. Hence I am asking \$\endgroup\$ – Mayukh Sarkar Jan 14 '16 at 9:41
  • \$\begingroup\$ @200_success I just need an algorithm, not the complete solution. Consequently a solution like the one mentioned above is too far fetched in my opinion and hard to solve which may not yield any true solution..correct me if I am wrong please \$\endgroup\$ – Mayukh Sarkar Jan 14 '16 at 9:43
  • \$\begingroup\$ I don't think even the solution proposed could even solve the runtime exceed problem Write it down as comments in the programming language of your choice, anyway. Ponder how to test the results, and have that coded, too (hint: you got one implementation - confident it gives correct results?). Flesh out the "comments only" version of the proposed approach until your friendly debugger steps you through the process. Compare results. Watch your algorithm/code handling a bigger problem instance: where does it look dumb? Could it have used earlier results? \$\endgroup\$ – greybeard Jan 14 '16 at 9:51
  • 2
    \$\begingroup\$ Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Jan 14 '16 at 12:21
3
\$\begingroup\$

It's been a while since I have worked in C, so a language-specific review would not be so accurate. The only thing I can say in that aspect is that you should put curly bracket even in single-command body ifs as the code gets more readable and less error prone.

Taking a look at the problem and at your solution I think that you're overcomplicating it. You are allocating memory for each box and working with it when you actually don't need them. All you need is a square matrix - to be more precise, a lower triangular matrix - of ints (in this case).

The idea is the following:

  1. Represent the boxes' status via the matrix \$A\$. If the box in the position \$(x, y)\$ is wet then \$A_{x,y} = 1\$, otherwise \$A_{x,y} = 0\$. So, initially, every item in the matrix is \$0\$.
  2. When the box in position \$(x, y)\$ leaks you just set all the appropriate cells of \$A\$ to \$1\$ and count the number of cells whose value has changed from \$0\$ to \$1\$.
  3. Return the value of the counter for each case.

In pseudo-code (I'm not so practical in C), it becomes something like the following:

int[,] A = new int[7,7];

void initialize_matrix(){
    for(int i = 0; i < 7, i++){
        for(int j = 0; j < 7; j++){
            A[i, j] = 0;
        }
    }
}

int count_wet_boxes(int x, int y){
    int counter = 0;

    for(int i = x; i >= 0; i--){
        for(int j = 0; (i + j) <= (x + y); j++){
            if(A[i, j] == 0){
                A[i, j] = 1;
                counter++;
            }
        }
    }

    return counter;
}

int main(){
    initialize_matrix();

    // the rest of the logic goes here
}

You can also try to ask in the Mathematics SE site if there is a formula you can use.

Let me know if anything's unclear.

\$\endgroup\$
  • \$\begingroup\$ ..Thanks for the solution but there is a problem...You assumed that the size of the matrix is 7x7 but in actual solution they will not provide any matrix size. It should work for any number of row and cols..A generic solution. Here matrix size means total number of boxes stacked \$\endgroup\$ – Mayukh Sarkar Jan 14 '16 at 10:29
  • \$\begingroup\$ Moreover Mathematics SE is more related to mathematical derivations but here it is more related to the approach of solving the question \$\endgroup\$ – Mayukh Sarkar Jan 14 '16 at 10:32
  • \$\begingroup\$ (It's been a while since I haven't worked in C I'm with you, but double negative is prone to misinterpretation.) This seems to visit O(y²) cells for every pair (x, y). \$\endgroup\$ – greybeard Jan 14 '16 at 10:34
  • \$\begingroup\$ @greybeard Yes you are correct..It is visiting each cells twice. \$\endgroup\$ – Mayukh Sarkar Jan 14 '16 at 10:40
  • \$\begingroup\$ @MayukhSarkar that's just an example from a practical case, from the one indicated in the original problem. In the case where you don't have a max size you can extend the current matrix (which is a \$O(n^2)\$ operation). The problem has some mathematical implications - the number of boxes getting wet from the leak of the box in position \$(x, y)\$ is \$1+...+(y+1) \$. Maybe there's a formula for this specific case... \$\endgroup\$ – Gentian Kasa Jan 14 '16 at 10:50
2
\$\begingroup\$

Each box is on a triangular grid... but actually, what is described by the coordinate system is a grid like this:

x
xx
xxx
xxxx

So what I'd do is instead make a single array that describes the lowest dry box in a column. Because if a box gets wet then so does the box beneath and the box beneath that...

So if box 2,10 becomes wet, then we say i = x and put ((y-(i-x))+1) in the column if it is higher than the value already there. Add the difference to the sum variable whilst changing the array.

0, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

pseudo

int sum = 0;
for(int i = x; ; i++){
  int dryBoxHeight = ((y-(i-x))+1);
  if (dryBoxHeight < 0 || array[i] >= dryBoxHeight){
     break;
  }
  sum += dryBoxHeight - array[i];
  array[i] = dryBoxHeight;
}

Then next, you get box 0,4 wet...

So column 0, we put 5, and 5-0 = 5, so 5 to sum

5, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 & sum = 5

Column 1, we put 4, and 4 - 0 = 4, so add 4 to sum

5, 4, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 & sum = 9

And column 2 we stop because 11 beats 3.

The only problem with this approach is that you need to be able to have a sparse array, otherwise you run into memory issues.

This solution is \$O(n)\$.

\$\endgroup\$
  • \$\begingroup\$ +1. I see what you did there. This is actually more efficient than the solution I proposed. I'd just suggest to keep an array with the \$y\$ coordinate of the top wet box and work with that. This could make the whole procedure more intuitive. \$\endgroup\$ – Gentian Kasa Jan 14 '16 at 12:01
  • \$\begingroup\$ @GentianKasa You have to deal with 0 also being a box that can get wet. So highest wet box of a dry stack is -1. \$\endgroup\$ – Pimgd Jan 14 '16 at 12:39
  • \$\begingroup\$ Yep. It's just a consideration from a human point of view. We're working on wet boxes, so I personally tend to have the data regarding the wet boxes rather than retrieve this data from the data of dry boxes. Other than that - from my point of view - this solution is perfect. \$\endgroup\$ – Gentian Kasa Jan 14 '16 at 14:01
  • \$\begingroup\$ @Pimgd Can you please comment and solve this new issue posted here stackoverflow.com/questions/34883334/… \$\endgroup\$ – Mayukh Sarkar Jan 19 '16 at 17:44
0
\$\begingroup\$

It looks like I have solved it:

#include <iostream>
#include <vector>
#include <algorithm>

int counter = 0;
std::vector<std::vector<int>> boxes;
void prune_boxes(int x, int y){
 if (y < 0)
   return;
 else{
   if (boxes[x][y] == 0){
     boxes[x][y] = 1;
     counter++;
   }
   prune_boxes(x, y - 1);
   prune_boxes(x + 1, y - 1);
 }
}



int main(){
  int wetBoxes;
  std::cin >> wetBoxes;
  std::vector<int> coordinatesX;
  std::vector<int> coordinatesY;
  int input;
  for (int i = 0; i < wetBoxes; i++){
    std::cin >> input;
    coordinatesX.push_back(input);
    std::cin >> input;
    coordinatesY.push_back(input);
  }

  int greatestX = *max_element(coordinatesX.begin(), coordinatesX.end());
  int greatestY = *max_element(coordinatesY.begin(), coordinatesY.end());

  int Y =  greatestY + 1;
  int X =  greatestX + greatestY + 1;
  boxes.resize(X);
  for (int i = 0; i < X; i++){
    for (int j = 0; j < Y; j++){
      boxes[i].push_back(0);
    }
  }

  for(int i = 0; i < wetBoxes; i++){
    prune_boxes(coordinatesX[i], coordinatesY[i]);
    std::cout << counter << std::endl;
    counter = 0;
  }
  return 0;
}

The only thing that has changed from the accepted answer is the fact that I am not storing each points as there is no need for it. Instead, I am maintaining a LUT as mentioned by @Gentian Kasa with all the values to be zero. Each time I visit them, I put 1, and if any cell is already 1, I would not increment the counter. If it is not 1, I would increment the counter. Although the actual tricky part was to select the row and column size of the matrix.

If out of all the points my greatest X-coordinate is 6 and greatest Y-coordinate is 12, then at each level my Y is decremented by 1 and X is incremented by 1 and if Y goes negative, I return from the function. Now this means I don't need a matrix whose height needs more than maximum Y + 1 (because it is always decremented) and I don't need a matrix whose breath needs more than maximum X + maximum Y + 1 (because X can increment only until the time Y can decrement).

Note: The performance is improved because every time I am not searching is that point is already included or not like in the previous solution. Accessing a member of any 2D array to check if it is 1 or 0 is constant time.

Moreover, the previous solution can pose a buffer overflow because I did x * y, without understanding that x never goes negative, only y does.

Edit 2: For number of points given as 1, the solution can be found in \$O(1)\$..This is how For n = 1 and the given point (x, y), the count value seems to be calculated by

count = ( (y + 1) (y + 2) ) / 2)

This is because it comes out to be sum of y + 1 natural numbers.

Plus the above solution can be improved further. The understanding is that if a box is already visited so does the 2 boxes below it and similar for those 4 boxes even below it. Hence there is no need for prunig those boxes further whose parent is already visited and hence can reduce the recursion calls by a lot for more than one points Hence the improved prune_boxes will be like this.

void prune_boxes(int x, int y){
     if (y < 0)
       return;
     else{
       if (boxes[x][y] == 0){
         boxes[x][y] = 1;
         counter++;
         prune_boxes(x, y - 1);
         prune_boxes(x + 1, y - 1);
       }else{
         return;
       }
     }
    }
\$\endgroup\$
  • \$\begingroup\$ Don't use static variables when you don't have to: how about having prune_boxes() return "ruinedThisTime"? \$\endgroup\$ – greybeard Jan 19 '16 at 22:36
  • \$\begingroup\$ Agreed on static variables. Are you talking about time elapsed for every prune_boxes() ? \$\endgroup\$ – Mayukh Sarkar Jan 20 '16 at 5:42
  • \$\begingroup\$ talking about time elapsed - no. Ruined, wasted, gotten wet in this iteration - this time. \$\endgroup\$ – greybeard Jan 20 '16 at 9:39
  • \$\begingroup\$ we can take another variable say currentCount and start with currentCount = count - 1 and then in every recursion we can get number of wet boxes by count - currentCount..correct me if I am wrong. \$\endgroup\$ – Mayukh Sarkar Jan 20 '16 at 9:54
  • \$\begingroup\$ To get rid of that static count, make it local and return a combination of that value with the return values of the recursive calls. \$\endgroup\$ – greybeard Jan 20 '16 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.