Re: [QUIZ] Fuzzy Time (#99)

Thanks for this week's interesting problem.  My solution is below and
I look forward to any feedback and seeing other techniques used.

There are two files pasted below; the second is the unit test, which
takes about 5-10 minutes to run to completion.  My first unit test
ever in any language :)

This is also my first greeting to the Ruby community... Hello!

Cheers,
Marcel


#!/usr/bin/env ruby
#
# Marcel Ward   <wardies ^a-t^ gmaildotcom>
# Sunday, 29 October 2006
# Solution for Ruby Quiz number 99
#
################################################
# fuzzy_time.rb

class FuzzyTime
  attr_reader :actual, :timed_observation_period

  # If the time passed is nil, then keep track of the time now.
  def initialize(tm=nil, range_secs=600, disp_accuracy_secs=range_secs,
                  fmt="%H:%M", obs_period=nil)
    @actual = @last_update = @next_diff = tm || Time.now
    @realtime = tm.nil?
    @maxrange = range_secs
    @display_accuracy = @best_accuracy = disp_accuracy_secs
    @tformat = fmt
    @last_observed = @max_disptime = Time.at(0)
    @timed_observation_period = obs_period
  end

  def to_s
    @last_update = Time.now
    @actual = @last_update if @realtime

    check_observation_period unless @timed_observation_period.nil?

	# We only calculate a new offset each time the last offset times out.
    if @next_diff <= @actual
      # Calculate a new time offset
      @diff = rand(@maxrange) - @maxrange/2
      # Decide when to calculate the next time offset
      @next_diff = @actual + rand(@maxrange)
    end
    @last_observed = @actual

    # Don't display a time less than the time already displayed
    @max_disptime = [@max_disptime, @actual + @diff].max

    # Take care to preserve any specific locale (time zone / dst) information
    # stored in @actual - for example, we cannot use Time::at(Time::to_i).
    disptime = @max_disptime.strftime(@tformat)

    # Lop off characters from the right of the display string until the
    # remaining string matches one of the extreme values; then fuzz out the
    # rightmost digits
    (0..disptime.size).to_a.reverse.each do
      |w|
      [@display_accuracy.div(2), - @display_accuracy.div(2)].map{
        |offs|
        (@max_disptime + offs).strftime(@tformat)
      }.each do
        |testtime|
        return disptime[0,w] + disptime[w..-1].tr("0123456789", "~") if \
          disptime[0,w] == testtime[0,w]
      end
    end
  end

  def advance(secs)
    if @realtime
      @actual = Time.now + secs
      # Once a real-time FuzzyTime is advanced, it can never again be
      # real-time.
      @realtime = false
    else
      @actual += secs
    end
    @last_update = Time.now
  end

  def update
    diff = Time.now - @last_update
    @actual += diff
    @last_update += diff
    # By calling update, you are effectively saying "set a fixed time"
    # so we must disable the real-time flag.
    @realtime = false
  end

  def accuracy
    "+/- #{@maxrange/2}s"
  end

  def dump
    "actual: #{@actual.strftime("%Y-%m-%d %H:%M:%S")}, " \
		"diff: #{@diff}, " \
		"next_diff: #{@next_diff.strftime("%Y-%m-%d %H:%M:%S")}, " \
		"accuracy: #{@display_accuracy}"
  end

private
  def check_observation_period
    # Is the clock being displayed too often?

    # Although this method seems to work, it may be a bit simplistic.
    # Proper statistical / mathematical analysis and a proper understanding
    # of the human ability to count seconds may be necessary to determine
    # whether this still gives away too much info for the average observer.

    patience = @actual - @last_observed

    if patience < @timed_observation_period / 2
      # Worsen display accuracy according to how impatient the observer is.
      @display_accuracy += (2 * @best_accuracy *
                            (@timed_observation_period - patience)) /
                            @timed_observation_period
    elsif patience < @timed_observation_period
      # Immediately punish impatience by enforcing a minumum accuracy
      # twice as bad as the best possible.
      # Don't give too much away but allow the accuracy to get slowly better
      # if the observer is a bit more patient and waits over half the
      # observation period
      @display_accuracy = [
          2 * @best_accuracy,
          @display_accuracy - ((@best_accuracy * patience) /
                                @timed_observation_period)
        ].max
    else
      # The observer has waited long enough.
      # Reset to the best possible accuracy.
      @display_accuracy = @best_accuracy
    end
  end
end

def wardies_clock
  # Get us a real-time clock by initializing Time with first parameter==nil
  # Make the seconds harder to guess by expanding the range to +/- 15s whilst
  # keeping the default display accuracy to +/- 5 secs.  The user will have
  # to wait 30s between observations to see the clock with best accuracy.
  ft = FuzzyTime.new(nil, 30, 10, "%H:%M:%S", 30)

  # This simpler instantiation does not check the observation period and
  # shows "HH:M~". (This is the default when no parameters are provided)
  #ft = FuzzyTime.new(nil, 600, 600, "%H:%M")

  puts "** Wardies Clock\n"
  puts "**\n** Observing more often than every " \
    "#{ft.timed_observation_period} seconds reduces accuracy" \
    unless ft.timed_observation_period.nil?
  puts "**\n\n"

  loop do
    puts "\n\nTime Now: #{ft.to_s}  (#{ft.accuracy})\n\n" \
      "-- Press Enter to observe the clock again or " \
      "q then Enter to quit --\n\n"

    # Flush the output text so that we can scan for character input.
    STDOUT.flush

    break if STDIN.getc == ?q
  end
end


def clocks_go_back_in_uk
  # Clocks go back in the UK on Sun Oct 29. (+0100 => +0000)
  # Start at Sun Oct 29 01:58:38 +0100 2006
  ft = FuzzyTime.new(Time.at(Time.at(1162083518)))

  # In the UK locale, we see time advancing as follows:
  # 01:5~
  # 01:5~
  # 01:0~  (clocks gone back one hour)
  # 01:0~
  # ...
  # 01:0~
  # 01:1~

  60.times do
    puts ft.to_s
    ft.advance(rand(30))
  end
end

def full_date_example
  # Accuracy can be set very high to fuzz out hours, days, etc.
  # E.g. accuracy of 2419200 (28 days) fuzzes out the day of the month
  # Note the fuzz factoring does not work so well with hours and
  # non-30-day months because these are not divisble exactly by 10.

  tm = FuzzyTime.new(nil, 2419200, 2419200, "%Y-%m-%d %H:%M:%S")
  300.times do
    puts "#{tm.to_s} (#{tm.dump})"
    # advance by about 23 days
    tm.advance(rand(2000000))
    #sleep 0.2
  end
end

# Note, all the examples given in the quiz are for time zone -0600.
# If you are in a different timezone, you should see other values.
def quiz_example
  ft = FuzzyTime.new                      # Start at the current time
  ft = FuzzyTime.new(Time.at(1161104503)) # Start at a specific time

  p ft.to_s                               # to_s format

  p ft.actual, ft.actual.class            # Reports real time as Time
  #=> Tue Oct 17 11:01:36 -0600 2006
  #=> Time

  ft.advance( 60 * 10 )                   # Manually advance time
  puts ft                                 # by a specified number of
  #=> 11:0~                               # seconds.

  sleep( 60 * 10 )

  ft.update              # Automatically update the time based on the
  puts ft                # time that has passed since the last call
  #=> 11:1~              # to #initialize, #advance or #update
end

if __FILE__ == $0
  wardies_clock
  #clocks_go_back_in_uk
  #full_date_example
  #quiz_example
end


################################################
# fuzzy_time_test.rb

require 'test/unit'
require 'fuzzy_time'

class FuzzyTime_Test < Test::Unit::TestCase
  #def setup
  #end

  #def teardown
  #end

  def test_advance

    # Initialize with a known UTC time (Tue Jun 10 03:14:52 UTC 1975)
    ft = FuzzyTime.new(Time.at(171602092).getgm, 60, 60, "%H:%M:%S")

    # Add 6 hours 45 minutes 30 secs to give us
    # (Tue Jun 10 09:59:22 UTC 1975)
    ft.advance(3600*6 + 60*45 + 30)
    @last_output = ""

    60.times do
      # Initial displayed time sourced from between 09:58:52 and 09:59:52
      # Time will be advanced by between 0 and 600 seconds.
      # So final displayed time source ranges from 10:08:52 to 10:09:52

      # The array of legal output strings:
      @legal  = ["09:58:~~", "09:59:~~", "10:00:~~", "10:01:~~",
        "10:02:~~", "10:03:~~", "10:04:~~", "10:05:~~",
        "10:06:~~", "10:07:~~", "10:08:~~", "10:09:~~"]

      @output = ft.to_s

      assert_block "#@output not one of #{@legal.inspect}" do
        @legal.include?( @output )
      end

      assert_block  "#@output must be greater than or equal to " \
        "last value, #@last_output" \
      do
        @output >= @last_output
      end
      @last_output = @output

      ft.advance( rand( 11 ) )
    end
  end

  def test_advance_rollover
    # Initialize with a known UTC time (Fri Dec 31 23:58:25 UTC 1999)
    # Test rollover at midnight
    # Note, we have an accuracy of +/- 5 secs now and enabled the
    # observations timer
    ft = FuzzyTime.new(Time.at(946684705).getgm, 10, 10, "%H:%M:%S", 10)

    30.times do
      # Initial displayed time sourced from between 23:58:20 and 23:58:30
      # Time will be advanced by between 0 and 150 seconds.
      # So final displayed time source ranges from 00:00:50 to 00:01:00

      # Note, if we watch too often over a short period of time,
      # our displayed accuracy will decrease.  Then we will lose
      # the 10's digit of the seconds and occasionally the 1's minute.

      # The array of legal output strings:
      @legal = ["23:58:1~", "23:58:2~", "23:58:3~",
        "23:58:4~", "23:58:5~", "23:58:6~",
        "23:58:~~", "23:59:~~", "23:5~:~~",
        "23:59:0~", "23:59:1~", "23:59:2~",
        "23:59:3~", "23:59:4~", "23:59:5~",
        "00:00:0~", "00:00:1~", "00:00:2~",
        "00:00:3~", "00:00:4~", "00:00:5~", "00:00:~~",
        "00:01:0~", "00:01:~~", "00:0~:~~"]

      @output = ft.to_s

      assert_block "#@output not one of #{@legal.inspect}" do
        @legal.include?( @output )
      end

      # We cannot easily check that the current output is greater or equal to
      # the last because with timed observations, a valid output sequence is:
      # 23:59:0~
      # 23:59:~~ (looking too often, accuracy has been reduced)
      # 23:59:0~ (waited long enough before observing for accuracy to return)

      ft.advance( rand(6) )
    end
  end

  def test_update
    # NOTE - this test takes 5-10 minutes to complete

    # Initialize with a known UTC time (Tue Jun 10 03:14:52 UTC 1975)
    ft = FuzzyTime.new(Time.at(171602092).getgm, 60, 60, "%H:%M:%S")
    @last_output = ""

    60.times do
      # Initial displayed time sourced from between 03:14:22 and 03:15:22
      # Duration of loop will be between 0 and ~600 seconds.
      # So final displayed time source ranges from 03:14:22 to 03:25:22

      # The array of legal output strings:
      @legal  = ["03:14:~~", "03:15:~~", "03:16:~~", "03:17:~~",
        "03:18:~~", "03:19:~~", "03:20:~~", "03:21:~~",
        "03:22:~~", "03:23:~~", "03:24:~~", "03:25:~~"]

      @output = ft.to_s

      assert_block "#@output not one of #{@legal.inspect}" do
        @legal.include?( @output )
      end

      assert_block  "#@output must be greater than or equal to " \
        "last value, #@last_output" \
      do
        @output >= @last_output
      end
      @last_output = @output

      sleep( rand( 11 ) ) # wait between 0..10 secs
      ft.update
    end
  end
end