A few weeks ago, Amazon.com added a nice benefit to Amazon Prime membership, free video streaming. They don't (yet) have a catalog as extensive as say, Netflix, but there is enough to be interesting. I've finally seen all the Steig Larsson, "Millenium Series" movies, so I know what people who mention "The Girl with the Dragon Tatoo" are talking about. They seem to have at least one story from each of the many Doctors Who. More recently I got into a series of documentaries on design related topics.

My talents like more in programming, but I've always had an interest in the arts. My grandfather, and his father before him, were jewelers and engravers. My uncle had a successful career as a graphics artist and corporate identity executive in several large companies. I got very interested in graphic design when graphical user interfaces and desktop publishing came into vogue in the mid-1980s, albeit more from an "art appreciation" viewpoint than an ability to produce good art.

Now there's not much directly applicable to web design in these, but I recommend them for your viewing pleasure:

• Helvetica - covers the Swiss design movement from the 1950s, particularly the Helvetica font, which is probably the most use font of all.
• Objectified - talks mostly about product design, with interviews with designers including Jon Ives of Apple, and Chris Bangle, late of BMW.
• Milton Glazer: To Delight and Inform - Milton Glazer was in a sense the American answer to the Swiss design movement. He is quite prolific. Among other things he started New York Magazine, and has done many magazine designs, he also did the iconic Bob Dylan in silhouette with multi-colored hair poster, the I HEART NY logo, and many other iconic designs. The documentary basically interview him at work, home and at the site of some of his projects.

Original article writen by Rick DeNatale and published on Talk Like A Duck | direct link to this article | If you are reading this article elsewhere than Talk Like A Duck, it has been illegally reproduced and without proper authorization.

My friend Brian Adkins just published an article on his blog comparing the performance of his Haskell program to find the longest palindrome in a string to a similar program in Ruby.

His Haskell program runs 25 times faster than his Ruby program. He reports that the Haskell program takes 7 times as long to process an input twice as long.

Brian's approach is to generate all of the substrings in the input string, then filter that list of substrings to those which are palindromes, and then output the longest one which passes through that filter. A cursory analysis indicates that this is O(n^2) which is in-line with his data.

I couldn't resist, so I sat down with my MacBook and my Sunday morning coffee and wrote my version of the program, in about 30-45 minutes.

My first thought was that we want to cut down on the search space, by only examining substrings that could be palindromes. By definition a palindrome starts and ends with the same character, so we only need consider such substrings. It took a few minutes to find a reasonable approach.

My basic idea was to start by looking for the initial substrings of the string ending with the first character, then do the same for subsequent characters. Then it occurred to me that I should find the LONGEST initial substring, since if it were a palindrome shorter substrings can't be longer.

In pondering the best way to do this in Ruby, and thinking about using a regular expression, I realized that rather than starting with the beginning of the string, it would be better to start at the end. I could then use Ruby 1.9's String.match(regexp, pos), to find the longest substring at the end of the string starting and ending with the same character, using the pos parameter to search for a shorter string when the last match is not a palindrome.

So in the end my algorithm examines each initial substring of the input string starting with the longest. For each of those it examines the final substrings which begin and end with the same character, again starting with the longest, and returns the longest of those which is a palindrome. The result of the overall program is the longest palindrome from any initial substring.

Here's the code:

  TEXT = <<END
  I'll just type in some example text here and embed a little
  palindrome - A man, a plan, a canal, Panama! - I expect that will be
  the longest palindrome found in this text.
  Lorem ipsum dolor sit amet, consectetur adipiscing elit.
  Integer volutpat lorem imperdiet ante bibendum ullamcorper. Mauris
  tempor hendrerit justo at elementum. Vivamus elit magna, accumsan id
  condimentum a, luctus a ipsum. Donec fermentum, lectus at posuere
  ullamcorper, mauris lectus tincidunt nulla, ut placerat justo odio sed
   odio. Nulla blandit lorem sit amet odio varius nec vestibulum ante
  ornare. Aliquam feugiat, velit a rhoncus rutrum, turpis metus pretium
  dolor, et mattis leo turpis non est. Sed aliquet, sapien quis
  consequat condimentum, sem magna ornare ligula, id blandit odio nisl
  vitae erat. Nam vulputate tincidunt quam, non lacinia risus tincidunt
  lacinia. Aenean fermentum tristique porttitor. Nam id dolor a eros
  accumsan imperdiet. Aliquam quis nibh et dui ultricies cursus. Nunc
  et ante non sapien vehicula rutrum. Duis posuere dictum blandit. Nunc
  vitae tempus purus.
  END

  def clean(str)
    str.gsub(/[^A-Za-z]/,'').downcase
  end

  class String
    def palindrome?
      self == self.reverse
    end

    def longest_palindrome_at_end
      first_possible_start = 0
      end_match_regexp = /#{self[-1]}/
      palindrome = nil
      while (palindrome.nil? && (candidate_start = self.match(end_match_regexp, first_possible_start)))
        candidate_index = candidate_start.begin(0)
        candidate = self[candidate_index..-1]
        if candidate.palindrome?
          palindrome = candidate
        else
          first_possible_start = candidate_index + 1
        end
      end
      palindrome || ""
    end

    def longest_palindrome
      longest = ""
      self.size.downto(1) do |last|
        break if last < longest.size
        candidate = self[0,last].longest_palindrome_at_end
        longest = candidate if candidate.size > longest.size
      end
      longest
    end
  end

  require 'benchmark'

  double = TEXT + TEXT

  puts Benchmark.measure {puts clean(TEXT).longest_palindrome}
  puts Benchmark.measure {puts clean(double).longest_palindrome}

And here's the output:

  amanaplanacanalpanama
    0.110000   0.000000   0.110000 (  0.110347)
  amanaplanacanalpanama
    0.470000   0.000000   0.470000 (  0.463541)

Now my MacBook Pro is a little newer than Brian's, it's a late 2009 model, with a 2.66 GHz Core 2 Duo. But my version is 36x faster (.11 vs. 4 seconds) than Brian's Haskell program, and 891x faster than his Ruby program. Hence the title of this article!

Original article writen by Rick DeNatale and published on Talk Like A Duck | direct link to this article | If you are reading this article elsewhere than Talk Like A Duck, it has been illegally reproduced and without proper authorization.

Yesterday, I happened to catch a bit of the annual Macy*s Thanksgiving Day Parade in New York.

In particular I saw Arlo Guthrie and his daughter perform Arlo's father, Woody's, song "This Land is Your Land" while standing in front of a giant Turkey on the Ocean Spray cranberry float.

I was struck by the combination of Arlo's still youthful face, framed by long white hair. Arlo is getting on in years. Thankfully he has outlived his father, who died of Huntingdon's disease at age 55 by some 8 years.

As an aside, although I grew up in the Connecticut suburbs of New York City, I've only gone to the Macy*s parade once in 1997, after I'd moved to North Carolina. That day was very windy and the crews handling those big parade balloons had their hands more than full. The Cat in the Hat balloon knocked over a lamp post, and a parade-goer was struck in the head with falling debris and suffered a month-long coma, my wife and I witnessed the Barney the Dinosaur being stabbed and stomped on by police to avert another accident. "Oh, the humanity!"

And I was reminded of Arlo again today when Andy Ihnatko picked the song Alice's Restaurant Massacree for his Amazon advent calendar.

For those readers of tender years who might not be familiar with Arlo and Alice's Restaurant, the song tells the tale of a communal Thanksgiving feast in a deconsecrated church in Great Barrington, Massachussetts, the home of his Alice and Ray Block. After the dinner Arlo and a friend volunteered to get rid of the post-feast trash, and loaded it into a VW Microbus, bound for the dump, only to find that the dump was closed for the holiday. So they dumped the trash over a fifteen foot cliff by a country road on top of a pile of trash that was already there, figuring "one big pile is better than two little piles." Two days later they were arrested for littering, when the local constable Officer Obie (no his last name wasn't Fernandez) discovered an envelope with Guthries name on it under the pile of garbage, and Arlo when asked about this said "Yes, sir, Officer Obie, I cannot tell a lie, I put that envelope under that garbage."

This led to a trial, for which he was fined $50 and ordered to pick up the garbage.

The story continues when Guthrie was later ordered to report for induction into the Army. Again, for the benefit of my younger audience, I probably need to explain that, during the Vietnam War, the US had a military draft, unlike today's "volunteer" military which attracts recruits out of a mixture of patriotism and economic necessity.

The upshot of the story was that after going through a series of medical examinations at the induction center, he was nearing being sworn into the Army, except that "the last man" asked a crucial question, "Kid, we only got one question. Have you ever been arrested?"

In reply Arlo told the tale of his conviction for littering, and was sent to the "Group W" bench.

Here's how Arlo decribes Group W.

" Group W's where they put you if you may not be moral enough to join the army after committing your special crime, and there was all kinds of mean nasty ugly looking people on the bench there. Mother rapers. Father stabbers. Father rapers! Father rapers sitting right there on the bench next to me! And they was mean and nasty and ugly and horrible crime-type guys sitting on the bench next to me. And the meanest, ugliest, nastiest one, the meanest father raper of them all, was coming over to me and he was mean 'n' ugly 'n' nasty 'n' horrible and all kind of things and he sat down next to me and said, "Kid, whad'ya get?" I said, "I didn't get nothing, I had to pay $50 and pick up the garbage." He said, "What were you arrested for, kid?" And I said, "Littering." And they all moved away from me on the bench there, and the hairy eyeball and all kinds of mean nasty things, till I said, "And creating a nuisance." And they all came back, shook my hand, and we had a great time on the bench, talkin about crime, mother stabbing, father raping, all kinds of groovy things that we was talking about on the bench.

After that a sergeant came over and gave him a long form to fill out with the details of his crime, ending with the question "Have you rehabilitated yourself?" Arlo took the form to the sergeant and said:

"Sergeant, you got a lot a damn gall to ask me if I've rehabilitated myself, I mean, I mean, I mean that just, I'm sittin' here on the bench, I mean I'm sittin here on the Group W bench 'cause you want to know if I'm moral enough join the army, burn women, kids, houses and villages after bein' a litterbug." He looked at me and said, "Kid, we don't like your kind, and we're gonna send your fingerprints off to Washington."

So What Does This Have to Do with Ruby?

I'm glad you asked that question.

The answer is that the main enumeration method names of Ruby, collect, select, reject, inject... came to Ruby from the Alice's Restaurant Massacree, indirectly via Smalltalk.

Some Ruby programmers, seem to have an aversion to the inject method. It seems particularly irksome to programmers who have come from languages which use map and reduce for collect and inject. Later ruby versions have made aliased map and collect, and reduce and inject. But this leaves map as taking an optional argument, which if passed is used as an artificial first element to be effectively pre-pended to the enumeration being mapped. That optional argument and the name inject comes from Smalltalk's inject:into: method which makes sense to a Smalltalk programmer since you are injecting that initial value into a reduction of the collection using the block given by the second argument. Smalltalk programmers get used to passing the 'right' value for that argument, for example if inject is used to sum a collection the initial argument is normally the identity value for addition, e.g. 0, or might be something else if we want to add the sum to another value.

A couple of months ago, I was listening to a podcast interview with Dan Ingalls who was the first implementor of Smalltalk, and probably the key contributor as Smalltalk evolved from Smalltalk from Smalltalk-71, through Smalltalk-72, and Smalltalk-76 up through Smalltalk-80 which is what most people think of as Smalltalk today. During the interview he was asked about the origin of those enumeration methods of the Smalltalk collection classes. Alan Kay had told the interviewer that they had come from a song. At first Dan didn't remember this but then remembered that there was a song which had a string of words like inject, select, detect etc. As far as I recall, though he didn't name the song.

But I recognized it right away, here's how "Alice's Restaurant Massacree" transitions from the littering trial to the draft:

Came to talk about the draft. They got a building down New York City, it's called Whitehall Street, where you walk in, you get injected, inspected, detected, infected, neglected and selected.

So Dan picked the collection enumeration method selectors in Smalltalk from "Alice's Restaurant", no doubt. I suspect that that initial argument of inject:into: came about because he wanted to use that pattern and map and reduce didn't fit. Actually I'm not sure that map and reduce were commonly used terms at that time.

So if you don't like inject in Ruby, don't blame Matz, blame Dan and Arlo!

Original article writen by Rick DeNatale and published on Talk Like A Duck | direct link to this article | If you are reading this article elsewhere than Talk Like A Duck, it has been illegally reproduced and without proper authorization.

One of the oldest Rails plugins is annotate_models which was originally written by Prag Dave Thomas. For those few of you who might not have run across it, it adds a comment block at the top of a rails active record model class with the relevant section from db/schema.rb.

I'd fallen out of using it, just falling into the habit of opening up schema.rb and searching for the model name. But I got the yen the other day to start using it again.

Google alerted me to what seems to be a popular, modernized fork, maintained by Cuong Tran, who gemified it and expanded the function. It now annotates things like model specs, fixtures (if you are still using them) and various fixture replacement files like machinist blueprints. It also provides a separate command/rake task for annotating your config/routes.rb with the output from rake routes.

Installing the gem provides an annotate gem binary with which you can manually produce these annotations.

The readme claims that installing it as a plugin also modifies the the db:migrate rake tasks to automatically run schema annotation to keep in sync with what your migrations are doing to the schema. But plugins are a bit passé in Rails 3. I wanted to install the gem with bundler, after which it took me a bit of experimentation to get automatic annotation.

After playing around with it for awhile I came up with this. First I added the annotate gem to the development group in my Gemfile. Then I added the following file which I called 'annotations.rake' to lib/tasks in my Rails 3 project:

  require 'annotate/annotate_models'

  def annotate_models
    AnnotateModels.do_annotations(
     :position_in_class => 'before', 
     :position_in_fixture => 'before'
     )
  end

  namespace :db do
    task :migrate do
      annotate_models
    end

    namespace :migrate do
      [:up, :down, :reset, :redo].each do |t|
        task t do
          annotate_models
        end
      end
    end
  end

It's pragmatic, it works, although I guess I'm a bit exposed to changes in the annotate gem. I think the right way to do this would be to fork annotate on github, and change it to register the rake task using a railtie, and then issue a pull request, but I guess I'm being lazy.

Original article writen by Rick DeNatale and published on Talk Like A Duck | direct link to this article | If you are reading this article elsewhere than Talk Like A Duck, it has been illegally reproduced and without proper authorization.

I just pushed two versions of the anniversary gem

Version 1.0.2 fixed a bug which I found when trying to answer one of the comments on my original blog post. It was an edge case which returned one two many months and a negative day count.

But I also realized in responding to the comment which exposed the bug, that I had a minor misconception about where extra monthiversaries should fall in March. I've now fixed that so that they always fall on March 1.

Since this is a breaking change, I've bumped the major version number to 2

Date calculations are just inherently complex!

Original article writen by Rick DeNatale and published on Talk Like A Duck | direct link to this article | If you are reading this article elsewhere than Talk Like A Duck, it has been illegally reproduced and without proper authorization.