From: Gibbs Tanton - tgibbs <Tanton.Gibbs@...>
Date: 2005-08-19T01:42:30+09:00
Subject: First Ruby Program

------_=_NextPart_001_01C5A413.D0D27634
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"

I thought I would try my hand at a ruby program.  I am a C++/perl programme=
r, but have really been impressed with ruby.  I picked the latest ruby quiz=
 (the scheduling problem).  It was challenging, but I have a solution.  I t=
hought I would share my solution in the hopes that people would comment on =
things like style and alternative ways to do things in a more ruby-ish fash=
ion.
=20
Before I begin I would like to say that there were two things that bit me o=
ver and over again.  The first was that !0 =3D=3D false.  This is just unin=
tuitive to me as a C++/Perl programmer and was very frustrating.  The secon=
d was the need to clone to avoid references to the same object.  Once again=
, this was unintuitive to me.  However, I don't see those hurdles as being =
too big.
=20
Ok, here is my solution.
=20
#First, I define a day class.  This class has only singleton objects for su=
nday through saturday.  It also defines an #order amongst days.
=20
class Day
   def initialize( name, idx )
     @name =3D name
     @idx =3D idx
   end
   def to_s
     @name
   end
   def to_i
     @idx
   end
   def <=3D>( other )
     return self.to_i <=3D> other.to_i
   end
   @@days =3D [ new("Sunday", 0), new( "Monday", 1),
                      new("Tuesday", 2), new("Wednesday", 3),
                      new("Thursday", 4), new("Friday", 5),
                      new("Saturday", 6) ]
   def self.sunday
     @@days[0]
   end
   def self.monday
     @@days[1]
   end
   def self.tuesday
     @@days[2]
   end
   def self.wednesday
     @@days[3]
   end
   def self.thursday
     @@days[4]
   end
   def self.friday
     @@days[5]
   end
   def self.saturday
     @@days[6]
   end
   private_class_method :new
   include Comparable
end
=20
# Next I define some useful constants
=20
WEEKDAYS =3D [Day.monday, Day.tuesday, Day.wednesday, Day.thursday, Day.fri=
day]
WEEKEND =3D [Day.sunday, Day.saturday]
MWF =3D [Day.monday, Day.wednesday, Day.friday]
TR =3D [Day.tuesday, Day.thursday]

# Now, I define a class to do work hours.  I use military time so I don't h=
ave to deal with AM/PM problems
class WorkHours
   include Comparable
   def initialize( days, start_time, stop_time )
     @days =3D days.sort { |a,b| a.to_i <=3D> b.to_i }
     @start_time =3D start_time
     @stop_time =3D stop_time
   end
   def include?( hour )
     hour.start_time >=3D @start_time and
     hour.stop_time <=3D @stop_time and
     (hour.days & @days).length =3D=3D hour.days.length
   end
   def to_s
     "[" + @days.map { |val| val.to_s }.join(',') + "]" +
     format_time(start_time) + "-" + format_time(stop_time)
   end
   def <=3D>( other )
      for arr in @days.zip(other.days)
         return -1 if !arr[0]
         return 1 if !arr[1]
         val =3D arr[0] <=3D> arr[1] ||
                 @start_time <=3D> other.start_time ||
                 @stop_time <=3D> other.stop_time
         return val unless val.zero?
      end
      return 0
   end
   attr_reader :days, :start_time, :stop_time
   private
   def format_time( time )
     hour =3D time / 100
     minutes =3D time % 100
     sprintf( "%0.2d", hour ) + ":" + sprintf( "%0.2d", minutes )
   end
end

#Now a class to represent the worker
INVALID_SCORE =3D -1000000
class Worker
   @@default_scores =3D { :preferred_scalar =3D> 3,
                                    :non_preferred_scalar =3D> 0,
                                    :exact_time_scalar =3D> 1,
                                    :am_pm_scalar =3D> 0,
                                    :time_change_scalar =3D> -1 }
   def initialize( preferred_hours, impossible_hours, scores =3D {} )
      @preferred_hours =3D preferred_hours
      @impossible_hours =3D impossible_hours
      @assigned =3D []
      @scores =3D @@default_scores.merge( scores )
   end
   def preferred?( hours )
      @preferred_hours.include?( hours )
   end
   def impossible?( hours )
      @impossible_hours.include?( hours )
   end
   def available?( hours )
      !impossible?( hours ) and !assigned?( hours )
   end
   def assign( hours )
      hours =3D [hours] unless hours.class =3D=3D Array
      for hour in hours
         raise "Already working!" unless available?( hour )
      end
      @assigned.concat( hours )
   end
   def assigned?( hours )
      !(@assigned.find { |obj| obj.include?( hours ) }).nil?
   end
   def clear_assigned_hours
      @assigned =3D []
   end
   def clone
      obj =3D Worker.new( @preferred_hours, @impossible_hours, @scores )
      obj.assigned =3D @assigned.clone
      obj
   end
   # a worker's happiness is dependent on whether he is working his preferr=
ed hours, or similar hours across all days, etc...   The scores are configu=
rable from the constructor
   def happiness
      preferred_hours =3D (@assigned.select { |obj| @preferred_hours.includ=
e?(obj) })
      total_count =3D @assigned.inject(0) { |memo, obj| memo + obj.days.len=
gth }
      preferred_count =3D preferred_hours.inject(0) { |memo, obj| memo + ob=
j=2Edays.length }
      preferred_score =3D preferred_count * @scores[:preferred_scalar]
      non_preferred_score =3D (total_count - preferred_count) * @scores[:no=
n_preferred_scalar]
      start_time_hash =3D Hash.new(0)
      @assigned.each do |obj|
          start_time_hash[obj.start_time] +=3D obj.days.length
      end
      exact =3D 0
      am_count =3D 0
      pm_count =3D 0
      start_time_hash.each_pair do | key, val |
         if( val > 1 )
            exact +=3D val
         else
            key < 1200 ? am_count +=3D val : pm_count +=3D val
         end
      end
      preferred_score + non_preferred_score +
         (exact * @scores[:exact_time_scalar]) +
         ((start_time_hash.length - 1) * @scores[:time_change_scalar]) +
         ((am_count + pm_count) * @scores[:am_pm_scalar])  =20
    end
    attr_reader :preferred_hours, :impossible_hours
    attr_accessor :assigned
    protected :assigned=3D
end

#Finally a manager class to schedule the workers
class Manager
   def initialize( workers )
      @workers =3D workers
   end
   # run through all legal scheduling permutations and remember the maximum=
 score...yes, this is inefficient!
   def schedule_helper( hours, debug =3D false )
      return [calc_happiness, all_assigned] if hours.length =3D=3D 0
      max_score =3D INVALID_SCORE
      max_assigned =3D nil
      for hour in hours
         for worker in @workers.find_all { |obj| obj.available?( hour ) }
            assign_hour_transaction(worker, hour) do
               (score,assigned) =3D schedule_helper(remove_hour(hours, hour=
), debug)
               (max_score, max_assigned) =3D [score, assigned] if score > m=
ax_score
            end
         end
      end
      [max_score, max_assigned]
   end
   def schedule( hours, debug =3D false )
      (score, assigned) =3D schedule_helper( hours, debug )
      if( score =3D=3D INVALID_SCORE )
         raise "Unable to schedule work hours."
      end
      @workers.zip( assigned ) do |worker, hours|
         worker.clear_assigned_hours
         worker.assign( hours )
      end
      true
   end
   def print_schedule
      idx =3D 0
      for w in @workers
         print "#{idx}:\n"
         print w.assigned.join("\n")
      end
   end
   attr_reader :workers
   private
   def calc_happiness
      return @workers.inject(0) { |memo, val| memo + val.happiness }
   end
   def all_assigned
      @workers.collect { |obj| obj.assigned.clone() }
   end
   def debug_print( ary )
      @workers.each_index do | idx |
         print "worker[#{idx}] is assigned\n"
         for hour in ary
            print "\t #{hour[0].to_s}\n"
         end
      end
   end
   def remove_hour( hours, hour )
      temp =3Dhours.clone
      temp.delete_at( temp.index(hour) )
      temp
   end
   def assign_hour_transaction( worker, hour )
      saved_assign =3D worker.assigned.clone
      worker.assign(hour)
      yield
      worker.clear_assigned_hours
      worker.assign(saved_assign)
   end
end
=20
# Here are some test cases
class TestManager < Test::Unit::TestCase
 def setup
  @ph1 =3D WorkHours.new( WEEKDAYS, 800, 1800 )
  @ih1 =3D WorkHours.new( WEEKEND, 0, 2399 )
  @nph1 =3D WorkHours.new( MWF, 200, 500 )
  @nph2 =3D WorkHours.new( TR, 200, 500 )
  @worker =3D Worker.new( @ph1, @ih1 )
  @worker2 =3D Worker.new( @ih1, @ph1 )
  @worker3 =3D Worker.new( [], [] )
  @manager =3D Manager.new( [@worker] )
  @manager2 =3D Manager.new( [@worker, @worker2] )
  @manager3 =3D Manager.new( [@worker3, @worker, @worker2] )
 end
 def testPreferredSchedule
  @manager.schedule( [@ph1] )
  assert( @worker.assigned?( @ph1 ) )
 end
 def testNoSchedule
  assert_raise(RuntimeError) { @manager.schedule( [@ih1] ) }
 end
 def testPreferredSchedule2
  @manager2.schedule( [@ph1,@ih1] )
  assert( @worker.assigned?( @ph1 ) )
  assert( @worker2.assigned?( @ih1 ) )
 end
 def testNonPreferredSchedule
  @manager2.schedule( [@nph1, @nph2] )
  assert( @worker.assigned?( @nph1 ) )
  assert( @worker.assigned?( @nph2 ) )
  assert( !@worker2.assigned?( @nph1 ) )
  assert( !@worker2.assigned?( @nph2 ) )
 end
 def testDoubleOccupancy
  @manager2.schedule( [@nph1, @nph1, @nph2, @nph2] )
  assert( @worker.assigned?( @nph1 ) )
  assert( @worker.assigned?( @nph2 ) )
  assert( @worker2.assigned?( @nph1 ) )
  assert( @worker2.assigned?( @nph2 ) )
 end
 def testPreferredAndNonPreferred
  @manager3.schedule( [@ph1,@nph2] )
  assert( @worker.assigned?( @ph1 ) )
  assert( @worker3.assigned?( @nph2 ) )
  assert( !@worker2.assigned <mailto:!@worker2.assigned> ?( @ph1 ) )
  assert( !@worker3.assigned?( @ph1 ) )
 end
=20
end
=20
Thanks for any comments you may make!
Tanton
**************************************************************************
The information contained in this communication is confidential, is
intended only for the use of the recipient named above, and may be legally
privileged.

If the reader of this message is not the intended recipient, you are
hereby notified that any dissemination, distribution or copying of this
communication is strictly prohibited.

If you have received this communication in error, please resend this
communication to the sender and delete the original message or any copy
of it from your computer system.

Thank You.
**************************************************************************

------_=_NextPart_001_01C5A413.D0D27634--