First Ruby Program

  • Thread starter Gibbs Tanton - tgibbs
  • Start date

G

Gibbs Tanton - tgibbs

------_=_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( [email protected]?( @nph1 ) )
assert( [email protected]?( @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( [email protected] <mailto:[email protected]> ?( @ph1 ) )
assert( [email protected]?( @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--
 
Ad

Advertisements

J

James Edward Gray II

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

#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( [email protected]?( @nph1 ) )
assert( [email protected]?( @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( [email protected] <mailto:[email protected]> ?( @ph1 ) )

Syntax Error.
assert( [email protected]?( @ph1 ) )
end

end

Hopefully that gives you some ideas for refinement.

Again, welcome to Ruby!

James Edward Gray II
 
Ad

Advertisements


Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top