The Human Resources manager informed that employees working in the corporate headquarters (CHQ) will have the second and fourth Saturday of the month off. This affected the leave balance calculation method in my Rails application. If a CHQ employee applies for leave and a second or fourth Saturday falls in between the start date and end date, they should not be deducted a leave.

I was already using the Rails date library. Given a date, I could get the beginning of the month and end of the month in which the date occurred. Before I could figure out how to proceed with this info, I went to stackoverflow.com and put up a question[1].

Very quickly, in about 10 minutes or so, Andrey posted a solution. It traverses from the beginning of the month to the end of the month and saves the Saturdays' dates in an array. Then it checks if an array of the second and fourth Saturday dates includes the given date.

I was happy, I got a solution so quickly. Just a few minutes later, Reggie proposed an improvised solution. The second Saturday has to be in the day range 8-14, the fourth in the day range 22-28, and so he just checks if the given date is a Saturday and falls between the 8th and 14th or 22nd and 28th of the month.

I thought I got a very good solution, so I can now use it. About half an hour later, Eric posted another solution that improvised upon the previous improved solution. He wrote:

Days 1 to 7 are week 0

Days 8 to 14 are week 1

Days 15 to 21 are week 2

Days 22 to 28 are week 3

To get the week id, we can calculate (date.day-1)/7. Since the id is zero-based, the second and fourth Saturdays have an odd week id.

This was the best solution. After that I did not get any other solution. So I proceeded with using it.

Later in the day, looking at these solutions, I noticed that the sequence we went through was as follows:

First solution: Brute force, just loop through all the data set and find out which one satisfies the solution criteria.

Second solution: Reduce the number of loops using elimination logic.

Third solution: Use a formula that doesn't require to do any looping.

Then it struck me that this is how algorithm design happens. You start with the brute-force method, then optimize the algorithm, then figure out a formula that will eliminate unnecessary steps. In many cases, the second step could be to pre-sort the data and use a data structure that does efficient operations.

Thus, all in an hour's play with Rails, I journeyed through algorithm design while solving a real-world problem and even though it was a small one, it was an insightful experience for me.

Reference

[1] http://stackoverflow.com/questions/41997584

I was already using the Rails date library. Given a date, I could get the beginning of the month and end of the month in which the date occurred. Before I could figure out how to proceed with this info, I went to stackoverflow.com and put up a question[1].

Very quickly, in about 10 minutes or so, Andrey posted a solution. It traverses from the beginning of the month to the end of the month and saves the Saturdays' dates in an array. Then it checks if an array of the second and fourth Saturday dates includes the given date.

I was happy, I got a solution so quickly. Just a few minutes later, Reggie proposed an improvised solution. The second Saturday has to be in the day range 8-14, the fourth in the day range 22-28, and so he just checks if the given date is a Saturday and falls between the 8th and 14th or 22nd and 28th of the month.

I thought I got a very good solution, so I can now use it. About half an hour later, Eric posted another solution that improvised upon the previous improved solution. He wrote:

Days 1 to 7 are week 0

Days 8 to 14 are week 1

Days 15 to 21 are week 2

Days 22 to 28 are week 3

To get the week id, we can calculate (date.day-1)/7. Since the id is zero-based, the second and fourth Saturdays have an odd week id.

This was the best solution. After that I did not get any other solution. So I proceeded with using it.

Later in the day, looking at these solutions, I noticed that the sequence we went through was as follows:

First solution: Brute force, just loop through all the data set and find out which one satisfies the solution criteria.

Second solution: Reduce the number of loops using elimination logic.

Third solution: Use a formula that doesn't require to do any looping.

Then it struck me that this is how algorithm design happens. You start with the brute-force method, then optimize the algorithm, then figure out a formula that will eliminate unnecessary steps. In many cases, the second step could be to pre-sort the data and use a data structure that does efficient operations.

Thus, all in an hour's play with Rails, I journeyed through algorithm design while solving a real-world problem and even though it was a small one, it was an insightful experience for me.

Reference

[1] http://stackoverflow.com/questions/41997584

DZone republished this blog post. Please find it at:

ReplyDeletehttps://dzone.com/articles/applied-rails-an-algorithmic-perspectin/