[QUIZ] VCR Program Manager (#101)

James_Edward_Gray_II · 10 November 2006 15:01

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!

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.rubyquiz.com/program_manager_test.rb

Kurt_Hindenburg1 · 12 November 2006 00:01

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

···

On 11/10/06, Ruby Quiz <james@grayproductions.net> wrote:

You can see the unit tests I used at:

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

Dema · 12 November 2006 21:20

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 · 13 November 2006 08:45

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

Francois_Beausoleil · 13 November 2006 18:41

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 · 13 November 2006 23:56

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

···

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_manager_test.rb

James_Edward_Gray_II · 12 November 2006 17:08

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

James Edward Gray II

···

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_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

Dale_Martenson · 13 November 2006 17:42

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-forum.com/.

James_Edward_Gray_II · 15 November 2006 14:54

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

···

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.

Ken_Bloom · 24 November 2006 19:49

I've done it for my quizzes, usually while writing the quiz. Last time,
(the s-expression quiz) *everyone* else's solution turned out to be more
elegant than mine.

I'd say it's nothing to worry about. The goal is to learn ruby
techniques, not to win. The hard part is not to bias your quiz toward your
own solution.

--Ken

···

On Tue, 14 Nov 2006 03:41:53 +0900, Francois Beausoleil wrote:

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.

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

Jamie_Macey · 15 November 2006 18:35

> 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

···

On 11/15/06, James Edward Gray II <james@grayproductions.net> wrote:

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

James_Edward_Gray_II · 15 November 2006 20:37

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

···

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

On 11/15/06, James Edward Gray II <james@grayproductions.net> wrote:

Adam_Shelly · 15 November 2006 21:39

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

···

On 11/15/06, James Edward Gray II <james@grayproductions.net> wrote:

On Nov 15, 2006, at 12:35 PM, Jamie Macey wrote:
> 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

----------------
# 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+= (7*24).hours
    @end_t+= (7*24).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

Topic		Replies	Views
Please Forward: Ruby Quiz Submission ruby-talk	0	117	12 November 2006
[SUMMARY] VCR Program Manager (#101) ruby-talk	1	112	16 November 2006
[OT] Programmatic VCR Control ruby-talk	3	63	17 February 2008
[QUIZ] VCR Program Manager (#101) ruby-talk	0	89	13 November 2006
[QUIZ] Scheduling (#42) ruby-talk	7	117	17 August 2005

[QUIZ] VCR Program Manager (#101)

Related topics