From: James Edward Gray II <james@...>
Date: 2005-08-17T02:52:05+09:00
Subject: Re: [QUIZ] Scheduling (#42)

My solution produces output like the following:

Mon:
    9 AM:  Brian
   10 AM:  Brian
   11 AM:  Brian
   12 PM:  Brian
    1 PM:  Brian
    2 PM:  Brian
    3 PM:  Brian
    4 PM:  Brian
    5 PM:  Brian
    6 PM:  Brian
Tue:
    9 AM:  Brian
   10 AM:  Brian
   11 AM:  Brian
   12 PM:  Brian
    1 PM:  Brian
    2 PM:  Brian
    3 PM:  Brian
    4 PM:  Brian
    5 PM:  Brian
    6 PM:  James
...
Sun:
    9 AM:  James
   10 AM:  James
   11 AM:  James
   12 PM:  James
    1 PM:  James
    2 PM:  James
    3 PM:  James
    4 PM:  James
    5 PM:  James
    6 PM:  Brian
    7 PM:  Brian
    8 PM:  Brian
    9 PM:  Brian
   10 PM:  Brian

This is a legal schedule, with everyone having shifts only when they  
are available.  On top of that, it tries to correct for preferred  
schedules as much as possible.

That's probably a bit of a problem, because you get schedules like  
Tuesday above, with one hour shifts.  To correct this, you probably  
need to set something like a minimum shift length and assign only in  
terms of those.  Exploration of such possibilities is left as an  
exercise to the reader...  :)

Here's the code:

#!/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

# 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 =~ /\((?:prefers )?([^)]+)\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

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

     # 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

     # 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

     # 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

__END__

James Edward Gray II