VCR Program Manager (#101)

Ruby
1

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

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

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

by François Beausoleil

The goal of this Ruby Q. 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.rubyquiz.com/program_manager_test.rb
2

On 11/10/06, Ruby Q. [email protected] wrote:

You can see the unit tests I used at:

    http://www.rubyquiz.com/program_manager_test.rb

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

3

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

23 tests, 736 assertions, 0 failures, 0 errors
If you feel something is missing, feel free to add it.

James Edward G. II

4

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

5

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 –

6

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

7

On 11/10/06, Ruby Q. [email protected] 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_manager_test.rb

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

8

Here is another similar solution. It may not be as efficient as others.
–Dale M.

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

9

On Nov 13, 2006, at 5:56 PM, Jamie M. 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 M.'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… :wink:

James Edward G. II

10

On 11/15/06, James Edward G. II [email protected] wrote:

For example, have a look at Dale M.'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… :wink:

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

  • 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

11

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

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

James Edward G. II

12

On 11/15/06, James Edward G. II [email protected] wrote:

You just learned what I also learned today, writing the summary. :wink:

James Edward G. II

So it seems I’ve already missed the summary, but here’s my solution.
I took a different approach - I stored the programs to record in a
linked list sorted by start time. As I was thinking about the
solution. I realized this is the first time I even considered a linked
list since I started using Ruby. For most places I would have used
them in other languages, I can use Arrays in Ruby. (For a moment I
thought - oh, can’t do lists, no pointers - but then I realized that
references worked just fine)

The solution needs serious refactoring. I have 2 classes where I
should have 4 or 5 to separate the list logic from the VCR logic.
But I don’t have any more time this week.

-Adam

A Program node. Contains the program recording information,

the linked list handle, and a few functions for list maintainance

class Program
attr_reader :start,:end_t,:channel, :repeat, :nxt
def initialize start,finish,channel,repeat=false
@start,@end_t,@channel = start,finish,channel
@repeat = repeat
end
def advance
@start+= (724).hours
@end_t+= (724).hours
self
end
def not_after? time
@end_t < time ||
(@end_t == time &&
(@nxt && @nxt.start <=time))
end

def split_and_insert node
tail = Program.new(node.start,@end_t,@channel,@repeat)
@end_t = node.start
insert_after_self node
node.insert_after_self tail
end
def insert_after_self node
node.set_next @nxt
@nxt = node
end
def set_next node
@nxt = node
end
end

class Time
#returns a Time object for the begining of the day
def daystart
arr = self.to_a
arr[0,3]=[0,0,0]
Time.local(*arr)
end
end

def hours_between daynum, daystr
days = %w{sun mon tue wed thu fri sat}.map{|d|Regexp.new(d)}
days.each_with_index{|dayname,idx|
if dayname =~ daystr
idx+=7 until idx-daynum >= 0
return (idx-daynum)*24.hours
end
}
end

class ProgramManager
def initialize
@head = nil
end

#adds programs to a linked list sorted by start time
def add args
start = args[:start]
finish = args[:end]
channel = args[:channel]
if !daylist = args[:days]
insert Program.new(start,finish,channel)
repeat = nil
else
t = Time.now #This is only going to future recurring dates on
the list
#t = Time.local(2006,10,30) #so in order to pass the unit tests,
#force back to Oct 30th
today = t.wday
daystart = t.daystart
daylist.each{|day|
offset = hours_between(today,day)
p_start = daystart+offset+start
p_finish = daystart+offset+finish
insert Program.new(p_start,p_finish,channel, true)
}
end
end

#inserts node in list, sorted by time.
#newer entries are inserted before older entries for the same period.
#we don’t do anything special if the end of the new entry overlaps
#the beginning of the older one - when the new entry is done, the
old one will be
#next on the list, so it will become active, wherever it is in it’s
range.
#the only tricky case is if a new program starts in the middle of an
older one
#then we have to split the old node, and insert the new one in the
split.
def insert new_node
prevNode,curNode=nil,@head
while curNode and curNode.end_t <= new_node.start
prevNode,curNode=curNode,curNode.nxt
end
if curNode and curNode.start < new_node.start
curNode.split_and_insert new_node
elsif prevNode
prevNode.insert_after_self new_node
else
new_node.set_next @head
@head = new_node
end
end

#pops all the nodes that end before the current time.
#if they are repeating, advance their time one week, and reinsert
them.
def find_current_node time
return false unless @head
while @head && @head.not_after?(time)
old_node = @head
@head = @head.nxt
insert old_node.advance if old_node.repeat
end
@head if @head && @head.start <= time
end

def record? time
node = find_current_node time
node && node.channel
end
end