Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Applied Rails: An Algorithmic Perspective

DZone's Guide to

Applied Rails: An Algorithmic Perspective

Here's the story of how an MVB, along with some help, reached an optimal Ruby on Rails application by following the tenants of algorithm design.

· Web Dev Zone
Free Resource

Learn how to build modern digital experience apps with Crafter CMS. Download this eBook now. Brought to you in partnership with Crafter Software

The Human Resources manager informed employees working in the corporate headquarters (CHQ) that they 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.

def fourth_saturday?(date)
saturdays = (date.beginning_of_month..date.end_of_month).select { |date| date.wday == 6 }
[saturdays.second, saturdays.fourth].include?(date)
end

I was happy that 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.

def second_or_fourth_saturday?(date)
  return false unless date.saturday?
  (8..14).include?(date.day) || (22..28).include?(date.day)
end

I thought I had gotten a very good solution that I could then use. And then, about half an hour later, Eric posted another solution that improvised upon the previously 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.

def second_or_fourth_saturday?(date)
  date.saturday? && ((date.day - 1) / 7).odd?
end

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 sets 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 you to do any looping.

Then it struck me that this is how algorithm design works. 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, in all of an hour of playing around 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

Crafter is a modern CMS platform for building modern websites and content-rich digital experiences. Download this eBook now. Brought to you in partnership with Crafter Software.

Topics:
web dev ,rails ,ruby ,algorithm

Published at DZone with permission of Mahboob Hussain, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}