«

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Hans Fugal

You have a list of employees along with the hours they would _like_ to work, and
the hours they _cannot_ work. You have a list of hours that need to be worked.
(Extra credit for allowing for a different number of employees needed at
different hours.)

Write a scheduler that schedules employees without scheduling them on hours they
cannot work. It would be nice if the employees got as many of the hours they
wanted as possible. It would be nice if the employees didn't end up with split
shifts, had more or less consistent hours from day to day (e.g. Joe gets
scheduled in mornings), and so forth.

On 13/08/05, Ruby Quiz <> wrote:
> The three rules of Ruby Quiz:
>=20
> 1. Please do not post any solutions or spoiler discussion for this quiz =
until
> 48 hours have passed from the time on this message.
>=20
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>=20
> http://www.rubyquiz.com/
>=20
> 3. Enjoy!
>=20
> -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D
>=20
> by Hans Fugal
>=20
> You have a list of employees along with the hours they would _like_ to wo=
rk, and
> the hours they _cannot_ work. You have a list of hours that need to be wo=
rked.
> (Extra credit for allowing for a different number of employees needed at
> different hours.)
>=20
> Write a scheduler that schedules employees without scheduling them on hou=
rs they
> cannot work. It would be nice if the employees got as many of the hours t=
hey
> wanted as possible. It would be nice if the employees didn't end up with =
split
> shifts, had more or less consistent hours from day to day (e.g. Joe gets
> scheduled in mornings), and so forth.
>=20
>=20

How are theses hours given? Is it a one-time appointment, repeating
appointments on a weekly/monthly basis? Is there an example input so
we can test the programs against each other?

regards,

Brian


--=20
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

On Aug 13, 2005, at 3:08 AM, Brian Schr=F6der wrote:

> How are theses hours given? Is it a one-time appointment, repeating
> appointments on a weekly/monthly basis? Is there an example input so
> we can test the programs against each other?

Here's one possible idea. What do you think?

James Edward Gray II

---
Schedule:
Wed: 9 AM to 6 PM
Sun: 9 AM to 10 PM
Thu: 9 AM to 8 PM
Mon: 9 AM to 6 PM
Tue: 9 AM to 6 PM
Sat: 9 AM to 10 PM
Fri: 9 AM to 6 PM
Workers:
James:
Wed: any
Sun: any (prefers before 5 PM)
Thu: 12 PM to 3 PM
Mon: before 3 PM (prefers before 12 PM)
Tue: any
Sat: not available
Fri: 12 PM to 3 PM
Brian:
Wed: not available
Sun: after 1 PM
Thu: any (prefers 8 AM to 5 PM)
Mon: any (prefers 8 AM to 5 PM)
Tue: any (prefers 8 AM to 5 PM)
Sat: any
Fri: any (prefers 8 AM to 5 PM)

On 13/08/05, James Edward Gray II <> wrote:
> On Aug 13, 2005, at 3:08 AM, Brian Schr=F6der wrote:
>=20
> > How are theses hours given? Is it a one-time appointment, repeating
> > appointments on a weekly/monthly basis? Is there an example input so
> > we can test the programs against each other?
>=20
> Here's one possible idea. What do you think?
>=20
> James Edward Gray II
>=20
> ---
> Schedule:
> Wed: 9 AM to 6 PM
> Sun: 9 AM to 10 PM
> Thu: 9 AM to 8 PM
> Mon: 9 AM to 6 PM
> Tue: 9 AM to 6 PM
> Sat: 9 AM to 10 PM
> Fri: 9 AM to 6 PM
> Workers:
> James:
> Wed: any
> Sun: any (prefers before 5 PM)
> Thu: 12 PM to 3 PM
> Mon: before 3 PM (prefers before 12 PM)
> Tue: any
> Sat: not available
> Fri: 12 PM to 3 PM
> Brian:
> Wed: not available
> Sun: after 1 PM
> Thu: any (prefers 8 AM to 5 PM)
> Mon: any (prefers 8 AM to 5 PM)
> Tue: any (prefers 8 AM to 5 PM)
> Sat: any
> Fri: any (prefers 8 AM to 5 PM)

Interesting to parse. May I assume then, that there are only timeslots
of full hours?

regards,

Brian

--=20
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

On Aug 13, 2005, at 3:01 PM, Brian Schr=F6der wrote:

> Interesting to parse.

If you've got an easier format in mind, toss it up here. I'm not picky.

> May I assume then, that there are only timeslots of full hours?

I assumed that from reading of quiz. It's probably an over =20
simplistic assumption, but I think it will do for this challenge.

James Edward Gray II

P.S. Hans, feel free to jump in here and save me at any time...

>> May I assume then, that there are only timeslots of full hours?
>
> I assumed that from reading of quiz. It's probably an over
> simplistic assumption, but I think it will do for this challenge.
> P.S. Hans, feel free to jump in here and save me at any time...

Isn't the problem in general NP hard? Meaning you have to make some
simplifications to keep the input small, or apply some other
restrictions to get the problem to P.

Of course, it is also possible to generate input for which there is no
solution. Then what? When to loosen bonus targets like regular times for
a person and when to give up?

I think everybody has to figure this out for him/herself.
Moreover, do not restrict the application to people and time, it can be
anything and time (or even boxes and space if you can restrict the space
to 1D meaningfully

I can't suppress the feeling that the quiz is meant to pick a "nice"
solution when there's plenty of solutions available. For which you need
(a lot of) example input...

+--- Kero ------------------------- kero@chello@nl ---+
| all the meaningless and empty words I spoke |
| Promises -- The Cranberries |
+--- M38c --- http://members.chello.nl/k.vangelder ---+

My solution produces output like the following:

Mon:
9 AM: Brian
10 AM: Brian
11 AM: Brian
12 PM: Brian
1 PM: Brian
2 PM: Brian
3 PM: Brian
4 PM: Brian
5 PM: Brian
6 PM: Brian
Tue:
9 AM: Brian
10 AM: Brian
11 AM: Brian
12 PM: Brian
1 PM: Brian
2 PM: Brian
3 PM: Brian
4 PM: Brian
5 PM: Brian
6 PM: James
...
Sun:
9 AM: James
10 AM: James
11 AM: James
12 PM: James
1 PM: James
2 PM: James
3 PM: James
4 PM: James
5 PM: James
6 PM: Brian
7 PM: Brian
8 PM: Brian
9 PM: Brian
10 PM: Brian

This is a legal schedule, with everyone having shifts only when they
are available. On top of that, it tries to correct for preferred
schedules as much as possible.

That's probably a bit of a problem, because you get schedules like
Tuesday above, with one hour shifts. To correct this, you probably
need to set something like a minimum shift length and assign only in
terms of those. Exploration of such possibilities is left as an
exercise to the reader...

Here's the code:

#!/usr/local/bin/ruby -w

require "yaml"

# A representation of a single hour. Usable in Ranges.
class Hour
def initialize( text )
@hour = case text
when "12 AM"
0
when "12 PM"
12
when /(\d+) PM/
$1.to_i + 12
else
text[/\d+/].to_i
end
end

include Comparable

def <=>( other )
@hour <=> other.instance_eval { @hour }
end

def succ
next_hour = Hour.new("12 AM")

next_time = (@hour + 1) % 24
next_hour.instance_eval { @hour = next_time }

next_hour
end

def to_s
str = case @hour
when 0
"12 AM"
when 12
"12 PM"
when 13..23
"#{@hour - 12} PM"
else
"#{@hour} AM"
end
"%5s" % str
end
end

# An object for tracking a worker's availability and preferences.
class Worker
def initialize( name )
@name = name

@avail = Hash.new
@prefers = Hash.new
end

attr_reader :name

def can_work( day, times )
@avail[day] = parse_times(times)

@prefers[day] = if times =~ /\((?refers )?([^)]+)\s*\)/
parse_times($1)
else
Hour.new("12 AM")..Hour.new("11 PM")
end
end

def available?( day, hour )
if @avail[day].nil?
false
else
@avail[day].include?(hour)
end
end

def prefers?( day, hour )
return false unless available? day, hour

if @prefers[day].nil?
false
else
@prefers[day].include?(hour)
end
end

def ==( other )
@name == other.name
end

def to_s
@name.to_s
end

private

def parse_times( times )
case times
when /^\s*any\b/i
Hour.new("12 AM")..Hour.new("11 PM")
when /^\s*before (\d+ [AP]M)\b/i
Hour.new("12 AM")..Hour.new($1)
when /^\s*after (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new("11 PM")
when /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new($2)
when /^\s*not available\b/i
nil
else
raise "Unexpected availability format."
end
end
end

if __FILE__ == $0
unless ARGV.size == 1 and File.exists?(ARGV.first)
puts "Usage: #{File.basename($0)} SCHEDULE_FILE"
exit
end

# load the data
data = File.open(ARGV.shift) { |file| YAML.load(file) }

# build worker list
workers = Array.new
data["Workers"].each do |name, avail|
worker = Worker.new(name)
avail.each { |day, times| worker.can_work(day, times) }
workers << worker
end

# create a legal schedule, respecting availability
schedule = Hash.new
data["Schedule"].each do |day, times|
schedule[day] = Array.new
if times =~ /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
start, finish = Hour.new($1), Hour.new($2)
else
raise "Unexpected schedule format."
end

(start..finish).each do |hour|
started_with = workers.first
loop do
if workers.first.available? day, hour
schedule[day] << [hour, workers.first]
break
else
workers << workers.shift
if workers.first == started_with
schedule[day] << [hour, "No workers
available!"]
break
end
end
end
end
workers << workers.shift
end

# make schedule swaps for preferred times
schedule.each do |day, hours|
hours.each_with_index do |(hour, worker), index|
next unless worker.is_a?(Worker)
unless worker.prefers?(day, hour)
alternate = workers.find { |w| w.prefers?(day, hour) }
hours[index][-1] = alternate unless alternate.nil?
end
end
end

# print schedule
%w{Mon Tue Wed Thu Fri Sat Sun}.each do |day|
puts "#{day}:"
schedule[day].each do |hour, worker|
puts " #{hour}: #{worker}"
end
end
end

__END__

James Edward Gray II

Kero wrote:
> >> May I assume then, that there are only timeslots of full hours?
> >
> > I assumed that from reading of quiz. It's probably an over
> > simplistic assumption, but I think it will do for this challenge.
> > P.S. Hans, feel free to jump in here and save me at any time...
>
> Isn't the problem in general NP hard? Meaning you have to make some
> simplifications to keep the input small, or apply some other
> restrictions to get the problem to P.

Well I'll take your word for it on the NP thing because I don't have
the brain cycles to spare at the moment. It is definitely not
trivial.

> Of course, it is also possible to generate input for which there is no
> solution. Then what? When to loosen bonus targets like regular times for
> a person and when to give up?

See below...

> I think everybody has to figure this out for him/herself.

I'm not clear what you mean by that. I think you might mean every
McDonalds manager has to figure this out him/herself. That's the
interesting thing here - lots and lots of people do this every single
day.

> Moreover, do not restrict the application to people and time, it can be
> anything and time (or even boxes and space if you can restrict the space
> to 1D meaningfully

Yes, it is essentially the knapsack problem with time dependence added.

> I can't suppress the feeling that the quiz is meant to pick a "nice"
> solution when there's plenty of solutions available. For which you need
> (a lot of) example input...

Yes and no. I alluded to the fact that people have minimal difficulty
doing this (although as you can imagine it is a common sore spot
between employees and employers) so that seems to suggest that one
approach would be an AI approach. We are looking for one of many
solutions. Ideally we find the optimal solution, but we're happy to
find a "good" solution. Your response has piqued my interest (I
unfortunately don't often find time to do these quizzes, even when I'm
the one who comes up with the idea. . Here's how I plan to do it:

We want to search the solution space for good answers. First we need to
represent things, and my first idea here is a sequence of (day, hour,
person) tuples, where day is a weekday name, hour is something like
1300, and person is the name of a person. The sequence for a whole week
(with a 12-hour business day) is 72 tuples long, not too bad.

Next we need to have a way to know if an answer is good, and how good
the answer is. This is called a utility function in AI. Normally you
award points for things you like and demerit points for things you
don't like. Finding a good utility function is the artistic and most
important part of a search like this.

Now we can represent whole and partial solutions and measure their
utility. Now all we have to do is search. I'm guessing an A* search
will do the trick nicely (it usually does). If not A* then one of its
variants, probably. Or maybe greedy will do the job sufficiently well
for most purposes. All that remains is to choose a good heuristic, this
is the other artistic and important part of the algorithm.

Assuming we can find a reasonable heuristic and utility function, the
computer should be able to find us good solutions. If we can find
sufficiently good heuristic and utility functions, we can say the
solution is optimal - whatever that means. (In other words, if we knew
what optimal was in the real world for this problem, and we could
represent it with utility/heuristic functions, we could find an optimal
solution).

I hope to find the time to code this up, for the proof is in the
pudding. The only real question in my (perhaps over-confident) mind is,
will it fit in memory and time constraints? When you have a problem
where valid solutions abound and you're looking for a "good" solution,
the answer is usually that you can find better and better solutions
given enough time and memory, and hopefully you can find something good
enough given realistic time and memory.

Hans