Talk Like A Duck

Lord Love a Duck!

Posted by Rick DeNatale Sat, 21 Jun 2008 12:08:00 GMT

A bit off the beaten track for this blog, but, “if it quacks…!”

Posted in humor | no comments | no trackbacks

Speaking Tomorrow at Raleigh Ruby Brigade

Posted by Rick DeNatale Mon, 16 Jun 2008 19:16:00 GMT

I’ll be giving a talk on “The Fall and Rise of Dynamic Languages” tomorrow at 7:00 p.m., at Red Hat HQ to the Raleigh Ruby Brigade.

Originally this was going to be a slightly revamped talk I gave some months ago to the local Agile group, with a slight change of emphasis from the history of agile methods to focus more on Ruby and other dynamic languages. It’s morphed into a completely different talk.

I plan to take a journey from the 1970s to today, and compare and contrast static and dynamic languages, and examine the recent resurgence in interest in dynamic languages and virtual machines. Along the way, I’ll have a few things to say about whether or not the recent news from RailsConf about MagLev is hype or reality.

If you’re in the area, please come by. Luckily the salmonella scare will probably keep the supply of (rotten) tomatoes to a minimum, so I should be fairly safe.

Posted in site_news | Tags javascript, ruby, smalltalk, talks | no comments | no trackbacks

How Did You Get Started in Programming

Posted by Rick DeNatale Sun, 08 Jun 2008 03:14:00 GMT

Joe O’Brien wrote an article about How he got started in programming.According to Joe, this is a meme started by Michael Eaton, and Sarah Dutkiewicz. It seemed like fun, so here’s my story, in the same form used by Michael and Sarah.

How old were you when you started programming?

I would have been 18 or 19. It was my freshman year in college (1970/71), but I can’t recall whether it was first or second semester, and my birthday is in December.

How did you get started in programming?

Let me go back just a little bit. When I was in high school, I was very interested in music. I’d played in various rock and blues bands since junior high. My high school in Connecticut was part of a program which taught electronic music. This was a time when synthesizers were just coming to the fore. Walter (now Wendy) Carlos’ album “Switched on Bach” had come out in 1968 when I was a high-school sophomore.

So I started at the University of Connecticut in the fall of 1970 and enrolled in the Electrical Engineering School, with the sole intention of becoming the next Robert Moog. All I really wanted to learn was how to design voltage-controlled oscilators and amplifiers.

One of the courses which all freshman engineers at UConn had to take was a 100 level CE course which consisted of one-half semester of “Engineering Graphics” i.e drafting on a board with a T-Square, Triangles and French-curves, and one-half semester of Fortran I programming on an IBM 1620.

That course got me hooked on programming, and my musical career ended in a hurry.

What was your first language?

As I mentioned it was Fortran I, but I quickly became one of those guys who wanted to dabble with every programming language I could get my hands on.

What was the first real program you wrote?

It’s been so long that I can’t really remember. One of the things I remember from school was writing a compiler as a class project. I also remember a computer architecture (hardware) course, taught by grad student with a recent math MS, who I baffled by designing a computer for the term project which had a very simple hardware design, because it was micro-programmed so the main part of the design was actually firmware. The poor guy didn’t really know what to make of it.

What languages have you used since you started programming?

This is probably not a complete list but:

• PL/I
• Snobol
• Lisp 1.5
• Formac
• 1620 Assembler Language
• PDP 8/5 Assembler Language
• IBM System/360/370 Assembler Language
• APL
• PL/S – an IBM internal mid-level language akin to C but with a PL/I like syntax, and a later variant PL/AS
• Basic – on the APPLE ][
• UCSD Pascal
• C
• Class-C, an object oriented C variant similar to Objective-C which I invented for use within IBM
• Object Pascal (using MacApp)
• C++ (as little as possible)
• Smalltalk – my first real love
• Java – mostly because I had no choice
• Ruby – my current love
• JavaScript – which I’ve decided is my language of the year for 2008.

If you knew then what you know now, would you have started programming?

Only because I can’t figure out how to become a real Rock Star.

If there is one thing you learned along the way that you would tell new developers, what would it be?

Try to get a broad a picture as possible of programming, try to use your knowledge of other languages enhance your learning of new ones instead of inhibiting yourself by misunderstanding how the languages differ from the ones you’ve already used,

What’s the most fun you’ve ever had … programming?

The most enjoyable aspects of programming are the social ones. I was doing pair programming before anyone had coined the term. I remember sessions where two or three guys were working on something, one working the keyboard, one the mouse, and maybe a third kibitzing. Beyond that it’s great to hang out with other programmers whether at local groups or at a conference like OOPSLA or RubyConf and talk about the craft of programming, maybe over a beer or two.

Posted in war_stories | no comments | no trackbacks

Solving the Final Google Treasure Hunt Problem in Ruby

Posted by Rick DeNatale Sun, 08 Jun 2008 01:43:00 GMT

For each of the four questions, I wrote a Ruby program to find the answer.

The final question was probably the hardest, and although it’s still ‘alive’, the spoilers have already started to appear on the internets. Peter Krumins has posted a solution using unix shell commands, so I figured I’d show my Ruby solution

The Problem

As Peter describes the problem is to find the smallest prime number which can be expressed as a sum of several different numbers of consecutive primes. Here’s the question as Google posed it to me:

Note that I’ve got a different set of four numbers of consecutive primes than Peter’s

The Approach

I always try to do ‘the simplest thing that could possibly work.’ Like Peter I had no desire to write a prime number generator. A little googling found me the same source of prime numbers. I figured as a first guess that the answer would probably lie somewhere within the first million prime numbers, so I downloaded that list, and examined the list in Textmate.

As Peter notes, the file has two lines of header, and then several primes in sequence on each line. I just deleted the header lines in Textmate and then wrote a class which would read the file and return each prime number in sequence:

class PrimeReader
  def initialize(file)
    @file = file
    read_line
    yield self
  end

  def next
    read_line if @numbers.empty?
    @numbers.shift.to_i
  end

  def read_line
    @numbers = @file.readline.split(' ')
  end
end

This should be fairly explanatory. PrimeReader reads the file as necessary and hands out each prime number.

Now that I had a source of consecutive primes it was time to write the code to search for the answer. Here’s the outer loop:

processor = Processor.new

File.open("#{File.dirname(__FILE__)}/primes1.txt") do |f|
  PrimeReader.new(f) do | primes |
    until processor.test(primes.next)
    end
  end
end

The real work is done, in the unimaginatively named Processor. The loop reads lines from the PrimeReader until the processor finds the desired prime or end of file generates an exception.

And here’s the Processor class:

class Processor
  def initialize
    @counts = [3, 5, 275, 1167].reverse
    # @counts = [3,6]
    @sums = @counts.inject({}) { |hash, count| hash[count] = []; hash}
    @processed = []
  end

  def test(prime)
    puts "testing #{1+@processed.length}: #{prime} "
    qualifies(prime) || process(prime)
  end

  def qualifies(prime)
    @sums.each_value do | sums |
      return false unless sums.include?(prime)
    end
    report(prime)
    true
  end

  def process(prime)
    @processed << prime
    @counts.each do |count|
      calc_sum(count)
    end
    false
  end

  def calc_sum(count)
    if @processed.length >= count
      @sums[count] << @processed[-count,count].inject(0) { |sum, p| sum + p}
    end
  end

  def report(found)
    puts "Found #{found}"
    @counts.each do | count|
      report_sum(count, found)
    end
  end

  def report_sum(count, found)
    sums = @sums[count]
    sum_start = sums.index(found)
    puts "#{found} = #{@processed[sum_start, count].join(" + ")}"
  end
end

The approach I took was to compute the sums and save them in arrays which in turn are the values for each count used as a key in the hash @sums. I keep each prime in the array @processed which is used to calculate the sums.

I hard coded the parameters in the initialize method, note the commented out assignment to counts, by changing the commenting I could test the code against the example given and show that my code found 41 as the lowest prime expressible by both 3 and 6 consecutive primes.

The test method reports the number and value of each prime it examines, purely as a ‘progress indicator.’ The statment “qualifies(prime) || process(prime)” will return true if qualifies returns a truthy value, otherwise it will invoke process which always returns false.

The qualifies method returns true only if the array for each count contains the current prime, which is the essence of what we are seeking. Otherwise it returns false.

The process method first appends the new prime to @processed, then calculates the sum for each count using the calc_sum method. This method determines if we have enough primes in @processed to calculate the particular sum, and if so calculates the sum and appends it to the array for the count.

Once the answer has been found, the report method prints it and the sums which total to it. The sums are calculated in the report_sum method. This method takes a slice out of the @processed array, consisting of the count elements starting at the index where the answer is found in the particular sums array. A bit of reflection will reveal that this is precisely the primes which add to the answer.

In the case of my parameters, the answer, in case you are wondering is 5,181,901, which was confirmed by Google when I gave my answer. This is the 360,245th prime number by the way.

Performance

Although this might be a bit of a brute force approach, the performance was acceptable.

The biggest feature of Ruby which makes this approach feasible is the copy-on-write nature of Ruby arrays. In Ruby Array#slice (a.k.a. Array#[]) doesn’t copy the elements of the array, it just creates a new Array with an offset from the beginning of the original array and the length of the result. As long as neither Array is changed to affect one of the shared elements, nothing is copied, but when a shared element in the source or result array is changed, Ruby first does the copy to preserve the semantics.

My code does a lot of slicing of the @processed array, but other than appending to the end of the @processed array, the accesses to that array and the slices are read-only, so nothing needs to be copied.

Posted in ruby | 7 comments | no trackbacks