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