2.2.3. Handling Holes in Computation

So, let us look for a better solution. So, as you might guess, since we are looking at these kind of inductive formulations and recursive programs, what we are really looking for is the inductive formulation of the grid path. So, let us ask ourselves the following question. How do I get to a point (i,j) on the grid? So, I claim, that given our structure, which is, that we can go right or we can go up, there are only two ways I can come here. I can either come right from the neighbor on my left. So, from (i,j minus 1) I can make one step right and come to (i,j) or from (i minus 1, j), I can go up once there. So, if I have any paths, which starts at (0,0), right, any path, which somehow comes to (i,j -1), then by taking one, exactly one step, that path becomes one path to (i,j) right.

In this chunk, we are exploring how to find paths on a grid through inductive reasoning. We focus on reaching a specific point (i,j) in a grid, starting from the origin point (0,0). The key idea is that we can only reach (i,j) from two places: either directly from the left (i, j-1) or from below (i-1, j). Accordingly, if we have paths leading to (i,j-1) or (i-1,j), they can contribute to a path leading to (i,j) after making the respective move. This understanding sets the stage for counting all possible paths to (i,j).

Imagine navigating a maze where you can only move either right or up. If you want to find your way to a specific spot, you could think of every route as coming from either the left path or the path below. If each route you took led you closer to your destination, you would recognize that your journey relies on steps taken from previous points, just like these paths depend on their predecessors.

So, let us write paths (i,j) to denote the number of paths from (0,0) to the current point (i,j). ... So, if I am at (0,0) and I want to go to (0,0), how many ways are there? Well, this is a trivial path, there is only one way, by just staying there.

In this chunk, we define a function paths(i,j) that calculates the number of paths from the starting point (0,0) to point (i,j). We address boundary conditions that play an important role in this calculation. For example, the entire leftmost column and bottom row can only be reached in one way (going only right or only up). Additionally, we note the special case of (0,0) which has exactly one path: remaining at the origin. These base cases are critical for building up the solution through dynamic programming.

Think of it as walking in a straight line along a edge of a field. If you're in the leftmost column or bottom row, there’s only one direction you can go: either up the row or across the column. When you stand still at the origin, you realize there’s essentially only a single option to 'walk'—which is to stay put!

So, how do we deal with holes in this setup? That is easy, we just say, that whenever there is a hole at a given point we just declare parts of ... So, any hole will just have by declaration paths (i,j) equal to 0 because nothing can go through it.

This chunk explains how to manage obstacles (holes) within the grid setup. When there is a hole at point (i,j), we define paths(i,j) to be zero. This means no paths can pass through this point, effectively cutting off any contributions to the points directly adjacent to the hole. Through this definition, the values computed for paths in the area become automatically adjusted to account for the absence of routes through the holes.

Imagine again navigating a maze but this time with obstacles blocking some paths. If a hole appears on your path, you cannot go through it, meaning that it won't contribute to any routes leading to the destination. Therefore, you must redirect and rely on alternative routes, which significantly changes the available paths.

So, we have seen before, we have two technologies to deal with this. So, one is memoization ... the other way is to, is to anticipate the sub problems, figure out how they depend on each other, then solve them directly iteratively in a suitable order ...

Here, we discuss two methods to enhance the efficiency of our path counting: memoization and dynamic programming. Memoization stores previously calculated results for specific paths(i,j) to avoid redundant calculations. In contrast, dynamic programming takes a proactive approach by understanding the dependencies of subproblems and solving them in a systematic manner. This usually leads to better performance because it avoids repeated calculations.

Think about how you memorize your friend's phone numbers, where each number you learn makes it easier to remember others (like memoization). However, when faced with an array of phone books organized by names (like dynamic programming), you sort through each systematically, which proves more effective than trying to recall randomly. Both methods serve to improve efficiency, but directed ordering can streamline the process.

So, how would we use dynamic programming on the grid? So, this is our grid with the two holes at the (2,4) and (4,4). The first thing is to identify DAG structure of the dependencies ...

In this chunk, we start to implement dynamic programming on our grid with holes by establishing a Directed Acyclic Graph (DAG) structure to map dependencies. The orientation of the grid helps us understand which nodes can be computed based on their previous nodes. By identifying these dependencies, we can perform calculations in a clear order, starting from (0,0) and filling in all necessary values sequentially.

Consider a project where tasks are interdependent. You must finish task A before moving on to task B, which must be done before task C. If you visualize these tasks as points in a diagram, you see a flow. Similarly, the grid allows us to visualize grid spaces so we can compute our paths effectively, ensuring all prerequisites are met before achieving the target.

So, we start at (0,0) and we fill the value there, which is 1. And now, we observe, that we have two possibilities. We can go to the right or we can go up ...

In this section, the process of traversing each point in the grid while filling in the path counts is elaborated. Starting at (0,0) with one path, we traverse row-wise or column-wise, systematically calculating the number of paths available to each point. While filling in the grid, attention is given to ensure that if we hit a hole, the path count at that point is declared zero automatically, thus propagating the absence of viable paths.

Think of this as filling out a report step-by-step, where with each section or point, you gather all relevant information to furnish it correctly. If you find a section that's incomplete or incorrect (a hole), you note it as zero and move on without it impacting the rest of your report.

--