Lazy Evaluation

euler problem #5

2008-05-02T01:40:00Z

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

----

To solve this problem easily, we need to remember that the smallest number that is evenly divisible by two numbers is their least common multiple. Armed with this knowledge (and the fact that ruby already has a least common multiple function!), we can write:

numbers=(1..20).to_a
puts numbers.inject{ |x,n| x.lcm(n) }

So for those of you at SRT (or elsewhere) that still harbor any doubts about ruby, can you beat that?! Fine, ok, so you might say that using a built-in lcm function is kind of lame. So as a bonus, here's how I implemented lcm myself in a cute way using the greatest common divisor:

def gcd(a,b)
if b==0 : a
else
gcd(b, a % b )
end
end

def lcm(a,b)
(a*b)/gcd(a,b)
end

Geeky gear

2008-04-13T03:51:00Z

A while ago, we had a discussion here at the office about nerdy t-shirts. We all know what I'm talking about: usually worn by a male geek/programmer with a neckbeard, a black shirt with a "witty" technical reference. Opinions about these shirts vary among SRT employees: some of us find them funny and even wear them on dates [no report on the results, though], some are skeptical. You might guess that I fall into the second camp. Here are the worst offenders in my book:

The geek love poem...

It's so bad it's good.

The worst one of all. Nearly ubiquitous in computer science buildings on campuses nationwide, but yet still considered brilliant and unique by the wearer.

And of course, I can't leave out geeky women's gear -- in some ways even more horrifying than the men's stuff. Evidence presented:

HTML tags -- get it?!

I have no words. Instead I'll leave you with ThinkGeek's description of these: "... we bring you HTTPanties for the discriminating woman who would prefer a web-savvy and somewhat-direct approach in the romance department. Feeling frisky? Well then don the black "200 OK" panties and see where they take you. Alternatively, the white "403 Forbidden" style sends a very different and hopefully clear message. We think "411 Length Required" and "413 Requested Entity Too Large" are pretty self-explanatory."

Euler Problem 4

2008-04-09T00:35:00Z

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

-----

First, I defined a palindrome recursively: a number is one if its first and last digits are the same, and if the inside is also a palindrome.

def palindrome?(digitArr)
if digitArr.empty?
    true
elsif digitArr.length == 1
    true
else
    (digitArr.first == digitArr.last && palindrome?(digitArr[1..-2]))
end
end

Note that in Ruby, methods can end with a question mark, a convention that really helps readability. Also note that the "else if" keyword is elsif, which is weird and unhelpful to me. I want that 20 minutes of staring at my code like "wtf?!" (before figuring that out) back.

Then we do a search of all the multiples of two three-digit numbers until we find the biggest palindrome:

def search(i,j)
maxPal=0
while i > 99 do
   j=999
   while j > 99 do
      if palindrome?((i*j).to_s.split("")) then
        if(i*j)> maxPal then maxPal = i*j
        end
      end
   j-=1
   end
i-=1
end
return maxPal
end

puts search(999,999)

There's probably a prettier way to do this.

Euler Problem 3

2008-04-09T00:07:00Z

What is the largest prime factor of the number 600851475143 ?

-----

I wrote this piece of disgusting, un-Rubylike Ruby to get the answer by creating a list of a number's prime factors:

def factor(composite)
i=1
flag=false
primefactors =[]
while (i < composite)
    i=i+1
    primefactors.each{|p| flag=true if (i%p).zero?}
    if flag then flag=false
    else # if it is a prime
      primefactors.push(i)   #add the prime (since it's a prime factor)
      while (composite%i).zero?   # as long as n is divisbible by the prime
          composite /= i    # divide n by the prime
      end
    end
end
primefactors
end

puts factor(600851475143).last

And then I learned that ruby has a prime number generator. All I need to do is:

require 'mathn'

n = 600851475143
factor = 0
primes = Prime.new
while n > 1
factor = primes.next
while (n % factor).zero?
n /= factor
end
end

puts factor

I am slightly ashamed.

Project Euler: Problem 2

2008-04-06T23:55:00Z

The problem:

Find the sum of all the even-valued terms in the [Fibonacci] sequence which do not exceed four million.

Here's my fibonacci function:

def fib(limit =nil)
f1 = 0
f2 = 1
while (not limit or f2 <= limit)
yield f2
f1,f2 = f2, f1+f2
end
end

And here's how I use it to get the answer:

evens=[]
fib { |x| if x%2==0 : evens.push(x) end ; if x>4000000: break end}
puts evens.inject {|sum, n| sum+n}

I learned about the awesomeness of 'yield' by doing this problem, so it was totally worth it. yield let me calculate as many fibonacci terms as I needed, but not more, and without having to calculate any term more than once.

Project Euler in Ruby

2008-04-06T17:31:00Z

I'm taking Bill Wagner up on his Project Euler challenge, but in Ruby. I've secretly wanted to learn Ruby for a long time, and this looks like the perfect chance. So if my code makes your eyes bleed, it's cause I'm a total n00b. Without further ado (because the excitement was becoming unbearable... I agree, Ruby is sexy!), here's my code that prints the answer to Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

answer = (0..999).select { |a| a%3 ==0 || a%5==0 }
puts answer.inject { |sum, n| sum+n }

I love the built-in ruby function inject, which is like foldl in some functional languages. (See a cute demo here.) Overall the code is very similar to Bill's C# version. I wonder if that'll still be the case as we get to the more complex problems.

[4/08/08: correction of a typo in the code]

The Google Data query interface

2008-03-30T00:01:00Z

I know I'm not the only one with tons of my data stored somewhere on Google's servers these days (frightening, I know.) Luckily, there's the Google Data API, which lets us access and modify our Google data programmatically, should we decide to, say, display it on our websites or build custom applications to process it.

The API uses HTTP requests to transfer data, building on top of RSS and Atom the ability to send a query and receive a feed of matching results. This is cool, because it means we can access our data easily, just by creating the appropriate HTTP query. Here's what I mean:

This is the XML feed of our SRT Events Google Calendar: http://www.google.com/calendar/feeds/v2433p4md2226qtd3ja1annifc%40group.calendar.google.com/public/basic

We can add query parameters to the end of this URL: http://www.google.com/calendar/feeds/v2433p4md2226qtd3ja1annifc%40group.calendar.google.com/public/basic?max-results=10&orderby=starttime

That new-and-improved feed is the full calendar feed of events, filtered to leave only 10 results and ordered by the start date of the event. Note that in addition to a standard set of parameters for all Google Data, there are some special ones defined for each app, like "racy" in YouTube.

Here's the metadata for the most-viewed YouTube videos:

http://gdata.youtube.com/feeds/api/standardfeeds/most_viewed

and adding these query parameters gives us just the family-friendly ones, ordered by rating.

http://gdata.youtube.com/feeds/api/standardfeeds/most_viewed?orderby=rating&racy=exclude

Now that we've got these custom feeds, we can just use any standard libraries to parse or display them. Pretty cool.