Aaron Feng

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

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.

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.