No T-Shirt For Me

This past Saturday my brain turned off and I failed to get even a single problem right in the 2^nd round of the TCO 2011. This was the round you had to get past to get a t-shirt.

So what happened? One thing I like to do with problems is work out a couple simple inputs by hand to make sure I understand the problem. As one of my former co-workers liked to say, if you don't know how to do something, you don't know how to do it with a computer. On the first problem from Saturday's contest, the input was a positive integer, and we had to return an integer based on the problem description. I worked out the answers for the inputs 1 - 6. Unfortunately, I had come up with the wrong answer for an input of 6. Since 6 wasn't one of the sample inputs, I didn't know I was wrong.

Not surprisingly, trying to generalize from my wrong solution to a general solution didn't work so well. I eventually gave up, but not in time to code up a correct solution to the next problem.

walk away from the problemThis is a problem that I've had before, and I've seen it in others. Once you make a mistake, it can be really hard to see that mistake. Your mind tends to stay in that rut and you repeat the mistake when you redo the problem. In the real world (i.e. not the artificially constrained world of programming contests), there are a couple of ways to solvie this type of mistake. The first is to talk through the problem with an external party. If you can, though, don't explain what you did, but rather let them solve it themselves. That way you don't lead their thought process into the same rut as your own. The second approach is to walk away from the problem. Often times, just walking away from a problem is enough to let you see the solution when you pick it up the next day.

Unfortunately, neither of those were options for me with the programming contest. So, instead, I get to kick myself for a year. Oh well. Maybe next year will go better.

Testing in Production

A co-worker of mine has the picture to the right posted on her door. Last week we put that into practice. We deployed a new internal app which depended on two other components which were also new. On Thursday at 4:30 PM an email went out to tell people they could use it. By 4:45 our server had crashed. Thursday was a late night, but we eventually got the system where it could run without crashing the server. On Friday morning (when it really got used), we had to scramble to fix some less obvious (at least to the end user) bugs, but just as critical.

So what happened?
The short answer is, we didn't do enough testing. Every bug that we've found (so far), arguably should've been found in testing. All in all, it was a pretty embarrassing experience. Especially since part of it was our first internal Rails app which I had pushed hard to get us to use. However, in hind-sight if I had it to do all over again, I think I'd have done the same thing. Why?

Obviously, it's not good to have such a big failure. Plus, I never like to *have* to work late. However, nothing is in a vacuum. Every decision has to be compared to the alternative. We probably could've found most or all of the bugs with another week of testing. So which was better to the Lab? That we test for another week, with the opportunity cost that two developers can't be working on other projects? Or that we deploy a poorly tested app, give a few users a poor experience, and have a couple people work one long day on a Thursday?

The fact of the matter is, 15 minutes of real user testing found bugs that would've taken at least a week of developer testing. In terms of people hours, it was much more efficient to get some real use than to continue testing. As Jeff Atwood says, release your buggy software. So what was the negative? In this particular situation it was an internal app so there are no customers to lose or investors to turn away. The only negative is that a few people probably think less of me and my division. On the plus side, getting the app in front of people helped define requirements better than any amount of up front analysis. Also, the majority of this code will be reused on future apps, so this testing should allow for future high quality releases, allowing us to regain some of that lost reputation.

Releasing finds missing requirementsSo what's the take home message? Well, I am still embarrassed by how many problems we had with this release. However, given that there were no real negative consequences, it was probably in everyone's best interest for us to release (potentially) buggy software, rather than delay it for more exhaustive testing. Releasing finds missing requirements and shows how the code is really used. No amount of testing can do that.

In general, I try to have this blog be a voice for higher quality software, and to not subject users to a bad experience. However, at times it might be better to give a temporary bad experience so that the majority can have a good experience sooner.

Too Slow

I have been remiss in getting my posts out. A few weeks ago I was at ICSE. I had intended on making a post based on that conference, but as soon as it was over, I went into vacation mode. While on vacation I found a number of things to do that kept me away from computers. About the only computer thing I did do was compete in the 2^nd round of the Google Code Jam.

This was more challenging than normal for me because Google tries to schedule their contests to be at a somewhat reasonable hour for most of the world. They've made the decision that there is this great big ocean without a lot of people living in it, and so they schedule it so the contest is in the middle of the night for the Pacific. Of course, I happened to be in Hawai'i at this time and so got up at O'dark-thirty for the 4AM contest start. Surprisingly, I not only did well enough to get a t-shirt (top 1000), but did well enough to advance to the next round (top 500).

So this is why I missed the last two posts. What about this post? Well, after two weeks away, we had a lot of catching up to do at home and at work. The little bit of free computer time I was able to find went to practicing for the 3^rd round of the Google Code Jam where they would select the top 25. Unfortunately, that was for naught, as I did not advance.

Too Slow
24 out of 25 of the advancers solved the first 3 problems, as well as the small input set on the 4^th problem. I, also, know how to solve the first 3 problems as well as the small input set on the 4^th problem. So what's the difference between the advancers and me? On this problem set, speed. At the same time as I was submitting my solution to the second problem, 25^th place was submitting his final solution.

The top competitors were probably a little faster at coming up with algorithms and at coding the algorithms. However, what killed me was debugging. In the first problem, I had numerous bugs in my code that I had to spend time tracking down. Careless mistakes on this problem singlehandedly knocked me out of the running to advance. On the third problem, bugs were again my downfall. I didn't take my own advice and I didn't spend a couple minutes thinking about how to best structure my data structures. I just used the first thing that popped into my head which ended up being very error prone. After the contest, when I had a couple minutes to think without the pressure, I came up with a much simpler way to code the same algorithm.

So what's the moral of this story? Don't make mistakes! :) And trying to do things in a rush just makes it more likely that you will make mistakes. Oh, and going on vacation during a contest is probably not conducive to preparing.

As for why this post is a day late... well, I am just a little bit slow.

Moore's Law Doesn't Catch Imagination

Back in 1992 I had an opportunity to use an iPSC super computer. If I recall correctly, the particular computer I used had a total of 192 MB of RAM. This was just an outrageously huge amount. It was enough that I didn't really pay too much attention to the memory I was using on the program I was writing. When it was suggested that maybe my program was failing due to using too much memory, I was incredulous. But upon further inspection of my program, sure enough, I was trying to allocate arrays requiring a few hundred megabytes of memory.

Using a generalization of Moore's Law that says that processing power should double every 18 months (I know, that's not the real law), and given that approximately 12 18month periods have passed since then, computers should be 4,000 times as powerful. And sure enough, you can find supercomputers with terabytes of RAM, and the laptop I just bought has 8GB of RAM, which is 4,000 times what was common then. I am actually kind of amazed at how accurate this rule of thumb is.

However, my programming goals apparently grow just as fast. Just the other day, as I was practicing for programming contests, I tried to allocate a 4 terabyte array. Needless to say, my program failed. And for some reason, instead of just crashing, it ground my computer to a halt, eventually requiring a reboot. I suspect in another two decades I'll be crashing programs by trying to allocate exabyte arrays.

Conclusion
For many business or web apps, network or database latency is going to be your biggest bottleneck. Because of this we often treat memory as infinite and processing time as zero. The emphasis on writing readable, maintainable code as opposed to the most efficient is typically the right trade-off. However, memory isn't infinite, and processing time isn't zero. Before coding a module that requires pulling your entire database into memory, think about whether this is a couple megabytes of memory or a hundreds of terabytes.  Modern computers are powerful, but they still aren't as powerful as we'd all like.

Rails form_for_hash

Ruby on Rails has some nice form building helpers if you are building an HTML form for populating an ActiveRecord model. But what if you want your front end forms to not exactly map to your back end models? Maybe you are presenting a logical view that corresponds to parts of different models. Well, Rails still provides helpers that let you roll your own form. However, now you have to manually handle reading and writing values to the form. It would be nice if you could get the form_for functionality with just a simple Hash.

Well, it turns out that with a little bit of work, you can. Based on an idea I found at http://pullmonkey.com/2008/1/6/convert-a-ruby-hash-into-a-class-object/, I created a simple Object which wraps a Hash and behaves like an ActiveRecord. This class looks like:

class HashObject
  def initialize(hash={})
    @hash = hash
  end

  def method_missing(sym, *args, &block)
    @hash[sym]
  end
end

Then to make it easy to use, I put a helper function in helper/application_helper.rb

def form_for_hash(hash, name, url, html_options={}, &proc)
  object = HashObject.new(hash)
  form_for object, :as=>name, :url=>url, :html=>html_options, &proc
end

Now I can use it in the view as such:  (e.g. new.html.haml)

= form_for_hash @person, :person, special_people_path do

  = f.label :first_name, 'First Name'
  = f.text_field :first_name

  = f.label :last_name, 'Last Name'
  = f.text_field :last_name
  %br
  = f.label :phone_number, 'Phone Number'
  = f.text_field :phone_number
  -# etc etc etc

Then in your SpecialPeopleController you would have methods like

def new
  @person = {:first_name=>'Jenny', :phone_number=>'867-5309'}
end

def create
  @person = params[:person]
  # logic for populating/updating models based on hash goes here
end

And that is all you need to do to be able to use a Hash to populate your forms.

Programming Contests and Languages

This past weekend was the qualifying round for the Google Code Jam. Google allows you to use any language you would like in this contest. This year I have decided to use Ruby as my language of choice. In the past I have always used Java, as that is the language that I currently know the best. However, I think Ruby will allow me to write cleaner, more compact code which will let me code faster and hopefully write fewer bugs.

Simplicity

Why do I think this? Let me give you a simple example. A common task in these contests is to be able to read in a line of space separated integers and convert it into an array for later processing. Here is how I accomplish this task in Java:

  1 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  2 String[] parts = reader.readLine().split(" "); 
  3 int[] array = new int[parts.length]; 
  4 for (int i = 0; i < array.length; i++) {
  5   array[i] = Integer.parseInt(parts[i]); 
  6 }

Here is how I do the same thing in Ruby:

array = gets.split.map { |i| i.to_i}

Bugs
Imagine I now want to loop through the array and determine how many array elements are the same as their position. I.e. if I have the array [0, 2, 1, 3, 5, 4], elements 0 and 3 are the same as their index and so I'd want to get a value of 2. Here is Java code that accomplishes this task:

  1 int count = 0;
  2 for (int i = 0; i < array.length; i++) {
  3   if (array[i] == i) count++; 
  4 }

Here's Ruby code that does the same thing:

count = 0
array.each_index {|i| count += 1 if array[i] == i }

Now these two code samples are almost identical. Some people would argue that its just a matter of style which you prefer. However, as someone who has written countless loops like this under the time pressure of programming contests I can tell you there is one crucial difference. In the Java code I am explicitly incrementing the index variable i in the for loop and checking it against the length of the array. In Ruby, the method each_index does this for me. Why does this matter? Well, imagine that you have nested loops. Well, it can be really easy to accidentally write your inner loop like:

for (int j = 0; j < array2.length; i++)

and now you suddenly have an infinite loop. More insidious, you could write:

int[][] map = new int[ROWS][COLS]; 
for (int r = 0; r < map.length; r++) 
   for (int c = 0; c < map.length; c++)
     array[r][c] = r + c;

when you meant to write the column loop:

for (int c = 0; c < map[r].length; c++)

and now you have code that works whenever ROWS == COLS, but not otherwise.

Having had many conversations with other competitors at contests, I can tell you that I am not the only one who has wasted large amounts of time tracking down dumb bugs just like these. Nor am I the only one who has unknowingly submitted a buggy solution because I only tested on square maps, and so failed a problem because of such a silly bug. My hope is that by using Ruby I will spend less time dealing with bugs like this, allowing me more time to actually solve the problem at hand.

Performance
Here's the catch. The dynamic aspect of Ruby comes at a cost. Many problems in programming contests like the Google Code Jam are very computationally intensive and there is always a time limit for how long your code can run. In fact GCJ's FAQ warns that Python's slowness may cause problems for you on some problems. My assumption is that Ruby has similar performance characteristics to Python, so I decided to do some simple comparison's between Ruby and Java performance on some programming contest type tasks.

Test 1
As my first test, I came up with a solution for GCJ's 2008 Round 1B's Problem C. Mousetrap. My Ruby solution takes about 40 seconds to correctly process Google's large input set. The same algorithm in Java takes about 4 seconds to process the same data set.

Test 2
My second test was based on a suggestion of a friend who was inspired by Problem D. GoroSort on this year's qualification round. What I did was write a program which creates every permutation of N integers, and then for each permutation counts up how many numbers are the same as their index. In addition to Java and Ruby, I dusted off my C and wrote a C implementation, as well, for comparison. Here are the results I get on my Macbook Pro. (all values are in seconds)

N	Ruby	Java	C
6	0.015	0.20	0.003
7	0.028	0.21	0.004
8	0.15	0.22	0.007
9	1.3	0.24	0.021
10	14	0.55	0.16
11	160	3.9	2.4
12	1,980	43	36

Conclusion
There is a definite and meaningful difference in performance between Ruby and the other languages for larger data sets. Still, for the majority of problems Ruby will be fast enough. I will just need to make sure I do a big-O analysis of my algorithms before I implement them, and if there is any doubt as to performance, write it in Java rather than Ruby. For any problems where speed doesn't look to be an issue, I think I will try to use Ruby. Hopefully this will work for me.

Session Timeouts on Rails

Session Timeouts are a perfect example of the conflict between usability and security. From a security standpoint you don't want to leave a user logged in for an extended time period, because someone else may get access to their browser and then act as that person. As an example I have a a Facebook friend who frequently has posts made in her name by friends who get a hold of her phone. On the other hand, as a user, it is really frustrating when I have to keep logging back into a site.

In general, be only as secure as you need to be. I am ok with my bank logging me out after a short period of inactivity. However, I am willing to risk the occasional prank post on Facebook to not have to keep logging back in. As long as the social sites require a re-entering of a password before allowing a password change or any other personal information changes, they are secure enough from my point of view.

Session Expiration Tasks
If you want to expire sessions, you need to do a couple of things:

• Keep track of the time of the user's last action
• Show the timeout on the client side, by having a javascript function running on the browser which will load the login page after the session has timed out
• Enforce the timeout on the server side by having the server redirect to a login page if a different page is requested after a timeout
• Make sure the redirect also happens on Ajax updates

Rail Implementation
For purposes of this code, I am assuming that you have a login system like shown in Michael Hartl's "Ruby on Rails Tutorial".

Tracking Timeout
 Following the example I found at http://snippets.dzone.com/posts/show/7400 I made my ApplicationController look like:

class ApplicationController < ActionController::Base
  protect_from_forgery
  before_filter :session_expiry
  before_filter :update_activity_time

  include SessionsHelper

  def session_expiry
    get_session_time_left
    unless @session_time_left > 0
      sign_out
      deny_access 'Your session has timed out. Please log back in.'
    end
  end

  def update_activity_time
    session[:expires_at] = 30.minutes.from_now
  end

  private

  def get_session_time_left
    expire_time = session[:expires_at] || Time.now
    @session_time_left = (expire_time - Time.now).to_i
  end

end

In this code we store an expiration time in the session scope, and we make sure the session hasn't expired before performing any actions. update_activity_time accomplishes the goal of tracking the user's last action and session_expiry enforces the timeout.

Support Ajax Calls
A complication comes up if your web application has Ajax calls. If an Ajax request comes in after the session times out you want to do a full page redirect to the login page, not just a partial update. To accomplish this I modified the deny_access method in the SessionsHelper module to look like:

def deny_access(msg = nil)
  msg ||= "Please sign in to access this page."
  flash[:notice] ||= msg
  respond_to do |format|
    format.html {
      store_location
      redirect_to signin_url
    }
    format.js {
      store_location request.referer
      render 'sessions/redirect_to_login', :layout=>false
    }
  end
end

As you can see, on an Ajax call we store the referrer, i.e. the page that the user was on when they made the Ajax call, and then render a javascript fragment. The file 'views/sessions/redirect_to_login.js.haml' just consists of the one line of javascript:

window.location.replace( '#{escape_javascript signin_url}' );

which tells the browser to redirect to the login page.

Client Side Timeout
It can be a frustrating user experience to perform an action on a page, only to find out that you have timed out. Since we've already decided that we will timeout the user, we can't prevent that behavior, but we can at least let the user know they have timed out by automatically redirecting them to the login page when they time out. To accomplish this we add the following javascript lines to our public/javascripts/application.js file

function checkSessionTimeout(url) {
 $.getScript(url);
}
function setSessionTimeout(url, seconds) {
 setTimeout("checkSessionTimeout(\'" + url + "\')", seconds*1000 + 15);
}

checkSessionTimeout is just a method which makes an Ajax call (using jQuery) to a URL and executes the returned javascript. setSessionTimeout sets a javascript timeout to call checkSessionTimeout after the specified delay.

To call these functions we add the following to our views/layout/application.html.haml

-if @session_time_left
  :javascript
    $(function() {
      setSessionTimeout('#{check_session_alive_sessions_path}', #{@session_time_left})
    });

Basically, if the @session_time_left variable is set, we use the jquery functionality to call the setSessionTimeout method when the page has been loaded. We pass the url that corresponds to the check_session_alive action on the sessions controller which looks like:

def check_session_alive

  get_session_time_left
  if @session_time_left > 0
    render 'sessions/check_session_alive', :layout=>false
  else
    sign_out
    deny_access 'Your session has timed out. Please log back in.'
  end
end

If the session has timed out, we just call deny_access which we showed above and already handles the redirect. If the session hasn't timed out, we render sessions/check_session_alive.js.haml which just calls setSessionTimeout again, with the new timeout value:

setSessionTimeout('#{check_session_alive_sessions_path}', #{@session_time_left})

One Catch
We don't want to enforce that the session is valid on the session actions like login, logout, and check_session_alive. To fix this we add the following to the top of our SessionsController:

class SessionsController < ApplicationController

  skip_before_filter :session_expiry
  skip_before_filter :update_activity_time

Conclusion
With that you have a bare bones session expiration system on your Rails app. I will leave it as an exercise to the reader to add extra features, like giving a user a 5 minute warning that they are about to be logged out.