Diagonal

In this post I will be attempting to solve the "Diagonal" problem given in class.

The problem is as follows: 

You have a rectangular grid made up of m rows and n columns where m, n represent positive whole numbers. Suppose you draw a line from the upper left corner to the lower right corner. How many of the grid squares will the line pass through the grid?

Understanding the problem: 
We are given a grid and we must determine how many squares will be intersected by a line drawn from the top left corner to the lower right corner.

Devise a plan: 

The goal here is to reduce the problem as much as possible. In other words, by reducing a larger grid into a smaller section which can be scaled back to the original grid, the problem can be simplified. We do this by dividing each side by the greatest common divisor of the two dimensions. For example, Figure 1 can be reduced to Figure 2 since Figure one is 4x2, it can be reduced to 2x1 since GCD(4,2) = 2

Figure 2

Figure 1

Once you have the smallest and simplest grid possible. You can compute the number of grids intersected by the equation L + W - 1 where L is the number of rows of this reduced grid and W is the number of columns of this reduced grid. Since this rectangle is a reduced version of the original, we must multiply (L + W - 1) by the GCD(X,Y) to get the number of grids intersected in the original grid.

The actual equation is GCD(X,Y) * (L + W - 1)
where X is the number of rows of the grid
where Y is the number of columns of the grid
where L = X/GCD(X,Y)
where W = Y/GCD(X,Y)

In python the code would be:
    from fractions import gcd

    def diagonal(length, width):
        return length + width - GCD(length, width)

Carry out the plan:
Let's suppose we are given the example in the handout where X = 4 and Y = 6.
In the diagram, 8 squares are intersected. If we use our solution with these values we get: 
Squares intersected = GCD(X,Y) * (L + W - 1)
                            = GCD(X,Y) * (X/GCD(X,Y) + Y/GCD(X,Y) - 1)
                            = GCD(4,6) * (4/GCD(4,6) + 6/GCD(4,6) - 1)
                            = 2 * (2 + 3 - 1)
                            = 2 * 4
                            = 8

Look back:
Does this solution work for every single possible combination of X and Y?
Of course, if the GCD of X and Y is 1, the reduced grid would have the same dimensions as the original grid but the solution would work regardless.
After verifying my solution with many different inputs, I believe this is the general solution. 
---------------------------------------------------------------------------------
If you look at a rectangular parallelepided that had X rows, Y columns and O layers, you'll notice that if you take the largest two of these three values and plug them into the equation for grids. It'll produce the number of cubes that a line from one vertex to the opposite vertex would intersect.