Asp Forum - [QUIZ] VCR Program Manager (#101

James Gray

11/10/2006 3:01:00 PM

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

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

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

by FranÃ§ois Beausoleil

The goal of this Ruby Quiz is to make a Video Cassette Recorder program manager.
The user is responsible for saying what times to record, and then the VCR will
query the program manager regularly to determine if it should be recording, and
if so, on which channel.

The interesting bit in this quiz is the conflict resolution.

Normally, users specify recording schedules such as this:

Monday to Friday, 3 PM to 4 PM, channel 8

Specific programs might overlap. Assuming the above program is active, if the
user added this program:

Wednesday Nov 8, 3:30 PM to 5 PM, channel 12

We should record from 3 to 3:30 channel 8, then switch to channel 12, and record
until 5 PM.

Another variation might be:

Thursday Nov 9, 3:30 PM to 4:30 PM, channel 8

In this case, the channel didn't change, so we should just keep on recording.

Interesting, optional features: fuzzy time (start a bit before and end a bit
after the specific times, to catch shows starting early / ending late) and
taking care of DST.

Your program manager must implement the following interface:

# Query to determine if we should be recording at any particular
# moment. It can be assumed that the VCR will query the program
# manager at most twice per minute, and with always increasing minutes.
# New programs may be added between two calls to #record?.
#
# This method must return either a +nil+, indicating to stop recording,
# or don't start, or an +Integer+, which is the channel number we should
# be recording.
def record?(time); end

# Adds a new Program to the list of programs to record.
def add(program_details); end

Your task is to provide an implementation for the ProgramManager.

You can see the unit tests I used at:

http://www.rub...program_manager_test.rb

12 Answers

Kurt Hindenburg

11/12/2006 12:01:00 AM

On 11/10/06, Ruby Quiz <james@grayproductions.net> wrote:
> You can see the unit tests I used at:
>
> http://www.rubyquiz.com/program_manag...
>
>
Hello,
Is this test suite exhaustive? I'm rather surprised my first
attempt passed all the tests.

23 tests, 736 assertions, 0 failures, 0 errors

Regards,
Kurt

James Gray

11/12/2006 5:09:00 PM

On Nov 11, 2006, at 6:01 PM, Kurt Hindenburg wrote:

> On 11/10/06, Ruby Quiz <james@grayproductions.net> wrote:
>> You can see the unit tests I used at:
>>
>> http://www.rubyquiz.com/program_manag...
>>
>>
> Hello,
> Is this test suite exhaustive? I'm rather surprised my first
> attempt passed all the tests.
>
> 23 tests, 736 assertions, 0 failures, 0 errors

If you feel something is missing, feel free to add it.

James Edward Gray II

Dema

11/12/2006 9:17:00 PM

Here is my solution (I extracted the Numeric extensions into a separate
core_ext.rb along with an extension to Time):

The key thing in the conflict resolution was partitioning the weekly
from the specific candidate programs and picking the most recent
addition.

Cheers.

# BEGIN -- program_manager.rb --

require 'core_ext'
require 'program'

class ProgramManager

def initialize
@programs = []
end

# Query to determine if we should be recording at any particular
# moment. It can be assumed that the VCR will query the program
# manager at most twice per minute, and with always increasing
minutes.
# New programs may be added between two calls to #record?.
#
# This method must return either a +nil+, indicating to stop
recording,
# or don't start, or an +Integer+, which is the channel number we
should
# be recording.
def record?(time)
candidates = @programs.select { |p| p.on?(time) }
weekly, specific = candidates.partition { |p| p.weekly? }
return specific.last.channel unless specific.empty?
return weekly.last.channel unless weekly.empty?
nil
end

# Adds a new Program to the list of programs to record.
def add(program)
@programs << Program.new(program)
end

end

# END -- program_manager.rb --

# BEGIN -- program.rb --

require 'core_ext'

class Program

WEEKDAYS = { 'sun' => 0, 'mon' => 1, 'tue' => 2, 'wed' => 3,
'thu' => 4, 'fri' => 5, 'sat' => 6 }

attr_reader :start, :end, :channel, :days

def initialize(program)
@start = program[:start]
@end = program[:end]
@channel = program[:channel]
@days = program[:days]

raise "Missing start or end" if @start.nil? || @end.nil?
raise "Wrong start or end types" unless (@start.is_a?(Time) &&
@end.is_a?(Time)) ||
(@start.is_a?(Integer) &&
@end.is_a?(Integer))
raise "Invalid program" if weekly? && (@start.is_a?(Time) ||
@end.is_a?(Time))
raise "End must come after Start" if !weekly? && @start > @end
raise "Missing channel" if !@channel.is_a?(Integer)
raise "Invalid weekday" if @days.is_a?(Array) && @days.any? { |day|
WEEKDAYS[day] == nil }
end

def weekly?
!@days.nil?
end

def on?(time)
if weekly? #weekly program
for day in @days
if WEEKDAYS[day] == time.wday
return @channel if time.secs >= @start && time.secs <= @end
end
end
else #specific time
return @channel if time >= @start && time <= @end
end
nil
end

end

# END -- program.rb --

# BEGIN -- core_ext.rb --

class Numeric
# Number of seconds since midnight
def hours
(self * 60).minutes
end

def minutes
self * 60
end

def seconds
self
end

alias_method :hour, :hours
alias_method :minute, :minutes
alias_method :second, :seconds
end

class Time
def secs
self.hour * 3600 + self.min * 60 + self.sec
end
end

# END -- core_ext.rb --

Peter Severin

11/13/2006 8:41:00 AM

Hi,

You can find my solution below. The main trick is the order of programs
maintained by ProgramManager. The programs array contains specific
programs at the beginning (in the reversed order so that a program
added last is placed first), and then repeating programs in order of
their addition.

# program_manager.rb

class Time
def seconds
(hour * 60 + min) * 60 + sec
end
end

class Program
attr_reader :channel

def initialize(program_details)
@program_start = program_details[:start]
@program_end = program_details[:end]
@channel = program_details[:channel]
end
end

class SpecificProgram < Program
def record?(time)
time.between?(@program_start, @program_end)
end
end

class RepeatingProgram < Program
WEEKDAYS = %w(mon tue wed thu fri sat sun)

def initialize(program_details)
super
@days = program_details[:days].map {|day| WEEKDAYS.index(day) + 1}
end

def record?(time)
@days.include?(time.wday) && time.seconds.between?(@program_start,
@program_end)
end
end

class ProgramManager
def initialize()
@programs = []
end

def add(program_details)
case program_details[:start]
when Numeric
@programs << RepeatingProgram.new(program_details)
when Time
@programs[0, 0] = SpecificProgram.new(program_details)
end

self
end

def record?(time)
program = @programs.find {|program| program.record?(time)}
program ? program.channel : nil
end
end

Dale Martenson

11/13/2006 5:43:00 PM

Here is another similar solution. It may not be as efficient as others.
--Dale Martenson

class Program
attr_accessor :start_time, :end_time, :channel, :days

def initialize( program_details )
@start_time = program_details[:start]
@end_time = program_details[:end]
@channel = program_details[:channel]
@days = program_details[:days]
end
end

class ProgramManager
def initialize
@programs = []
end

def record?(time)
@programs.reverse.each do |p|
if p.days.nil?
# specific program
if (p.start_time..p.end_time).include?(time)
return p.channel
end
else
# repeating program
weekday = %w( sun mon tue wed thu fri sat )[time.wday]
time_of_day = (time.hour * 3600) + (time.min * 60) + time.sec
if p.days.include?(weekday) &&
(p.start_time..p.end_time).include?(time_of_day)
return p.channel
end
end
end

return nil
end

def add(program_details)
@programs << Program.new( program_details )
end
end

--
Posted via http://www.ruby-....

Francois Beausoleil

11/13/2006 6:42:00 PM

Hi all,

I don't know what the ethics are about writing a solution for your own
quiz, but here is the solution I came up with while building the unit
tests.

My solution put most of the code in Program. Program is responsible
for determining if a given Time is part of itself. Then, in
ProgramManager, I find all candidate programs, and select the one with
the best specificity, in reverse order of adding.

class ProgramManager
def initialize
@programs = Array.new
end

def add(program)
@programs << program
end

def record?(time)
candidates = @programs.select {|program| program.include?(time)}
return nil if candidates.empty?
return candidates.first.channel if candidates.size == 1
candidates.sort_by {|candidate| candidate.specificity}.last.channel
end
end

class Program
WEEKDAY_NAMES = %w(sun mon tue wed thu fri sat).freeze

attr_reader :options

def initialize(options)
@options = options.dup
end

def include?(time)
if options[:start].respond_to?(:strftime) then
(options[:start] .. options[:end]).include?(time)
else
return false unless self.time?(time)
return false unless self.day?(time)
true
end
end

def channel
options[:channel]
end

def specificity
return 2 if options[:start].respond_to?(:strftime)
1
end

protected
def time?(time)
start = time - time.at_midnight
(options[:start] .. options[:end]).include?(start)
end

def day?(time)
options[:days].include?(WEEKDAY_NAMES[time.wday])
end
end

Jamie Macey

11/13/2006 11:56:00 PM

On 11/10/06, Ruby Quiz <james@grayproductions.net> wrote:
> Your task is to provide an implementation for the ProgramManager.
>
> You can see the unit tests I used at:
> http://www.rubyquiz.com/program_manag...

I started from the first test class here, and progressively re-enabled
the test cases to make them pass as I went along. This class passes
all tests.

Rule of the day was the simplest thing that could possibly work. As
such, I didn't feel the need to split the logic out into a separate
Program class, but I kept two arrays of prospective programs - one for
recurring and one for one-shot.

- Jamie

class ProgramManager
DAYS = %w(sun mon tue wed thu fri sat)

def initialize
@recurring = Hash.new{|h,k| h[k] = []}
@concrete = []
end

def add(o)
case o[:start]
when Fixnum:
o[:days].each do |day|
@recurring[DAYS.index(day)] << [o[:start]..o[:end], o[:channel]]
end
when Time:
@concrete.unshift [o[:start]..o[:end], o[:channel]]
end
end

def record?(time)
@concrete.each do |times, channel|
return channel if times.include? time
end

time_s = (time.hour*60 + time.min)*60 + time.sec
@recurring.each do |day, programs|
next unless day == time.wday
programs.each do |times, channel|
return channel if times.include? time_s
end
end
nil
end
end

James Gray

11/15/2006 2:55:00 PM

On Nov 13, 2006, at 5:56 PM, Jamie Macey wrote:

> Rule of the day was the simplest thing that could possibly work. As
> such, I didn't feel the need to split the logic out into a separate
> Program class, but I kept two arrays of prospective programs - one for
> recurring and one for one-shot.

When I was new from to Ruby, from Perl, I use to think those ad hoc
data structures were "the simplest thing" too. With a fair amount of
Ruby experience now, I'm not so sure though.

For example, have a look at Dale Martenson's solution, which is very
close to your own in size. Dale used a Program class.

In fact, Program could be as simple as:

Program = Struct.new(:start_time, :end_time, :channel, :days)

Then add could be:

class ProgramManager
def add(program_details)
@programs << Program.new(
*program_details.values_at(:start, :end, :channel, :days)
)
end
end

I'm not saying anything about your solution here. Just thinking out
loud in hopes of inspiring discussion... ;)

James Edward Gray II

Jamie Macey

11/15/2006 6:35:00 PM

On 11/15/06, James Edward Gray II <james@grayproductions.net> wrote:
> On Nov 13, 2006, at 5:56 PM, Jamie Macey wrote:
>
> > Rule of the day was the simplest thing that could possibly work. As
> > such, I didn't feel the need to split the logic out into a separate
> > Program class, but I kept two arrays of prospective programs - one for
> > recurring and one for one-shot.
>
> When I was new from to Ruby, from Perl, I use to think those ad hoc
> data structures were "the simplest thing" too. With a fair amount of
> Ruby experience now, I'm not so sure though.
>
> For example, have a look at Dale Martenson's solution, which is very
> close to your own in size. Dale used a Program class.
>
> In fact, Program could be as simple as:
>
> Program = Struct.new(:start_time, :end_time, :channel, :days)

I think that there's a trade-off here. If you have a stupid (no
internal logic) Program class, you can trade a very simple add method
for a more complicated record? method.

My position on it is that if I'm going to be leaving the brunt of the
logic in the ProgramManager, I don't think there's a huge difference
between nested arrays, a struct, or a class being the holder of the
data.

That being said, on a lark I did a bit of refactoring and tried to
move as much logic out of the ProgramManager into an actual Program
class - the results are below.

I definitely prefer the second version. It's got 10 more lines of
actual code, but there's less random logic strewn about (and the logic
is simpler). There's a definite separation of responsibilities -
Program just does querying, ProgramManager handles priorities.

> I'm not saying anything about your solution here. Just thinking out
> loud in hopes of inspiring discussion... ;)

Discussion is always good - and this time it caused a better solution
to the problem to spring into being :)

- Jamie

class Program
DAYS = %w(sun mon tue wed thu fri sat)
attr_reader :channel

def initialize(settings)
@range = settings[:start]..settings[:end]
@channel = settings[:channel]
@days = settings[:days]
end

def recurring?
!@days.nil?
end

def include?(time)
if recurring?
return false unless @days.include? DAYS[time.wday]
time_s = (time.hour*60 + time.min)*60 + time.sec
@range.include? time_s
else
@range.include? time
end
end
end

class ProgramManager

def initialize
@programs = []
end

def add(settings)
program = Program.new(settings)
if program.recurring?
@programs << program # Recurring to end of list
else
@programs.unshift program # Non-recurring to front
end
end

def record?(time)
@programs.each do |program|
return program.channel if program.include? time
end
nil
end
end

James Gray

11/15/2006 8:37:00 PM

On Nov 15, 2006, at 12:35 PM, Jamie Macey wrote:

> On 11/15/06, James Edward Gray II <james@grayproductions.net> wrote:
>> In fact, Program could be as simple as:
>>
>> Program = Struct.new(:start_time, :end_time, :channel, :days)
>
> I think that there's a trade-off here. If you have a stupid (no
> internal logic) Program class, you can trade a very simple add method
> for a more complicated record? method.
>
> My position on it is that if I'm going to be leaving the brunt of the
> logic in the ProgramManager, I don't think there's a huge difference
> between nested arrays, a struct, or a class being the holder of the
> data.

Good point.

> That being said, on a lark I did a bit of refactoring and tried to
> move as much logic out of the ProgramManager into an actual Program
> class - the results are below.
>
> I definitely prefer the second version. It's got 10 more lines of
> actual code, but there's less random logic strewn about (and the logic
> is simpler). There's a definite separation of responsibilities -
> Program just does querying, ProgramManager handles priorities.

You just learned what I also learned today, writing the summary. ;)

James Edward Gray II

comp.lang.ruby

[QUIZ] VCR Program Manager (#101

James Gray

Kurt Hindenburg

James Gray

Dema

Peter Severin

Dale Martenson

Francois Beausoleil

Jamie Macey

James Gray

Jamie Macey

James Gray

x Login to ForumsZone