[SUMMARY] Fuzzy Time (#99)

Discussion in 'Ruby' started by Gavin Kistner, Nov 2, 2006.

  1. The core requirements for this quiz were somewhat easy. Let's look at
    what needed to be done, and how some people accomplished it:
    =20
    =20
    =20
    1) How do you represent the internal time?
    =20
    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.
    =20
    =20
    =20
    2) How to you handle the 'overloaded' constructor?
    =20
    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'.
    =20
    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:
    =20
    def initialize( time =3D Time.now )
    @start_time =3D time
    end
    =20
    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.
    =20

    A variation is how Tom Pollard handled it:
    =20
    def initialize ( actual=3Dnil )=20
    @actual =3D actual || Time.new()
    end
    =20
    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).
    =20

    Less ideal (but functional) variations included:
    =20
    def initialize(*args)=20
    now =3D Time.new=20
    @internal_time =3D args[0] || now=20
    end
    =20
    def initialize(*args)
    if args.size =3D=3D 0
    @timeshift =3D 0
    else
    @timeshift =3D Time.now.to_i - args[0].to_i
    end
    =20
    Writing code like this certainly works, but it makes the code less
    self-explanatory.
    =20
    =20
    =20
    3) How do you convert to a fuzzy string?
    =20
    I was surprised by the variation in this category. The major variations:
    =20
    def to_s
    @my_time.strftime("%H:%M")[0..3] + "~"
    end
    =20
    def to_s=20
    s =3D @my_time.strftime("%H:%M")=20
    s[4] =3D '~'=20
    s=20
    end=20
    =20
    def to_s
    fuzzy_hour, fuzzy_min, fuzzy_sec =3D get_time
    "#{fuzzy_hour}:#{fuzzy_min / 10}~"
    end
    =20
    def to_s=20
    sprintf('%02d:%d~%s',=20
    @mode =3D=3D 24 ? @my_time.hour : @my_time.hour % 12,=20
    @my_time.min / 10,=20
    @mode !=3D 24 ? @my_time.hour / 12 =3D=3D 1 ? ' pm' : ' am' : ''=20
    )=20
    end
    =20
    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.
    =20
    =20
    =20
    3) How do you keep track of the last displayed time?
    =20
    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.
    =20

    4) How do you ensure no backtracking?
    =20
    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:
    =20
    @time_to_display =3D ... #some Time instance
    if @time_to_display < @last_displayed_time
    @time_to_display =3D @last_displayed_time
    end
    # (Display the time here)
    @last_displayed_time =3D @time_to_display
    =20
    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~".
    =20
    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.
    =20
    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.
    =20
    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.
    =20
    y,mon,day =3D t.year, t.mon, t.day
    h,m =3D last_value.scan(/\d+/).map{ |s| s.to_i }
    m *=3D 10
    if (m -=3D 10) < 0
    m %=3D 60
    if (h -=3D 1) < 0
    h %=3D 24
    end
    end
    illegal_old_value =3D Time.local( y,mon,day,h,m ).to_fuzzy
    =20
    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:
    =20
    class Time
    def round_to( seconds )
    seconds =3D seconds.round
    Time.at( self.to_i / seconds * seconds )
    end
    end
    ...
    TEN_MINS =3D 10 * 60
    ...
    if @fuzzy.round_to( TEN_MINS ) < @last_fuzzy.round_to( TEN_MINS )
    =20

    However, Jeremy Hinegardner rounded the minutes down to 10 *before*
    displaying, and used that to create a new Time:
    =20
    min =3D (@fuzzed.min / 10) * 10
    @display =3D Time.mktime( @fuzzed.year, @fuzzed.month, @fuzzed.day,
    @fuzzed.hour, min, 0, 0)
    =20
    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!
    =20
    =20
    =20

    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.
    =20
    =20
    =20
    5) How do you attempt even distribution?
    =20
    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.=20
    =20
    At first, I thought I was a statistician. I started writing this out in
    my code.
    =20
    # The chance of success after n attempts of something with probability p
    # per attempt is: s =3D 1-(1-p)**n
    #
    # Solving for p:
    # 1-s =3D (1-p)**n
    # (1-s)**(1/n) =3D=3D 1-p
    # p =3D=3D 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 =3D 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.
    =20
    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.
    =20
    I wrote:
    =20
    if rand < per_advance_probability
    # Uhm...what do I do here?
    =20
    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.
    =20
    My point, other than sharing my pain, is twofold:
    =20
    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.
    =20
    2) It's amazing how even simple programming problems can require some
    interesting cross-disciplinary knowledge, like probability and
    statistics.
    =20

    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.
    =20

    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. :)
    =20
    Which gives me an interesting idea for a new quiz...
    Hmmmm...yes...
    =20

    See you next time!
    =20

    [1]
    http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/7e6b564a
    10d65735/dc30cb4ade9531d9#dc30cb4ade9531d9
     
    Gavin Kistner, Nov 2, 2006
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Giovanni Azua
    Replies:
    3
    Views:
    644
    Ingo R. Homann
    Aug 9, 2005
  2. VisionSet

    Fuzzy Logic Library

    VisionSet, Dec 12, 2005, in forum: Java
    Replies:
    3
    Views:
    1,078
    Roedy Green
    Dec 12, 2005
  3. flamesrock
    Replies:
    8
    Views:
    502
    Hendrik van Rooyen
    Nov 24, 2006
  4. Ruby Quiz

    [QUIZ] Fuzzy Time (#99)

    Ruby Quiz, Oct 27, 2006, in forum: Ruby
    Replies:
    22
    Views:
    292
    Tom Pollard
    Nov 1, 2006
  5. Gavin Kistner

    [QUIZ] Fuzzy Time (#99) - Results

    Gavin Kistner, Nov 2, 2006, in forum: Ruby
    Replies:
    1
    Views:
    123
    Marcel Ward
    Nov 2, 2006
Loading...

Share This Page