by Gavin Kistner
The Background
---------------------------------------------------------------------
Last night I was having trouble falling asleep, and was staring at my digital alarm clock (as I do so often under that circumstance). Something on the bedside table was occluding the minutes digit, however, so all I could tell is that it was "10 4". (Oddly, my alarm clock has no ":" between the hours and minutes.)
"How nice!" I thought. "An imposed vagueness to keep me from obsessing on exactly what time it is! Should I really be worried about the exact time? Shouldn't I be more relaxed? Shouldn't a 10-minute precision in life be enough to keep me roughly on time, without obsessing on exacting promptitude?"
I realized that if I kept staring at the clock (as I did), and I were to observe it changing from "10 4" to "10 5", that I would, at that moment, know exactly what time it is.
"Bah" I thought, "so much for that idea."
And then I thought some more. I thought of bad ideas: analog watches where the hand erratically swings forward and backward, digital clocks that showed random times near the correct time. And then I dreamed of the watch I wanted to own...
The Challenge
---------------------------------------------------------------------
Requirement #1: Write a Ruby program that shows the current time, but only the 'tens' part of the minutes. For example, if the time is 10:37, then the program might output "10:3~"
Requirement #2: The time shown by the clock must randomly vary +/- 5 minutes from reality. For example, if the time is actually 10:37, the program might output "10:3~" or "10:4~" (but not "10:2~" or "10:5~").
Requirement #3: The time on the clock should continuously increase. If the time shows "10:4~" it must continue to show "10:4~" until it shows "10:5~". (It can't show "10:4~", then "10:3~" for a bit and then come back to "10:4~".)
Putting the three requirements together, the left column below shows the actual time and the next three columns show the possible outputs from three different runs of the same program:
10:35 10:3~ 10:4~ 10:3~
10:36 10:3~ 10:4~ 10:3~
10:37 10:3~ 10:4~ 10:3~
10:38 10:3~ 10:4~ 10:3~
10:39 10:4~ 10:4~ 10:3~
10:40 10:4~ 10:4~ 10:3~
10:41 10:4~ 10:4~ 10:3~
10:42 10:4~ 10:4~ 10:3~
10:43 10:4~ 10:4~ 10:3~
10:44 10:4~ 10:4~ 10:3~
10:45 10:4~ 10:4~ 10:4~
10:46 10:4~ 10:4~ 10:5~
10:47 10:4~ 10:4~ 10:5~
10:48 10:4~ 10:4~ 10:5~
10:49 10:4~ 10:4~ 10:5~
10:50 10:4~ 10:4~ 10:5~
10:51 10:4~ 10:4~ 10:5~
10:52 10:5~ 10:4~ 10:5~
10:53 10:5~ 10:4~ 10:5~
10:54 10:5~ 10:4~ 10:5~
10:55 10:5~ 10:5~ 10:5~
10:56 10:5~ 10:5~ 11:0~
10:57 10:5~ 10:5~ 11:0~
10:58 10:5~ 10:5~ 11:0~
10:59 10:5~ 10:5~ 11:0~
11:00 10:5~ 10:5~ 11:0~
11:01 10:5~ 10:5~ 11:0~
Testing your Output
---------------------------------------------------------------------
You should supply a FuzzyTime class that supports the following:
ft = FuzzyTime.new(Time.at(1161104503)) # Start at a specific time
p ft.to_s # to_s format
#=> "10:5~"
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
Your class and output will be tested with code like the following:
# Initialize with a well-known time
ft = FuzzyTime.new( Time.at( ... ) )
60.times do
@legal = ... # Find the array of legal output strings
@output = ft.to_s
assert_block "#@output not one of #@legal.inspect" do
@legal.include?( @output )
end
sleep( rand( 30 ) )
ft.update
end
60.times do
@legal = ... # Find the array of legal output strings
@output = ft.to_s
assert_block "#@output not one of #@legal.inspect" do
@legal.include?( @output )
end
ft.advance( rand( 30 ) )
end
end
Extra Credit
---------------------------------------------------------------------
* Provide a self-running application that shows the time somehow.
(ASCII in the terminal, some GUI window, etc.)
* Allow your class to be customized to display 12- or 24-hour time.
* Allow your class to be customized to change how close to reality
it must display. (+/- 3 minutes, +/- 12 minutes, etc.)
* Allow your class to be customized to change how roughly it displays
the time (e.g. 1 minute, 10 minute, 1 hour intervals).
* Ensure that the transition from one digit to the next occurs
randomly across the range of -5 to +5. (So, while the digit might
change 5 minutes before or 5 minutes after the real transition, on
average the change should occur around the transition itself.)
You might need to assume that your update/advance method will be
called with a certain regularity (e.g. once per second, once every
7 seconds, once every 30 seconds, etc.)
* Come up with your own technique of displaying time that
(a) is always 'close' to right, but (b) never allows a
watchful person to ever know exactly what time it is.
Things to Keep in Mind
---------------------------------------------------------------------
* You need to be able to handle the transition across hour/day
boundaries. (10:5~ might change to 11:0~ when the real time is still
10:58, or might continue to display 10:5~ when the real time is
11:04. On a 24-hour click, you also need to be able to wrap from
23:5~ to 00:0~)
* For testing purposes of the real-time #update advancing, you might
find it easier to work with minutes and seconds instead of hours and
minutes.
* Requirement #3 is, well, a requirement. Repeated #update/#to_s
calls to a FuzzyTime instance should never show an earlier time
(unless 24 hours occurred between #update calls ;).
Quiz Summary
by Gavin Kistner
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:
@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:
@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:
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:
@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.
4) 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.
5) 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:
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.
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:
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:
@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.
6) 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.
# 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:
# 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!
