R
Ruby Quiz
The problem space of scheduling is vast and complicated, but it's not too hard
to get some form of working solution. The real trick is the quality of the
schedule generated.
I took a very easy approach, to keep the problem manageable. My initial thought
when reading the problem was to use a "Hill Climbing" algorithm. I planned to
start by just assigning every shift (ignoring availability and preference), and
then swap shifts until I had a corrected schedule. That process changed a bit
when I was actually coding it up though. More on that later.
The first thing I needed was some notion of time. I did consider using the
built-in Time class, but I really wanted something simple. My approach only
considers time in hour slices and the main functionality I needed was support
for use in a Range object. Here's what I settled on:
#!/usr/local/bin/ruby -w
require "yaml"
# A representation of a single hour. Usable in Ranges.
class Hour
def initialize( text )
@hour = case text
when "12 AM"
0
when "12 PM"
12
when /(\d+) PM/
$1.to_i + 12
else
text[/\d+/].to_i
end
end
include Comparable
def <=>( other )
@hour <=> other.instance_eval { @hour }
end
def succ
next_hour = Hour.new("12 AM")
next_time = (@hour + 1) % 24
next_hour.instance_eval { @hour = next_time }
next_hour
end
def to_s
str = case @hour
when 0
"12 AM"
when 12
"12 PM"
when 13..23
"#{@hour - 12} PM"
else
"#{@hour} AM"
end
"%5s" % str
end
end
# ...
The easiest way to get a unique and comparable representation of an hour I could
think of was to use military time. That's exactly what the constructor does. I
parse the string representation of a time and store the military hour (0-23)
internally.
If you glance down, you'll see that to_s() is simply the reverse of this
process. I use it in printing results.
The other two methods are simple. The documentation for Range say that you can
use any object that supports <=>() and succ(), so that's what we have here. The
<=>() method just compares the military hours. succ() builds a new Hour object
then sets it to one hour ahead of the current object and returns the new Hour.
You can see that I'm using instance_eval() in both of these methods to read and
adjust the internal representation in other Hour objects. That felt more
correct than exposing the internal representation with an accessor and I think
it's great that Ruby lets me make this choice.
The other helper class I felt need for was something to represent a worker. I
wanted to be able to feed it the worker's requested schedule and then query it
as needed. Here's the code:
# ...
# An object for tracking a worker's availability and preferences.
class Worker
def initialize( name )
@name = name
@avail = Hash.new
@prefers = Hash.new
end
attr_reader :name
def can_work( day, times )
@avail[day] = parse_times(times)
@prefers[day] = if times =~ /\((?
refers )?([^)]+)\s*\)/
parse_times($1)
else
Hour.new("12 AM")..Hour.new("11 PM")
end
end
def available?( day, hour )
if @avail[day].nil?
false
else
@avail[day].include?(hour)
end
end
def prefers?( day, hour )
return false unless available? day, hour
if @prefers[day].nil?
false
else
@prefers[day].include?(hour)
end
end
def ==( other )
@name == other.name
end
def to_s
@name.to_s
end
private
def parse_times( times )
case times
when /^\s*any\b/i
Hour.new("12 AM")..Hour.new("11 PM")
when /^\s*before (\d+ [AP]M)\b/i
Hour.new("12 AM")..Hour.new($1)
when /^\s*after (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new("11 PM")
when /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new($2)
when /^\s*not available\b/i
nil
else
raise "Unexpected availability format."
end
end
end
# ...
The constructor just makes note of the name for this Worker, then sets up two
Hash objects to hold availability and preferred schedule. The Hashes will use a
day of the week as a key and a Range of Hour objects as the value. An
availability of "any" can be represented as a Range of all the Hours in a day.
This is easy to work with, but it can't handle split-shift style availabilities.
You could fix this by making the values Arrays of Ranges.
The next three methods are all closely related. First, can_work() takes a day
String and a String representation of available times and uses those to set the
previously mentioned Hashes. The actual parsing is delegated to the private
parse_time() method, which just uses Regexps to break down the input. Once a
schedule has been loaded, you can check availability for a given day and hour
with available?(). The prefers?() method takes the same input but returns a
preference instead. A Worker must be available to work a given time to have a
preference about it.
Those are the only helper classes I built. The rest is application code:
# ...
if __FILE__ == $0
unless ARGV.size == 1 and File.exists?(ARGV.first)
puts "Usage: #{File.basename($0)} SCHEDULE_FILE"
exit
end
# load the data
data = File.open(ARGV.shift) { |file| YAML.load(file) }
# build worker list
workers = Array.new
data["Workers"].each do |name, avail|
worker = Worker.new(name)
avail.each { |day, times| worker.can_work(day, times) }
workers << worker
end
# ...
That's all pretty basic. Check and display usage, if needed; load the YAML
representation of workers and schedule hours to be filled; anf finally, build an
Array of Worker objects that are aware of their availability and preferences.
Here's the YAML file I'm using:
---
Schedule:
Wed: 9 AM to 6 PM
Sun: 9 AM to 10 PM
Thu: 9 AM to 8 PM
Mon: 9 AM to 6 PM
Tue: 9 AM to 6 PM
Sat: 9 AM to 10 PM
Fri: 9 AM to 6 PM
Workers:
James:
Wed: any
Sun: any (prefers before 5 PM)
Thu: 12 PM to 3 PM
Mon: before 3 PM (prefers before 12 PM)
Tue: any
Sat: not available
Fri: 12 PM to 3 PM
Brian:
Wed: not available
Sun: after 1 PM
Thu: any (prefers 8 AM to 5 PM)
Mon: any (prefers 8 AM to 5 PM)
Tue: any (prefers 8 AM to 5 PM)
Sat: any
Fri: any (prefers 8 AM to 5 PM)
The next step is to build a schedule. Here's where I deviated from my original
plan. I realized that if I limit myself to just worrying about availability at
first, I can build a correct schedule in those terms as I load it. Here's how
that turns out:
# ...
# create a legal schedule, respecting availability
schedule = Hash.new
data["Schedule"].each do |day, times|
schedule[day] = Array.new
if times =~ /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
start, finish = Hour.new($1), Hour.new($2)
else
raise "Unexpected schedule format."
end
(start..finish).each do |hour|
started_with = workers.first
loop do
if workers.first.available? day, hour
schedule[day] << [hour, workers.first]
break
else
workers << workers.shift
if workers.first == started_with
schedule[day] << [hour, "No workers available!"]
break
end
end
end
end
workers << workers.shift
end
# ...
A schedule is a Hash that stores day names paired with Arrays of Arrays. The
Arrays are a collection of Hour and Worker pairs, showing who is scheduled to
work at that time.
The second half of that code is what assembles the initial schedule. It just
walks every hour of every day assigning a worker. It starts with the first
worker in the list and keeps assigning them until them end of the day or until
the worker has a schedule conflict. Anytime either of those conditions happens,
the worker list is rotated and we try the next worker.
If we make it all the way through the list of workers without finding a person
who could work at that time, we just set the Worker slot to a warning message
and rely on the user to fix the problem. Blowing up with an exception here
seemed too drastic for what is likely a fairly common snag that I doubt software
is qualified to resolve.
The main issue with the above system is that it can assign people very long or
very short shifts. I think a good way to correct this would be to set minimum
and maximum shift lengths and adjust the software to honor them. Of course,
this will create more conflicts so you either have to accept that or make them
soft limitations.
Now, my code does make a second pass adjusting shifts, but now the focus turns
from availability to preference. Let's examine that:
# ...
# make schedule swaps for preferred times
schedule.each do |day, hours|
hours.each_with_index do |(hour, worker), index|
next unless worker.is_a?(Worker)
unless worker.prefers?(day, hour)
alternate = workers.find { |w| w.prefers?(day, hour) }
hours[index][-1] = alternate unless alternate.nil?
end
end
end
# ...
Here I'm just searching for people working hours they didn't prefer. When
found, I try to swap them out for someone who did prefer the time, if I can find
such a person. Otherwise, they have to stay.
Again, this can create some odd schedules. Mainly, people are traded on an
hourly basis and this can cause scheduling of one hour shifts. Again, I think
the answer is minimum shift lengths as I mentioned above, but in practice this
wasn't a chronic problem with availabilities like the ones in the YAML file.
When someone passed out of the times they preferred, it would generally cause
the rest of their shift to be replaced with someone that did want to work the
time.
All that remains is to print the schedule:
# ...
# print schedule
%w{Mon Tue Wed Thu Fri Sat Sun}.each do |day|
puts "#{day}:"
schedule[day].each do |hour, worker|
puts " #{hour}: #{worker}"
end
end
end
That's as easy as it looks. Walk the days, printing hours and who's working at
that time.
All-in-all it's an imperfect solution, but I think you could keep tuning it
until you get what you need. It works, but can certainly be made better.
Next week's Ruby Quiz is the number game that's been requested of me twice now,
so I really hope I'm not the only guy working that one...
to get some form of working solution. The real trick is the quality of the
schedule generated.
I took a very easy approach, to keep the problem manageable. My initial thought
when reading the problem was to use a "Hill Climbing" algorithm. I planned to
start by just assigning every shift (ignoring availability and preference), and
then swap shifts until I had a corrected schedule. That process changed a bit
when I was actually coding it up though. More on that later.
The first thing I needed was some notion of time. I did consider using the
built-in Time class, but I really wanted something simple. My approach only
considers time in hour slices and the main functionality I needed was support
for use in a Range object. Here's what I settled on:
#!/usr/local/bin/ruby -w
require "yaml"
# A representation of a single hour. Usable in Ranges.
class Hour
def initialize( text )
@hour = case text
when "12 AM"
0
when "12 PM"
12
when /(\d+) PM/
$1.to_i + 12
else
text[/\d+/].to_i
end
end
include Comparable
def <=>( other )
@hour <=> other.instance_eval { @hour }
end
def succ
next_hour = Hour.new("12 AM")
next_time = (@hour + 1) % 24
next_hour.instance_eval { @hour = next_time }
next_hour
end
def to_s
str = case @hour
when 0
"12 AM"
when 12
"12 PM"
when 13..23
"#{@hour - 12} PM"
else
"#{@hour} AM"
end
"%5s" % str
end
end
# ...
The easiest way to get a unique and comparable representation of an hour I could
think of was to use military time. That's exactly what the constructor does. I
parse the string representation of a time and store the military hour (0-23)
internally.
If you glance down, you'll see that to_s() is simply the reverse of this
process. I use it in printing results.
The other two methods are simple. The documentation for Range say that you can
use any object that supports <=>() and succ(), so that's what we have here. The
<=>() method just compares the military hours. succ() builds a new Hour object
then sets it to one hour ahead of the current object and returns the new Hour.
You can see that I'm using instance_eval() in both of these methods to read and
adjust the internal representation in other Hour objects. That felt more
correct than exposing the internal representation with an accessor and I think
it's great that Ruby lets me make this choice.
The other helper class I felt need for was something to represent a worker. I
wanted to be able to feed it the worker's requested schedule and then query it
as needed. Here's the code:
# ...
# An object for tracking a worker's availability and preferences.
class Worker
def initialize( name )
@name = name
@avail = Hash.new
@prefers = Hash.new
end
attr_reader :name
def can_work( day, times )
@avail[day] = parse_times(times)
@prefers[day] = if times =~ /\((?
refers )?([^)]+)\s*\)/parse_times($1)
else
Hour.new("12 AM")..Hour.new("11 PM")
end
end
def available?( day, hour )
if @avail[day].nil?
false
else
@avail[day].include?(hour)
end
end
def prefers?( day, hour )
return false unless available? day, hour
if @prefers[day].nil?
false
else
@prefers[day].include?(hour)
end
end
def ==( other )
@name == other.name
end
def to_s
@name.to_s
end
private
def parse_times( times )
case times
when /^\s*any\b/i
Hour.new("12 AM")..Hour.new("11 PM")
when /^\s*before (\d+ [AP]M)\b/i
Hour.new("12 AM")..Hour.new($1)
when /^\s*after (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new("11 PM")
when /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new($2)
when /^\s*not available\b/i
nil
else
raise "Unexpected availability format."
end
end
end
# ...
The constructor just makes note of the name for this Worker, then sets up two
Hash objects to hold availability and preferred schedule. The Hashes will use a
day of the week as a key and a Range of Hour objects as the value. An
availability of "any" can be represented as a Range of all the Hours in a day.
This is easy to work with, but it can't handle split-shift style availabilities.
You could fix this by making the values Arrays of Ranges.
The next three methods are all closely related. First, can_work() takes a day
String and a String representation of available times and uses those to set the
previously mentioned Hashes. The actual parsing is delegated to the private
parse_time() method, which just uses Regexps to break down the input. Once a
schedule has been loaded, you can check availability for a given day and hour
with available?(). The prefers?() method takes the same input but returns a
preference instead. A Worker must be available to work a given time to have a
preference about it.
Those are the only helper classes I built. The rest is application code:
# ...
if __FILE__ == $0
unless ARGV.size == 1 and File.exists?(ARGV.first)
puts "Usage: #{File.basename($0)} SCHEDULE_FILE"
exit
end
# load the data
data = File.open(ARGV.shift) { |file| YAML.load(file) }
# build worker list
workers = Array.new
data["Workers"].each do |name, avail|
worker = Worker.new(name)
avail.each { |day, times| worker.can_work(day, times) }
workers << worker
end
# ...
That's all pretty basic. Check and display usage, if needed; load the YAML
representation of workers and schedule hours to be filled; anf finally, build an
Array of Worker objects that are aware of their availability and preferences.
Here's the YAML file I'm using:
---
Schedule:
Wed: 9 AM to 6 PM
Sun: 9 AM to 10 PM
Thu: 9 AM to 8 PM
Mon: 9 AM to 6 PM
Tue: 9 AM to 6 PM
Sat: 9 AM to 10 PM
Fri: 9 AM to 6 PM
Workers:
James:
Wed: any
Sun: any (prefers before 5 PM)
Thu: 12 PM to 3 PM
Mon: before 3 PM (prefers before 12 PM)
Tue: any
Sat: not available
Fri: 12 PM to 3 PM
Brian:
Wed: not available
Sun: after 1 PM
Thu: any (prefers 8 AM to 5 PM)
Mon: any (prefers 8 AM to 5 PM)
Tue: any (prefers 8 AM to 5 PM)
Sat: any
Fri: any (prefers 8 AM to 5 PM)
The next step is to build a schedule. Here's where I deviated from my original
plan. I realized that if I limit myself to just worrying about availability at
first, I can build a correct schedule in those terms as I load it. Here's how
that turns out:
# ...
# create a legal schedule, respecting availability
schedule = Hash.new
data["Schedule"].each do |day, times|
schedule[day] = Array.new
if times =~ /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
start, finish = Hour.new($1), Hour.new($2)
else
raise "Unexpected schedule format."
end
(start..finish).each do |hour|
started_with = workers.first
loop do
if workers.first.available? day, hour
schedule[day] << [hour, workers.first]
break
else
workers << workers.shift
if workers.first == started_with
schedule[day] << [hour, "No workers available!"]
break
end
end
end
end
workers << workers.shift
end
# ...
A schedule is a Hash that stores day names paired with Arrays of Arrays. The
Arrays are a collection of Hour and Worker pairs, showing who is scheduled to
work at that time.
The second half of that code is what assembles the initial schedule. It just
walks every hour of every day assigning a worker. It starts with the first
worker in the list and keeps assigning them until them end of the day or until
the worker has a schedule conflict. Anytime either of those conditions happens,
the worker list is rotated and we try the next worker.
If we make it all the way through the list of workers without finding a person
who could work at that time, we just set the Worker slot to a warning message
and rely on the user to fix the problem. Blowing up with an exception here
seemed too drastic for what is likely a fairly common snag that I doubt software
is qualified to resolve.
The main issue with the above system is that it can assign people very long or
very short shifts. I think a good way to correct this would be to set minimum
and maximum shift lengths and adjust the software to honor them. Of course,
this will create more conflicts so you either have to accept that or make them
soft limitations.
Now, my code does make a second pass adjusting shifts, but now the focus turns
from availability to preference. Let's examine that:
# ...
# make schedule swaps for preferred times
schedule.each do |day, hours|
hours.each_with_index do |(hour, worker), index|
next unless worker.is_a?(Worker)
unless worker.prefers?(day, hour)
alternate = workers.find { |w| w.prefers?(day, hour) }
hours[index][-1] = alternate unless alternate.nil?
end
end
end
# ...
Here I'm just searching for people working hours they didn't prefer. When
found, I try to swap them out for someone who did prefer the time, if I can find
such a person. Otherwise, they have to stay.
Again, this can create some odd schedules. Mainly, people are traded on an
hourly basis and this can cause scheduling of one hour shifts. Again, I think
the answer is minimum shift lengths as I mentioned above, but in practice this
wasn't a chronic problem with availabilities like the ones in the YAML file.
When someone passed out of the times they preferred, it would generally cause
the rest of their shift to be replaced with someone that did want to work the
time.
All that remains is to print the schedule:
# ...
# print schedule
%w{Mon Tue Wed Thu Fri Sat Sun}.each do |day|
puts "#{day}:"
schedule[day].each do |hour, worker|
puts " #{hour}: #{worker}"
end
end
end
That's as easy as it looks. Walk the days, printing hours and who's working at
that time.
All-in-all it's an imperfect solution, but I think you could keep tuning it
until you get what you need. It works, but can certainly be made better.
Next week's Ruby Quiz is the number game that's been requested of me twice now,
so I really hope I'm not the only guy working that one...