Prepare the bunnies escape error

[hanuor]

Hi, I tried to run your code for 'Prepare the bunnies escape' challenge and its throwing an error saying 'The execution took too long'. Can you help me with the solution? Thanks, Shantanu

[xphoniex]

Hi Shantanu,

Are you submitting the code into Foobar or running it on your machine? I just ran it on compilejava.net with no problem.

If you're submitting it to foobar then you should reconsider :)

[hanuor]

Hey, Yeah no I took help from the solution that you gave but failed two test cases (3&4). Then thought to give this one a try and got the error.

[xphoniex]

I'm looking at the code right now and nothing comes to mind :) either I've changed something last minute before I submitted the code or they've changed their test cases.

I suggest you use return somewhere in your code to see where it gets stuck, a good place to start would be before for (int o = 0; o < ones.size(); o++) ...

[hanuor]

Yup, and one more thing. Are we talking about square matrices here only. There's only one line mentioning this. We can tweak up the algo a bit if it is. What do you think?

[xphoniex]

There's no mention of the map being square on the description. Wouldn't matter either, how can you improve it if it's square only?

[hanuor]

Well if it is a square that means the shortest path possible would not be less than ((h+w)-1) definitely. That means if we get our calculated path value equal to this then we don't have to move to the flipping part. Actually this works for a non -square matrix too. Regarding the algorithm, I think what you implemented is a recursive backtracking approach. This can be improved by using a BFS or Djikstra to find the above said value. Regarding the flipping. I couldn't exactly figure out your part of the code. I figured a hacky but efficient way to do it that would take a linear amount of time.

[xphoniex]

Yup, we can safely terminate if we get h+w.

The algorithm is very similar to Djikstra, I'm traversing the graph once starting from (0,0) and once from (h,w), keeping a global min and then going through each 1 in the map and checking if we can connect it's adjacent cells and get a shorter path than the global min :

path_1_till_this_point + 1 + path_2_till_this_point < min

What's your hacky way?

[hanuor]

• To find the shortest path there are two possible ways

  Either move right or move downwards

If we move right by flipping a 1 then it would not give us a shortest path whatsoever because we are just moving alongside a row which wouldn't contribute much and not the column. That means the only case we need focus is moving downwards. So the first step is to map each co-ordinate of the points that we traverse when we calculate our shortest path. So for this matrix: [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]] we would have: (0,0)>(0,1)>(0,2)>(0,3)>(0,4)>(0,5)>(1,5)>(2,5)>(2,4)>(2,3)>(2,2)>(2,1)>(2,0)>(3,0)>(4,0)>(5,0)>(5,1)>(5,2)>(5,3)>(5,4)>(5,5) We could store this in a HashMap/Table (but I don't think we require a key here). So ArrayList would be fine. Next, we break these points into actual numbers. So for example point (2,3) would be 23 and (5,1) would be 51.

Now we sort them and find the pairs with a difference of 20 (see the image). Maximum complexity of O(nlogn) would be there.

Next we start with the first pair. We break the numbers in the pairs into points, So in our case the first pair would be 0 and 20. We will break it into points (0,0) and (2,0). Now we simply check that if these points exist in our ArrayList. If yes then we remove all of the points that lie between these two. So now we would have: (0,0)>(2,0)>(3,0)>(4,0)>(5,0)>(5,1)>(5,2)>(5,3)>(5,4)>(5,5) That's it, we just need to calculated its size and add a 1 to it for the point that we flipped. Next we would check if this size is lesser than our previous one. If it is then we would assign this size as our lowest and move on to check for other pairs. This will be of O(n) time complexity.

[xphoniex]

You can find all pairs with 20 difference in O(n): add them to both hash list & array, check if +-20 of each one is included in the hash.

However your solution won't work when you must flip one cell, you won't be able to come up with the path in the first place :

0 0 0 
0 1 1 
1 0 0

So you need to somehow traverse backwards from (h,w) too.

Also how can you solve this one?

0 0 0 1 0
0 1 1 1 0
0 1 0 0 0
0 0 0 1 0
1 0 0 1 0

if I'm not mistaken, path would be : (0,0) -> (1,0) -> (2,0) -> (3,0) -> (3,1) -> (3,2) -> (2,2) -> (2,3) -> (2,4) -> (3,4) -> (4,4) , pairs with twenty difference would only have zeroes in-between which doesn't count.

[hanuor]

For both of the cases: Considering the problem statement the matrix is always solvable (Bunnies are allowed to pass through the maze, as quoted "The map will always be solvable, though you may or may not need to remove a wall.") and we have to find the shortest path possible for this.

Even if this wasn't the case, the hack would work. In the first case if you would focus on position (1,1), we would get the result by flipping it. The total path would be equal to the minimum shortest path.

For the second case, notice the position (1,2). The hack is applicable there. I haven't tested this against many test cases but till now I haven't found a test case in which it fails. About the '20 difference' part. We can overlook this but if you'll consider the solutions for the cases when a 1 is flipped you would notice a pattern which is solvable by using another method. The '20 difference' one is quite easy to understand.

[xphoniex]

Right but once you remove (1,1), you have to traverse the graph to get the full path, and it's size.

Consider this :

0 0 1 1 0
0 1 1 1 0
0 1 0 0 0
0 0 0 1 0
1 0 0 1 0

[hanuor]

Yeah it fails here.

[xphoniex]

In case it still exceeds time limit, you could use this to limit the search space on ones, right now we're adding every 1 blindly while we should only add those who have two 0s as neighbours.

[hanuor]

No worries, I wasn't able to find the right solution. I'll update you soon with a new version of my hack. :) Thanks!

[wli75]

Hi, I didn't get the foobar challenge but I'm interested in this problem. In this loop, if a majority of the cells are 0, would it amount to exponential time complexity?

while (!q.isEmpty()) {

    point p = q.poll();

    if (visited[p.y][p.x] == 0)
        if (maze[p.y][p.x] == 1)
            ones.add(new point(p.y,p.x));

    visited[p.y][p.x] = 1;

    if (maze[p.y][p.x] != 1) {
        placeP(minRegular, visited, q, p, h, w);
    }
}

[xphoniex]

we'll check if each of the neighbors has been visited inside PlaceP :

        if (p.x < w-1 && visited[p.y][p.x+1] == 0)
            q.add(new point(p.y, p.x + 1));
        if (p.x > 0 && visited[p.y][p.x-1] == 0)
            q.add(new point(p.y, p.x - 1));
        if (p.y < h-1 && visited[p.y + 1][p.x] == 0)
            q.add(new point(p.y + 1, p.x));
        if (p.y > 0 && visited[p.y - 1][p.x] == 0)
            q.add(new point(p.y - 1, p.x));

but we'll process each only once.

[wli75]

Is my following understanding of your algorithm correct? When we first visit (1,0), we add to the queue (2,0) and (1,1). Then we visit (0,1), since (1,1) hasn't been marked as visited, it will be added to the queue again. We next add (0,2).

[xphoniex]

You're completely right. This should fix the issue :

 public static void placeP(int[][] minRegular, int[][] visited, Queue<point> q, point p, int h, int w) {

    if (p.x > 0 && minRegular[p.y][p.x-1] > 0)
    minRegular[p.y][p.x] = Math.max(minRegular[p.y][p.x], minRegular[p.y][p.x-1] + 1);
    if (p.x < w-1 && minRegular[p.y][p.x+1] > 0)
    minRegular[p.y][p.x] = Math.max(minRegular[p.y][p.x], minRegular[p.y][p.x+1] + 1);
    if (p.y > 0 && minRegular[p.y-1][p.x] > 0)
    minRegular[p.y][p.x] = Math.max(minRegular[p.y][p.x], minRegular[p.y-1][p.x] + 1);
    if (p.y < h-1 && minRegular[p.y+1][p.x] > 0)
    minRegular[p.y][p.x] = Math.max(minRegular[p.y][p.x], minRegular[p.y+1][p.x] + 1);

    if (p.x < w-1 && visited[p.y][p.x+1] == 0) {
        q.add(new point(p.y, p.x + 1));
        visited[p.y][p.x+1] = 1;        
    }
    if (p.x > 0 && visited[p.y][p.x-1] == 0) {
    q.add(new point(p.y, p.x - 1));
        visited[p.y][p.x-1] = 1;
    }
    if (p.y < h-1 && visited[p.y + 1][p.x] == 0) {
    q.add(new point(p.y + 1, p.x));
        visited[p.y + 1][p.x] = 1;
    }
    if (p.y > 0 && visited[p.y - 1][p.x] == 0) {
    q.add(new point(p.y - 1, p.x));
        visited[p.y - 1][p.x] = 1;
    }

}

Comment out visited[p.y][p.x] = 1; and if (visited[p.y][p.x] == 0) inside the loops too. Can you try this @hanuor ?

[xphoniex]

While ^ should fix time limit issue, I found a bad apple for one of my assumptions too :

int[][] maze = {
    {0,0,0,0,0},
    {1,0,1,1,0},
    {0,0,1,1,0},
    {0,1,1,0,1},
    {0,1,0,0,0},
    {0,0,0,1,0}
};
// min is 10, instead we get 12

Add this :

      int[][] minRegular = new int[h][w];
      int[][] minRegular2 = new int[h][w];

      for (int i = 0 ; i < h ; ++i) {
        for (int j = 0 ; j < w ; ++j) {
          if (maze[i][j] == 0) { 
            minRegular[i][j] = 201;
            minRegular2[i][j] = 201;
          }
        }
      }

And use Math.min instead inside PlaceP :

 public static void placeP(int[][] minRegular, int[][] visited, Queue<point> q, point p, int h, int w) {

    if (p.x > 0 && minRegular[p.y][p.x-1] > 0)
    minRegular[p.y][p.x] = Math.min(minRegular[p.y][p.x], minRegular[p.y][p.x-1] + 1);
    if (p.x < w-1 && minRegular[p.y][p.x+1] > 0)
    minRegular[p.y][p.x] = Math.min(minRegular[p.y][p.x], minRegular[p.y][p.x+1] + 1);
    if (p.y > 0 && minRegular[p.y-1][p.x] > 0)
    minRegular[p.y][p.x] = Math.min(minRegular[p.y][p.x], minRegular[p.y-1][p.x] + 1);
    if (p.y < h-1 && minRegular[p.y+1][p.x] > 0)
    minRegular[p.y][p.x] = Math.min(minRegular[p.y][p.x], minRegular[p.y+1][p.x] + 1);

    if (p.x < w-1 && visited[p.y][p.x+1] == 0) {
        q.add(new point(p.y, p.x + 1));
        visited[p.y][p.x+1] = 1;        
    }
    if (p.x > 0 && visited[p.y][p.x-1] == 0) {
    q.add(new point(p.y, p.x - 1));
        visited[p.y][p.x-1] = 1;
    }
    if (p.y < h-1 && visited[p.y + 1][p.x] == 0) {
    q.add(new point(p.y + 1, p.x));
        visited[p.y + 1][p.x] = 1;
    }
    if (p.y > 0 && visited[p.y - 1][p.x] == 0) {
    q.add(new point(p.y - 1, p.x));
        visited[p.y - 1][p.x] = 1;
    }

}

[xphoniex]

@bhargavb34 did you follow directions on my last two comments?

[abhishekmatcha]

can you please give me exact code which works with good time your code takes more time while running in foobar

[wli75]

I've never submitted this solution to foobar, but if you want to try it here you go: https://pastebin.com/1bwF10Lg Otherwise, you may consider modifying Dave's code with the instructions he listed above :)

[ArnavKhera]

Hi wli75, your solution to the challenge works fantastically for all the tests, but I was wondering how the code worked, like if you could explain or show the logic behind it.

[ArnavKhera]

I mean I get what the code is doing, but I don't understand why it is doing it and how it gives out the correct answer.

[wli75]

I'm glad it works!

So cost[i][j][0] stores the shortest path from (0,0) to (i,j) without removing a wall, and cost[i][j][1] stores the shortest path if a wall is removed. If the cost of a cell has changed, we need to update the costs of the other cells along its path, particularly cells higher or to the left of the changed cell. Since a path has roughly O(mn) cells, the outer hasChanged loop will be called O(mn) times. So the whole algorithm is O( (mn)^2 ), but it's okay since m,n <= 20.

If you're interested, here's another challenge that uses a similar technique https://www.hackerrank.com/contests/booking-womenintech/challenges/manhattan-2

[ArnavKhera]

I think I get the logic now... Thanks a lot wli75!

[Abhisssss]

` int[][] minRegular = new int[h][w];
  int[][] minRegular2 = new int[h][w];

  for (int i = 0 ; i < h ; ++i) {
    for (int j = 0 ; j < w ; ++j) {
      if (maze[i][j] == 0) { 
        minRegular[i][j] = 201;
        minRegular2[i][j] = 201;
      }
    }
  }

`

In the above modification why exactly you took 201 number and what is it for ?