DPS909 0.2 Release – Pull Request 5

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.

Add program to count dyck paths #6

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).

PR5

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).

PR5.1

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.

PR5.2

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.

PR5.3

After completing my program, I made the pull request and made sure to reference the issue in my pull request.

Count dyck paths #138

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.

References

Dyck Path

C++

Tutorial

Published by

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s