find baby sitting gaps by Ruby
How does the Incredibles arrange baby sitting? This demanding baby needs non-stop care 24 hours a day, and their life would go crazy if there's a gap. Let's take a look at the baby's schedule and find the gap:
"That's ridiculous", you may think, "why would we need a program to find this?". Well it's very easy to spot the gap if there's only one baby with several babysitters, but when there're hundreds of dying patients and busy nurses it's definitely a nightmare to find gaps in a highly dynamic schedule. It's not a joke, it's a real situation my sister's facing and as a developer I got to write a program to help this. But how?
My first thought was to write a method, to loop every hour of the day and check if it's within the shift of the baby sitter on the schedule. However, loops and flow controls are slow. Is there a better way? Fortunately in Ruby we have two flexible data structures: Array and Hash. They can be sets of any available objects, and marvellously there's a wonderful property of Array when it comes to the subtraction:
Apparently, the subtraction of a array from another array will take away all overlapping objects. So we can use array to represent shifts, the gaps can be obtained by simple subtraction, and the program won't go nuts if a section of the time is already assigned. The gap of the baby can be simply calculated by Array(whole day) - Array(babysitter 1) - Array(babysitter 2) - Array(babysitter 3), etc. Let's start a 24 hr whole day for the baby, and put the array into the Hash.
Now let's record everybody's shift in the unit of 24-hour clock, using the exact same way we created the entire day Array. The two shifts of Rob, the Mr.Incredible, can be created by adding Arrays.
Now Kari, the babysitter asks: what time do you want me to fill? We can get the answer by a quick subtraction:
Yes, that's right, no flow controls or loops at all. It took me almost a week to comes to this solution. And theoretically speaking this algorithm doesn't even need to load everybody's shifts all at once. Fast and easy, let's enjoy the magic power of Ruby!