[SUMMARY] Fuzzy Time (#99)

The core requirements for this quiz were somewhat easy. Let's look at
what needed to be done, and how some people accomplished it:
 
 
 
1) How do you represent the internal time?
 
While it would be possible to manage the time yourself, everyone
(sensibly) chose to use Ruby's built-in Time class to represent the
'real' time behind the fuzz. Everyone gets a pat on the back.
 
 
 
2) How to you handle the 'overloaded' constructor?
 
How do you write one initialize function that allows you to specify a
start time or omit it? It seems almost silly to focus on it, and yet
it's a common enough need that it's important to know how to do it
'right'.
 
There were a few approaches to this. The simplest, I think, is to use
Ruby's default values in the method definition. As Daniel Lucraft wrote:
 
  def initialize( time = Time.now )
    @start_time = time
  end
  
Not only is this easy to write, but it also documents nicely. "If you
don't give me a value for the time parameter, I'm going to use Time.now
instead." RDoc handles this case when generating documentation.
 

A variation is how Tom Pollard handled it:
 
  def initialize ( actual=nil ) 
    @actual = actual || Time.new()
  end
 
The above says to the user, "You may pass me an actual time or not, but
what value I use if you don't give it to me is a detail you probably
don't need to know about." Under some circumstances, this sort of
implementation hiding might be preferable (coupled with good
documentation about what it means to not supply the value).
 

Less ideal (but functional) variations included:
 
  def initialize(*args) 
    now = Time.new 
    @internal_time = args[0] || now 
  end
  
  def initialize(*args)
    if args.size == 0
      @timeshift  = 0
    else
      @timeshift  = Time.now.to_i - args[0].to_i
  end
 
Writing code like this certainly works, but it makes the code less
self-explanatory.
 
 
 
3) How do you convert to a fuzzy string?
 
I was surprised by the variation in this category. The major variations:
 
  def to_s
     @my_time.strftime("%H:%M")[0..3] + "~"
  end
 
  def to_s 
    s = @my_time.strftime("%H:%M") 
    s[4] = '~' 
    s 
  end 
  
  def to_s
    fuzzy_hour, fuzzy_min, fuzzy_sec = get_time
    "#{fuzzy_hour}:#{fuzzy_min / 10}~"
  end
 
  def to_s 
    sprintf('%02d:%d~%s', 
      @mode == 24 ? @my_time.hour : @my_time.hour % 12, 
      @my_time.min / 10, 
      @mode != 24 ? @my_time.hour / 12 == 1 ? ' pm' : ' am' : '' 
    ) 
  end
 
I like the one-line simplicity of the first. It happens to create three
strings in the process of creating the final, while the second
(annoying-to-type, ugly) technique creates just one. I personally went
with the second approach (create a string and then replace a character
in-place) in the pointless pursuit of memory savings. Premature
optimization at its finest, I think.
 
 
 
3) How do you keep track of the last displayed time?
 
Because the Time class plays well with seconds as a sort of atomic base
unit, some people chose to keep the 'fuzzy' time being displayed
internally as an offset from the real time maintained internally. Others
(including myself) chose to maintain the last displayed time as a
separate Time instance. I don't see a major benefit of using one over
the other, but wanted to point out the alternative.
 

4) How do you ensure no backtracking?
 
This was the trickiest part of the quiz (outside of the 'extra credit'
options). The requirement was that the time never display a time earlier
than the last displayed time. I originally (naively) coded this roughly
as:
 
  @time_to_display = ... #some Time instance
  if @time_to_display < @last_displayed_time
    @time_to_display = @last_displayed_time
  end
  # (Display the time here)
  @last_displayed_time = @time_to_display
   
The problem with this approach is that it's overly restrictive. For
example, assume that the last time shown by the class was 10:49, which
was displayed at "10:4~". If the class then generates a random time to
display of 10:45, the above code will say "Nope, that's before 10:49,
gotta stick to 10:49". Of course, 10:45 is a perfectly reasonable time
to use internally, since it still displays as "10:4~".
 
Using any sort of approach that adds or subtracts an offset from a
moving 'fuzzy' time, the above approach is like the ratchets on a roller
coaster hill. Each step forward you take prevents you from coming
backwards. Before you know it, your wandering time is pinned as far
forward as it can go.
 
The desire, then, is to ensure that the internal time never becomes
earlier than the bottom of the *displayed* version of the internal fuzzy
time.
 
In my test case (because I had no access to the internals of the class),
I did this by parsing the string and backing it up manually.
 
  y,mon,day = t.year, t.mon, t.day
  h,m = last_value.scan(/\d+/).map{ |s| s.to_i }
  m *= 10
  if (m -= 10) < 0
    m %= 60
    if (h -= 1) < 0
      h %= 24
    end
  end
  illegal_old_value = Time.local( y,mon,day,h,m ).to_fuzzy
 
Ugh. Time is so messy. In my class, I used the fact that rounding the
internal seconds of a time class to a resolution of 600 gives you a time
rounded to 10 minutes:
 
  class Time
    def round_to( seconds )
      seconds = seconds.round
      Time.at( self.to_i / seconds * seconds )
    end
  end
  ...
  TEN_MINS = 10 * 60
  ...
  if @fuzzy.round_to( TEN_MINS ) < @last_fuzzy.round_to( TEN_MINS )
 

However, Jeremy Hinegardner rounded the minutes down to 10 *before*
displaying, and used that to create a new Time:
 
  min = (@fuzzed.min / 10) * 10
  @display = Time.mktime( @fuzzed.year, @fuzzed.month, @fuzzed.day,
                          @fuzzed.hour, min, 0, 0)
                          
This is nice, because the same Time instance used to display the time is
also the lower limit for the next display. Nice work, Jeremy!
 
 
 

That's most of the interesting stuff from the quiz...outside of the
extra credit. Particularly the bit about trying to get an even
distribution of random times. Other extra credit solutions were nice -
check out the code for some interesting ways to round time to various
degrees. But I wanted to mention this one just a bit.
 
 
 
5) How do you attempt even distribution?
 
I'm not a statistician. For most of this topic, I suggest that you read
some of the very interesting discussions[1] that took place on the
mailing list. 
 
At first, I thought I was a statistician. I started writing this out in
my code.
 
# The chance of success after n attempts of something with probability p
# per attempt is: s = 1-(1-p)**n
#
# Solving for p:
# 1-s = (1-p)**n
# (1-s)**(1/n) == 1-p
# p == 1 - (1-s)**(1/n)
#
# I want to have a 50% chance of moving ahead at the exact correct time,
# so if I am going to make n updates between -5 minutes and the correct
# time, I should try for a per attempt chance of p = 1 - 0.5**(1.0/n).
#
# This leaves me with a total chance of success of 75% after 2n
# attempts (+5 minutes), which (I think) means that the algorithm will
be
# weighted towards running on the not-too-fast side. That's probably OK,
# given the one-way time valve.
 
Then I went to put this idea into code. I wrote some code that
automatically tracked how frequently the advance method was being called
(using a simple low-pass filter instead of a running average). I used
that number to calculate how many times per minute it was being called,
and calculated the ideal probability to use per attempt.
 
I wrote:
  
  if rand < per_advance_probability
    # Uhm...what do I do here?
    
Then I punted and went with a simple even distributation probability
instead. (See the solution I submitted.) I just couldn't figure out
where to go from there.
 
My point, other than sharing my pain, is twofold:
 
1) Having a rough, good idea of how to solve a problem is not the same
as knowing how to solve it. My advice (to myself) is not to start
randomly writing code, HOPING that when I get to the bit I'm not sure of
that it will all work out. Time gets wasted that way.
 
2) It's amazing how even simple programming problems can require some
interesting cross-disciplinary knowledge, like probability and
statistics.
 

Finally, I wanted to mention how much of a challenge it turned out to be
trying to write a test for random distribution. Min/maxes, means and
standard deviations can give you an idea of how random some output
is...but in this case a big curtain was being held up over half the
output. If the time is 10:47 and the program displays "10:4~", I have no
idea if internally it's running fast, slow, or on time. The only way I
could think to test for randomness (other than peeking at the internals
of the class) was to watch for the change from one displayed value to
the next and see at that point how fast/slow the class was running.
 

Thanks to everyone for contributing to this quiz! Great to see some new
contributors. Yet again the requirements that I provided turned out to
have some holes in them, which I hope that the test cases I provided
helped to clarify my intent. I've decided I won't apologize for that,
and instead use it as a life lesson on edge cases and getting clear
problem specifications from your boss/client. :)
 
Which gives me an interesting idea for a new quiz...
Hmmmm...yes...
 

See you next time!
 

[1]
http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/7e6b564a
10d65735/dc30cb4ade9531d9#dc30cb4ade9531d9