First Ruby Program

(Gibbs Tanton - tgibbs) #1

I thought I would try my hand at a ruby program. I am a C++/perl programmer, 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 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.

Before I begin I would like to say that there were two things that bit me over and over again. The first was that !0 == false. This is just unintuitive to me as a C++/Perl programmer and was very frustrating. The second 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.

Ok, here is my solution.

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

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

# 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]

# 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 }
     @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)
   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
   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 )
   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 }
   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

#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
   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
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 ) )
  assert( !@worker3.assigned?( @ph1 ) )
end

end

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.
**************************************************************************

(James Edward Gray II) #2

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. :slight_smile:

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. :wink:

#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

···

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

(Gene Tani) #3

a couple disconnectd observes:

the best thing to smooth perl > ruby conversion is Hal Fulton's purple
"Ruby Way" book. There's a direct language comparison and a "gotcha
list"

some other resources:


http://www.glue.umd.edu/~billtj/ruby.html
http://rpa-base.rubyforge.org/wiki/wiki.cgi?GoodAPIDesign
http://www.rubygarden.org/ruby?RubyIdioms

(Gene Tani) #4

i think the best thing to smooth perl > ruby conversion is the chapter
in the back of Hal Fulton "Ruby Way" the compares 2 languages. Also,
around page 48, there's sort of a ruby gotcha list


http://www.glue.umd.edu/~billtj/ruby.html
http://rpa-base.rubyforge.org/wiki/wiki.cgi?GoodAPIDesign
http://www.rubygarden.org/ruby?RubyIdioms

(mathew) #5

Gibbs Tanton - tgibbs wrote:

Before I begin I would like to say that there were two things that
bit
me over and over again. The first was that !0 == false. This is just
unintuitive to me as a C++/Perl programmer and was very frustrating.

> The second was the need to clone to avoid references to the same object.

Once again, this was unintuitive to me.

I used to think the same. However, I eventually decided Ruby does the right thing. My logic is as follows:

- Perl sidesteps the issue (mostly) by using sigils, so that references vs values are always visibly different. Given that Ruby doesn't use sigils, let's consider the three options: everything's a reference, everything's a value, or 'it depends'.

- Option 1: Everything by value. This doesn't work, because it's very inefficient when passing objects as function arguments.

- Option 2: "It depends". Java does this. I find it incredibly irritating, because it means I have to remember which types are passed by value, and which are passed by reference, and code accordingly. The "it depends" style of behavior then ends up being extended to other parts of the language--for example, '+' dereferences its arguments if they're references to strings, but not if they're references to integers. If you take some code written to perform a calculation on ints, and use it to calculate the same thing for complex values, it may not work, or may overwrite your variables. "It depends" also makes polymorphism harder. So, I don't like that option.

- Hence by a process of elimination, the best option is Option 3: Everything by reference.

(Actually, there's one more option: don't have imperative variables. If you like that, try ML.)

**************************************************************************
The information contained in this communication is confidential, is
intended only for the use of the recipient named above, and may be legally
privileged.

Yeah, right.

mathew

···

--
<URL:http://www.pobox.com/~meta/>
          WE HAVE TACOS