On Aug 18, 2005, at 11:42 AM, Gibbs Tanton - tgibbs wrote:

> I thought I would try my hand at a ruby program.  I am a C++/perl  
> programmer, but have really been impressed with ruby.

Welcome!

> I picked the latest ruby quiz (the scheduling problem).

Glad to hear somebody got some use out of that one.  :)

> I thought 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 fashion.

First, some my general comment about the code, then I'll try to show  
what I mean.  Dave Thomas says in one of his Ruby books (talking  
about some example code), "...and it's even less code, which is how  
you know it's right."  On the whole, that's what jumps out at me from  
this solution.

My advice:  Write less code.  ;)

> #First, I define a day class.  This class has only singleton  
> objects for sunday through saturday.  It also defines an #order  
> amongst days.

I'll try to alter this one class to see if I can't put you on the  
right track...

> class Day
>    def initialize( name, idx )
>      @name = name
>      @idx = idx
>    end
>    def to_s
>      @name
>    end
>    def to_i
>      @idx
>    end
>    def <=>( other )
>      return self.to_i <=> other.to_i
>    end
>    @@days = [ 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

Here's my version that does the same thing:

class Day
    @@days = %w{Sunday Monday Tuesday Wednesday Thursday Friday  
Saturday}
    @@days.each do |day|
       class_eval "def self.#{day.downcase}; new('#{day}'); end"
    end

    def initialize( name )
      @name = name
    end
    private_class_method :new

    def to_s
      @name
    end
    def to_i
      @@days.index(@name)
    end

    def <=>( other )
      return self.to_i <=> other.to_i
    end
    include Comparable
end

Below I'll just make some general comments...

> # Next I define some useful constants
>
> WEEKDAYS = [Day.monday, Day.tuesday, Day.wednesday, Day.thursday,  
> Day.friday]
> WEEKEND = [Day.sunday, Day.saturday]
> MWF = [Day.monday, Day.wednesday, Day.friday]
> TR = [Day.tuesday, Day.thursday]

Do these make more sense inside the Day class?

> # Now, I define a class to do work hours.  I use military time so I  
> don't have to deal with AM/PM problems
> class WorkHours
>    include Comparable
>    def initialize( days, start_time, stop_time )
>      @days = days.sort { |a,b| a.to_i <=> b.to_i }

@days = days.sort_by { |d| d.to_i }

>      @start_time = start_time
>      @stop_time = stop_time
>    end
>    def include?( hour )
>      hour.start_time >= @start_time and
>      hour.stop_time <= @stop_time and
>      (hour.days & @days).length == hour.days.length
>    end
>    def to_s
>      "[" + @days.map { |val| val.to_s }.join(',') + "]" +
>      format_time(start_time) + "-" + format_time(stop_time)

In Ruby, prefer interpolation to concatenation:

"[#{@days.join(',')}]#{format_time(start_time)}-#{format_time 
(stop_time)}"

>    end
>    def <=>( other )
>       for arr in @days.zip(other.days)
>          return -1 if !arr[0]
>          return 1 if !arr[1]
>          val = arr[0] <=> arr[1] ||
>                  @start_time <=> other.start_time ||
>                  @stop_time <=> other.stop_time
>          return val unless val.zero?
>       end
>       return 0
>    end

This method is bugging me.  <laughs>  Ruby should be pretty.  I can't  
even tell what it's doing.  <=>() return -1, 0, or 1, so a trailing  
|| has now meaning.  (They're all true.)

What are we trying to do here compare start_time, stop_time, and  
days?  How about this:

def <=>( other )
     [@start_time, @stop_time, @days] <=> [other.start_time,  
other.stop_time, other.days]
end

>    attr_reader :days, :start_time, :stop_time
>    private
>    def format_time( time )
>      hour = time / 100
>      minutes = time % 100
>      sprintf( "%0.2d", hour ) + ":" + sprintf( "%0.2d", minutes )

sprintf("%0.2d:%0.2d", hour, minutes)

>    end
> end
>
> #Now a class to represent the worker
> INVALID_SCORE = -1000000
> class Worker
>    @@default_scores = { :preferred_scalar => 3,
>                                     :non_preferred_scalar => 0,
>                                     :exact_time_scalar => 1,
>                                     :am_pm_scalar => 0,
>                                     :time_change_scalar => -1 }
>

It's not immediately obvious to me what the above values stand for.

>    def initialize( preferred_hours, impossible_hours, scores = {} )
>       @preferred_hours = preferred_hours
>       @impossible_hours = impossible_hours
>       @assigned = []
>       @scores = @@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 = [hours] unless hours.class == 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 = []
>    end
>    def clone
>       obj = Worker.new( @preferred_hours, @impossible_hours, @scores )
>       obj.assigned = @assigned.clone
>       obj
>    end
>    # a worker's happiness is dependent on whether he is working his  
> preferred hours, or similar hours across all days, etc...   The  
> scores are configurable from the constructor
>    def happiness
>       preferred_hours = (@assigned.select { |obj|  
> @preferred_hours.include?(obj) })
>       total_count = @assigned.inject(0) { |memo, obj| memo +  
> obj.days.length }
>       preferred_count = preferred_hours.inject(0) { |memo, obj|  
> memo + obj.days.length }
>       preferred_score = preferred_count * @scores[:preferred_scalar]
>       non_preferred_score = (total_count - preferred_count) *  
> @scores[:non_preferred_scalar]
>       start_time_hash = Hash.new(0)
>       @assigned.each do |obj|
>           start_time_hash[obj.start_time] += obj.days.length
>       end
>       exact = 0
>       am_count = 0
>       pm_count = 0
>       start_time_hash.each_pair do | key, val |
>          if( val > 1 )
>             exact += val
>          else
>             key < 1200 ? am_count += val : pm_count += 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])
>     end
>     attr_reader :preferred_hours, :impossible_hours
>     attr_accessor :assigned
>     protected :assigned=
> end

That methods is too long!  <laughs>  Try breaking it up into small  
concise chunks.  I should be able to tell what's going on at a glance.

> #Finally a manager class to schedule the workers
> class Manager
>    def initialize( workers )
>       @workers = workers
>    end
>    # run through all legal scheduling permutations and remember the  
> maximum score...yes, this is inefficient!
>    def schedule_helper( hours, debug = false )
>       return [calc_happiness, all_assigned] if hours.length == 0
>       max_score = INVALID_SCORE
>       max_assigned = nil
>       for hour in hours
>          for worker in @workers.find_all { |obj| obj.available? 
> ( hour ) }
>             assign_hour_transaction(worker, hour) do
>                (score,assigned) = schedule_helper(remove_hour 
> (hours, hour), debug)
>                (max_score, max_assigned) = [score, assigned] if  
> score > max_score
>             end
>          end
>       end
>       [max_score, max_assigned]
>    end
>    def schedule( hours, debug = false )
>       (score, assigned) = schedule_helper( hours, debug )
>       if( score == 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 = 0
>       for w in @workers
>          print "#{idx}:\n"
>          print w.assigned.join("\n")
>       end
>    end

Are those indexes suppose to be going up?

@workers.each_with_index |w, idx|
     puts "#{idx}:"
     puts w.assigned.join("\n")
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 =hours.clone
>       temp.delete_at( temp.index(hour) )
>       temp
>    end
>    def assign_hour_transaction( worker, hour )
>       saved_assign = worker.assigned.clone
>       worker.assign(hour)
>       yield
>       worker.clear_assigned_hours
>       worker.assign(saved_assign)
>    end

Somethings not right in the above method.  Too much busy work.   
That's the sign of a problem.  I would look for a way to attack these  
operations non-destructively so you can do away with the clone-and- 
remove dance.

> end
>
> # Here are some test cases
> class TestManager < Test::Unit::TestCase
>  def setup
>   @ph1 = WorkHours.new( WEEKDAYS, 800, 1800 )
>   @ih1 = WorkHours.new( WEEKEND, 0, 2399 )
>   @nph1 = WorkHours.new( MWF, 200, 500 )
>   @nph2 = WorkHours.new( TR, 200, 500 )
>   @worker = Worker.new( @ph1, @ih1 )
>   @worker2 = Worker.new( @ih1, @ph1 )
>   @worker3 = Worker.new( [], [] )
>   @manager = Manager.new( [@worker] )
>   @manager2 = Manager.new( [@worker, @worker2] )
>   @manager3 = 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 ) )

Syntax Error.

>   assert( !@worker3.assigned?( @ph1 ) )
>  end
>
> end

Hopefully that gives you some ideas for refinement.

Again, welcome to Ruby!

James Edward Gray II