Aaron Feng

My company has hosted the last two Philly Lambda meetings. Toby DiPasquale gave the first presentation on Scala then Kyle Burton gave a presentation on Lisp. Both presentations were very interesting especially for a functional noob like me. There's a wealth of information amongst this group of people, so it's definitely a good experience.

Currently there are around 60 people on the mailing list. However, there's not much discussion happening on it right now. Hopefully it will pick up eventually. I'm definitely looking forward to seeing what's coming up next.

Well, not in a forever way. Ruby is the language I use mostly on my own time. Since my free time is very limited, I need to shelf it for now. Making room for me to hack some lisp.

Like many people, my free time comes in small chunks. I have been using project euler as a way to learn new languages (also math). The code required to solve each problem is usually very short (30 lines or less). I can usually fit each problem into my small chunks of time very easily. It's a great way to get your hands dirty on the language you want to learn.

For those who follow my blog, you probably noticed that I have been posting project euler solutions in ruby. Since I'm trying to learn lisp now, I'll start to solve the problems using lisp. I'll post the rest of my solutions written in ruby in the following post.

Overall, I still enjoy using ruby. The lack of free time has forced me to make this hard decision.

A couple of months ago I wrote a utility that will download a web page with all the dependencies (css, and images) to your hard drive. All the references in the web page will be changed to refer to your local copy.

I wrote it as a prototype, and it took me 30 to 40 minutes to write it, so I'm sure there is room for improvement. I pointed to a few web pages, such as amazon, ebay, google, and my blog it worked pretty well!

The code requires Why the lucky stiff's Hpricot library. With out further adieu, here is the code below:

require 'rubygems'
require 'hpricot'
require 'open-uri'
require 'rio'

module Hpricot
  class Elem
    def is_css
      if self.name == "link"
        self["type"] == "text/css"
      else
        false
      end
    end
    def is_full_path
      if self.name == "link"
        self["href"][0..6] == "http://"
      elsif self.name == "img"
        self["src"][0..6] == "http://"
      else
        false
      end
    end
  end
end

if ARGV.size.zero?
  puts "Missing web page you wish to snatch."
  exit
end

url_scheme = "http://"
url = ARGV[0]
doc = Hpricot(open(url_scheme + url))

Dir.mkdir(url) unless File.directory?(url)

doc.search("link") do |item|
  if item.is_css
    if item.is_full_path
      rio(item['href']) > rio(url)
    else
      rio(url_scheme + url + item['href']) > rio(url)
    end

    # nested style sheets in another style sheet
    css_path = File.dirname(item['href'])
    css_file = File.basename(item['href']).scan(/(.*?\.css)/m).flatten.to_s

    file = File.open(url + "/" + css_file,"r")

    inner_css = file.read.scan(/@import '(.*?\.css)';/m).flatten
    inner_css.each do |css|
      css_url = url_scheme + url + css_path + "/" + css
      rio(css_url) > rio(url)
    end
    file.close

    item['href'] = css_file
  end
end

doc.search("img") do |item|
  if item.is_full_path
    rio(item["src"]) > rio(url)
  else
    rio(url_scheme + url + item["src"]) > rio(url)
  end
  item["src"] = item["src"].split("/")[-1]
end

File.open(url + "/" + url + ".html", "w") do |file|
  file << doc.to_s
end

Learning Lisp has been a challenge so far. I'm plunging my way through Practical Common Lisp at a decent pace though. Learning Lisp development environment is another story. Since all the hardcore Lisp hackers are all using emacs with slime I figured I would do the same. I have no previous experience with emacs, so I'm simultaneously learning 3 things at once.

One night I came across Maco Baringer's slime video. After I watched the video, all the dots in my head started to connect. In the video, Maco demonstrated the usage of slime while he developed a morse code application. I kept rewinding to figure out the key strokes used. Recently Peter Christensen wrote a transcript for the slime video. This made the video much easier to follow. Christensen also has a transcript for Baringer's Hello World video using Uncommon Web framework.

Besides the transcripts, Christensen is also working on emacs/slime cheat sheet. As a noob learning Lisp, I need all the help I can get.

For the past few weeks I have been playing around with Lisp during pretty much all my free time. Yes, Lisp. This is not my first encounter with Lisp. I played around with Lisp when I was in college, and I hated every moment of it. Functional languages have always been foreign to me, and I tried to stay far away from that path. I'm at the point in my career I can no longer ignore the existence of functional languages.

Last year I decided to learn Erlang since it received a lot of buzz in the community. Shortly after learning the basics, I lost interest. Even though I no longer keep up with Erlang on a regular basis, it has eased me into the realm of functional languages.

Back in 2004, I read Hackers & Painters by Paul Graham. The chapter entitled "Beating the average" has stuck in my mind since I first read it. In this chapter, Graham described how he was able to overtake the big corporations during the internet boom using an unconventional programming language: Lisp. I decided to give the chapter another read to refresh my mind. After reading it again, I was inspiredto give Lisp another try. To setup my Lisp environment, I installed emacs, slime, and sbcl on my macbook.

After going through a few online Common Lisp tutorials, I just couldn't get enough of it. The more I learned about it, the deeper I wanted to understand.Eventually I stumbled on to Practical Common Lisp book by Peter Seibel. The book is very well written and easy to read. By the nature of the language, Lisp tends to be more theoretical. Seibel connected the theoretical with the practical which made the book relevent and enjoyable. Best of all, the whole book is freely available online. Even if you have no desire to learn Lisp, just read the first 3 chapters (they are very short). Who knows, you might just continue to read the whole thing.

6. What is the difference between the sum of the squares and the square of the sums?

start = Time.now
sum_of_squares = 0
square_of_sums = 0

(1..100).each do |n|
  sum_of_squares = sum_of_squares + n ** 2  
  square_of_sums = square_of_sums + n  
end

puts "Took: #{Time.now - start} seconds"
puts (square_of_sums ** 2) - sum_of_squares

Took: 0.000165 seconds

7. Find the 10001st prime.

max = 150000
table = {}
prime = [] 

start = Time.now

(2..max).each do |n|
  table[n.to_s] = n
end

(2..(max + 1 / 2)).each do |n|
  unless table[n.to_s].nil? then prime << n; end
  if prime.length >= 10001 then break; end
  index = n + n 
  while index <= max
    table.delete(index.to_s)
    index = index + n
  end
end

puts "Took: #{Time.now - start} seconds"
puts "#{prime.length} prime is #{prime.last}"

Took: 2.576914

8. Discover the largest product of five consecutive digits in the 1000-digit number.

lines = DATA.readlines

greatest = 0
greatest_5 = []

start = Time.now

lines.each do |line|
  line_chars = line.split(//)

  while not line_chars.empty?
    result = 1
    next_5 = line_chars.slice(0,5)

    next_5.each do |n|
      result = n.to_i * result
    end

    if result > greatest
      greatest = result
      greatest_5.replace(next_5)
    end

    line_chars.slice!(0,1)
  end

end

puts "Took: #{Time.now - start} seconds"
puts "#{greatest}"
__END__
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Took: 0.0071 seconds

9. Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

start = Time.now
(1..1000).each do |a|
  ((a + 1)..1000).each do |b|
    a_2 = a ** 2
    b_2 = b ** 2
    c = Math.sqrt(a_2 + b_2)
    if c == c.to_i
      c = c.to_i
      c_2 = c ** 2

      sum =  Math.sqrt(a_2) + Math.sqrt(b_2) + Math.sqrt(c_2) 

      if sum == 1000 
        puts "Took: #{Time.now - start} seconds"
        p "#{a} + #{b} + #{c} = #{a + b + c}"
        p "Product is #{a * b * c}"
        exit
      end     
    end
  end
end

Took: 0.522663 seconds

10. Calculate the sum of all the primes below two million.

start = Time.now

max_prime = 2000000 
table = {}
(2...max_prime).each do |n|
  table[n.to_s] = n
end

(2...(max_prime / 2)).each do |n|
  index = n + n 

  while index < max_prime
    table.delete(index.to_s)
    index = index + n
  end
end

result = 0

table.each do |k,v|
  result = result + v
end

puts "Took: #{Time.now - start} seconds"
puts "Result is: #{result}"

Took: 48.149662 seconds

A few days ago I came up with an idea for a side ruby (possibly using rails too) project. After doing the initial research, I realized it makes more sense to test out the idea on Linux instead of OS X. I don't want to change the setup of my MacBook since I'm just toying with the idea, so I decided to install Linux using Parallels. Parallels is a virtual machine for Mac that is capable of running any operating system.

There has been a lot of hype around Ubuntu, so I decided to give it a try. The latest version at the time of this writing is 7.10 (codename Gutsy Gibbons). Installing Ubuntu on my MacBook via Parallels was a much more difficult task than I expected. Shortly after I started the installation, I was faced with the following error:

The display server has been shut down about 6 times in the last 90 seconds

After some googling, I found the fix on Shane Duffy's blog - Ubuntu 7.10 Install guide - Parallels Macbook pro. The installation worked as expected. However, Unbuntu wasn't able to connect to the internet during the installation, so the software package management system (apt-get) configuration file was commented out. apt-get is similar to MacPorts on Mac. I uncommented all the locations in the /etc/apt/source.list. I ran the following command to get the system up to date:

apt-get update
apt-get dist-update

The apt-get is pretty slick. Learning more about it will definitely pay off in the future. A good place to start is the AptGetHowto.

Moving on to the ruby and rails installation. apt-get wants to manage all the packages it installs, so installing gem using apt-get won't be feasible. Walter Wilfinger has posted complete instructions on how to get ruby and rails running in his post Installing Ruby and Ruby on Rails in Ubuntu 7.10 Gutsy Gibbon.

Last but not least, I found it annoying that I can't use the apple key as control key in Ubuntu. Once again I found a post written by Stuart Colville on how to remap the apple keys.

Wait, the system is not complete if you can't watch videos on youtube. When I tried to open a video on youtube firefox prompted me to install the missing flash plugin. Don't install it, it won't work. Download the Linux flash player from Adobe from here. Open a terminal window and run the following commands:

# exist firefox before running these commands
tar xvfz install_flash_player_9_linux.tar.gz
cd install_flash_player_9_linux
./flashplayer-installer
# at this point, the installer should ask you where the firefox
# directory is, it should be in /usr/lib/firefox

Overall, the installation went well, but was time consuming. There were some pitfalls, but they were easy to overcome. Ubuntu runs well on my MacBook with Parallels (I'm actually blogging from it). I'm sure it would run even better on a MacBook Pro. I really enjoy having a complete separate environment for development. I have complete freedom of experimenting with different things without worrying about messing up my system. If you ever wanted to play around with Ubuntu on a Mac, Parallels is definitely the way to go. If this works out well, I might just keep all my development stuff on a separate Parallels image.

Click on each problem for a more detailed solution.

1. Add all the natural numbers below 1000 that are multiples of 3 or 5.

start = Time.now
total = 0
(1...1000).each do |n|
  total += n if (n % 3).zero? or (n % 5).zero?
end

puts "Took: #{Time.now - start} seconds"
puts total

Took: 0.000977 seconds

2. Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

start = Time.now
def fib(n1, n2, total)
  return total if n2 > 1000000 
  total += n2 if (n2 % 2).zero? 
  fib(n2, n1 + n2, total)
end

puts "Took: #{Time.now - start} seconds"
puts fib(1, 2, 0)

Took: 1.0e-05 seconds

3. Find the largest prime factor of 317584931803.

def next_prime(start_num, max_num)
  is_prime = true
  prime = 0
  (start_num + 1..max_num).each do |n|
    prime = n
    (2..n - 1).each do |nn| 
      if (n % nn).zero? then is_prime = false; break; end
    end
    if is_prime then break; end
    is_prime = true
  end
  prime
end

start = Time.now
n = 1
biggest_prime = 0
num = 317584931803

while(num != 1 or num > n)
  n = next_prime(n,  num)
  if n > 0
    result = num % n 

    if (result).zero?
      biggest_prime = n
      num = num / n 
    end
  end
  n += 1  
end

puts "Took: #{Time.now - start} seconds"
puts biggest_prime

Took: 0.477182 seconds

4. Find the largest palindrome made from the product of two 3-digit numbers.

start = Time.now
result = 0
left = 0
right = 0

(100...1000).to_a.reverse.each do |l|
  (100...1000).to_a.reverse.each do |r|
    temp = (l * r).to_s 

    if temp == temp.reverse and temp.to_i > result
      result = temp.to_i
      left = l
      right = r
    end     
  end
end

puts "Took: #{Time.now - start} seconds"
puts "#{left} * #{right} = #{result}"

Took: 1.501993 seconds

5. What is the smallest number divisible by each of the numbers 1 to 20?

def is_prime(num)
  if num < 2  then return false; end
  (2..num - 1).each do |n|
    if (num % n).zero?
      return false
    end
  end
  return true
end

def smallest_factor(num)
  (2..num - 1).each do |n|
    if (num % n).zero? then return n; end
  end
  return num
end

start = Time.now
result = 1 
(1..20).each do |n|
  if is_prime(n) 
    result = result * n
  elsif not (result % n).zero? 
    result = result * smallest_factor(n) 
  end
end

puts "Took: #{Time.now - start} seconds"
puts result

Took: 0.00018 seconds

A while back my friend James Horsley told me about Project Euler. I just pushed it onto my stack of things to look into. Recently, I was reminded of it again from Steve Eichert at work, so decided to give a try.

Project Euler contains a collection of mathematical problems ranging in difficulties. A problem can be solved using pencil and paper or using a computer program. The only requirement using a computer program is that it should run under one minute. It's an honor system because all you need to submit is the answer.

My choice of weapon is Ruby. I have been spectating Ruby for the past 5 years (not entirely true, but mostly). I figured it's time to roll up my sleeves. I'll be posting my solutions in batches for those who are interested. In addition to posting the solutions, I'll also post the amount of time each solution took. However, I will not post the answers. You can run the code on your own machine if you wish to see the answers. This way I will not ruin it for people who are interested in solving the problems themselves. All the code has been run on my MacBook on an Intel Core 2 Duo 2.0 Ghz with Ruby 1.8.

This week we upgraded to VS 2008 RTM at work. Our solution contains database scripts for both SQL Server and Oracle. I noticed when I ran the script on an Oracle database via sqlplus an error appeared on the first line of the script. After a closer examination with a Hex editor, VS 2008 apparently inserts 3 non-printable characters in the beginning of a new file. Check out the image below:

I'm not sure why, or what those characters mean, but they seem to be ignored by most Windows programs except for sqlplus.