My fifth and final pull request for the 0.2 Release was on C++. This my second time in this release working with C++. C++ is a general-purpose programming language. It has imperative, object-oriented and generic programming features, while also providing facilities for low-level memory manipulation. When trying to figure out what I should work on for my final pull request, I was not able to be picky about it. A lot of the issues that would go up would get taken minutes after. Some people might not leave comments under issues. Instead they would just reference the issue in their pull request. So if I’m scrolling through the issues and see an issue with no comments I would get excited thinking I could work on it, but most of the time, the issue would be completed with some one else leaving a link to their pull request on the issue page. At first I sorted the issues by Least Commented but that would mostly show issues from a year ago. So I went back to sorting the issues by Newest. I had to go back a couple of pages and finally I found an issue that was posted four days ago which I felt I was confident in completing. The following is the link to the issue.
What was being asked from the issue was to create a new file, where the number of Dyck Paths could be solved. A Dyck path is a staircase walk from (0, 0) to (n, n) that lies strictly below (but may touch) the diagonal y = x. The number of Dyck paths of order n is given by the Catalan number.
Consider a n x n grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (n-1, 0) to top right, i.e., (0, n-1) that lies above the diagonal cells (or cells on line from bottom left to top right).
The following are example inputs:
- Input: n = 1 – Output: 1
- Input: n = 2 – Output: 2
- Input: n = 3 – Output: 5
- Input: n = 4 – Output: 14
The following is the mathematical equation to calculate the Dyck Path which is given by the Catalan Number C(n).
In terms of what I had in my code was the following equation. It seemed simple enough, but when it came to calculating the factorial, I had to take some time to figure that out.
Since there are three instances of using the factorial in the equation, it made sense to make a factorial function. I created two more variables to hold the values after the value entered is multiplied by 2 and added with 1. I coded everything but at first something did not seem right. When I entered the value 7 to calculate the number of Dyck paths, I was getting a different value compared to what was calculated on my sheet of paper because I was testing to see if my program was working properly. It turns out that because I was using an
int data type, the number of Dyck paths would be beyond the range of an
int data type. I looked up different data types and used the data type with the highest range which was a
long long. Since we’re only working with positive values, I made the variables of type
unsigned long long int. After changing the data types, and after entering 7 to calculate the number of Dyck paths, I got the same value as what I had calculated manually. The following image is an example of different inputs with the number of Dyck paths calculated.
After completing my program, I made the pull request and made sure to reference the issue in my pull request.
After completing this second release, I feel more confident working with GitHub and Git Bash. For the third and fourth release, I look forward to working with larger projects and collaborating with more people and starting on new projects with people from our class.