I have been participating in an online challenge by Google. After tackling one of the challenges this weekend, I came across a challenge that revolved around the traversal of a 2D-array, from the top-left cell to the bottom-right cell, only by moving down and right. I was inspired by this challenge to try and model the number of pathways, traversed in this manner, through an n-by-n 2D-array.
What it does
Through the weekend, my project turned into trying to precisely mathematically model the number of pathways of "traversing" the n-by-n grid.
How I built it
In order to find a formula that models the behavior of the number of pathways for any size n-by-n, I first started by calculating the number of pathways for specific values of n. I did the computations using various methods and tried to find patterns between the different values of n.
Challenges I ran into
After running the numbers for several values of n and plotting using excel, I could not find a simple model to fit the data (like exponential, or power). I could only approximate a function using nth-degree polynomials. Ultimately, I was unable to solve the problem completely.
Accomplishments that I'm proud of
I am proud to say that I found several relationships and patterns between various relevant parameters in the data and have come close to cracking the problem.
What I learned
I learned more about recursive functions as this relationship seems to acts recursively like some series functions. I also learned that approaching the problem from many different angles can result in discovering and fitting more pieces together. Finally, I learned how integral mathematics is to computer science.
What's next for 2D Array Traversal
The next step is to find what I am referring to as the recursive relationship (the n-th output depends on the n-1th output) that describes this behavior. Then the final step would be to convert that recursive model to a non-recursive one so that you can easily get the output for any input.